Min første datalogibog

I dag kom jeg til at snakke med nogen om lærebøger om algoritmer og datastrukturer, der er et af de helt grundlæggende fag på datalogiuddannelser. En udbredt lærebog om dette emne er i vore dage blevet Introduction to Algorithms af Cormen, Leiserson, Rivest og Stein. Det er en grundig og præcis bog, der også tager videregående emner op, men den er også på nogle måder ved at blive en encyklopædi. Den udgave, jeg selv ejer, er en mursten på 1180 sider.

Selv blev jeg introduceret til algoritmer og datastrukturer af en bog på sølle 427 sider, Data Structures and Algorithms af Aho, Hopcroft og Ullman. Jeg kom dengang lige fra matematikstudiet og syntes, at denne bog var en “underlig matematikbog”. I dag har jeg en noget mere positiv opfattelse af den – og den er rar at slå op i. Men om denne klassiker ville være en god introduktion i dag, ved jeg ikke.

Engang var mange lærebøger kortfattede; jeg mindes Principles of Mathematical Analysis af Walter Rudin, den første kortfattede bog, jeg stødte på. Der var et hav af mellem-ræsonnementer, som læseren selv skulle opdage, og det kunne sagtens tage en time eller mere at læse en side. Som lærebog betragtet var Rudins bog noget af en mundfuld. Til gengæld var mange af mine medstuderende glade for A First Course in Abstract Algebra af John B. Fraleigh. Den var (selvfølgelig) helt stringent, men noget mere “snakkende” end Principles of Mathematical Analysis. I dag er jeg lidt mere forbeholden over for den og noget mere positiv over for Rudins bog.

En datalogibog, der virkelig delte vandene i min studietid, var Introduction to Automata Theory, Languages and Computation fra 1979 af Hopcroft og Ullman. Bogen var forholdsvis kortfattet, men nåede meget langt omkring inden for automatteori, beregnelighed og kompleksitetsteori. En senere udgave havde Motwani som medforfatter og var meget mere “snakkende” og havde skåret en del stof væk. De fleste foretrækker at henvise til 1979-udgaven, og sådan har jeg det også.

Alt dette tyder på, at man i virkeligheden har brug for to forskellige fremstillinger af det grundlæggende stof – en indledende, der er grundigt forklarende og er målrettet begyndere, og en fremstilling beregnet på den erfarne fagperson, der har brug for et godt opslagsværk. Men der er samtidig ikke nogen grund til at den indledende fremstilling skal være så lang, som indledende fremstillinger ofte har en tendens til at være.

Kun én artikel om året?

Tasawar Hayat – vor tids største matematiker? Han er i al fald den mest publicerende.

I går fik jeg besked om at jeg har fået en artikel optaget til en konference, der finder sted i februar 2020, så næste års publikationsrunde er allerede i gang. Artiklen dokumenterer resultater, som stammer fra et speciale som jeg vejledte i foråret. Men én artikel er ikke meget, og de sølle fire artikler, jeg fik publiceret sidste år, er bestemt heller ikke noget imponerende antal.

I den akademiske verden er det vigtigt at publicere så meget som muligt i så gode tidsskrifter og ved så gode konferencer som overhovedet muligt. Den mest publicerende forsker i årene fra 2016 til 2018 er Tasawar Hayat, der er professer i matematik ved Quaid-i-Azam University i Pakistan. Han publicerede hele 996 artikler i den periode, dvs. næsten én publikation om dagen. Så vidt jeg kan se, er en stor del af hans forskningsområde inden for matematisk fysik i den mest anvendelsesorienterede ende og har berøringsflader til maskinintelligens. Lødigheden af Hayats bidrag tør jeg ikke udtale mig om. Men det er forbløffende med denne ekstreme publikationsfrekvens; mange matematikere inden for den rene matematik publicerer kun 1-2 artikler om året.

Den tyske kognitionsforsker Uta Frith, der er professor med University College London, har en lidt anden tilgang. I en helt ny artikel i tidsskriftet Trends in Cognitive Sciences anbefaler hun faktisk, at det bliver et krav, at man kun publicerer én artikel om året. Hun skriver endda

