Donald Knuth

Donald Ervin Knuth (născut la 10 ianuarie 1938) este un informatician, matematician și profesor emeritus american la Universitatea Stanford. El este câștigătorul din 1974 al premiului ACM Turing Award (Premiul Turing), considerat în mod informal Premiul Nobel pentru informatică. Knuth a fost numit „părintele analizei algoritmilor”.

Este autorul operei cu volume multiple The Art of Computer Programming (Arta programării calculatoarelor). A contribuit la dezvoltarea analizei riguroase a complexității computaționale a algoritmilor și a tehnicilor matematice formale sistematizate pentru acestea. În același timp, a popularizat și notația asimptotică. Pe lângă contribuțiile fundamentale aduse anumitor ramuri din informatica teoretică, Knuth este creatorul sistemului computerizat de tip typesetting TeX, limbajul de definire a fontului și sistemul de rendering METAFONT, precum și a familiei de typefaces (tipuri de caracter) Computer Modern.

Ca scriitor și academician, Knuth a creat sistemele de programare de calculator WEB și CWEB, proiectate pentru a încuraja și facilita programarea alfabetizată și a proiectat MIX/MMIX – arhitecturi de set de instrucțiuni. Knuth se opune cu tărie acordării de brevete de software, susținându-și opinia în fața Oficiului de Brevete și Mărci înregistrate din Statele Unite și Organizației Europeane de Brevetare.

Biografie

Copilărie

Knuth s-a născut în Milwaukee, Wisconsin, fiul germano-americanilor Ervin Henry Knuth și Louise Marie Bohning. Tatăl său deținea o tipografie și preda contabilitate. Donald, student la liceul Milwaukee Lutheran High School, s-a gândit la moduri ingenioase pentru a rezolva probleme. De exemplu, în clasa a opta, s-a înscris într-un concurs pentru a găsi numărul de cuvinte în care puteau fi rearanjate literele din expresia „Ziegler’s Giant Bar”; juriul a identificat 2.500 asemenea cuvinte. Cu timpul acumulat departe de școală din cauza unei false dureri de stomac și lucrând la problemă în alt mod, Knuth a utilizat un dicționar nelimitat și a determinat dacă fiecare intrare de dicționar poate fi formată utilizând literele din frază. Folosind acest algoritm, el a identificat peste 4.500 de cuvinte, câștigând concursul. Ca premii, școala a primit un televizor nou și suficiente batoane de ciocolată pentru toți colegii săi.

Educație

Knuth a obținut o bursă în fizică la Institutul de Tehnologie Case (acum parte din Universitatea Case Western Reserve) din Cleveland, Ohio, unde s-a înscris în anul 1956. Totodată, s-a alăturat Capitolului Beta Nu al Frăției Theta Chi. În timp ce studia fizică la Case, Knuth a avut pentru prima dată contact cu IBM 650, un calculator comercial timpuriu. După ce a citit manualul calculatorului, Knuth a decis să rescrie codul de asamblare și compilatorul pentru dispozitivul utilizat în școala sa, deoarece considera că îl poate face mai bine.

În 1958, Knuth a creat un program pentru a ajuta echipa de baschet a liceului să câștige jocurile. El a atribuit „valori” jucătorilor pentru a măsura probabilitatea acestora de a obține puncte, o abordare nouă despre care Newsweek și CBS Evening News au raportat ulterior.

Knuth a fost unul din editorii fondatori ai revistei Engineering and Science Review de la Institutul Case, care a câștigat un premiul național de cea mai bună revistă tehnică din 1959. A trecut apoi la fizică și matematică, și a primit două diplome de la Case în 1960: licența sa în științe și o diplomă de master în științe oferită special de către facultate, care a considerat munca sa ca fiind excepțională.

În 1963, împreună cu matematicianul Marshall Hall în rolul de consilier personal, și-a luat doctoratul în matematică de la Institutul de Tehnologie din California.

Activitate profesională timpurie

După dobândirea doctoratului, s-a alăturat facultății Caltech ca lector universitar.

A acceptat un comision să scrie o carte despre compilatoare de limbaj de programare pentru calculatoare. În timp ce lucra la acest proiect, Knuth s-a decis că nu poate trata în mod adecvat subiectul fără a dezvolta mai întâi o teorie fundamentală a programării calculatoarelor, care a devenit apoi The Art of Computer Programming. Inițial, avusese de gând să o publice ca o singură carte. Pe măsură ce Knuth dezvolta cadrul cărții sale, a conchis că necesita șase volume, apoi șapte, pentru a acoperi în mod amănunțit subiectul. A publicat primul volum în 1968.

