Alan Cobham (mathematician)
Alan Belmont Cobham | |
|---|---|
| Born | (1927年11月04日)November 4, 1927 |
| Died | June 28, 2011(2011年06月28日) (aged 83) |
| Nationality | American |
| Occupation | Theoretical computer scientist |
| Known for | Defining the class P, Cobham's thesis, Cobham's theorem, inventing priority queues, writing a program to play contract bridge |
Alan Belmont Cobham (4 November 1927 – 28 June 2011)[1] was an American mathematician and computer scientist known for (with Jack Edmonds and Michael O. Rabin) inventing the notion of polynomial time and the complexity class P,[2] [B] for Cobham's thesis stating that the problems that have practically usable computer solutions are characterized by having polynomial time,[3] [B] and for Cobham's theorem on the sets of numbers that can be recognized by finite automata.[4] [C] He also did foundational work on automatic sequences,[5] [D] invented priority queues and studied them from the point of view of queueing theory,[6] [A] and wrote a program for playing contract bridge that was at the time (in the mid-1980s) one of the best in the world.[7]
Cobham was a student at Oberlin College, the University of Chicago, the University of California, Berkeley, and the Massachusetts Institute of Technology, but did not complete a doctorate. He became an operations researcher for the United States Navy, a researcher for IBM Research at the Thomas J. Watson Research Center, and a professor and founding department chair of the computer science department at Wesleyan University.[1]
Selected publications
[edit ]References
[edit ]- ^ a b Shallit, Jeffrey (March 31, 2010). "Alan Cobham". Recursivity. Shallit, Jeffrey (November 12, 2014). "Alan Cobham: An Appreciation". Recursivity.
- ^ Kozen, Dexter C. (2006). Theory of Computation. Springer. p. 4. ISBN 978-1-84628-297-3.
- ^ Ausiello, Giorgio (2018). The Making of a New Science: A Personal Journey Through the Early Years of Theoretical Computer Science. Springer. p. 43. ISBN 978-3-319-62680-2.
- ^ Durand, Fabien; Rigo, Michel (2010). "On Cobham's Theorem" (PDF). In Pin, J.-É. (ed.). Automata: from Mathematics to Applications. European Mathematical Society.
- ^ Rowland, Eric (March 2015). "What is...an automatic sequence?" (PDF). Notices of the American Mathematical Society. 62 (3): 274–276. doi:10.1090/noti1218.
- ^ Miller, Rupert G. Jr. (1960). "Priority queues". Annals of Mathematical Statistics. 31: 86–103. doi:10.1214/aoms/1177705990 . MR 0120688.
- ^ Truscott, Alan (October 7, 1984). "Bridge: Playing against computers". The New York Times .
This article about an American mathematician is a stub. You can help Wikipedia by expanding it.