Discrete math first comes to mind first: lists, trees, graphs, etc. Used in basic algorithms 101, but you need some more serious probability theory for probabilistic algorithms.
Linear algebra is useful for computer graphics, but also for general "system thinking" concepts like inputs spaces, output spaces, transformations, and properties of transformations.
Basic differential calculus, meeeh, but multivariable calculus—specifically optimization—is really important in many programming contexts (e.g. machine learning).
Of course, the most important and most basic of all is the notion of a function f(x), its definition, inputs, outputs, properties, etc.
Rather than thinking just of how math ideas are used in CS, we should think of the relation as a two-way street: computing can help us better understand math too. Here is a short tutorial on basic math for programmers: https://minireference.com/static/tutorials/sympy_tutorial.pd...
It serves to review basic high school math, calculus, and even a bit of linear algebra. SymPy is very powerful stuff...
Someone asked this a few months ago and the book that was referred was Concrete Mathematics by Knuth (https://www.amazon.com/Concrete-Mathematics-Foundation-Compu...) which I have since purchased and have enjoyed re-learning from college. Highly recommended, and should cover all you need to know. Very approachable text.
Lots of areas are important. Every job I have worked has had a specific math specializations that were important. Reed-Solomon codes are used in storage and communication systems. They make use of abstract algebra (finite/Galois fields). Linear systems theory is essential for signal processing and control systems. Quaternions are important in aerospace and graphics.
About 40 years ago the company I was working for bought a big videotape recorder, and procured a custom controller for it to use it as a large random access storage device. The controller used a large Reed-Solomon code to detect and correct fairly large multi-bit errors. It worked quite well, storing images for Boeing, Lockheed, and McDonnel-Douglas aircraft maintenance manuals.
Basic algebra for the substitution model and basic calculus for high order functions and the notion of a transformation in general.
Set theory is, probably, the most fundamental. Everything could be defined as a set or as a function.
Lambda calculus, obviously.
Some combinators. Basics of linear algebra.
No category theory and other bullshit is needed. Sets will do.
It is actually very important skill to avoid wasting time in disconnected from reality obscure academic bullshit, be it philosophy, physics or math. Do not follow other people's hallucinations. Have your own.)
As a rule of thumb - you need just enough math to understand The Wizards Lectures and SICP.
Again, the substitution model, sets (for notion of types and basic collecttions) and high order functions (the "domain and range" mantra) is enough.
For algorithms the notion of being bound by some function and orders of growth.
Not to start a math war, but why is set theory okay but category theory bullshit?
While they're both useful, I think category theory encompasses a bit more than set theory and it's only a little more abstract. I also like the more functional approach that a lot of category theory requires you to take; if you're used to imperative programming it's a pretty different and useful way to think about things and it's great for adding to your critical thinking/general problem solving skills.
The difference between the set theory and category theory is the same as between the philosophy of Spinoza and Hegel. The first is grounded in reality, while the second one is an abstract metaphysics bullshit. Developing some abstract vocabulary to describe spherical horses in vacuum contribute nothing to programming, which is a discipline of describing and modeling some aspects and processes of reality.
Knowing where to stop in a heuristic-guided search is the most difficult part. In my opinion one should stop after realizing that the subject becomes too abstract and too academic and cease to be a tool of clarification.
Let's say that it has something to do with the pragmatism of Ayn Rand, Quality of Robert Pirsig, and to the general scientific method of removing bullshit, dogmas and nonsense in order to let the truth standing.
Abstract algebra is certainly abstract, but it is far from "metaphysical bullshit". Abstract algebra is just the precise articulation of patterns that we see across different mathematical formalisms.
Now, the fact that it is so abstract does mean that your average programmer won't use it on a day to day basis. I'm certainly not going to argue that it is the most important math to understand. However, we are finding that there is uses for it. Not just in a "oh look, I can describe my code using abstract algebra, nifty" sort of way, but in a "knowing this was essential to finding the correct solution" sort of way.
For instance, the folks working on .NET's LINQ knew they were implementing monadic comprehensions; they just had the good taste to not use the word "monad".
Oh, monads.. sooner or later they will be mentioned.) Actually it is a canonical example of abstraction for the sake of having an abstraction, which only increases confusion.
> Oh, monads.. sooner or later they will be mentioned.
Yep, monads :).
> Actually it is a canonical example of abstraction for the sake of having an abstraction, which only increases confusion.
I intentionally brought them up with a concrete, real-world example where they were useful.
> Monads make no sense in a non-lazy language.
A more accurate statement might be "monads make no sense in a non-lazy evaluation context". There are plenty of cases when working in an otherwise strict language you will compose a series of computations over a lazy data-source. For example: you want to process a potentially large series of rows coming from a database without blowing through RAM.
You can solve this problem on an ad-hoc basis, but as far as I understand it, the folks working on LINQ wanted to develop a declarative, readable, sql-like syntax for creating/composing such computations in a way that would work generically across data-sources. The question is, what is the pattern of operations and constraints that is common to all of the disparate data-sources that can be used in this way? The monadic functions + monadic laws is a precise (if arcane) description of those operations and constraints.
Using monads is not the only way to structure computation in the context of lazy evaluation, but it is one that is relatively well understood and worked well with the goal of being "sql-like" because SQL queries can be modeled as monadic computations.
> Metaphysics is a branch of philosophy concerned with explaining the fundamental nature of being and the world that encompasses it. Metaphysics attempts to answer two basic questions in the broadest possible terms:
> Ultimately, what is there? What is it like?
Does category theory have anything to do with that? No.
I have a great deal of respect for Rand and her ideas, despite not agreeing with them.
However, her status as an intellectual heir of Aristotle is highly debatable. She's as much a disciple of Nietzsche as anyone.
Meanwhile, metaphysics is a subject that stems directly from Greek philosophy: specifically the subjects addressed in Aristotle's work Metaphysics (literally "the book that came after Physics"). Spinoza's theory of monism is itself a metaphysical theory in this sense.
Perhaps by metaphysics, you mean to certain metaphysical theories, such as the Idealism of the 18th century?
> It is actually very important skill to avoid wasting time in disconnected from reality obscure academic bullshit, be it philosophy, physics or math. Do not follow other people's hallucinations. Have your own.
This. So much this. I've lived in a few hacker houses and worked at hacker spaces in the last year. The most impressive programmers I met had picked up just one set of skills (mostly web dev or mobile dev) and while being good at just one thing is less glamorous, these people were actually finishing projects. It was really incredible to watch them create and transform a project into real life in a very short amount of time. The most frustrating people I met were ones trying to learn everything--Machine Learning, IoT, VR/AR, mobile, web full stack--and getting nothing done on a daily basis.
The math you need to learn is completely dependent on what programming you want to do. What will be most impressive is your ability to focus on one or two areas and not get distracted into trying to learn all of it, and not feel envy towards those who are experts in domains that you don't know.
I've been recently trying to make my way though Elements of Programming (https://www.amazon.com/Elements-Programming-Alexander-Stepan...) by Alexander Stepanov and Paul McJones and it makes me say abstract algebra. It's the first and only rigorous foundation of software engineering that I've seen. It basically maps abstract algebra to this somewhat simple subset of C++, introduces new algebraic objects (such as memory) and then shows this really nice correspondence between the the C++-- and the abstract algebra.
If you are not familiar with the author, Alexander Stepanov is the guy who basically figured out generic programming, was instrumental in the design of C++ templates and the C++ STL. C++ gets a lot of flak but templates are very powerful (if you disregard the complexity). I think that they are actually one of the main reasons why C++ is still relevant. Also I'm starting to think that generic programming might actually be the most powerful paradigm out there (this is just a hunch). This book doesn't take the middle road, only the low level (C++) and extreme high level (abstract algebra) and totally cuts out the middle part (aka boiler plate).
Funnily enough, this C++-like language actually translates very nicely to the modern C++ successors like Swift and Rust (or it seems, I'm in the progress of exploring this).
Has anyone here tried to explore the contents of this book in either Swift or Rust?
But remember that this is not an easy book, I've met very smart people who told me they read only a part of this and are still wrapping their heads around that.
I just picked this up after having finished 'From Mathematics to Generic Programming' which is a ride in the park compared to what you're reading now. Looking forward to the task of slowly working my way through it.
[Edit] Interested in Rust for the same reason, but I'm not attracted to Swift. It looks so much like Kotlin, I am not sure I understand the fuss over it other than it gives Apple devs a way out of ObjC.
Anyway, I am going full on Android now, not in the hopes of app money, but the sheer numbers of devices out there, Google's backing, and it is more of a hacker's platform than iOS. I will most likely try Kotlin again, and this will prepare me for any possible switch to Swift.
I'm using a very similar approach in the design of my library of data structures and algorithms:
(0) The interface of an abstract data type (set, heap, etc.) is the signature of a variety in the universal algebra sense. Implementations are concrete algebras of this variety.
(1) Homomorphisms of varieties can be used to bootstrap abstract data types from simpler ones in a generic way. Chapter 10 of Okasaki's book “Purely Functional Data Structures” is entirely dedicated to this technique, although he doesn't make the connection to universal algebra.
But are also some differences:
(2) I'm using a functional programming language (Standard ML), rather than an imperative one (C++).
(3) I emphasize persistent data structures over ephemeral ones. I don't reject destructive updates that are compatible with persistence (e.g. laziness).
(4) I use algebraic data types to statically rule out unreachable code paths. Inexhaustive pattern matching is considered a bug. Raising an exception saying “this path was supposed to be unreachable” is also considered a bug. This would be at best very difficult to enforce in C++.
I know Alexander Stepanov personally, and Paul McJones through him, and they are both interested in seeing the ideas in the book implemented in other languages. Rust is a particularly compelling candidate, because it allows you to specify type constraints on generic functions through traits. This is similar in some ways to "concepts" which Alex has been hoping to see implemented in C++ for a very long time but which keeps getting kicked down the road.
Good ideas are often reinvented by different people in different contexts: An STL concept is a type class equipped with laws is an algebraic variety. Universal algebra tells us that we can gain a lot from paying attention not just to individual varieties in isolation, but also to homomorphisms of varieties, which translated back to programming languages correspond to bootstrapping data structures from simpler ones in a generic way.
Also, a while back, I reinvented InputIterators, OutputIterators and `std::copy` in a more type-safe way, using algebraic data types: https://github.com/eduardoleon/shit . (Sorry for the repo's name!) Although I only provide Standard ML and Scala implementations, this is perfectly doable in Rust as well. (In fact, my code is linearly typed, not just affinely typed.) The only requirements for a port to another language are parametric polymorphism and algebraic data types.
Favorite Stepanov quote below - apparently mixing mathematics and bad fish is quite potent:
Question:
What is the origin of STL? Has STL been conceived to be what it is now, that is "the" C++ Standard Library, or does it come from some other project? Could you tell us a history of STL?
Answer:
In 1976, still back in the USSR, I got a very serious case of food poisoning from eating raw fish. While in the hospital, in the state of delirium, I suddenly realized that the ability to add numbers in parallel depends on the fact that addition is associative. (So, putting it simply, STL is the result of a bacterial infection.) In other words, I realized that a parallel reduction algorithm is associated with a semigroup structure type.
It really depends on your domain. Knowing more math is never a bad thing. It provides you tools for you to model and solve problems. That said, two areas that I felt most broadened my horizons are probability and linear algebra. They are pretty ubiquitous topics that come up regularly in more sophisticated and exotic algorithms.
Good question... Calculus? Of course it has a long history with computing, but I would say that probably less than 10% of programmers outside scientific fields use any calculus. There is calculus in machine learning but I think that counts as less than 10% of programmers, and it will probably become its own specialty separate from programming in the coming decades (to some extent it is already)
From what I know of topology, you use logic and algebra as tools to learn about it, just as you use logic and algebra in computing. But you probably wouldn't use topology to say anything about computing.
Number theory is relevant to crypto, but I would be hard pressed to say it is practical for programmers in general. You could probably have a pretty long and successful career in programming without knowing basic things like what a prime factorization is.
> Good question... Calculus? Of course it has a long history with computing, but I would say that probably less than 10% of programmers outside scientific fields use any calculus.
Calculus is pretty useful in computer graphics and vision, if you want to understand what is going on there are integrals left and right. Audio processing and finance too.
On further reflection, it does seem pretty hard to find a subfield of math which isn't relevant to SOME subfield of computing. I was going to say non-Euclidean geometry, but that's very relevant if you're doing mapping software.
But that's a different thing than saying that a particular subfield of math is "practical to programmers".
I would say that programmers need the foundations of logic, algebra, and probability, and a bit of calculus (less than I was taught). And THEN they can learn topology, number theory, non-Euclidean geometry or advanced calculus if they need to, for their specific domain. You never know what you're going to end up doing 10 years down the road.
And of course that seems to be what happens in a good undergrad CS education, so apparently people better than us have thought about it :) Indeed college is supposed to give you the ability to learn how to learn, when new things come up, as they always do in programming. Quantum computing is basically a ton of linear algebra as far as I can tell.
Most programmers can forget the specifics of calculus, but the conceptual ideas of integration and differentiation are important. Many problems are better solved when you transform a series of changes into a whole (integration) and/or vice versa (differentiation).
Calculus (yes, continuous calculus) is pretty much the most important area of math you need to know to program well. In my books, if one can't integrate/differentiate a formula, they shouldn't be allowed to program a computer. Because that's how you end up with algorithms that take way too long to finish because the author couldn't bother to estimate how much computation the algorithm needs to perform at large inputs.
Math is rarely necessary for software development. However, math is one way great engineers distinguish themselves from okay engineers.
I work primarily on audio software. Linear algebra is most important, followed closely by signal processing. Those are sufficient to write good software. Great software requires statistics, calculus (mostly for optimization but also modeling), and discrete math (again mostly for optimization). Other specialties probably require more discrete math and less linear algebra and signal processing.
Abstract reasoning is necessary for programming. We typically develop those skills doing and applying math, but it is an open question if abstract reasoning is math.
Also, there are many kind of maths, the Europeans even get this right over the Americans by making it plural. Math is necessary is like saying things are necessary...which thing? It really depends on what you are doing, and experience with a known field of math might not be useful for some problems (beyond the abstract reasoning you need to write code at all).
Applies also to mobile, DevOps, and data engineering. Take the average ~$150K SV software engineering job and you don't need continuous math (just discrete to get in the door and maybe once every 6-12 months after that, when an interesting problem arises like some kind of divine salvation).
People that don't know math just reinvent it poorly. A lot of people use databases, and their SQL query with joins is performing set operations and they have no idea it's math. If You gave them the same dataset in an array, they wouldn't use a Set collection to solve it, but would loop over the dataset multiple times plucking what they need.
This is another reason why I would like to improve my math skills. I sometimes sense that there would be a much more elegant and efficient way to solve a problem if I could apply some math theory to it. 2 examples:
1:When I try to learn a new language I try to work through some of the problems on project Euler. I'm always impressed by some people's one line math solutions to something that took me 50 lines of code.
2: I once try to implement a timetable scheduling Web app (matching available teachers to courses) I could see that a solid understanding of set theory would have allowed me to - a: reason about the problem domain more easily and b: find the best way to set up my SQL queries.
Surprised nobody has mentioned any/all of Alan Turing's work, it is the mathematics which caused the foundation of Computer Science. See Turing Completeness and Universal Turing Machines.
Graph Theory is important for understanding data structures, I would also stress that the math equivalence of idempotency and isomorphism. We use these concepts a LOT in our work - but admittedly, we're a database ( http://gun.js.org/ ), which is a very different line of work than building consumer apps.
Other people already mentioned Big-O notation. Combinatorics, etc.
I'd recommend reading Knuth's The Art of Computer Programming for his perspective. Very math intensive and things you won't find in other textbooks.
Definitely a lot of discrete math (e.g. combinatorics), some calculus, number theory (esp. for cryptography), coding theory (e.g. for error correction), information theory, computational complexity theory. The border between theoretical computer science and math in general is very blurry, pretty much anything that is CS pretty quickly touches on more "traditional" mathematics.
A lot depends on your area of programming, things like machine learning will definitely involve more linear algebra, calculus, statistics. If you're programming a 3d engine then again algebra, geometry, etc. Things like finite state machines have a mathematical underpinning.
EDIT: From what I've seen at a university level CS program, Calculus, Linear Algebra, Discrete Math, Group Theory, Logic and Statistics were (IIRC) the core required math courses. Doesn't mean everything you learn there is applicable to any kind of program you might write but at least that's what someone thought was important...
Important to note that the maths used in AOCP is briefly covered at the start of Vol I. This was expanded upon in the form of Concrete Mathematics.
If you want just the maths and at a slightly slower pace, go with Concrete Mathematics. If that's a struggle, I found the first part of Discrete Mathematics and its applications by Kenneth Rosen was enough for me to make progress in Concrete Mathematics.
I also found learning a bit of linear algebra and calculus was a mind changer. I expect more fruits by my continuing of those studies.
Disclaimer: I know nothing about math but have been researching it recently as I want to go to university next year to study CS so I have about 8 months to 'learn' math (45 year old street programmer here :).
I would appreciate any feedback on if this post has any merit, and will be following this thread as it's relevant to my interests :)
First I would recommend Cal Newport's blog about using time wisely. http://calnewport.com/blog/2008/11/25/case-study-how-i-got-t...
Plenty more great info in the archive: http://calnewport.com/blog/archive/ Obviously the best way would be to go through your school's course syllabus for whatever classes you want to take and look at the material you will be doing, but these are good for a general preparedness:
Axler - Precalculus 2nd version
http://precalculus.axler.net/
He works through every odd exercise solution, in full. Also gives you a good intro to sets and series, summation notation, binomial theorem, all this will come up later in discrete math. He assumes the reader knows nothing about Trig as well.
Gilbert Strang's videos "Highlights of Calculus"
https://ocw.mit.edu/resources/res-18-005-highlights-of-calcu... just to get an overview of what calculus really is since I assume your university will throw you into an applied single variable class first year. MIT Open Courseware has their calculus (18.01/18.02) course lectures up if you want to watch them too to get an idea of what you'll run into.
"Elements of Mathematics: From Euclid to Gödel" gives quite a good explanation of Mathematics as a whole, like why we learn elementary math the way we do and how it applies to more advanced concepts, explains Rings/Fields and has a really good introduction to Logic. I wish this book existed 5 years ago when I started http://press.princeton.edu/titles/10697.html
"An Introduction to Mathematical Reasoning" by Eccles is short and excellent. You can also download the lecture notes here from CMU's course on proofs http://math.cmu.edu/~svasey/concepts-summer-1-2014/ and try some of the homework if you want but you probably won't see any of this until second year judging by most university calendars and recommended program course list I've seen.
CLRS https://en.wikipedia.org/wiki/Introduction_to_Algorithms which has a great first chapter "Foundations" that compliments Knuth's 'Mathematical Preliminaries' chapter in TAOCP vol 1. Knuth's book you can really drill yourself in these concepts though with the many, many exercises writing proofs. The skills I learned doing these exercises paid in full years later when I started more advanced math and even at work.
Thanks for the info. Do you think I will be able to use the Elements of Mathematics to kind of build a "Tech Tree" of math? One of the hardest things for me to find so far is what should be my order of acquisition for math. I did find this:
This is a common complaint with a simple solution.
Just look at the curricula for various undergrad math programs at some number of decent universities. They have a set of required courses and the course descriptions usually list the prerequisites, and sometimes this is even accompanied with a diagram of the DAG as a flowchart.
For any given course, there's usually a canonical text or set of roughly equivalent in quality texts.
You can do the same thing for basically any area of study that can be found as an undergrad major at most universities.
I am a self-taught programmer in my 30s (with an undergrad degree in humanities) now back in school. One of the main reasons I decided to return to school rather than continuing to program on the job was that I wanted to improve my math skills.
When you say you know nothing about math, does that mean you have no Calculus? That was where I was starting. To prepare for Calculus, get solid in algebra and trig. Then do single-variable Calculus (Calc 1 & 2). My recommendation would be to do linear algebra before multivariate calculus. You can do Calc 2 and Linear Algebra at the same time.
If you have no Physics experience you might also consider studying it. Physics helps you learn by applying math concepts. Also, I think it is very good for teaching you to problem solve as an engineer.
Could you perhaps be a little more specific? Sure, we use OR, AND, and even XOR to deal with conditionals that map to T and F, but this seems like kind of a surface level use of booleans. When do we invoke the algebraic properties of the structure when coding?
De Morgan's laws! I am sure people use it routinely to simplify complicated boolean expressions while writing code or mentally simplify complicated boolean expressions while reading code.
I want to stress before answering that everything you learn is useful if your mind is limber and willing to make connections. Some of the most valuable lessons in programming I learned from editing a philosophy journal in graduate school. I'll answer in terms of mathematical areas/concepts I've found immediately applicable in my programming career (format: what | why):
linear algebra | graphics, scientific computation, mostly graphics.
discrete probability | a whole shitload of perf solutions, understanding risk while planning
number theory, particularly factorization | modular arithmetic for crypto, a lot of very clever hacks for compressed representation of state spaces
predicate logic, basic set theory | I cannot count the number of times someone I work with has expressed something that required one elegant logical operation in a horribly convoluted way.
ammortized analysis | just learn it
statistics | operational reasoning using performance metrics, how to test/alarm rationally, how to reason about your customers
calculus | marginal returns (important when managing a team and optimizing where to spend resources). also if you ever end up doing any kind of convex optimization, which you might, maybe. (I do, but I don't think that's super normal outside datascience).
TL;DR: there's a reason CSCI curricula look like they do.
Of course. As I said, there's a reason most CSCI curricula look similar. That said though, most applied programming work does not require hard/deep math with a steep learning cost. It requires good instincts and precise logical reasoning.
Good instincts require a breadth of knowledge, moreso than a depth in any particular domain. Precise logical reasoning requires practice and patience in any of a very wide range of fields, not exclusive to mathematics. In both cases, I think developing a careful knowledge of history or neuroscience or any rigorous intellectual discipline is effective practice, although I think a foundation in logic is irreplaceable.
Being an excellent programmer in some specific domains requires deep domain specific knowledge in applied math, which does have a steep opportunity cost. Absolutely. But I did not believe that was the question at hand.
Mostly that simplicity and clarity are hard to achieve but very worth it. Learning what it feels like to correct and simplify logic into something that is easy to read and easy to verify is experience that has transferred well.
From my experience:
Everything you publish in science/academia will be read by a wide, potentially hostile audience. It is very easy to be misinterpreted, and misinterpretation wastes a lot of time and effort.
Stating what you mean in clear, precise terms is far more work than writing things that make you sound 'smart'. Good writers make their work seem terribly obvious, but it comes at the labor of many, many drafts. Most of the hardest work in editing is helping an author subtract and simplify to get right to the point. The labor of being precise and explicit exposes errors that the illusion of understanding tends to conceal.
Young/inexperienced writers often have a gigantic blind spot when it comes to their own writing, and correcting that is a very painful process.
Also, sometimes the original author was right, and the only precise way to express something was really ugly and horrific and your attempts to make it simple did violence to a lot of careful thought.
The world would be a better place if everybody took the effort to make their point with precision, simplicity and clarity.
However the truth in many situations is that if person A spends an hour constructing a beautifully worded five-liner, and if person B spends the same time to produce several rambling pages, then person B's argument may well win out. Readers who have spent ten times as long wading through B's contribution are quite likely to have forgotten entirely about A's.
>I cannot count the number of times someone I work with has expressed something that required one elegant logical operation in a horribly convoluted way.
Would be great if you can write/blog about it or just provide some examples here...
The CS departments in universities around the world have worked out good answers for this. Their thinking is summarized in the curricula they outline: which math courses they require as core subjects in the undergraduate CS degree program.
False. Decisions like this can be made at a higher level than the department. The mandatory courses in my programme were applied univariate calculus and an introduction to statistical modelling (with examples drawn from biology), imposed by the faculty of science on all science majors - all the while the CS professors were screaming for an introduction to logic and discrete maths to be added to the curriculum.
Well, yes; you have to look at the set difference between the CS math courses, and the common ones that all science students have to take.
That said, nobody in a STEM field should go without knowing at least univariate calculus. Without calculus, you can have only a poor intuition for situation involving rates of change, or little deltas being applied in one place resulting in other little deltas elsewhere. It's also necessary for stats, because you're dealing with oh, integrals such as the area under sections of a probability density function.
Part of computer science is numerical analysis, too. Once upon a time, numerical analysis constituted the bulk of "computer science".
CS undergrads arguably need some exposure to numerical analysis, and in such a course, the knowledge from other math courses provides support.
The math courses in most CS programs are not particularly useful, except as a weed-out function, and even there, I would argue that it's not particularly useful, since the Calc 1/2/3/Diff EQ sequence is not all that beneficial for anything I've ever encountered, in school or my career.
Proof and problem solving (It's not always taught in its own course). These assumptions about this code lead to these conclusions about its validity. If you can't prove your code works (to a human level of proof, not a machine's), why do you think it won't break? The skills of writing a simple proof (break it down so that each logical component is clear) is the same skill as writing clean and testable code.
100 comments
[ 2.5 ms ] story [ 108 ms ] threadLinear algebra is useful for computer graphics, but also for general "system thinking" concepts like inputs spaces, output spaces, transformations, and properties of transformations.
Basic differential calculus, meeeh, but multivariable calculus—specifically optimization—is really important in many programming contexts (e.g. machine learning).
Of course, the most important and most basic of all is the notion of a function f(x), its definition, inputs, outputs, properties, etc.
It serves to review basic high school math, calculus, and even a bit of linear algebra. SymPy is very powerful stuff...
And on the more esoteric side of things, in Quantum Computing every logic gate is actually a Matrix Multiplication
We employ some very talented people working on these sorts of problems for rail: http://biarrirail.com
Set theory is, probably, the most fundamental. Everything could be defined as a set or as a function.
Lambda calculus, obviously.
Some combinators. Basics of linear algebra.
No category theory and other bullshit is needed. Sets will do.
It is actually very important skill to avoid wasting time in disconnected from reality obscure academic bullshit, be it philosophy, physics or math. Do not follow other people's hallucinations. Have your own.)
As a rule of thumb - you need just enough math to understand The Wizards Lectures and SICP.
Again, the substitution model, sets (for notion of types and basic collecttions) and high order functions (the "domain and range" mantra) is enough.
For algorithms the notion of being bound by some function and orders of growth.
https://groups.csail.mit.edu/mac/classes/6.001/abelson-sussm...
Timeless classic. And nostalgic diving back into 80s. And MIT Scheme on a monochrome monitor with a clicky keyboard.
While they're both useful, I think category theory encompasses a bit more than set theory and it's only a little more abstract. I also like the more functional approach that a lot of category theory requires you to take; if you're used to imperative programming it's a pretty different and useful way to think about things and it's great for adding to your critical thinking/general problem solving skills.
Knowing where to stop in a heuristic-guided search is the most difficult part. In my opinion one should stop after realizing that the subject becomes too abstract and too academic and cease to be a tool of clarification.
Let's say that it has something to do with the pragmatism of Ayn Rand, Quality of Robert Pirsig, and to the general scientific method of removing bullshit, dogmas and nonsense in order to let the truth standing.
Now, the fact that it is so abstract does mean that your average programmer won't use it on a day to day basis. I'm certainly not going to argue that it is the most important math to understand. However, we are finding that there is uses for it. Not just in a "oh look, I can describe my code using abstract algebra, nifty" sort of way, but in a "knowing this was essential to finding the correct solution" sort of way.
For instance, the folks working on .NET's LINQ knew they were implementing monadic comprehensions; they just had the good taste to not use the word "monad".
Furthermore, it seems that having an understanding of abstract algebra is essential to making a distributed real-time analytics engine[0] [0]https://www.infoq.com/presentations/abstract-algebra-analyti...
Monads make no sense in a non-lazy language.
http://karma-engineering.com/lab/wiki/Monads2
Yep, monads :).
> Actually it is a canonical example of abstraction for the sake of having an abstraction, which only increases confusion.
I intentionally brought them up with a concrete, real-world example where they were useful.
> Monads make no sense in a non-lazy language.
A more accurate statement might be "monads make no sense in a non-lazy evaluation context". There are plenty of cases when working in an otherwise strict language you will compose a series of computations over a lazy data-source. For example: you want to process a potentially large series of rows coming from a database without blowing through RAM.
You can solve this problem on an ad-hoc basis, but as far as I understand it, the folks working on LINQ wanted to develop a declarative, readable, sql-like syntax for creating/composing such computations in a way that would work generically across data-sources. The question is, what is the pattern of operations and constraints that is common to all of the disparate data-sources that can be used in this way? The monadic functions + monadic laws is a precise (if arcane) description of those operations and constraints.
Using monads is not the only way to structure computation in the context of lazy evaluation, but it is one that is relatively well understood and worked well with the goal of being "sql-like" because SQL queries can be modeled as monadic computations.
Your value judgments in this case actually seem dogmatic and nonsensical... which makes sense if it's derived from Ayn Rand.
Ayn Rand was a student of the classic Greek philosophy, nothing wrong with her.
> Metaphysics is a branch of philosophy concerned with explaining the fundamental nature of being and the world that encompasses it. Metaphysics attempts to answer two basic questions in the broadest possible terms:
> Ultimately, what is there? What is it like?
Does category theory have anything to do with that? No.
> Does category theory have anything to do with that? No.
I could argue that category theory is claiming to answer those questions for mathematics. (So is the axiomatization based on set theory.)
However, her status as an intellectual heir of Aristotle is highly debatable. She's as much a disciple of Nietzsche as anyone.
Meanwhile, metaphysics is a subject that stems directly from Greek philosophy: specifically the subjects addressed in Aristotle's work Metaphysics (literally "the book that came after Physics"). Spinoza's theory of monism is itself a metaphysical theory in this sense.
Perhaps by metaphysics, you mean to certain metaphysical theories, such as the Idealism of the 18th century?
edit: missing punctuation
This. So much this. I've lived in a few hacker houses and worked at hacker spaces in the last year. The most impressive programmers I met had picked up just one set of skills (mostly web dev or mobile dev) and while being good at just one thing is less glamorous, these people were actually finishing projects. It was really incredible to watch them create and transform a project into real life in a very short amount of time. The most frustrating people I met were ones trying to learn everything--Machine Learning, IoT, VR/AR, mobile, web full stack--and getting nothing done on a daily basis.
The math you need to learn is completely dependent on what programming you want to do. What will be most impressive is your ability to focus on one or two areas and not get distracted into trying to learn all of it, and not feel envy towards those who are experts in domains that you don't know.
If you are not familiar with the author, Alexander Stepanov is the guy who basically figured out generic programming, was instrumental in the design of C++ templates and the C++ STL. C++ gets a lot of flak but templates are very powerful (if you disregard the complexity). I think that they are actually one of the main reasons why C++ is still relevant. Also I'm starting to think that generic programming might actually be the most powerful paradigm out there (this is just a hunch). This book doesn't take the middle road, only the low level (C++) and extreme high level (abstract algebra) and totally cuts out the middle part (aka boiler plate).
Funnily enough, this C++-like language actually translates very nicely to the modern C++ successors like Swift and Rust (or it seems, I'm in the progress of exploring this).
Has anyone here tried to explore the contents of this book in either Swift or Rust?
But remember that this is not an easy book, I've met very smart people who told me they read only a part of this and are still wrapping their heads around that.
[Edit] Interested in Rust for the same reason, but I'm not attracted to Swift. It looks so much like Kotlin, I am not sure I understand the fuss over it other than it gives Apple devs a way out of ObjC.
Anyway, I am going full on Android now, not in the hopes of app money, but the sheer numbers of devices out there, Google's backing, and it is more of a hacker's platform than iOS. I will most likely try Kotlin again, and this will prepare me for any possible switch to Swift.
(0) The interface of an abstract data type (set, heap, etc.) is the signature of a variety in the universal algebra sense. Implementations are concrete algebras of this variety.
(1) Homomorphisms of varieties can be used to bootstrap abstract data types from simpler ones in a generic way. Chapter 10 of Okasaki's book “Purely Functional Data Structures” is entirely dedicated to this technique, although he doesn't make the connection to universal algebra.
But are also some differences:
(2) I'm using a functional programming language (Standard ML), rather than an imperative one (C++).
(3) I emphasize persistent data structures over ephemeral ones. I don't reject destructive updates that are compatible with persistence (e.g. laziness).
(4) I use algebraic data types to statically rule out unreachable code paths. Inexhaustive pattern matching is considered a bug. Raising an exception saying “this path was supposed to be unreachable” is also considered a bug. This would be at best very difficult to enforce in C++.
I know Alexander Stepanov personally, and Paul McJones through him, and they are both interested in seeing the ideas in the book implemented in other languages. Rust is a particularly compelling candidate, because it allows you to specify type constraints on generic functions through traits. This is similar in some ways to "concepts" which Alex has been hoping to see implemented in C++ for a very long time but which keeps getting kicked down the road.
Also, a while back, I reinvented InputIterators, OutputIterators and `std::copy` in a more type-safe way, using algebraic data types: https://github.com/eduardoleon/shit . (Sorry for the repo's name!) Although I only provide Standard ML and Scala implementations, this is perfectly doable in Rust as well. (In fact, my code is linearly typed, not just affinely typed.) The only requirements for a port to another language are parametric polymorphism and algebraic data types.
Question: What is the origin of STL? Has STL been conceived to be what it is now, that is "the" C++ Standard Library, or does it come from some other project? Could you tell us a history of STL?
Answer: In 1976, still back in the USSR, I got a very serious case of food poisoning from eating raw fish. While in the hospital, in the state of delirium, I suddenly realized that the ability to add numbers in parallel depends on the fact that addition is associative. (So, putting it simply, STL is the result of a bacterial infection.) In other words, I realized that a parallel reduction algorithm is associated with a semigroup structure type.
The full interview can be found at:
http://www.stlport.org/resources/StepanovUSA.html
[0] - https://en.wikipedia.org/wiki/Formal_language
From what I know of topology, you use logic and algebra as tools to learn about it, just as you use logic and algebra in computing. But you probably wouldn't use topology to say anything about computing.
Number theory is relevant to crypto, but I would be hard pressed to say it is practical for programmers in general. You could probably have a pretty long and successful career in programming without knowing basic things like what a prime factorization is.
Calculus is pretty useful in computer graphics and vision, if you want to understand what is going on there are integrals left and right. Audio processing and finance too.
But that's a different thing than saying that a particular subfield of math is "practical to programmers".
I would say that programmers need the foundations of logic, algebra, and probability, and a bit of calculus (less than I was taught). And THEN they can learn topology, number theory, non-Euclidean geometry or advanced calculus if they need to, for their specific domain. You never know what you're going to end up doing 10 years down the road.
And of course that seems to be what happens in a good undergrad CS education, so apparently people better than us have thought about it :) Indeed college is supposed to give you the ability to learn how to learn, when new things come up, as they always do in programming. Quantum computing is basically a ton of linear algebra as far as I can tell.
I work primarily on audio software. Linear algebra is most important, followed closely by signal processing. Those are sufficient to write good software. Great software requires statistics, calculus (mostly for optimization but also modeling), and discrete math (again mostly for optimization). Other specialties probably require more discrete math and less linear algebra and signal processing.
I recently realized that math is not necessary for programming... if you want to be stuck doing boring stuff like webdev or CRUD apps.
Also, there are many kind of maths, the Europeans even get this right over the Americans by making it plural. Math is necessary is like saying things are necessary...which thing? It really depends on what you are doing, and experience with a known field of math might not be useful for some problems (beyond the abstract reasoning you need to write code at all).
1:When I try to learn a new language I try to work through some of the problems on project Euler. I'm always impressed by some people's one line math solutions to something that took me 50 lines of code.
2: I once try to implement a timetable scheduling Web app (matching available teachers to courses) I could see that a solid understanding of set theory would have allowed me to - a: reason about the problem domain more easily and b: find the best way to set up my SQL queries.
It's cool to learn recognize how simpler math concepts apply to computing. Ie, associativity allows for map/reduce
Graph Theory is important for understanding data structures, I would also stress that the math equivalence of idempotency and isomorphism. We use these concepts a LOT in our work - but admittedly, we're a database ( http://gun.js.org/ ), which is a very different line of work than building consumer apps.
Other people already mentioned Big-O notation. Combinatorics, etc.
Definitely a lot of discrete math (e.g. combinatorics), some calculus, number theory (esp. for cryptography), coding theory (e.g. for error correction), information theory, computational complexity theory. The border between theoretical computer science and math in general is very blurry, pretty much anything that is CS pretty quickly touches on more "traditional" mathematics.
A lot depends on your area of programming, things like machine learning will definitely involve more linear algebra, calculus, statistics. If you're programming a 3d engine then again algebra, geometry, etc. Things like finite state machines have a mathematical underpinning.
EDIT: From what I've seen at a university level CS program, Calculus, Linear Algebra, Discrete Math, Group Theory, Logic and Statistics were (IIRC) the core required math courses. Doesn't mean everything you learn there is applicable to any kind of program you might write but at least that's what someone thought was important...
If you want just the maths and at a slightly slower pace, go with Concrete Mathematics. If that's a struggle, I found the first part of Discrete Mathematics and its applications by Kenneth Rosen was enough for me to make progress in Concrete Mathematics.
I also found learning a bit of linear algebra and calculus was a mind changer. I expect more fruits by my continuing of those studies.
http://steve-yegge.blogspot.cz/2006/03/math-for-programmers....
Disclaimer: I know nothing about math but have been researching it recently as I want to go to university next year to study CS so I have about 8 months to 'learn' math (45 year old street programmer here :).
I would appreciate any feedback on if this post has any merit, and will be following this thread as it's relevant to my interests :)
Axler - Precalculus 2nd version http://precalculus.axler.net/ He works through every odd exercise solution, in full. Also gives you a good intro to sets and series, summation notation, binomial theorem, all this will come up later in discrete math. He assumes the reader knows nothing about Trig as well.
Gilbert Strang's videos "Highlights of Calculus" https://ocw.mit.edu/resources/res-18-005-highlights-of-calcu... just to get an overview of what calculus really is since I assume your university will throw you into an applied single variable class first year. MIT Open Courseware has their calculus (18.01/18.02) course lectures up if you want to watch them too to get an idea of what you'll run into.
"Elements of Mathematics: From Euclid to Gödel" gives quite a good explanation of Mathematics as a whole, like why we learn elementary math the way we do and how it applies to more advanced concepts, explains Rings/Fields and has a really good introduction to Logic. I wish this book existed 5 years ago when I started http://press.princeton.edu/titles/10697.html
"An Introduction to Mathematical Reasoning" by Eccles is short and excellent. You can also download the lecture notes here from CMU's course on proofs http://math.cmu.edu/~svasey/concepts-summer-1-2014/ and try some of the homework if you want but you probably won't see any of this until second year judging by most university calendars and recommended program course list I've seen.
CLRS https://en.wikipedia.org/wiki/Introduction_to_Algorithms which has a great first chapter "Foundations" that compliments Knuth's 'Mathematical Preliminaries' chapter in TAOCP vol 1. Knuth's book you can really drill yourself in these concepts though with the many, many exercises writing proofs. The skills I learned doing these exercises paid in full years later when I started more advanced math and even at work.
http://forums.xkcd.com/download/file.php?id=29015&sid=060c11...
But I have no others to go on to compare.
Just look at the curricula for various undergrad math programs at some number of decent universities. They have a set of required courses and the course descriptions usually list the prerequisites, and sometimes this is even accompanied with a diagram of the DAG as a flowchart.
For any given course, there's usually a canonical text or set of roughly equivalent in quality texts.
You can do the same thing for basically any area of study that can be found as an undergrad major at most universities.
When you say you know nothing about math, does that mean you have no Calculus? That was where I was starting. To prepare for Calculus, get solid in algebra and trig. Then do single-variable Calculus (Calc 1 & 2). My recommendation would be to do linear algebra before multivariate calculus. You can do Calc 2 and Linear Algebra at the same time.
If you have no Physics experience you might also consider studying it. Physics helps you learn by applying math concepts. Also, I think it is very good for teaching you to problem solve as an engineer.
linear algebra | graphics, scientific computation, mostly graphics.
discrete probability | a whole shitload of perf solutions, understanding risk while planning
number theory, particularly factorization | modular arithmetic for crypto, a lot of very clever hacks for compressed representation of state spaces
predicate logic, basic set theory | I cannot count the number of times someone I work with has expressed something that required one elegant logical operation in a horribly convoluted way.
ammortized analysis | just learn it
statistics | operational reasoning using performance metrics, how to test/alarm rationally, how to reason about your customers
calculus | marginal returns (important when managing a team and optimizing where to spend resources). also if you ever end up doing any kind of convex optimization, which you might, maybe. (I do, but I don't think that's super normal outside datascience).
TL;DR: there's a reason CSCI curricula look like they do.
There are some things you don't want to learn, and there is also an oppurtunity cost to learning/practicing A instead of B.
Good instincts require a breadth of knowledge, moreso than a depth in any particular domain. Precise logical reasoning requires practice and patience in any of a very wide range of fields, not exclusive to mathematics. In both cases, I think developing a careful knowledge of history or neuroscience or any rigorous intellectual discipline is effective practice, although I think a foundation in logic is irreplaceable.
Being an excellent programmer in some specific domains requires deep domain specific knowledge in applied math, which does have a steep opportunity cost. Absolutely. But I did not believe that was the question at hand.
From my experience:
Everything you publish in science/academia will be read by a wide, potentially hostile audience. It is very easy to be misinterpreted, and misinterpretation wastes a lot of time and effort.
Stating what you mean in clear, precise terms is far more work than writing things that make you sound 'smart'. Good writers make their work seem terribly obvious, but it comes at the labor of many, many drafts. Most of the hardest work in editing is helping an author subtract and simplify to get right to the point. The labor of being precise and explicit exposes errors that the illusion of understanding tends to conceal.
Young/inexperienced writers often have a gigantic blind spot when it comes to their own writing, and correcting that is a very painful process.
Also, sometimes the original author was right, and the only precise way to express something was really ugly and horrific and your attempts to make it simple did violence to a lot of careful thought.
However the truth in many situations is that if person A spends an hour constructing a beautifully worded five-liner, and if person B spends the same time to produce several rambling pages, then person B's argument may well win out. Readers who have spent ten times as long wading through B's contribution are quite likely to have forgotten entirely about A's.
Would be great if you can write/blog about it or just provide some examples here...
That said, nobody in a STEM field should go without knowing at least univariate calculus. Without calculus, you can have only a poor intuition for situation involving rates of change, or little deltas being applied in one place resulting in other little deltas elsewhere. It's also necessary for stats, because you're dealing with oh, integrals such as the area under sections of a probability density function.
Part of computer science is numerical analysis, too. Once upon a time, numerical analysis constituted the bulk of "computer science".
CS undergrads arguably need some exposure to numerical analysis, and in such a course, the knowledge from other math courses provides support.