Kornene på skakbrættet og COVID-19

Skakbræt med hvedekorn.

Hvis jeg endelig skal kritisere noget ved den igangværende håndtering af COVID-19-epidemien, er det at kommunikationen af, hvorfor vi har at gøre med et problem, først nu her til sidst blev klar – og så alligevel ikke. De allerfleste borgere forstår vel nu, at COVID-19 kan belaste sundhedsvæsenet voldsomt, men mange oplever stadig situationen som paradoksal. Det er jo i de fleste tilfælde ikke alvorlige sygdomsforløb, vi har med at gøre (og personligt er jeg da heller ikke bekymret for mit helbred). Den korte forklaring er, at når der er rigtig mange smittede, er der, selv når antallet af alvorligt behandlingskrævende patienter er en lille procentdel, mange alvorligt behandlingskrævende patienter.

Hvorfor bliver der så så mange smittede? Problemet er netop, at COVID-19-sygen så ofte har et mildere forløb end influenza. For da kan da de smittede gå rundt blandt andre i længere tid og føre smitten videre, inden de selv opdager, at der er noget galt og lægger sig syge. Hvis hver enkelt COVID-19-smittet person i løbet af 2 dage når at smitte 2 personer, bliver antallet af nye smittede fordoblet i løbet af 2 dage. Og det lyder ikke slemt for lægfolk, men det er det – thi hvis hver ny smittet person smitter nogen på denne måde, er der i et godt stykke tid tilnærmelsesvis tale om eksponentiel vækst i antallet af nye tilfælde.

Den bedste illustration af eksponentiel vækst er måske historien om hvedekornene på skakbrættet fra 1256; den skyldes den kurdiske historiker Ibn Khalikan. En vismand opfandt skakspillet og bad kongen om at få en lille belønning for at have opfundet dette gode brætspil, nemlig nogle hvedekorn på et skakbræt. På felt 1 skulle der være 1 hvedekorn, og på hvert efterfølgende felt skulle der lægges dobbelt så mange korn som på det foregående. Det lyder som et beskedent forlangende, men er det ikke. Allerede på felt 24 er der ca. 8 millioner hvedekorn, og kongen måtte da også til sidst give fortabt.

Lad os så genfortælle historien om skakbrættet som en historie om COVID-19-tilfælde, hvor felterne er perioder på 2 dage og smitten får lov at sprede sig frit. Felt nummer 24 svarer så til dag 48, og da er alle 5,6 millioner borgere i Danmark blevet smittet. Selvfølgelig er det ikke sådan; antagelsen om eksponentiel vækst er kun korrekt på kortere sigt. Rigtig mange er efter knap to måneder for længst blevet raske igen da og er derefter immune. Andre kan ikke blive syge, fordi de har mistet livet. Men selv hvis kun 2 procent er alvorligt behandlingskrævende (det tal er meget lavt sat), vil det betyde, at 280.000 borgere har skullet modtage behandling i løbet af knap to måneder. Den slags ville sundhedsvæsenet i Danmark selvfølgelig ikke kunne håndtere. Jeg håber, de nye og meget vidtgående foranstaltninger kan fjerne hvedekornene fra skakbrættet.

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!