The Greatest Innovation of Theoretical Computer Science
Spiked magazine has asked me to contribute 200 words on the subject of
the "greatest innovation in my field". Here's my answer:
In theoretical computer science, the greatest innovation is the
realization that algorithms are mathematical objects, and can be
rigorously analyzed in terms of their consumption of scarce resources,
including space, time, and randomness.
One of the first to analyze an algorithm was the French mathematician
Pierre-Joseph-�tienne Finck (1797-1870). In an 1841 book, he showed
that the Euclidean algorithm for computing the greatest common divisor
of two integers uses a number of division steps that is linearly
bounded in the number of digits of the inputs. Finck's work is all but
forgotten today, but I discussed it in a paper in Historia Mathematica
in 1994.
In recent times, much of the credit for the development of algorithm
analysis certainly belongs to Donald Ervin Knuth (b. 1938), who in a
series of books entitled The Art of Computer Programming, popularized
many of the tools now used routinely to analyze algorithms. Almost
overnight, algorithm analysis changed from a purely engineering
No comments:
Post a Comment