Donald Knut

Donald Ervin Knut (engl. Donald Ervin Knuth; Milvoki, 10. januar 1938) je jedan od najpoznatijih informatičara programera i penzionisani profesor na univerzitetu Stanford. Često je nazivan „ocem algoritama“ jer je doprineo razvoju i sistematizaciji matematičke tehnike za analizu složenih računarskih algoritama.

Donald Knut
Knut na Open Content Alliance prijemu, 25. oktobra 2005.
Лични подаци
Датум рођења	(1938-01-10)10. јануар 1938.
Место рођења	Milvoki, SAD
Научни рад
Поље	matematika, informatika
Институција	Univerzitet Stanford
Познат по	analiza algoritama, programski jezici, digitalna tipografija
Награде	Grace Murray Hopper Award (1971) Turing Award (1974) National Medal of Science (1979) John von Neumann Medal (1995) Harvey Prize (1995) Kyoto Prize (1996) Computer History Museum Fellow (1998) ForMemRS (2003) Faraday Medal (2011) BBVA Foundation Frontiers of Knowledge Award (2010) Turing Lecture (2011)
Званични веб-сајт
www-cs-faculty.stanford.edu/~knuth

Pored velikog doprinosa u nekoliko grana informatike i računarstva, Knut je, možda, najpoznatiji kao tvorac TeX-a, računarskog sistema za slog i prelom teksta, kao i METAFONT-a, jezika za definisanje fonta i sistema za kompajliranje. Knut je takođe tvorac WEB/CWEB računarskog sistema za programiranje čiji je cilj da olakša programiranje. Takođe je stvorio i MMIX — računarski set instrukcija i asembler kojim je ilustrovao primere u svom delu Umetnost računarskog programiranja (engl. The Art of Computer Programming).

Život i rad

Donald Ervin Knut rođen je 10. januara 1938. godine u Milvokiju. Roditelji su mu bili Ervin Henri Knut i Luisi Meri Bohning. Ervin je bio učitelj i upravo on je kod Donalda razvio ljubav prema školi, muzici i matematici.

U srednjoj školi raste Donaldovo interesovanje za muziku te je u jednom trenutku bio odlučio da nakon diplomiranja studira muziku (svirao je saksofon, a kasnije i trubu), ali se na kraju posvetio prirodnim naukama. Prvi „naučni“ članak, pod nazivom Potrzebie System of Weights and Measures objavio je u školskom magazinu. U njemu je definisao osnovnu jedinicu dužine kao debljinu magazina Mad broj 26, a osnovnu jedinicu sile nazvao je whatmeworry po frazi maskote tog magazina: „Šta? Ja zabrinut?“ (engl. What? Me worry?). „Mad“ magazin je otkupio članak i objavio ga juna 1957. godine.

Knutov prvi matematički članak se odnosio na srednjoškolsko takmičenje koje se zvalo „Potraga za talentima“ (1955). Knutov članak o računarskoj složenosti pesama je štampan više puta u računarskim časopisima.

Kada mu je ponuđena stipendija za studiranje fizike na Institutu tehnologije u Klivlendu prihvatio ju je, ali se vremenom udaljio od fizike i posvetio matematici. Diplomirao je u jesen 1960. godine. Nakon tog je upisao Kalifornijski tehnološki institut, a juna 1963. godine je nagrađen za rad u polju matematike. Iako je još uvek bio student, 1962. godine se zaposlio u izdavačkoj kući „Adison-Vesli“. U svom radu Knut je kombinovao znanje iz matematike i informatike pa je, na primer, izračunao Ojlerovu konstantu na 1.271 decimalu i svoje rešenje objavio 1962. godine. Iste godine je objavio rad vezan za računanje polinoma. Knut se oženio sa Nensi Džil Karter 24. juna 1961. godine sa kojom ima dvoje dece: Džona Martina Knuta i Dženifer Sijeru Knut.

Nakon što je 1963. godine doktorirao, Knut je postao docent na Tehnološkom institutu u Kaliforniji na odseku za matematiku, a 1966. godine je unapređen u zvanje redovnog profesora i postao je stalni član Instituta. Od 1964. do 1967. godine radio je kao redaktor za programske jezike u Asocijaciji za računarske mašine (engl. Association for Computing Machiney). Do 1966. godine njegov rad na kompilatorima (programima za prevođenje) je dostigao 3.000 napisanih strana te su Adison i Vesli zajedno sa Knutom rešili da započnu rad na seriji knjiga koje bi obuhvatile i razne druge stvari vezane za računare, a ne samo kompilatore.