Exact înainte de a publica primul volum din The Art of Computer Programming, Knuth a plecat de la Caltech pentru a accepta o poziție la Divizia de Cercetare a Comunicațiilor din cadrul Institutului pentru Analize de Apărare, la vremea aceea localizată în campusul universitar de la Universitatea Princeton, care realiza cercetare matematică în criptografie pentru a susține Agenția Națională de Securitate.

În 1967, Knuth a mers la conferința Societății pentru Matematică Industrială și Aplicată și cineva l-a întrebat ce face. La momentul respectiv, informatica era împărțită în analiză numerică, inteligență artificială și limbaj de programare. Pe baza studiului său și cărții The Art of Computer Programming, Knuth s-a decis ca data viitoare când îl va întreba cineva ce face, va spune „Analiza algoritmilor”.

Knuth și-a părăsit apoi locul de muncă de atunci pentru a se alătura corpului profesoral de la Universitatea Stanford în 1969, unde devine Profesorul Fletcher Jones de Informatică, Emeritus.

Scrieri

Knuth este un scriitor și informatician.

The Art of Computer Programming (TAOCP)

În 1970, Knuth a descris informatica drept „un câmp complet nou fără o identitate reală. Iar standardul publicațiilor disponibile nu este atât de ridicat. Multe din lucrările publicate sunt, sincer, pur și simplu greșite. … Așadar, una din motivațiile mele a fost de a îndrepta o poveste foarte prost spusă”. Primele trei volume și partea întâi din volumul patru fuseseră publicate până în 2011. Concrete Mathematics: A Foundation for Computer Science ediția a 2-a, care și-a avut originea în extinderea secțiunii de preliminarii matematice din volumul 1 al TaoCP, a fost de asemenea publicată. Knuth a spus că lucrează din greu la partea B a volumului 4 și anticipează că va fi compusă din părți cel puțin de la A la F.

Bill Gates a lăudat dificultatea subiectului din The Art of Computer Programming, afirmând „Dacă tu consideri că ești un programator foarte bun… Trebuie neapărat să îmi trimiți un CV dacă poți citi toată cartea”.

Alte lucrări

Knuth este și autorul Surreal Numbers, un roman matematic scurt privind lucrarea lui John Conway asupra teoriei setului, respectiv construirea unui sistem alternativ de numere. În loc să explice pur și simplu subiectul, cartea dorește să prezinte dezvoltarea matematicii. Knuth voia ca această carte să pregătească studenții pentru cercetare originală, creativă.

În 1995, Knuth a scris cuvântul înainte pentru cartea A=B scrisă de Marko Petkovšek, Herbert Wilf și Doron Zeilberger. Knuth este și un contribuitor ocazional al puzzle-urilor de limbă ale World Ways: The Journal of Recreational Linguistics.

Knuth a explorat și matematică recreațională. A contribuit și la Journal of Recreational Mathematics începând cu anii 1960 și a fost recunoscut ca un contribuitor important la cartea lui Joseph Madachy Mathematics on Vacation.

Knuth a apărut și într-un număr al Numberphile și în videoclipuri Computerphile pe YouTube unde a discutat subiecte de la scrierea cărții Surreal Numbers, la de ce nu folosește e-mail.

Lucrări privind convingerile religioase ale lui Knuth

Pe lângă scrierile sale despre informatică, Knuth, un luteran, este și autorul 3:16 Bible Texts Illuminated, în care examinează Biblia printr-un proces de eșantionare sistematică, respectiv o analiză a capitolului 3, versul 16 din fiecare evanghelie. Fiecare vers este însoțit de o redare în artă caligrafică, oferită de un grup de caligrafi conduși de Hermann Zapf. Ulterior, el a fost invitat să țină un număr de lecturi cu privire la proiectul său 3:16, ducând la o altă carte Things a Computer Scientist Rarely Talks About (Lucruri despre care un informatician vorbește rar), unde a publicat lecturile „God and Computer Science”.

Opinia sa asupra brevetelor de software

Ca membru al comunității academice și științifice, Knuth se opune cu tărie politicii de acordare a brevetelor de software pentru soluții triviale care ar trebui să fie evidente, dar a exprimat opinii mai pronunțate pentru soluții non-triviale ca metoda punctului-interior a programării lineare. Și-a exprimat dezacordul în mod direct atât în fața Oficiului de Brevete și Mărci Înregistrare al Statelor Unite, cât și în fața Organizației Europene de Brevetare.

