La scienza è quello che comprendiamo abbastanza bene da spiegare a un computer; l'arte è tutto il resto.
Donald Ervin Knuth è uno scienziato informatico, matematico e professore emerito presso la Stanford University. È il destinatario del premio Turing ACM del 1974, informalmente considerato il premio Nobel dell'informatica. Knuth è stato chiamato il "padre dell'analisi degli algoritmi".
È l'autore dell'opera in più volumi The Art of Computer Programming. Ha contribuito allo sviluppo dell'analisi rigorosa della complessità computazionale degli algoritmi e ha sistematizzato tecniche matematiche formali per essa. Nel processo ha anche popularizzato la notazione asintotica. Oltre ai contributi fondamentali in diversi rami dell'informatica teorica, Knuth è il creatore del sistema di composizione tipografica TeX, del relativo linguaggio di definizione dei caratteri METAFONT e del sistema di rendering, e della famiglia di caratteri Computer Modern.
Come scrittore e studioso, Knuth ha creato i sistemi di programmazione WEB e CWEB progettati per incoraggiare e facilitare la programmazione letterale, e ha progettato le architetture del set di istruzioni MIX/MMIX. Knuth si oppone fortemente alla concessione di brevetti software, avendo espresso la sua opinione all'Ufficio brevetti e marchi degli Stati Uniti e all'Organizzazione europea dei brevetti.
Biografia
Primi anni
Knuth è nato a Milwaukee, Wisconsin, da genitori di origine tedesca Ervin Henry Knuth e Louise Marie Bohning. Suo padre possedeva una piccola azienda di stampa e insegnava contabilità. Donald, uno studente alla Milwaukee Lutheran High School, ha pensato a modi ingegnosi per risolvere i problemi. Ad esempio, in terza media, ha partecipato a un concorso per trovare il numero di parole che le lettere in "Ziegler's Giant Bar" potevano essere riordinate per creare; i giudici avevano identificato 2.500 parole di questo tipo. Con il tempo guadagnato lontano dalla scuola a causa di un finto mal di stomaco, e affrontando il problema al contrario, Knuth ha utilizzato un dizionario integrale e ha determinato se ogni voce del dizionario poteva essere formata utilizzando le lettere nella frase. Usando questo algoritmo, ha identificato oltre 4.500 parole, vincendo il concorso. Come premi, la scuola ha ricevuto una nuova televisione e abbastanza barrette di cioccolato per tutti i suoi compagni di classe da mangiare.
Istruzione
Knuth ha ricevuto una borsa di studio in fisica presso il Case Institute of Technology, ora parte della Case Western Reserve University a Cleveland, Ohio, iscrivendosi nel 1956. Si è anche unito al Beta Nu Chapter della fraternità Theta Chi. Mentre studiava fisica al Case, Knuth è stato introdotto all'IBM 650, un primo computer commerciale. Dopo aver letto il manuale del computer, Knuth ha deciso di riscrivere il codice assembly e del compilatore per la macchina utilizzata nella sua scuola, perché credeva di poterlo fare meglio.
Nel 1958, Knuth ha creato un programma per aiutare la squadra di basket della sua scuola a vincere le partite. Ha assegnato "valori" ai giocatori al fine di valutare la loro probabilità di segnare punti, un approccio innovativo che Newsweek e CBS Evening News hanno successivamente riportato.
Knuth è stato uno dei redattori fondatori della Engineering and Science Review del Case Institute, che ha vinto un premio nazionale come miglior rivista tecnica nel 1959. Ha quindi cambiato dalla fisica alla matematica, e ha ricevuto due diplomi dal Case nel 1960: il suo diploma di laurea in scienze e contemporaneamente un master in scienze con un special award della facoltà, che ha considerato il suo lavoro eccezionalmente straordinario.
Nel 1963, con il matematico Marshall Hall come suo consigliere, ha conseguito un dottorato di ricerca in matematica dal California Institute of Technology.
Primi lavori
Dopo aver ricevuto il suo dottorato, Knuth si è unito alla facoltà del Caltech come professore assistente.
Ha accettato una commissione per scrivere un libro sui compilatori dei linguaggi di programmazione. Mentre lavorava a questo progetto, Knuth ha deciso che non poteva affrontare adeguatamente l'argomento senza prima sviluppare una teoria fondamentale della programmazione informatica, che è diventata The Art of Computer Programming. Originariamente aveva pianificato di pubblicarla come un singolo libro. Mentre Knuth sviluppava il suo schema per il libro, ha concluso che aveva bisogno di sei volumi, e poi sette, per coprire completamente l'argomento. Ha pubblicato il primo volume nel 1968.
Poco prima di pubblicare il primo volume di The Art of Computer Programming, Knuth ha lasciato il Caltech per accettare un impiego presso la Communications Research Division dell'Institute for Defense Analyses, allora situata nel campus della Princeton University, che stava conducendo ricerche matematiche in crittografia per supportare la National Security Agency.
Nel 1967 Knuth ha partecipato alla conferenza della Society for Industrial and Applied Mathematics e qualcuno gli ha chiesto cosa faceva. All'epoca l'informatica era divisa in analisi numerica, intelligenza artificiale e linguaggi di programmazione. Sulla base del suo studio e del libro The Art of Computer Programming, Knuth ha deciso che la prossima volta che qualcuno lo avesse chiesto, avrebbe detto, "Analisi degli algoritmi".
Knuth ha quindi lasciato questa posizione per unirsi alla facoltà della Stanford University nel 1969, dove è ora Fletcher Jones Professor of Computer Science, Emeritus.
Scritti
Knuth è uno scrittore, così come uno scienziato informatico.
The Art of Computer Programming TAOCP
Negli anni '70, Knuth ha descritto l'informatica come "un campo completamente nuovo senza una vera identità. E lo standard delle pubblicazioni disponibili non era così alto. Molti dei documenti pubblicati erano semplicemente sbagliati. ... Quindi una delle mie motivazioni era mettere in ordine una storia che era stata molto male raccontata". Entro il 2011, i primi tre volumi e la prima parte del volume quattro della sua serie erano stati pubblicati. Concrete Mathematics: A Foundation for Computer Science 2nd ed., che ha avuto origine con un'espansione della sezione preliminare matematica del Volume 1 di TAoCP, è stata anche pubblicata. Ad aprile 2020, Knuth ha detto che sta lavorando duramente sulla parte B del volume 4, e prevede che il libro avrà almeno le parti da A a F.
Altri lavori
Knuth è anche l'autore di Surreal Numbers, una novella matematica sulla costruzione della teoria degli insiemi di John Conway di un sistema alternativo di numeri. Invece di semplicemente spiegare l'argomento, il libro cerca di mostrare lo sviluppo della matematica. Knuth voleva che il libro preparasse gli studenti a fare ricerca originale e creativa.
Nel 1995, Knuth ha scritto la prefazione del libro A=B di Marko Petkovšek, Herbert Wilf e Doron Zeilberger. Knuth è anche un contributore occasionale di puzzle linguistici a Word Ways: The Journal of Recreational Linguistics.
Knuth si è anche dedicato alla matematica ricreativa. Ha contribuito con articoli al Journal of Recreational Mathematics a partire dagli anni '60, ed è stato riconosciuto come un grande contributore in Mathematics on Vacation di Joseph Madachy.
Knuth è anche apparso in numerosi video di Numberphile e Computerphile su YouTube dove ha discusso argomenti dalla scrittura di Surreal Numbers al motivo per cui non usa la posta elettronica.
Opere riguardanti le convinzioni religiose di Knuth
Oltre ai suoi scritti di informatica, Knuth, un luterano, è anche l'autore di 3:16 Bible Texts Illuminated, in cui esamina la Bibbia attraverso un processo di campionamento sistematico, vale a dire un'analisi del capitolo 3, verso 16 di ogni libro. Ogni verso è accompagnato da un'illustrazione in arte calligrafica, fornita da un gruppo di calligrafi sotto la guida di Hermann Zapf. Successivamente, è stato invitato a tenere una serie di conferenze al MIT sulle sue opinioni riguardanti la religione e l'informatica dietro il suo progetto 3:16, risultando in un altro libro, Things a Computer Scientist Rarely Talks About, dove ha pubblicato le conferenze "God and Computer Science".
Opinione sui brevetti software
Come membro della comunità accademica e scientifica, Knuth si oppone fortemente alla politica di concessione di brevetti software per soluzioni banali che dovrebbero essere ovvie, ma ha espresso opinioni più sfumate per soluzioni non banali come il metodo del punto interno della programmazione lineare. Ha espresso il suo disaccordo direttamente sia all'Ufficio brevetti e marchi degli Stati Uniti che all'Organizzazione europea dei brevetti.
Computer Musings
Knuth tiene lezioni informali poche volte all'anno presso la Stanford University, che ha intitolato "Computer Musings". È stato professore visitatore presso il Department of Computer Science dell'Oxford University nel Regno Unito fino al 2017 e Fellow onorario del Magdalen College.
Programmazione
Composizione tipografica digitale
Negli anni '70, gli editori di TAOCP hanno abbandonato Monotype a favore della fotocomposizione. Knuth è diventato così frustrato dall'incapacità di quest'ultimo sistema di avvicinarsi alla qualità dei volumi precedenti, che erano composti utilizzando il sistema più vecchio, che si è preso il tempo per lavorare sulla composizione tipografica digitale e ha creato TeX e Metafont.
Programmazione letterale
Durante lo sviluppo di TeX, Knuth ha creato una nuova metodologia di programmazione, che ha chiamato programmazione letterale, perché credeva che i programmatori dovessero pensare ai programmi come opere di letteratura. "Invece di immaginare che il nostro compito principale sia dire a un computer cosa fare, concentriamoci piuttosto sulla spiegazione agli esseri umani di quello che vogliamo che un computer faccia."
Knuth ha incorporato l'idea della programmazione letterale nel sistema WEB. Lo stesso codice sorgente WEB viene utilizzato per tessere un file TeX e per intrecciare un file sorgente Pascal. A loro volta producono una descrizione leggibile del programma e un binario eseguibile rispettivamente. Un'iterazione successiva del sistema, CWEB, sostituisce Pascal con C.
Knuth ha utilizzato WEB per programmare TeX e METAFONT, e ha pubblicato entrambi i programmi come libri: The TeXbook, pubblicato originariamente nel 1984, e The METAFONTbook, pubblicato originariamente nel 1986. Più o meno nello stesso periodo, LaTeX, il pacchetto di macro ormai ampiamente adottato basato su TeX, è stato sviluppato per la prima volta da Leslie Lamport, che ha successivamente pubblicato il suo primo manuale utente nel 1986.
Musica
Knuth è un organista e un compositore. Nel 2016 ha completato un brano musicale per organo intitolato Fantasia Apocalyptica, che descrive come "traduzione del testo greco dell'Apocalisse di San Giovanni l'Evangelista in musica". È stato presentato in Svezia il 10 gennaio 2018.
Vita personale
Donald Knuth ha sposato Nancy Jill Carter il 24 giugno 1961, mentre era uno studente laureando presso il California Institute of Technology. Hanno due figli: John Martin Knuth e Jennifer Sierra Knuth.
Nome cinese
Il nome cinese di Knuth è Gao Dena. Nel 1977, gli è stato dato questo nome da Frances Yao, poco prima di intraprendere un viaggio di 3 settimane in Cina. Nel suo volume del 1980 di The Art of Computer Programming, Knuth spiega che ha abbracciato il suo nome cinese perché voleva essere conosciuto dal crescente numero di programmatori informatici in Cina all'epoca. Nel 1989, il suo nome cinese è stato collocato in cima all'intestazione della rivista Journal of Computer Science and Technology, di cui Knuth dice "mi fa sentire vicino a tutti i cinesi anche se non posso parlare la vostra lingua".
Problemi di salute
Nel 2006, Knuth è stato diagnosticato con cancro alla prostata. Ha subito un intervento chirurgico a dicembre di quell'anno e ha dichiarato, "un po' di radioterapia ... come precauzione ma la prognosi sembra abbastanza buona", come ha riferito nella sua autobiografia video.
Umorismo
Knuth era solito pagare una tassa di ricerca di $ 2,56 per eventuali errori tipografici o errori scoperti nei suoi libri, perché "256 centesimi è un dollaro esadecimale", e $ 0,32 per "suggerimenti preziosi". Secondo un articolo in Technology Review del Massachusetts Institute of Technology, questi assegni di premio di Knuth sono "tra i trofei più preziosi del mondo dei computer". Knuth ha dovuto smettere di inviare assegni veri nel 2008 a causa di frodi bancarie, e invece ora offre a ogni scopritore di errori un "certificato di deposito" da un saldo pubblicamente quotato nella sua fittizia "Bank of San Serriffe".
Ha una volta avvertito un corrispondente, "Attento ai bug nel codice qui sopra; l'ho solo provato corretto, non provato."
Knuth ha pubblicato il suo primo articolo "scientifico" in una rivista scolastica nel 1957 con il titolo "The Potrzebie System of Weights and Measures". In esso, ha definito l'unità fondamentale di lunghezza come lo spessore di Mad No. 26, e ha denominato l'unità fondamentale di forza "whatmeworry". Mad ha pubblicato l'articolo nel numero 33 giugno 1957.
Per dimostrare il concetto di ricorsione, Knuth ha intenzionalmente riferito "Circular definition" e "Definition, circular" l'uno all'altro nell'indice di The Art of Computer Programming, Volume 1.
La prefazione di Concrete Mathematics ha il seguente paragrafo:
Quando DEK ha insegnato Concrete Mathematics a Stanford per la prima volta, ha spiegato il titolo piuttosto strano dicendo che era il suo tentativo di insegnare un corso di matematica che era difficile invece di morbido. Ha annunciato che, contrariamente alle aspettative dei suoi colleghi, non avrebbe insegnato la Theory of Aggregates, né Stone's Embedding Theorem, né nemmeno la Stone–Čech compactification. (Diversi studenti del dipartimento di ingegneria civile si alzarono e se ne andarono tranquillamente.)
Alla conferenza TUG 2010, Knuth ha annunciato un successore satirico basato su XML a TeX, intitolato "iTeX" pronunciato, eseguito con una campana che suona, che supporterebbe caratteristiche come unità irrazionali arbitrariamente scalate, stampa 3D, input da seis