Knjiga „Umetnost računarskog programiranja — prvi deo: Osnovni algoritmi“ (engl. The Art of Computer Programming—Volume 1: Fundamental Algorithms) objavljena je 1968. godine. Drugi deo: „Seminumerički algoritmi“ (engl. Volume 2: Seminumerical Algorithms) objavljen je sledeće godine, a treći deo: „Sortiranje i pretraga“ (engl. Volume 3: Sorting and Searching) 1973. godine. Knutov cilj je bio da sakupi i sumira ono što je poznato o računarskim metodama i pokaže koliko je duboka veza između matematike i informatike.

Od 1968. godine Knut počinje da radi kao profesor informatike i računarstva na univerzitetu Stanford. Knut je dao veliki doprinos matematici i informatici. Svakako treba pomenuti Knut-Bendiks algoritam, jedan od osnovnih računarskih algoritama sa algebarskom strukturom, posebno sa grupama i polugrupama. Ovaj algoritam je objavio zajedno sa svojim studentom Piterom Bendiksom 1970. godine.

Drugo značajno Knutovo delo je izum TeX-a, jezika za računarsko slaganje matematičkih i naučnih tekstova. TeX je promenio tehnologiju digitalne obrade matematičkih i naučnih tekstova jer pruža izuzetan kvalitet sloga i preloma matematičke notacije, kao i običnog teksta. TeX ne samo da je pomogao u objavljivanju i pisanju članaka već je omogućio i bolju komunikaciju među naučnicima i matematičarima.

Treba pomenuti i druga Knutova dela: programski jezici, razvoj LR(k) raščlanjivanja, Knut-Moris-Prat algoritam za sravnjivanje niza karaktera itd.

Malo je poznato da je Knut predložio naziv „Bekus-Naurova forma“, da je napisao jedan od najsloženijih kompilatora za programski jezik algol u 22. godini i da je prvu knjigu, Umetnost računarskog programiranja, objavio u svojoj 28. godini.

Nagrade i priznanja

Za značajan i veliki doprinos informatici i matematici Knut je dobio veliki broj nagrada, diploma i odlikovanja:

• Godine 1971. postao je prvi dobitnik nagrade „Grejs Mari Hoper“ (engl. Grace Murray Hopper Award) koju dodeljuje Asocijacija za računarske mašine
• Godine 1973. postao je član Američke akademije za nauku i umetnost
• Godine 1974. osvojio je „Alan M. Tjuring“ nagradu (engl. Alan M. Turing Award)
• Godine 1975. godine osvojio je nagradu „Lester-Ford“ (engl. Lester R. Ford Award) koju dodeljuje Američka matematička asocijacija
• Godine 1979. dodeljena mu je nacionalna medalja u polju nauke
• Godine 1981. postao je član Nacionalne akademije za inženjering
• Godine 1982. postao je počasni član asocijacije IEEE
• Godine 1988. dobio je Frenklinovu medalju
• Godine 1992. postaje član Francuske akademije nauke i umetnosti
• Godine 1994. nagrađen je Adelskoldovom medaljom koju dodeljuje Švedska akademija nauke i umetnosti
• Godine 1995. dodeljena mu je i Medalja „Džon fon Nojman“ (engl. John von Neumann Medal) koju dodeljuje udruženje IEEE čiji je bio član
• Godine 1996. dobio je Kjoto nagradu koju dodeljuje fondacija „Inamori“

Zaostavština

Knut se danas smatra legendarnom ličnošću u oblasti informatike. Njegove tri knjige o računarskom programiranju imale su značajnu ulogu u definisanju informatike kao složene i bitne naučne discipline. Trenutno radi na zaokruživanju serije knjiga Umetnost računarskog programiranja, koju smatra svojim životnim delom. Takođe je docent na Oksfordskom univerzitetu.

Nagrada „Donald Knut“ (engl. The Donald E. Knuth Prize) je nazvana upravo po njemu, a od 1996. godine se dodeljuje jednom godišnje i iznosi 5.000 dolara. Nagradu dodeljuju Association for Computing Machinery's Special Interest Group on Algorithms and Computing Theory (ACM SIGACT) i Institute of Electrical and Electronics Engineers's Technical Committee on the Mathematical Foundations of Computing (IEEE).

Galerija

• 
  Кнут, 4. март 2005. године
