Expanding Programming Capabilities with Better Math_问答_开发者

I have come to the realization that sooner or later I'm going to wa开发者_JAVA技巧nt to build more complex applications that will make better decisions rather just simple if/else statements.

My math background right now is at basic trigonometry, I would like to gain the skills needed to be able to create and understand algorithms.

From what I have researched I would need to understand and learn the following subjects:

Advanced Algebra
Calculus
Discrete Mathematics

This is the conclusion I have come to. Also I was wondering if there is a site where you can practice this type of Mathematics and track your progress.

Thanks.

Let me list off a few areas and why you should learn them:

Algebra/Number Theory: There are a number of number useful theoretic algorithms out there and at some point you may need to use/modify an existing one. Knowing the theory behind why they work makes it significantly easier to memorize them (and rederive them if you happen to forget ;)). The classic of such an algorithm would be the Euclidean algorithm for finding the greatest common divisor of two numbers. More advanced algorithms like quadratic sieve, etc have many uses in cryptography.

Graph Theory: I hope I don't need to explain this one too much. Graphs are used to solve a many many many different problems in computer science. They are used to represent networks, relationships between objects, as well as a huge class of ad-hoc uses. Algorithms include shortest path, network flow, coloring, etc.

Linear Algebra: Again, there are many scientific uses of linear algebra. I think I can safely say that the primary use of linear algebra is to solve systems of equations. Complicated differential equations are solved using linear algebra. Knowing how to multiply huge matrices and solve huge systems of linear equations are at the heart of many computer simulations. More closely related to everyday computing, computer graphics (especially 3D graphics) are all based on linear algebra.

Calculus: This should also be self-explanatory. You won't get very far in doing anything related to math and science without knowing calculus. While the bane of college students, it really is everywhere in modern science.

Probability: There are a number of probabalistic algorithms that rely on probability to do their dirty work. Also simulations may also use randomness and probability to achieve good results. It's not terribly hard to learn the fundamentals of probability which is all you really need.

Statistics: Whether you're writing a program which calculates statistics and does statistical tests or you're using statistics yourself, it is an immensely helpful tool to decipher and interpret information. Really anyone, not just mathematicians and scientists, should at least have a basic handle of statistics.

Numerical Analysis: This is kind of a catch-all. This is what ties the math and the computer science together. Math works well and good on paper, but when you start discretizing and bounding real numbers, you will run into problems. This is what numerical analysis is for. It describes the different numerical problems you may face in running these mathematical algorithms as well as mathematical/computer science tricks you can use to avoid/fix them.

Although it's a highly subjective question, for which an answer's correctness cannot properly be evaluated, here are a few pointers:

Most algorithms require only one branch of mathematics. If you're looking to build algorithms in a certain problem domain, you may not need to learn all these branches. (If you just want to improve for the sake of it, an answer becomes even harder as obviously everything you learn is valuable.)
Check the algorithm competition sites. Some of them, like Project Euler, focus mostly on mathematical problems. Others, (TopCoder, ACM ICPC, spoj,...) focus on all kinds of algorithms.

You've left a few important ones off your list:

probability
statistics
linear algebra

You can't be too rich, too thin, or know too much math, but I'd question whether it's necessary for you to take this path. You can do a lot of relatively complex and rewarding programming work without using calculus or linear algegra; it just won't include scientific computing or graphics at Pixar.

I'd also question how likely it is that something as rigorous as this could be done by self-study. You'd be a rare individual who mastered calculus on their own after completing formal schooling. Math is usually a one-way door - if you don't get through it early, it's hard to go back later on.

I found that mathematical induction can be very helpful designing and understanding a large variety of algorithms. There's a nice book that takes this idea pretty far: http://www.amazon.com/Introduction-Algorithms-Creative-Udi-Manber/dp/0201120372

A good overview of topics useful for computer science can be found on MIT's OpenCourseWare. By looking at the syllabus for the class 6.042 (Mathematics for Computer Science), you can gain an idea of what topics are useful: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/

That link leads to the online course notes for the class, which are a great teaching tool. The course examinations and answers are also available on OCW. I would definitely start by working through some of this material, as it is required for all CS students at MIT.