Donald Knuth
Donald Ervin Knuth | |
![]() | |
Rođenje | 10. 1. 1938. Milwaukee, SAD |
---|---|
Prebivalište | SAD |
Polje | matematika računarstvo |
Alma mater | Case Institute of Technology California Institute of Technology |
Akademski mentor | Marshall Hall, Jr. |
Istaknuti studenti | Leonidas J. Guibas Michael Fredman Scott Kim Vaughan Pratt Robert Sedgewick Jeffrey Vitter Andrei Broder |
Poznat po | The Art of Computer Programming TeX, METAFONT Knuth–Morris–Prattov algoritam Knuth–Bendixov algoritam dovršetka MMIX |
Istaknute nagrade | Turingova nagrada (1974) John von Neumannova medalja (1995) Harveyeva nagrada (1995) Nagrada iz Kjota (1996) |
Donald Ervin Knut (engleski: 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.
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 (engleski: The Art of Computer Programming).
Donald Ervin Knut rođen je 10. januara 1938. 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?“ (engleski: What? Me worry?). „Mad“ magazin je otkupio članak i objavio ga juna 1957.
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 stpendija 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. Nakon tog je upisao Kalifornijski tehnološki institut, a juna 1963. je nagrađen za rad u polju matematike. Iako je još uvek bio student, godine 1962. 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. Iste godine je objavio rad vezan za računanje polinoma. Knut se oženio sa Nensi Džil Karter 24. juna 1961. sa kojom ima dvoje dece: Džona Martina Knuta i Dženifer Sijeru Knut.
Nakon što je 1963. doktorirao, Knut je postao docent na Tehnološkom institutu u Kaliforniji na odseku za matematiku, a 1966. je unapređen u zvanje redovnog profesora i postao je stalni član Instituta. Od 1964. do 1967. radio je kao redaktor za programske jezike u Asocijaciji za računarske mašine (engleski: Association for Computing Machiney). Do 1966. 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“ (engleski: The Art of Computer Programming—Volume 1: Fundamental Algorithms) objavljena je 1968. Drugi deo: „Seminumerički algoritmi“ (engleski: Volume 2: Seminumerical Algorithms) objavljen je sledeće godine, a treći deo: „Sortiranje i pretraga“ (engleski: Volume 3: Sorting and Searching) 1973. 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. 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.
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“ (engleski: 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 (engleski: Alan M. Turing Award)
- Godine 1975. godine osvojio je nagradu „Lester-Ford“ (engleski: 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“ (engleski: John von Neumann Medal) koju dodeljuje udruženje IEEE čiji je bio član
- Godine 1996. dobio je Kjoto nagradu koju dodeljuje fondacija „Inamori“
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“ (engleski: 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 dodeljujuAssociation 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).
- Knutov sajt Arhivirano 2004-07-14 na Wayback Machine-u