Computer Musings

Knuth oferă lecturi informale de câteva ori pe an la Universitatea Stanford, pe care le-a denumit „Computer Musings”. A fost profesor vizitator la Departamentul de Informatică al Universității Oxford din Regatul Unit până în anul 2017 și colaborator onorific la Magdalen College.

Programare

Typesetting digital

În anii 1970, editorii TAOCP au abandonat Monotype în favoarea phototypesetting. Knuth a devenit atât de frustrat de inabilitatea sistemului din urmă de a aborda calitatea volumelor anterioare, care erau setate utilizând sistemul vechi, încât și-a făcut timp să lucreze asupra typesetting și a creat TeX și Metafont.

Programare alfabetizată

În timp ce dezvolta TeX, Knuth a creat o nouă metodologie de programare, pe care a numit-o programare alfabetizată, deoarece considera că programatorii trebuie să privească programele ca opere literare. „În loc de a ne imagina că principala noastră sarcină este a spune calculatorului ce trebuie să facă, să ne concentrăm mai curând asupra explicării ființelor umane ceea ce ne dorim să facă un calculator”.

Knuth a reprezentat idea programării alfabetizate prin sistemul WEB. Aceeași sursă WEB este utilizată pentru a țese fișierul TeX și pentru a încurca un fișier sursă Pascal. La rândul lor, acestea produc o descriere a programului, care poate fi citită și, respectiv, un fișier binar executabil. O repetare ulterioară a sistemului, CWEB, a înlocuit Pascal cu C.

Knuth a utilizat WEB pentru a programa TeX și METAFONT și a publicat ambele programe sub formă de cărți: The TeXbook, publicată inițial în 1984, și The METAFONTbook, publicată inițial în 1986. Cam în același timp, LaTeX, pachetul macro care acum este vast adoptat bazat pe TeX, a fost dezvoltat de Leslie Lamport, care a publicat mai apoi primul manual de utilizator în 1986.

Muzică

Knuth este un organist și compozitor. În 2016, a terminat o piesă muzicală pentru orgă intitulată Fantasia Apocalyptica, pe care o descrie ca o „traducere din greacă a textului Revelația Sfântului Ioan de Patmos (Divinul) în muzică”. Premiera a avut loc în Elveția la 10 ianuarie 2018.

Viața personală

Donald Knuth s-a căsătorit cu Nancy Jill Carter la 24 iunie 1961, în timp ce era student la Institutul de Tehnologie din California. Au doi copii împreună: John Martin Knuth și Jennifer Sierra Knuth.

Nume chinezesc

Numele chinezesc al lui Knuth este Gao Dena (chineză simplificată: 高德纳; chineză tradițională: 高德納; pinyin: Gāo dé nà). În 1977, a primit numele Frances Yao, la puțin timp după călătoria sa de 3 săptămâni în China. În volumul său din 1980 The Art of Computer Programming (chineză simplificată: 计算机程序设计艺术; chineză tradițională: 電腦程式設計藝術; pinyin: Jìsuànjī chéngxù shèjì yìshù), Knuth explică motivul pentru care se bucură de numele său chinez, deoarece a vrut să fie cunoscut de numărul în creștere de programatori din China de la vremea respectivă. În 1989, numele său chinez a fost amplasat pe antetul revistei Journal of Computer Science and Technology, despre care Knuth spune că „mă face să mă simt apropiat de întregul popor chinez, deși nu pot vorbi limba voastră”.

Preocupări privind sănătatea

În 2006, Knuth a fost diagnosticat cu cancer de prostată. A fost supus unei intervenții chirurgicale în luna decembrie a aceluiași an și a afirmat „puțină radioterapie… ca precauție, dar prognosticul e destul de bun”, așa cum a raportat în autobiografia sa video.

Umor

Knuth obișnuia să plătească o taxă de descoperire de 2,56 de dolari pentru orice erori de tipografie sau greșeli descoperite în cărțile sale, deoarece „256 de penny este un dolar hexadecimal”, și 0,32 de dolari pentru „sugestii valoroase”. Conform unui articol din revista Institutului de Tehnologie din Massachusetts Technology Review, aceste verificări premiate ale lui Knuth sunt „printre cele mai apreciate trofee”. Knuth a încetat să mai trimită cecuri veritabile în 2008 din cauza fraudei bancare și, în prezent, oferă fiecărui descoperitor de erori „un certificat de depunere” dintr-un sold listat public la „San Sherriffe”, banca sa fictivă.

