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 approach involving coding and testing, to a rigorous branch of mathematics where the challenge is proving theorems.
Subscribe to:
Post Comments (Atom)
1 comment:
I tend to agree.
However, the willingness or ability of computer science to code for all types of mathematics may be its strongest asset.
This may be particulary true for Noncooperative Game Theory.
Post a Comment