When I look at my CV, I see papers that I wish I had not published, because they are either not sufficiently original or methodologically robust. I think it is important to tell younger researchers about this regret and make them aware that in time they might feel similarly. There are plenty of examples to show that a scientist’s reputation in the long run will be built on their best publications and lessened or even undermined by their weaker ones.

(fra Frith, Fast Lane to Slow Science, Trends in Cognitive Sciences (2019), https://doi.org/10.1016/j.tics.2019.10.007)

Det er en betragtning, jeg deler. Som Frith nævner, er det i virkeligheden et spørgsmål om at have et godt ry som forsker, der er det væsentlige, og om at kvalitet ikke nemt lader sig “fortynde”. Mange konferencerækker i datalogi har nu indstiftet en Test of Time Award, som bliver givet til 10 år gamle publikationer fra samme konference, der senere har vist sig at være særligt indflydelsesrige. Og når jeg ser på prisvinderne fra den lille del af datalogi, som jeg selv beskæftiger mig med, er jeg helt enig med udnævnelserne. Problemet er selvfølgelig, at dette gode ry på længere sigt ikke kan måles med det kortsigtede her-og-nu-fokus, som man i være dage bruger for at måle forskningens kvalitet, men i virkeligheden i mindst lige så stort omfang måler dens kvantitet.

Hvordan man løser det

Flere gange på det seneste har jeg anbefalet nogen at læse klassikeren How To Solve It af den store ungarsk/amerikanske matematiker George Pólya (ungarsk: Pólya György). Bogen, der udkom i 1975. har gjort et stort indtryk på mig; jeg købte den i 1982, ugen inden jeg begyndte at studere. I lang tid var jeg mest fascineret af alle bogens snedige opgaver, men i dag er jeg optaget af alle Pólyas indsigtsfulde, erfaringsbaserede råd til løsning af (især, men vel ikke kun) problemer fra matematikkens verden.

Hans bud på de fire trin i god problemløsning er

  • Trin 1: Forstå problemet
  • Trin 2: Udarbejd en plan (oversæt)
  • Trin 3: Udfør planen (løs)
  • Trin 4: Kig tilbage (tjek og fortolk løsningen)

På denne måde er der klare paralleller til problemorienteret projektarbejde, selv om fokus i How To Solve It er på små/mindre opgaver. Tænk, hvis de, der skal lære at løse matematiske problemer i forbindelse med deres uddannelse, kunne læse Pólyas lille klassiker på et tidspunkt – og tænk hvis de, der skal undervise andre i at løse problemer, kunne med dem om at sammenligene deres proces med de fire forholdsvis veldefinerede skridt ovenfor. Og tænk, hvis nogen en dag ville sørge for at How To Solve It kunne blive oversat til dansk. Det er nemlig stadig en bog, mange uddannelsessøgende kunne have glæde af at læse.

At aksiomatisere det hele

Det kommutative diagram for et pullback.

En person fra mit fagområde sagde engang i al venskabelighed, at han ligesom jeg gerne ville kunne aksiomatisere det hele, men at det jo langt fra er alle inden for datalogi, der har det på den måde. Han havde og har ret. En del af mine publikationer fra de seneste år er netop forsøg på at give en generel teoretisk forståelse af en bestemt slags typesystemer, og på den måde har jeg netop haft som formål at aksiomatisere, om ikke det hele, så dog et lille hjørne.

Det er fascinerende at læse om mere ambitiøse anstrengelser i matematisk regi. Quanta Magazine har nu en artikel (også udgivet hos Wired) om kategoriteori – eller rettere toposteori – som et bud på matematikkens grundlag. Her er det interessant at læse forsøgene på at forklare toposteori for lægfolk med interesse for matematik; jeg er ikke sikker på at det helt er lykkedes.

Jeg ville selv ønske, at jeg havde et mere naturligt forhold til kategoriteori. Selv om jeg engang har fulgt et kursus i kategoriteori, da jeg var PhD-studerende i Edinburgh, har jeg haft en ærgerlig fornemmelse af at skulle gen-lære kategoriteori, de få gange jeg har haft brug for det senere. Det er desværre stadig ikke et sprog, jeg taler flydende, selv om jeg er sådan én, der gerne ville aksiomatisere det hele. Min eneste trøst (og den er en underlig én) er, at jeg ikke er den eneste, der har det sådan. Selv blandt “rigtige” matematikere er det ikke alle forundt at beherske sproget flydende. Mit håb er nu at kunne genbesøge kategoriteori ud fra en forståelse af den som en visualisering af begreber inden for funktionel programmering – men det er en anden snak.

Glæden ved tavler

Differentialgeometri tegnet og skrevet af André Neves fra Imperial College, dengang ved Institute for Advanced Studies. Princeton.

Foto: Jessica Wynne (https://static01.nyt.com/images/2019/09/23/science/23SCI-BLACKBOARDS11/merlin_161146965_420b76c3-6d86-4228-b8fe-06ad92be4f2f-superJumbo.jpg?quality=90&auto=webp)

Både i min undervisning og i min forskning har jeg haft stor glæde af tavler. Her mener jeg rigtige tavler, sorte tavler, som jeg skrev på med hvidt kridt – ikke de underlige whiteboards. Med tiden har jeg endda lært mig en vis tavleorden. Selv om der er kommet ganske mange andre værktøjer til i tidens løb, er der noget, man kan med en tavle, som man ikke kan ellers. I matematik og fag, der anvender matematik og matematiske ræsonnementer, er tavler uomgængelige som et kommunikations- og tænkeredskab. Faktisk er det kombinationen af disse to anvendelser, der gør tavler til noget helt særligt.

Der er et fascinerende billedessay i New York Times netop om matematikeres brug af tavler. Og det er fascinerende endnu engang at se de mange måder, tavler bliver brugt på. Det er tydeligt, at mange udvikler deres egen “tavlestil”, og det bliver også meget tydeligt, at der er nogle, der først og fremmest er visuelt anlagte og andre, der ser matematisk praksis som forbundet med at manipulere symboler.

One trick pony i madlavning – og matematik

Foto: Vonguard (https://www.flickr.com/photos/vonguard/2873485758/)

Der er tre tilgange til madlavning i hjemmet, og de minder om de tilgange, vi ser på mange andre områder, og de svarer til forskellige kompetencer.

Den ene tilgang er den, hvor man holder sig nøje til en opskrift. I den opskriftsbaserede verden kommer problemerne, hvis opskriften viser sig umulig at følge eller noget uventet sker. Der er dem, der bliver fortvivlede, når de opdager at de havde tilsat 285 gram hvedemel til en dej i stedet for 275 gram. Og jeg har selv prøvet at stå med hel muskatnød i stedet for revet muskatnød (det kunne selvfølgelig løses med et rivejern, men træls var det).

Den anden tilgang er den, hvor man improviserer sig frem med de forhåndenværende ingredienser. Her kommer problemerne, hvis man fejlvurderer eller slet ikke ved, hvordan ingredienserne skal behandles. Jeg har selv prøvet at stå med gryderetter, som fik lidt for lang tid, så de ellers så friske grøntsager endte som en slatten omgang.

Den tredie tilgang er den, hvor man simpelthen giver op og ikke engang åbner kogebogen, fordi den ikke er til at hitte rede i. Jeg har oplevet meget begavede mennesker, der gik i baglås og blev helt fortvivlede i køkkenet hjemme ved mig – det viste sig som regel, når jeg spurgte dem, at de foretrak at spise ude eller købe færdigretter.

En del mennesker formår i et eller andet omfang at kombinere de to første tilgange. De har et repertoire af (typer af) madretter, som baserer sig på opskrifter, som de improviserer videre fra. Selv tror jeg efterhånden, det er lykkedes mig at få et sådant, ret begrænset repertoire inden for frokost- og middagsretter. Men det har taget mange år, og hvis jeg skal lave kager eller desserter, må jeg stadig ty til opskrifter. Jeg er måske ikke en one trick pony, som man siger på engelsk, men jeg kan nogle ganske få tricks, jeg kan variere.

Det er interessant for mig at opleve, at det forholder sig tilsvarende vis i et fag som matematik (og beslægtede områder). Der er desværre dem, der desværre går helt i baglås, når de møder matematik (af en eller anden grund ser journalister ud til at være overrepræsenteret i denne gruppe). Andre, der skal lære matematik, holder sig til en “opskrift” når de skal læse en tekst eller løse en opgave. Hvis der står et uventet symbol eller begreb, går det galt. Andre har nogle få “opskrifter”, der virker inden for et lille fagområde, men virker godt. Hvis jeg kigger ned over mine egne forskningsresultater i teoretisk datalogi, ser det ud som om jeg har nogle få sådanne “opskrifter”, og de ser alle ud til at have rekursive definitioner og induktionsbeviser som centrale ingredienser. Jeg er vel en pony, der kan to-tre tricks. Nogle af de dygtigste mennesker, jeg kender, ser til gengæld ud til at have mange “opskrifter”, der hver især afspejler en dyb indsigt i matematisk metode.

Set på denne måde svarer de forskellige kompetenceniveauer inden for madlavning på en måde til de niveauer af matematisk kompetence, som bl.a. Terence Tao har identificeret og som jeg tidligere har skrevet om på denne blog.

Myter i matematik

Fra A Handbook of Mathematical Discourse.

En af de mest interessante bøger om matematik, jeg kender, er A Handbook of Mathematical Discourse af den amerikanske matematiker Charles Wells. Den er frit tilgængelig på nettet. Og jeg bemærker her, at dette ikke er en matematikbog, men en bog om hvad de, der beskæftiger sig med matematik, gør og siger/skriver. Dette er med andre ord en bog både om matematikeres praksis og om den praksis, de der lærer matematik, udøver.

A Handbook of Mathematical Discourse er et af de opslagsværker, man får lyst til at bladre i på må og få, for der er mange guldkorn at hente. En af de interessante artikler er artiklen om matematiske myter, dvs. det, som mange studerende tror er sandt og som optræder i generation efter generation. F.eks. er der mange studerende, der tror at den tomme mængde er et element i enhver mængde. Denne myte har Charles Wells mødt, og jeg har også! Mine år som underviser har gjort mig helt enig i Wells’ udsagn om at der findes rigtig mange myter om den tomme mængde.

Hvorfor findes myterne? Charles Wells giver matematikundervisningen noget af skylden, men det kan ikke være hele årsagen. Den danske videnskabshistoriker Kirsten Paludan udgav i sin tid den fascinerende bog Videnskaben, verden og vi om myter hos dem, der lærer naturvidenskab. Formodentlig kunne man skrive en tilsvarende bog om myter i matematik – og det kunne faktisk være rigtig interessant at finde ud af, hvor myterne kommer fra og hvorfor så mange ender med at falde for de samme myter. Ideen er hermed givet videre.

PhD ved et tilfælde

George Dantzig.

En af de mest fascinerende anekdoter i universitetsmatematik er vel beretningen om George Dantzig, manden bag simplex-algoritmen, kendt fra lineær programmering.

I et interview fra 1986 fortæller han, hvordan han i 1939 som første-års PhD-studerende på Berkeley engang kom for sent til en statistikforelæsning med Jerzy Neyman. Dantzig så at Neyman havde skrevet to problemer på tavlen, og han regnede med at der var tale om hjemmearbejde til næste kursusgang. Så gav Dantzig sig til at løse de to problemer; han undskyldte bagefter til Neyman at han afleverede sin besvarelse for sent.

Men det var slet ikke to hjemmeopgaver; det var faktisk to åbne problemer fra matematisk statistik, som Neyman havde skrevet på tavlen – og George Dantzig havde løst dem “i god tro”.

Jeg har ikke kunnet finde ret mange oplysninger om hvad det var for to åbne problemer, men det ene problem handler om det såkaldte Neyman-Pearson-lemma, der fortæller hvordan man finder den stærkeste test for et givet signifikansniveau.

Jerzy Neyman foreslog George Dantzig at publicere sine beviser og lade dem udgøre en PhD-afhandling. Så det gjorde han (Anden Verdenskrig kom ganske vist i vejen for en tid.)

Jeg burde lære det…

Logoet for Coq (http://www.inria.fr)

I dag var der statusseminar på 4. semester af datalogiuddannelsen, hvor projektgrupper fremlagde problemformuleringerne i deres projekter. En projektgruppe, som jeg vejleder, havde i deres materiale nævnt bevisassistenten Coq (som et eksempel på hvordan man ved hjælp af en bevisassistent kan implementere en bevisligt korrekt oversætter til et programmeringssprog). og da måtte jeg modstræbende indrømme, at jeg inden for de seneste år ofte har haft en ambition om at komme til at lære at bruge Coq, så jeg kunne formalisere alle mine beviser én gang for alle. Jeg har tidligere her skrevet om de store resultater inden for formaliseret matematik, som er nået gennem brug af Coq. Og jeg røbede, at jeg havde købt Adam Chlipalas bog om Coq, da jeg var til POPL2019 i Portugal i januar i år. Nu ligger bogen og truer på et bord på mit kontor; jeg havde lovet mig selv at bruge en eftermiddag om ugen på at komme i gang med at lære at bruge bevisassistenten. Men endnu har jeg end ikke fået læst bogens forord. Min ambition om at lære Coq er desværre på vej samme sted hen som min ambition om at blive bedre til at spille guitar. Og jeg ved, at jeg ikke er den eneste, der har det på denne måde. Til POPL2019 mødte jeg flere, der havde det på den måde og havde samme underlige længsel som mig.

En studerende fra en anden gruppe spurgte til statusseminaret, om ikke jeg kunne give ham en henvisning til Chlipalas bog, for det ville han da gerne give sig i kast med. Og det kunne jeg selvfølgelig – bogen kan hentes kvit og frit hos forfatteren som PDF-fil.Det vil være noget helt særligt, hvis den første person på Aalborg, der lærer at bruge Coq, bliver en studerende på 4. semester af bacheloruddannelsen!

En af de sidste af slagsen?

Foto: Brian Flaherty/New York Times.

I New York Times’ netudgave er der i dag en lang portrætartikel om Donald Knuth, den (for mig og andre af min slags) legendariske amerikanske datalog og matematiker, der har så mange store opdagelser på samvittigheden. Jeg har skrevet om Knuth før her på bloggen; han er altid værd at vende tilbage til. Han er gammel nu – den 10. januar bliver han 81.

Knuth-Morris-Pratt-algoritmen til søgning i tekst (som alle, der søger i en tekst med CTRL-F bruger) ig dokumentbehandlingssystemet TeX (som jeg bruger dagligt – i form af LaTeX) er bare to af mange af Knuths bidrag.

Portrætartiklen er i det store og hele præcis (omend jeg ikke er så glad for forsøget på at forklare hvad et højniveau-programmeringssprog er), og den røber, at vi kan regne med snart at se næste bind af The Art of Computer Programming., Til ikke-fagfolk: Dette flerbindsværk er ikke er en bog om programmering, men derimod er en bog om algoritmeteori og langt hen ad vejen en lærebog i matematik (og en god én af slagsen).

Det, der slår mig for alvor, er dog at Donald Knuth måske er en af de sidste af sin slags. Knuth begyndte sin karriere, mens datalogi endnu blev set som en gren af anvendt matematik. Så alene her favner han bredere, end moderne dataloger som oftest gør. Han interesserer sig for musik, sprog, typografi og litteratur og har noget interessant at sige om hvert af disse områder. Og hans måde at publicere på har været en helt anden end den, man ser i dag. Han har ikke publiceret siden 2012 – ikke så sært, for det er meget længe siden, han gik på pension. Knuths publikationer op gennem årene er temmelig få, og også i hans egentlige aktive periode var der år, hvor han ikke publicerede. Andre år havde han kun én publikation, men den var så til gengæld en bog.

I dag laver vi (og jeg er medskyldig her) mere og mere specialiserede kandidater i alle universitetsfagene, og selvfølgelig også i datalogi. Men jeg ville ønske, at vi også kunne stimulere de studerende til også at have en anden slags forbilleder end de hyppigt publicerende og iværksætter-aktive kandidater med formuer af forskningsmidler, der så ofte bliver hyldet i disse år. Jeg tror selv, at det er dét. der skal til for at skabe en ny Donald Knuth-skikkelse.