A prevenit la un moment dat un corespondent „Ai grijă la erorile din codul de mai sus; Eu doar l-am dovedit ca fiind corect, nu l-am încercat”.

Knuth a publicat primul său articol „științific” în revista școlii în 1957 sub titlul „The Potrzebie System of Weights and Measures” în care a definit unitatea fundamentală a lungimii ca subiectul principal din Mad Nr. 26 și a denumit unitatea fundamentală de forță „whatmeworry”. Mad a publicat articolul în ediția nr. 33 (iunie 1957).

Pentru a demonstra conceptul de recursivitate, Knuth a făcut referire în mod intenționat la „Definiția circulară” la intrarea „Definiție, circulară” și invers în indexul cărții The Art of Computer Programming, Volumul 1.

Prefața cărții Concrete Mathematics conține următorul paragraf: Atunci când DEK a predat Concrete Mathematics la Stanford pentru prima dată, el a explicat titlul oarecum bizar afirmând că a fost tentativa sa de a preda un curs de matematică care era dificil în loc de ușor. A anunțat că, în ciuda așteptărilor colegilor săi, el nu avea de gând să predea Teoria Agregatelor, nici Teorema încorporării a lui Stone, nici măcar compactificarea Stone–Čech. (Câțiva studenți de la departamentul de inginerie civilă s-au ridicat și au părăsit sala în liniște.)

La conferința TUG 2010, Knuth a anunțat un succesor satiric pe bază de XML al TeX, intitulat „iTeX”, care va accepta caracteristici ca unități iraționale scalate arbitrar, imprimare 3D, intrare în seismografe și monitoare cardiace, animare și sunet stereofonic.

Premii și onoruri

În 1971, Knuth a primit primul premiu ACM Grace Murray Hopper Award. El a primit mai multe premii, inclusiv Turing Award, premiul National Medal of Science, premiul John von Neumann Medal și premiul Kyoto Prize.

Knuth a fost ales Colaborator Distins al Societății Britanice de Informatică (DFBCS) în 1980, ca recunoaștere pentru contribuțiile sale din câmpul informaticii.

În 1990 a primit titlul academic unic de Professor of The Art of Computer Programming (profesor în arta programării), care a fost schimbat mai apoi în Profesor Emeritus în arta programării.
Knuth a fost ales la Academia Națională de Științe în 1975. În 1992, a devenit un asociat al Academiei Franceze de Științe. De asemenea, s-a retras din poziția regulată de cercetare și predare de la Universitatea Stanford pentru a termina The Art of Computer Programming. A fost ales Foreign Member of the Royal Society (ForMemRS) (Membru străin al Societății Regale) în 2003.

Knuth a fost ales Colaborator (prima clasă de Colaboratori) la Societatea de Matematică Industrială și Aplicată în 2009 pentru contribuții excepționale în matematică. Este membru al Academiei Norvegiene de Științe și Litere În 2012, a devenit colaborator al Societății Americane de Matematică. Alte premii și onoruri includ:

• Primul premiu ACM Grace Murray Hopper Award, 1971
• Turing Award, 1974
• Premiul Lester R. Ford Award, 1975 și 1993
• Premiul Josiah Willard Gibbs Lecturer, 1978
• Medalia National Medal of Science, 1979
• Premiul Golden Plate Award al American Academy of Achievement, 1985
• Medalia Franklin Medal, 1988
• Premiul John von Neumann Medal, 1995
• Premiul Harvey Prize de la Technion, 1995
• Premiul Kyoto Prize, 1996
• Colaborator al Muzeului de Istoria Calculatoarelor „pentru munca sa timpurie fundamentală în istoria algoritmilor computațional, dezvoltarea limbajului TeX typesetting și pentru contribuții majore în matematică și informatică”, 1998
• Asteroidul 21656 Knuth, denumit în onoarea sa în mai 2001
• Premiul Katayanagi Prize, 2010
• Premiul BBVA Foundation Frontiers of Knowledge Award la categoria Tehnologii Informaționale și de Comunicații, 2010
• Premiul Turing Lecture, 2011
• Universitatea Stanford, Facultatea de Inginerie, Premiul Hero, 2011