Which mathematical ideas have done most to change history? I'm planning a course for the general public with the general theme of "Mathematical ideas that have changed history" and I would welcome people's opinions on this topic.  What do you think have been the most influential mathematical ideas in terms of what has influenced science/history or changed the way humans think, and why?
I won't expect my audience to have any mathematical background other than high-school.
My thoughts so far are: non-Euclidean geometry, Cantor's ideas on uncountability, undecidability, chaos theory and fractals, the invention of new number systems (i.e. negative numbers, zero, irrational, imaginary numbers), calculus, graphs and networks, probability theory, Bayesian statistics.
My apologies if this has already been discussed in another post.
 A: A great, simple, invention not on your list is decimal number notation, which made arithmetic operations easy enough to teach to schoolchildren. Likewise, logarithms were what made rigorous engineering (prior to the invention of the computer) possible, since they turned multiplication and division into addition and subtraction, and so made many computations feasible.  
More philosophically, Frege's invention of predicate calculus made mathematics itself into a subject fit for mathematical study. 
A: Before we get over ourselves (structuralism in mathematics? game theory? please), I'd point out the simple things:


*

*The deductive method (some Greek did it, most likely not Euclid). The basis of everything;

*Logic (from Aristotle onward). The basis of almost everything;

*The indo-arabic Decimal (and
positional) system, which vastly
increased computational capabilities
and ways to think about quantities
(including logarithms and the concept
of order of magnitude);

*The method of coordinates, introduced
by Descartes and Fermat, which has
changes our idea of geometry,
established a relation between
algebra and geometry, and laid the
bais for the concept of space and
basis;

*Calculus, by Leibnitz and Newton.
Need I say more?

*The concept of probability (Fermat-Pascal), and the connection between probability and measure.
A: Turing's work on computability, extending those of Goedel and the other early logicians, paved the way for the development of modern computers. Before Turing and Goedel, the concept of computability was murky. It was Turing who realized that there could be a universal computer---a computer whose hardware does not have to be separately modified for every change in application. Although we all take this for granted now, as we install various programs on our laptop computers, the mathematical idea of it was and is profound. Turing's early work introduced the formal concept of subroutines in computation, computational languages, and so on, which laid the groundwork for the later development of computers as we know them.
A: Calculus, particularly the ideas of derivation and integration, is surely the mathematical idea which has changed history most in the last 400 years. The ability to study and quantify change and rate of change has been of key importance in science and engineering. Integration allowed calculation of volume and areas, and has been investigated (in a primitive form) for practical applications for millennea, starting with the Egyptian Moscow papyrus (c. 1820 BC). This includes in it the discovery and approximation of π, and with it the ability to estimate circumference and area of circles.
A: Kleinrock's work on queueing theory was (neglecting Baran et al.) the thing that made packet switching possible (his research group implemented a computer network connection first as well).
A: Probably it can be viewed as a variant on already posted answers (cryptography etc.), but the study of permutation groups and its application in cracking the Enigma code literally changed history (namely, the outcome of World War II). Here is an article by Marian Rejewski, one of the people involved in the code-cracking, explaining what was done and how:
http://www.impan.pl/Great/Rejewski/article.html
Rejewski and his achievements were also mentioned in answers to the following MO questions:
Real-world applications of mathematics, by arxiv subject area?
Notable mathematics during World War II
A: My vote goes for calculus and in particular the Fundamental Theorem of Calculus (FTC) and Stirling's approximation for the factorial. Can you imagine doing basic mathematics in any scientific field without FTC? What about quick and dirty approximations in physics without Stirling's formula? Perhaps modern science would have gotten to it's current level without the help of FTC or Stirling, but I bet it would have happened a thousand years too late!
A: A couple of years ago, I saw a talk by Keith Devlin around his book The unfinished game. In his talk, the three revolutions were (and excuse me as I butcher this a little bit, this is from memory)


*

*numbering systems

*measurements (Galileo)

*probability theory


