Datalogiens 'grand old man' udgiver 4. bind af kult-klassiker

Ét af datalogiens største skriftlige værker er i denne måned blevet et bind tykkere - mere end 40 år efter, at første bind så dagens lys.

Der er tale om bind 4A 'Combinatorial Algorithms' i serien The Art of Computer Programming, som den berømte amerikanske datalog Donald Knuth står bag.

Han betragtes normalt som én af de mest betydningsfulde dataloger i det 20. århundrede.

Da de tre første bind er skrevet mellem 1968 og 1973, vækker det opsigt, at den nu 73-årige Donald Knuth endelig tager hul på udgivelsen af bind fire.

»Han er faderen til den kvantitative del af den teoretiske datalogi. Altså den del, hvor man måler algoritmer efter deres tidskompleksitet, som er et meget centralt begreb i teoretisk datalogi,« fortæller Peter Bro Miltersen, der er professor i matematisk datalogi ved Datalogisk Institut på Aarhus Universitet, til Version2.

Tidskompleksiteten af en algoritme er kort fortalt et udtryk for, hvordan dens køretid vokser som en funktion af størrelsen på input til algoritmen.

Altså hvor effektivt et computerprogram er, når det behandler data.

Tidskompleksiteten udtrykkes med notationerne O(), Omega() og Theta(), der beskriver henholdvis øvre grænse, nedre grænse og begge dele for en algoritmes køretid.

Stoffet er obligatorisk lærdom for alle datalogistuderende på deres første år, og lærer man ikke at forstå det, er det nok en god idé at skifte studieretning.

Netop populariseringen af notationen i datalogien er Donald Knuths fortjeneste, forklarer Peter Bro Miltersen.

»Hele det 'mindset' skylder vi Knuth, og det er derfor, at han er blevet en datalogiens 'grand old man',« siger han.

Viste gode takter tidligt

Donald Knuth demonstrerede allerede tidligt sit talent for tal, kombinatorik og mønstre.

I den biografiske bog Out of Their Minds af Dennis Shasha og Cathy Lazere fortælles historien om, hvordan Donald Knuth i ottende klasse vandt et fjernsyn til sin skole.

Fjernsynet var førstepræmien i en konkurrence udskrevet af en slikfabrikant om, hvem der kunne danne flest nye ord ud af teksten 'Ziegler's Giant Bar'.

Dommerne i konkurrencen havde omkring 2.500 ord på deres referenceliste. Donald Knuth fandt omkring 4.500 - uden at bruge apostroffen.

I 1974 blev han tildelt datalogiens allerfornemmeste pris - A.M. Turing-prisen fra det amerikanske Association of Computing Machinery.

Turing-prisen fik han både for sine fundamentale bidrag til analysen af algoritmer og designet af programmeringssprog, men også for sit store arbejde med netop The Art of Computer Programming-bøgerne.

En hexadecimal dollar

Donald Knuth er også berømt for at have udviklet det matematiske typesetting-sprog TeX, som også hans egne bøger er skrevet i.

TeX er senere fra anden side blevet videreudviklet til LaTeX, som især er populært til rapporter og artikler i den matematiske og datalogiske del af universitetsverdenen.

Donald Knuth er samtidig kendt for at være ekstremt grundig i sit arbejde.

I den forbindelse udlodder han små dusører på 2,56 dollar - en hexadecimal dollar ifølge ham selv - til læsere, der finder fejl i hans bøger.

»Der gik kult i at få sådan en check på 2,56 dollar fra ham. Jeg fandt selv en fejl i anden udgave af bind 3, nemlig at mit efternavn var stavet 'Milterson' i stedet for 'Miltersen'. Men den blev desværre fundet og indsendt af nogen andre, før jeg nåede det,« siger Peter Bro Miltersen.

Er Donald Knuths nye bog relevant set ud fra et forskningsperspektiv?

»Det er ikke der, man finder det allermest hotte og nye inden for datalogien. Men der er nogle ting i bind 4A, som peger hen i mod nogle moderne anvendelser, blandt andet ordniveau-parallelisme. Og så har han en meget kategorisk og systematisk, ja nærmest encyklopædisk, tilgang til stoffet, som er interessant, og som man kan lære meget af,« siger Peter Bro Miltersen.

Du er selv citeret i bind 4A. Hvad er det, Donald Knuth er faldet over ved din forskning?

»Det er netop relateret til ordniveau-parallelisme. Jeg har skrevet en videnskabelig artikel sammen med andre forskere, hvor vi har fundet både en øvre og en nedre grænse for, hvor mange CPU-standardinstruktioner, der skal til for at finde det mest betydende bit i et ord. Det er ekstremt nørdet selv for os, men Knuth er også en slags nørdhelt for os,« siger Peter Bro Miltersen.

Bind 4A ventes efterfulgt af bind 4B, 4C og 4D. Du kan læse mere om bogen her.