• 
  Knuth in front of statue St. Mesrop Mashtots, Matenadaran, Yerevan, Armenia, June 9, 2006
• 
  Shustek, Russell, Alcorn, Knuth, Wozniak, Mathews, Allen, CHM 2011
• 
  Кнут и Стив Вознијак, CHM 2011

Publikacije

Kratka lista njegovih publikacija uključuje:

The Art of Computer Programming:

• ——— (1997). The Art of Computer Programming. 1: Fundamental Algorithms (3rd изд.). Addison-Wesley Professional. ISBN 978-0-201-89683-1. 
• ——— (1997). The Art of Computer Programming. 2: Seminumerical Algorithms (3rd изд.). Addison-Wesley Professional. ISBN 978-0-201-89684-8. 
• ——— (1998). The Art of Computer Programming. 3: Sorting and Searching (2nd изд.). Addison-Wesley Professional. ISBN 978-0-201-89685-5. 
• ——— (2011). The Art of Computer Programming. 4A: Combinatorial Algorithms. Addison-Wesley Professional. ISBN 978-0-201-03804-0. 
• ——— (2005). MMIX—A RISC Computer for the New Millennium. 1, Fascicle 1. ISBN 978-0-201-85392-6. 
• ——— (2008). The Art of Computer Programming. 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions. ISBN 978-0-321-53496-5. 
• ——— (2009). The Art of Computer Programming. 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams. Addison-Wesley. ISBN 978-0-321-58050-4. 
• ——— (2005). The Art of Computer Programming. 4, Fascicle 2: Generating All Tuples and Permutations. Addison-Wesley. ISBN 978-0-201-85393-3. 
• ——— (2005). The Art of Computer Programming. 4, Fascicle 3: Generating All Combinations and Partitions. ISBN 978-0-201-85394-0. 
• ——— (2006). The Art of Computer Programming. 4, Fascicle 4: Generating All Trees—History of Combinatorial Generation. Addison-Wesley. ISBN 978-0-321-33570-8. 
• ——— (2018). The Art of Computer Programming. 4, Fascicle 5: Mathematical Preliminaries Redux; Backtracking; Dancing Links. ISBN 978-0-13-467179-6. 
• ——— (2015). The Art of Computer Programming. 4, Fascicle 6: Satisfiability. ISBN 978-0-13-439760-3. 

Computers and Typesetting (all books are hardcover unless otherwise noted):

• ——— (1984). Computers & Typesetting. A, The TeXbook. Reading, MA: Addison-Wesley. ISBN 978-0-201-13447-6. , x+483pp.
• ——— (1984). Computers & Typesetting. A, The TeXbook. Reading, MA: Addison-Wesley. ISBN 978-0-201-13448-3.  (softcover).
• ——— (1986). Computers & Typesetting. B, TeX: The Program. Reading, MA: Addison-Wesley. ISBN 978-0-201-13437-7. , xviii+600pp.
• ——— (1986). Computers & Typesetting. C, The METAFONTbook. Reading, MA: Addison-Wesley. ISBN 978-0-201-13445-2. , xii+361pp.
• ——— (1986). Computers & Typesetting. C, The METAFONTbook. Reading, MA: Addison-Wesley. ISBN 978-0-201-13444-5.  (softcover).
• ——— (1986). Computers & Typesetting. D, METAFONT: The Program. Reading, MA: Addison-Wesley. ISBN 978-0-201-13438-4. , xviii+566pp.
• ——— (1986). Computers & Typesetting. E, Computer Modern Typefaces. Reading, MA: Addison-Wesley. ISBN 978-0-201-13446-9. , xvi+588pp.
• ——— (2000). Computers & Typesetting. A-E Boxed Set. Reading, MA: Addison-Wesley. ISBN 978-0-201-73416-4. 

Knjige od prikupljenih radova:

• ——— (1992). Literate Programming. Lecture Notes. Stanford, CA: Center for the Study of Language and Information—CSLI. ISBN 978-0-937073-80-3. 
• ——— (1996). Selected Papers on Computer Science. Lecture Notes. Stanford, CA: Center for the Study of Language and Information—CSLI. ISBN 978-1-881526-91-9. 
• ——— (1999). Digital Typography. Lecture Notes. Stanford, CA: Center for the Study of Language and Information—CSLI. ISBN 978-1-57586-010-7. 
• ——— (2000). Selected Papers on Analysis of Algorithms. Lecture Notes. Stanford, CA: Center for the Study of Language and Information—CSLI. ISBN 978-1-57586-212-5. 
• ——— (2003). Selected Papers on Computer Languages (cloth). Lecture Notes. Stanford, CA: Center for the Study of Language and Information—CSLI. ISBN 978-1-57586-381-8. . ISBN 978-1-57586-382-5. (paperback)
• ——— (2003). Selected Papers on Discrete Mathematics (cloth). Lecture Notes. Stanford, CA: Center for the Study of Language and Information—CSLI. ISBN 978-1-57586-249-1. . ISBN 978-1-57586-248-4. (paperback)
• Donald E. Knuth, Selected Papers on Design of Algorithms (Stanford, California: Center for the Study of Language and Information—CSLI Lecture Notes, no. 191). 2010. ISBN 978-1-57586-583-6. (cloth). ISBN 978-1-57586-582-9. (paperback)

1. Donald E. Knuth, Selected Papers on Fun and Games (Stanford, California: Center for the Study of Language and Information—CSLI Lecture Notes, no. 192). 2011. ISBN 978-1-57586-585-0. (cloth). ISBN 978-1-57586-584-3. (paperback)
2. Donald E. Knuth, Companion to the Papers of Donald Knuth (Stanford, California: Center for the Study of Language and Information—CSLI Lecture Notes, no. 202). 2011. ISBN 978-1-57586-635-2. (cloth). ISBN 978-1-57586-634-5. (paperback)

Druge knjige:

• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete mathematics: A foundation for computer science (Second изд.). Reading, MA: Addison-Wesley. ISBN 978-0-201-55802-9. MR 1397498.  xiv+657 pp.
• Knuth, Donald Ervin (1974). Surreal numbers: how two ex-students turned on to pure mathematics and found total happiness: a mathematical novelette. Addison-Wesley. ISBN 978-0-201-03812-5. 
• Donald E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing (New York, ACM Press) 1993. second paperback printing. 2009. ISBN 978-0-321-60632-7.

1. Donald E. Knuth, 3:16 Bible Texts Illuminated . 3:16 Bible Texts Illuminated. Madison, Wisconsin: A-R Editions. 1990. ISBN 978-0-89579-252-5. 
2. Donald E. Knuth, Things a Computer Scientist Rarely Talks About (Center for the Study of Language and Information—CSLI Lecture Notes no 136). 2001. ISBN 978-1-57586-326-9.
3. Donald E. Knuth, MMIXware: A RISC Computer for the Third Millennium (Heidelberg: Springer-Verlag— Lecture Notes in Computer Science, no. 1750), 1999. viii+550pp. ISBN 978-3-540-66938-8.

• Donald E. Knuth and Silvio Levy, The CWEB System of Structured Documentation (Reading, Massachusetts: Addison-Wesley), iv+227pp. 1993. ISBN 978-0-201-57569-9. Third printing 2001 with hypertext support, ii + 237 pp.

1. Donald E. Knuth, Tracy L. Larrabee, and Paul M. Roberts, Mathematical Writing (Washington, D.C.: Mathematical Association of America), 1989. ii+115pp
2. Daniel H. Greene and Donald E. Knuth, Mathematics for the Analysis of Algorithms (Boston: Birkhäuser), 1990. viii+132pp.
3. Donald E. Knuth, Mariages Stables: et leurs relations avec d'autres problèmes combinatoires (Montréal: Les Presses de l'Université de Montréal), 1976. 106pp.
4. Donald E. Knuth, Axioms and Hulls (Heidelberg: Springer-Verlag—Lecture Notes in Computer Science, no. 606), 1992. ix+109pp. ISBN 978-3-540-55611-4.

Vidi još

• Umetnost računarskog programiranja
• TeX

Bibliografija

• Knuth, Donald Ervin. Home page. Stanford University. Архивирано из оригинала 11. 05. 2019. г. Приступљено 26. 04. 2018. 
• Knuth, Donald Ervin. „The Art of Computer Programming (TAOCP)”. Архивирано из оригинала 22. 01. 2018. г. Приступљено 20. 5. 2012. 
• Platoni, Kara; Archibald, Timothy (2006). „Love at First Byte”. Stanford Magazine. Stanford Alumni. Архивирано из оригинала 25. 9. 2006. г. Приступљено 26. 4. 2018. 

Spoljašnje veze

• Knutov sajt Архивирано на сајту Wayback Machine (14. јул 2004)