So where's calculus and algebra and geometry? The argument was that these three have entered everyone's life to stay. Everyone uses numbers daily, measures things (temperature, speed), and talks about probabilities (chances of rain and so on). 
Of course, that doesn't mean that people do any of this well, are aware of the intricacies involved, or, for probabilities, have a good intuition. But the point is that these revolutions now completely permeate everyday life (unlike calculus!) to the extent that it is very difficult to imagine what went on in people's minds before these inventions came on the scene. (If you've ever tried to do euclidean geometry by requiring that numbers can only be described as proportions of physical magnitudes, you know what I mean.)
The thought-provoking part of course is that the first two items don't seem to belong at all in the same order of mathematics as probability. 
A: Together with the decimal system, already proposed by Neel Krishnaswami, I would also put binary notation.  
A: Depending which perspective to "information" resonates with your background, I'd suggest either Shannon's theory as foundation of telecommunications, or Relational Algebra and Calculus invented and promoted by Edgar Codd as foundation of database systems. In mathematical context database theory is a curiosity: algebra of binary relations has been developed for some time (DeMorgan-Peirce-Schroder-Tarski), yet Codd invented completely new algebra of relations with named attributes. The later took programming community by storm, while the original relation algebra still awaits its major application.   
A: The central limit theorem, with all its application in statistics and test theory, which guide a lot of current research in the medical sciences as well as the social sciences. On a more general note, the notion of statistics, tests, and risk assessment. Given the recent turn of events I guess we still have a lot to learn unfortunately.
You can also get some ideas by looking in the article 
"The Best of the 20th Century: Editors Name Top 10 Algorithms" published in 2000 in SIAM news. The pdf can be accessed here for instance:
http://x86.cs.duke.edu/courses/fall06/cps258/references/topten.pdf
A: Euclid's axiomatic treatment of geometry.  Very important in medieval thought.
A: The pagerank algorithm is currently having a big impact on how the world organises information.
A: There is a very nice category of mathematical results (that are also relevant to culture) : the negative results. 
For example there is no solution problem X (Say Fermat last Theorem) is negative and usually the result is not very interesting or motivated for laymen.
But think of the following : There no program checking that a program has no bugs ( by classical diagonal argument: how would this program test itself). 
In this case we prove something is impossible and so we save a hell of a lot of time: no need to search any more. 
Negative results are extremely useful : in a negative way you avoid loosing money and in fact it is a good justification for pure research. 
Yet beware that tough simple negative statements are not always understood some people say : "Oh Fermat equation has no solution , that is because they did not try hard enough , I will do it". 
This is akin to the trisectors and other poor souls looking for perpetual motion machines. 
A: The Fast Fourier Transform.
A: Korner wrote a lovely book on this topic, "The Pleasures of Counting."  Among the ideas he discusses not already mentioned,


*

*how statistics helped early epidemiologists discover how cholera was transmitted

*how mathematicians developed radar in WWII, saving Britain from the Luftwaffe

*also in WWII: the development of sonar & cryptography

*how basic ideas in operations research were developed to optimize convoys in WWI to elude submarines

A: The invention of numbers beyond "one", "two", and "many" probably had more impact than any other development in mathematics. You need to be able to count your livestock!  Modern civilization would never have gotten started without the key insight that you can memorize an ordered list of words, and put objects in bijective correspondence with them.
A: The work of Oliver Heaviside and Laplace put the electrical theories in a firm footing.
Heaviside invented an operational calculus for solving differential equations arising out of electrical network analysis, which was justified rigorously later by Laplace Transforms(but which makes full sense only incorporating the theory of distributions).
This might not seem important enough historically. But, all power generation, motors, the light you have in your room, and indeed all uses of electricity were able to be set up properly thanks to the work of these people, and the midnight oil they burned. We wouldn't have computers or MO without electricity distribution everywhere, for instance.
A: One simple invention of profound impact that does not seem to have been mentioned yet is the use of symbols for unknown variables. Modern science would be unthinkable if everything had to be put in words like it was throughout the middle ages.
A: Operations Research. The power of modeling situations from reality for scheduling problems, logistics and other sciences... The best is that you can model your problem and several methods exist to achieve your goal, and every day with the computer sciences insights It's easier to compute solutions.
A: Public key encryption is the basis for secure communication over the internet and thus the basis for our internet economy.  (If my students buy a song using iTunes then they are using public key encryption.  See the Wikipedia
 article on TSL and SSL protocols.)
A fundamental form of public key encryption (widely used now and the also the first example of public key encryption) is the RSA algorithm. It is based on Euler's theorem that $a^{\phi(n)}\equiv 1 \mod n$ for all $a$ relatively prime to $n$.
Without Euler's theorem we would not have RSA; without RSA we would not have IDEA, SSL, TSL and our internet economy.
A: The invention of new number systems is already mentioned, but I think that the invention of numbers itself is important too. Abstract notion of (natural) number is not so self-evident.
The discovery of mathematical induction. It is interesting that our brain makes us understand the infinite number of very similar theorems when we understand only one of them and the one step between two nearby theorems.
A: Error correcting codes. Without these, digital communications would be orders of magnitude more inefficient, and the internet, CD's, HDTV, and so on would not be possible.
A: Modular arithmetic underlies many public key cryptography algorithms, for example RSA and Diffie-Hellman Key exchange. Although its applications are not limited to e-commerce, I think that this application alone would merit inclusion on your list.
A: Every time I see a question like this I am reminded of something V.I. Arnold wrote, which I take the liberty of quoting here:

All mathematics is divided into three
  parts: cryptography (paid for by CIA,
  KGB and the like), hydrodynamics
  (supported by manufacturers of atomic
  submarines) and celestial mechanics
  (financed by military and by other
  institutions dealing with missiles,
  such as NASA.).
Cryptography has generated number
  theory, algebraic geometry over finite
  fields, algebra \footnote{The creator
  of modern algebra, Vi`ete, was the
  cryptographer of King Henry~I/V of
  France.}, combinatorics and computers.
Hydrodynamics procreated complex
  analysis, partial derivative
  equations, Lie groups and algebra
  theory, cohomology theory and 
  scientific computing. 
Celestial mechanics is the origin of
  dynamical systems, linear algebra, 
  topology, variational calculus and
  symplectic geometry.
The existence of mysterious relations
  between all these different domains is
  the most striking and delightful
  feature of mathematics  (having no
  rational explanation).

A: The invention of Zero.
A: Probability theory and statistics have changed the way we think about many things and they are used in a lot of aspects of everyday life.
A: $i$. (But my favorite by far is Cartesian coordinates, already mentioned by Scott Carter below.)
A: Compound interest! Einstein may have claimed (but likely didn't -- snopes.com) that it is "the most powerful force in the universe". Certainly it is an important idea in finance. 
A: The idea that new knowledge can be obtained by careful deduction from previous truths has in my opinion had an enormous impact on european history and is certainly not a trivial one. Be it found in the work of Plato (think of the Meno, the Theaetetus or the famous warning sign in the Academy), Aristotle, Descartes (whose prime example of analysis in the philosophical sense was the derivation of the equation of the tangent to a curve), Spinoza (Ethica Ordine Geometrico Demonstrata), Kant (with his discussion of analytic and synthetic knowledge) or even arguably in modern guise, this idea has been tied to mathematics.
Consequently, if I were to teach such a class, I would first try to convey how crucial the ideas of Plato, Bacon, Descartes, Galileo, Newton, Kant (and so on...) have been in shaping the way we think about society, politics, moral, history, even religion. Then I would try to convince my audience that these ideas have been intrinsically linked with contemporary mathematical thoughts, and ultimately with the concept of proof and reasoning as understood in mathematics.
So perhaps my suggestion for the most influential mathematical idea in terms of what has influenced science/history or changed the way humans think would be the idea that mathematics is possible, and that playing this game of proving theorems is in fact a deeply worthy activity.
A: Structuralism in mathematics.  It may have started in linguistics, but it reached mathematics next, promoted largely through Weil and Bourbaki, category theory, and then the grand vision of Grothendieck.   Structuralism is not so much a single mathematical idea as a way of thinking about properties and definitions, what mathematical objects are, and how we should study them.  The ideas expanded out from mathematics swiftly, and in the course of 20th century intellectual development, it is hard to find an idea as pervasive and influential as the structuralist approach.  
(There is a book by Amir Aczel on Bourbaki that some of the story.  I found the book to be unfortunately rather poorly written, but informative nonetheless.)
Structuralism is literally everywhere.  It contains the idea the objects are characterised by their relationships relative to all other objects, rather than having an inherent identity of their own.  For example, one sees an element of this in passing from old notions of groups and collections of transformations of something to the more abstract notion of a set equipped with the structure of a group multiplication law.  Through Levi-Strauss, structuralism was introduced into anthropology.  It created a large school of thought in history, sociology, political science, and so on.
Up above, I see that the Google PageRank algorithm was mentioned.  One can view this as an example of structuralism in action - the rank of a website is computed by the algorithm as a certain function of its relationship to all other websites rather than as a function of the content of the site itself.
A: Analytic geometry, both in the sense of Fermat and Descartes, and in the modern sense of "Feynman diagrams" encrypting algebraic axioms. Certainly the former precedes Wallis, Newton, and Leibniz, and from a modern perspective, it seems trivial, too trivial to mention. But that geometric problems can be dealt with analytically (algebraically), and vice versa, helped formulate and inform the revolutions of science. 
I agree that we have not yet understood the role that  algebraic diagrammatics play in our understanding of mathematics, physics, or even how they will affect the average person in the street. However, I will be surprised if they are not at least as important as the use of arrows to indicate functions. (They are a generalization thereof).
A: The Fourier transform (in its many incarnations) is a good candidate for your course. The applications would take me several hours to list, so I will refer you to the book "Fourier Analysis" by Thomas William Korner (Cambridge University Press, 1989), some of which could be made accessible to your target audience.
A: The idea that mathematics could be used as the language of gravitation and optics in particular, and in science more generally.
A: Turing machines and now modern-day computers would be a big one. 
A: Linear programming gives an organization a quantitative way to optimize resource allocation.  This (together with the Dantzig's simplex method) was pioneered on the allied side during the second world war.
A: Numerical analysis is of key importance in sciences and applications, including biology, economics, computing, and medicine. The idea of approximating a solution, and how that might be carried out. The Newton-Raphson method is an example of one result which has surely changed history. Indeed, calculus would be a lot less useful than it is in practice if not for numerical methods to approximate solutions to differential equations.
A: Game Theory
This helped to shape the cold war.
At least 12 nobel prizes have been awarded to game theorists.
A: The Ito-Integral and the Black-Scholes formula which started the revolution of quantitative finance because they made a proper pricing of derivatives possible.
A: Can you say something about the audience of this course?  Popular math? Undergrads?  grads?  That might set some appropriate response parameters.
If this were a graduate-level course (I suspect not, but I feel like addressing this option anyway :)), I'd probably point to categories, sheaves, and cohomology -- and maybe just "cohomology" as a general concept, if I had to pick one.  Also, the link provided by algebraic geometry between manifolds, varieties, and commutative algebra.
For an undergraduate non-major course, I don't think there's any way of overstating the historical significance of calculus.  The scope of problems, both mathematical and physical, that were instantaneously solvable by mathematicians all over the world after its development and deployment, was mind-boggling.  
I think there are probably more important ideas than those above if the scope of the question is how much impact they've had on humanities' development (e.g., development of serious linear algebra would certainly go in there for applications to just about everything, someone else mentioned RSA), but the above are my votes for ideas that have changed the way that people (or at least mathematicians) have thought about mathematics.
A: The introduction of order. Orders are ubiquitous in life. And orders are ubiquitous mathematics. These are the concepts of reflexivity, antisymmetry and transitivity and those of maximality.
A: I think we have to mention Archimedes who was one of the most brilliant mathematicians of the ancient times. Although he couldn't formulate it rigourously (because he did not have the concept of limit), he was the first to work with the concept of integral and he was able to calculate exactly surfaces and volumes of many shapes. He could do this using a formalisation of physical concepts. I think this was a major breakthrough in mathematics. Of course, we now have a whole theory on this topic today (calculus, integrals, differential geometry...), but it should not be forgotten that the founding ideas go back to Archimedes and are really worth mentioning.
A: Two simple ideas I attribute to a pre-mathematical thought in this respect 
1= The closed line (more or less a circle), and the idea of a boundary, of an inside and outside with its many derivations in life strikes me as a very ancient concept with very deep implications on thought, culture and society.
At the same time this idea is still fruitful in contemporary mathematics with homology, limits, inequalities, etc. as well as in our society.
2= The line as a path, a track, linked with time, that one follows, step by step, joining a start and an end exactly for the same reasons as above, with multiple current incarnations in today mathematics.
A: Galois. One of the founders of group theory, which led to most of algebra and maths in general. Galois theory and Galois groups led to Lie groups, which led to much of modern physics. As an added bonus, depending on your audience, the story of Galois' death is very interesting. 
A: Category theory and in particular Yoneda's lemma. Thinking of mathematical objects as part of a category changes eveything. It allows one to define an object only by the way it relates to other objects (universal problems, Yoneda's lemma). 
Obviously people knew that $K[X]$ was a the free $K$-algebra on one element long before category theory was invented but expressing it in the abstract language of categories leads to a much deeper understanding and much much simpler proofs. Just think of how painful it would be to study tensor products of modules without their functorial characterization for example. 
And the mathematical community owes a great debt to Grothendieck for showing how powerful this point of view can be.   
A: Poincare' and Algebraic Topology: Poincare's (basically) single-handed invention of homology and homotopy theory in 1900 really changed everything. 
He sowed the seeds for a great deal in differential geometry, analysis, homotopy theory, homological algebra, category theory, and algebraic geometry with the 'simple' concept of a functor (though it certainly wasn't called that) from spaces to groups. It tied spacial reasoning to algebraic reasoning in a way that, as I said, changed everything.
A: The normal distribution in probability theory. It is everywhere in moderen science.
A: I would say the invention of zero.
A: I have been impressed by "the theory of transformation groups'; sophus lie; the way it interconnects analysis and geometry.
