Kategoriarkiv: Datalogi

Hemmelig deling

Secretsharing-3-point

I dag var jeg til workshop om secret sharing på Institut for matematiske fag. Dette er et emne med forbindelse til kodningsteori og kryptologi, og der var både matematikere og dataloger til stede fra flere danske universiteter (og en enkelt industriel personlighed). Det er ikke nogen ny idé, vi har med at gøre – den skyldes israeleren Adi Shamir og amerikaneren George Blakley, der fandt hver deres løsning på samme udfordring hver for sig i 1979. Secret sharing er den udfordring at lade et antal deltagere have hver deres del af et hemmeligt stykke data, men på en sådan måde at der skal et vist, bestemt antal deltageres viden til for at det hemmelige stykke data kan rekonstrueres.

Blakleys løsning er måske den nemmeste at forstå; hvis hemmeligheden skal deles med n deltagere, skal vi opfatte den som et punkt i et n-dimensionalt rum og fortælle hver af de n deltagere en plan i rummet. Planerne skal man vælge sådan, at de skærer hinanden i ét punkt – nemlig det punkt, man vil holde hemmeligt. Kun når man har kendskab til alle n planer, ved man hvad det hemmelige punkt er.

Shamirs løsning går (meget løst sagt) ud på dette: Hvis vi vil holde et tal hemmeligt og dele det med n deltagere, og tærskelværdien skal være t, dvs. at der skal t af de n deltagere til for at finde frem til den hemmelige talværdi, skal man at konstruere et polynomium af grad t-1 og oplyse n punkter fra polynomiets graf. Vi ved nemlig at vi kan bestemme et polynomium af grad t-1 entydigt, hvis vi kender t punkter på dets graf. Den ledende koefficient i polynomielt (dvs. den, der har højest orden) skal være den hemmelige værdi; resten vælger vi tilfældigt. Her kommer forbindelsen til kodningsteori ind, for det vi har lavet her, er det man også kalder for en Reed-Solomon-kodning.

I al fald er emnet stadig vigtigt i både matematik og datalogi, og Olav Geil og Diego Ruano fra AAU har allerede en del interessante resultater om emnet – og de har for nylig fået forskningsrådspenge til at arbejde videre med det.

Til dagens workshop var der både italienere og spaniere til stede, og stemningen var så positiv, at de endog helt frivilligt begyndte at snakke om VM i frokostpausen!

flattr this!

Det hele er i stykker

wordle-norton

I Information er der en lang artikel af den amerikanske journalist Quinn Norton, der var kæreste med den ligeledes amerikanske aktivist og softwareudvikler Aaron Swartz, som sidste år begik selvmord.

Dette er en artikel, jeg vældig gerne ville synes om, for jeg deler de bekymringer, Quinn Norton giver udtryk for om den manglende sikkerhed ved brug af computere. Især de store problemer, dårlig softwarekvalitet fører med sig, bekymrer mig.

Men artiklen er skrevet i et poppet, floskelpræget sprog med lav informationstæthed – mest af alt minder den desværre om de P0-rapporter, helt uerfarne studerende hos os laver i begyndelsen af 1. semester. Det er på dette tidspunkt, inden man ved noget om datalogi og om softwareteknologi, at man er mest tilbøjelig til at komme med store udsagn om hvad der kan lade sig gøre og (især) hvad der ikke kan lade sig gøre. Og så er der en frygtelig masse “du-sprog”. Det er pænt, at Quinn Norton tænker på mig, men jeg ville ønske at hun lod være.

Prøv bare at læse dette:

Software er så dårligt, fordi det er så komplekst, og fordi det forsøger at tale med andre programmer på samme computer eller gennem forbindelser til andre computere. Faktisk er din egen computer på en måde mere end én computer, den er æsker inden i æsker, og hver af dem er fuld af små programmer, som forsøger at koordinere handlinger og kommunikere indbyrdes. Computere er blevet ufatteligt komplekse, altimens vi mennesker er forblevet de samme grå mudderhoveder, der tror, vi er guder. Din gennemsnitlige middelmådige Windowsflade er så indviklet, at ingen på hele kloden reelt kender til alt, hvad den gør, endsige hvorfor.

Quinn Norton har fat i et reelt problem, nemlig at moderne softwaresystemer er alt for komplekse – både “hver for sig” og når de er del af et netværk. Men dette er et problem, som allerede bliver diskuteret i datalogi i forskellige afskygninger og ligger bag de Grand Challenges, som betydningsfulde forskere (bl.a Tony Hoare og Robin Milner) siden årtusindskiftet har formuleret.

Den oprindelige artikel på engelsk er desværre ikke bedre. Der må da være nogen derude, der kan skrive lige så lødigt om disse problemstillinger som man kan skrive om f.eks. udenrigspolitik eller global økonomi.

flattr this!

Er der en doktor til stede?

flag
Det “schweiziske flag” i 2 og flere dimensioner (fra Martin Raussens doktorafhandling).

I dag forsvarede Martin Raussen sin doktorafhandling i matematik her på Aalborg Universitet. Jeg har kendt Martin i mange år og har lidt på afstand prøvet at følge med i hvordan han sammen med bl.a. Lisbeth Fajstrup, der også er fra Institut for matematiske flag – undskyld, Institut for matematiske fag –og udenbys kolleger været motiveret af bestemte problemer inden for parallel programmering med gensidig udelukkelse til at udvikle et nyt område af algebraisk topologi, hvor man betragter homotopier mellem (klasser af) orienterede stier i planer. Stier svarer til “spor” i en programudførelse, og dimensionerne af det rum man betragter, svarer til antallet af parallelle komponenter. Orienteringen kommer ind i billedet på grund af den temporale ordning af programskridt.

Hvis man tror, at det kun er “diskret matematik” (som vel ofte mest forstås som al den matematik, der ikke er “kontinuert matematik”) som har forbindelser til datalogi, tager man fejl. Martin hævder selv at hans resultater ikke er særligt dybe, men her er det vist hans beskedenhed, der sætter ind.

Jeg fik dog ikke hele forsvaret med, for jeg var kommet af sted til NOVI uden mit adgangskort – døren lukker kl. 16, og jeg ville nødig smækkes ude. Dog har jeg en særdeles velbegrundet formodning om at Martin får sin doktorgrad og tør derfor godt ønske ham tillykke!

flattr this!

Noget om at bestå Turing-testen

eugene

Jeg har flere gange tidligere skrevet om Turing-testen, første gang i januar 2012 og siden igen i august samme år.

I dag kan jeg læse i The Independent, at der skulle være et program, der har bestået Turing-testen. Programmet er en såkaldt bot, og det er tilgængeligt online, så alle kan prøve at have en dialog med det. Programmet er en simulering af en 13-årig dreng fra Odessa i Ukraine ved navn Eugene Goostman. I en test foretaget af Royal Society skulle hele 33% af forsøgsdeltagerne have ment at de førte en dialog med et menneske.

Nu må jeg så hellere indrømme at jeg selv ikke er nær så imponeret – det virker som om programmet bare konsekvent snakker udenom. Men bevares, sådan er der jo så mange 13-årige der gør.

Her er den samtale, jeg selv prøvede at føre.

Tell me about your family.

I have a great number of relatives. Parents, elder broz and aunt Sonya in America. I visit my aunt every Summer and she’s always complaining that my visits are more destructive than floods and typhoons.

Where does Sonya live?

If you mean my aunt Sonya, she is doing well, and sends the best wishes to you.

No no. I mean: Whereabouts in the US does your aunt Sonya live?

If you mean my aunt Sonya, she is doing well, and sends the best wishes to you.

Og allerede efter tre spørgsmål er det klart for mig, at dette ikke kan være et menneske. Jeg prøvede at spørge lidt videre til den russiske besættelse af det østlige Ukraine, og jeg prøvede at få noget at vide om “Eugene Goostmans” hjem – men begge gange blev det helt klart fra goddag-mand-økseskaft-svarene at “Eugene Goostman” ikke er et menneske.

Den britiske datalog Kevin Warwick er citeret for dette:

“In the field of Artificial Intelligence there is no more iconic and controversial milestone than the Turing Test, when a computer convinces a sufficient number of interrogators into believing that it is not a machine but rather is a human,” he said. “Having a computer that can trick a human into thinking that someone, or even something, is a person we trust is a wake-up call to cybercrime.

Selv ville jeg hævde noget andet og mindre dommedagsklingende – det er ikke det ukrainske program, der er godt. Det er derimod mennesker, der er for godtroende. De kluntede svar og klodsede formuleringer i “Eugene Goostman” ligner lidt dem man kan finde i de til tider automatisk genererede e-mails, der forsøger sig med phishing. Ligegyldigt hvor åbenlyst tåbelige den slags beskeder har det med at være, er der stadig mennesker der ukritisk hopper på dem. Hvis Turing-testen skal have en berettigelse, skal man måske også tænke på hvilke mennesker, der deltager i testen som forsøgspersoner.

flattr this!

P=NP, siger Knuth

hex

Da jeg studerede, var der et spil, vi ofte spillede, nemlig Hex. Spillet blev opfundet af Piet Hein tilbage i 1942 og spilles af to mennesker (vi kan jo kalde dem rød og blå) med blyant og ovenstående spillebræt på et stykke papir. Hver spiller har to modstående sider af rhomben.

De to spillere skiftes til at afkrydse et felt. Målet er at blive den første, der kan lave en ubrudt følge af krydser der forbinder de to modstående sider.

I 1949 viste John Nash (ham fra A Beautiful Mind) at der er vindende strategi i Hex men han viste ikke hvordan sådan en strategi ser ud! Man ved hvordan vindende strategier ser ud op til 9 gange 9 felter, derefter ved man ikke noget endnu. Hvis man skal se positivt på det, betyder det at det stadig bør være sjovt at spille Hex.

Men den slags ikke-konstruktive argumenter bør få én til at tænke. Det er underligt at vide at der findes et bestemt objekt (som her er en strategi) men ikke at vide hvordan det ser ud.

Der er et interessant interview med den legendariske datalog og matematiker Donald Knuth hvor han bruger Hex som del af en begrundelse for at tro at \mathrm{P=NP}-formodningen har et positivt svar, dvs. at \mathrm{P=NP}. Det er der ellers ikke så mange, der mener. Knuth er til gengæld tilbøjelig til at mene at der er et ikke-konstruktivt bevis for sætningen.

As you say, I’ve come to believe that \mathrm{P=NP}, namely that there does exist an integer M and an algorithm \mathcal{A} that will solve every n-bit problem belonging to the class \mathrm{NP} in n^M elementary steps.

Some of my reasoning is admittedly naïve: It’s hard to believe that \mathrm{P \neq NP} and that so many brilliant people have failed to discover why. On the other hand if you imagine a number M that’s finite but incredibly large—like say the number 10 3 discussed in my paper on “coping with finiteness”—then there’s a humongous number of possible algorithms that do n^M bitwise or addition or shift operations on n given bits, and it’s really hard to believe that all of those algorithms fail.

My main point, however, is that I don’t believe that the equality \mathrm{P=NP} will turn out to be helpful even if it is proved, because such a proof will almost surely be nonconstructive. Although I think M probably exists, I also think human beings will never know such a value. I even suspect that nobody will even know an upper bound on M.

Er det så et godt argument at sige at “Jeg kan ikke forestille mig at det ikke er tilfældet”? Jeg ved det ikke rigtig, men det er interessant og (synes jeg) også lidt skræmmende hvis \mathrm{P=NP} og vi ikke kan få glæde af den viden.

flattr this!

P=NP og Hilberts basissætning

pudlak

Et af de emner, som mange inden for datalogi og matematik ynder at tale om er \mathrm{P=NP}-problemet. Problemet er underligt fristende og frustrerende; vi kender problemet godt nok til at kunne formulere det præcist, men løsningen kender vi ikke. Det er lidt som det pæretræ, der står et sted i min svigerfars have; fem meter oppe sidder der hvert år en masse flotte pærer. Men stammen er helt lige og med få grene.

Jeg kan ikke lade være med at tænke på hvordan andre åbne problemer i matematik først er blevet løst efter at der er kommet ny og overraskende indsigt. Bagefter kom standardpensum og lærebøgerne. Et af de helt store problemer i 1800-tallets matematik var det, vi nu kender som Hilberts basissætning i algebra. Er det tilfældet at hvis R er en Noethersk ring, da er ethvert ideal i polynomiumsringen R[x_1,\ldots,x_n] endeligt frembragt? Hermed menes der at der skal findes der en endelig mængde \{k_1,\ldots,k_m\} af elementer i idealet M, således at ethvert element i det kan skrives som en linearkombination af dem.

En Noethersk ring R er en ring, hvor enhver ikke-tom familie af idealer fra R har et maksimalt element. Legemer (men såmænd også bare den sædvanlige ring over  \mathbb{Z}) er eksempler på Noetherske ringe.

Vi har med andre ord at gøre med begreber, som man i dag lærer i algebrakurset på første del af en matematikuddannelse. Så dette problem er inden for rækkevidde på samme måde som \mathrm{P=NP}-problemet er det for datalogistuderende.

Hilberts bevis var et snedigt induktionsbevis – og ikke-konstruktivt. Det er bestemt ikke en overdrivelse at sige, at ikke alle var glade for at dét var tilfældet. Også beviset er i dag inden for rækkevidde af en studerende på første del af en matematikuddannelse. (Senere er der kommet konstruktive beviser for udgaver af basissætningen.)

Klaus Frovin Jørgensen har en gennemgang af hvad Hilberts basissætning førte med sig. På nogle måder er konstruktiv matematik og alt det, den har ført med sig, en reaktion mod Hilberts ikke-konstruktive tilgang. Jeg tror selv at et bevis for \mathrm{P=NP}-problemet vil føre til et lignende jordskred og at beviset for at \mathrm{P=NP} (eller for at \mathrm{P \neq NP}) en dag bliver del af pensum på datalogiuddannelsen. Om jeg så selv når at komme til at undervise i det, er en helt anden snak.

flattr this!

At genopdage hvad man selv har skrevet

2014-05-08 13.49.32

En af de underlige oplevelser, man får, når man er universitetslærer og i en periode ikke har tid til at fordybe sig i sin forskning, er gensynet med en gammel, ufærdig tekst. I dag har jeg for første gang i månedsvis en hel dag til min rådighed til at rydde op i et ufærdigt manuskript, der blev til i vinters. Jeg prøver at forstå de halvfærdige beviser og de definitioner, jeg lavede mig. Og det tager forbløffende lang tid at genfinde meningen i det, jeg skrev for 4 måneder siden.  Nogle gange dukker der et svar op på en tvivl, jeg efter manuskriptet at dømme må have haft dengang. Andre gange tager jeg mig selv i at få lyst til at skrive det hele om. Hvor var det dog knudret! Hvis jeg bruger den røde kuglepen flittigt, når jeg retter opgaver, bruger jeg den faktisk lige så flittigt, når jeg genser mine egne gamle manuskripter. Jeg håber at få teksten færdig til en deadline, for jeg har ikke lyst til at slippe den igen nu.

Noget, der også går op for mig (der er meget, jeg genopdager lige nu!) er at gensynet med en gammel tekst er en god mulighed for at lave peer review på sit eget værk. Jeg tror at ideen kan bruges systematisk i projektarbejde – vi skal bede de studerende om at skrive meget i starten, lægge arbejdsbladene væk og gå videre til noget andet for en stund inden de vender tilbage til arbejdsbladene.

flattr this!

Forskningens Døgn 2014

2014-04-24 13.11.32
Bag mig: Klaus Høeck, Anne-Marie Mai, FInn Kjærsdam og Holger Elmo Mikkelsen (rektor fra VIA).

2014-04-24 15.35.19

2014-04-24 14.10.31

2014-04-24 13.10.57  2014-04-24 12.52.02 2014-04-24 12.51.52

2014-04-24 12.57.16

I dag deltog jeg i åbningen af Forskningens Døgn 2014 på Nordkraft. I år var det blevet Aalborg, der skulle lægge lokaler til. Ligesom til AAUs 40-års jubilæum var der kongeligt besøg, denne gang af kronprinsesse Mary. Og ligesom hendes mand kom for sent til jubilæumsfesten, således sørgede kongehuset også denne gang for at vi kunne starte med 20 minutters forsinkelse. Ulla Essendrop, der som de fleste andre tv-personligheder ikke er så høj som man skulle tro, var konferencier.

Mit eget bidrag var et science slam, som jeg vil genopføre i morgen, når den egentlige Science Slam-konkurrence finder sted på Studenterhuset. Mette Marie (der ikke er den norske kronprinsesse) bad mig huske at nikke i kronprinsessens retning, når nu jeg ikke kunne indpasse en kongelig højhed i teksten, men det tror jeg nu jeg glemte. Så vidt jeg kunne fornemme, blev mit indslag vel modtaget alligevel.

Forskningens Døgn tager heldigvis fat på formidling af alle slags forskning. Kronprinsessen holdt en tale for at begrunde valget af modtageren af Forskningskommunikationsprisen, som er Anne-Marie Mai, der er professor i litteraturhistorie på SDU. Hun fik prisen for sit arbejde med formidling af forskning i dansk litteratur. Selv husker jeg hende for bogen med hendes samtaler med Michael Strunge. Det gik op for mig at Klaus Høeck (ham med In Nomine) også var der i dag – hvorfor var han nu det? Nåh jo, han er jo gift med Anne-Marie Mai!

Der var også nogle interessante præsentationer af lokale initiativer. Først fortalte Jonas Dyhr Johansen, der fortalte om sit firma Sky-Watch som udvikler droner til fornuftige civile formål som f.eks. sporing af ofre for naturkatastrofer og overvågning af truede dyrearter. Derefter gav Benedict Kjærgaard fra Aalborg Universitetshospital et kort og faktisk også meget gribende foredrag om hvordan en transportabel hjerte-lunge-maskine kan genoplive underafkølede druknede.

Bagefter åbnede standene, og kronprinsessen blev vist rundt på nogle af dem, mens vi andre kunne få lov til at se resten. Der var god mulighed for at tale med udvalgte kolleger (endnu en mindelse om 40_års-jubilæet). Jeg talte bl.a. med en professor, der skriver en fantasy-trilogi der foregår på Ærø og med en fraskilt konsulent, der har oparbejdet talrige erfaringer med netdating. Og til allersidst, på vej mod udgangen, kom Mary herself hen og hilste på mig. Hun sagde at mit science slam havde været godt og humoristisk. Jeg prøvede at smile kongeligt.

Desværre må jeg efterhånden være lidt miskrediteret som modstander af monarkiet efter to gange at have deltaget i arrangementer, hvor jeg skulle rejse mig for en royal og nu endda har trykket en af dem i hånden og fået ros af selvsamme. (Nå, i næste uge er det 1. maj.)

flattr this!

Børn af Brouwer og Prior

Luitzen_Egbertus_Jan_Brouwer
L.E.J. Brouwer
prior
Arthur N. Prior

Det er værd at tænke over at to af de vigtige erkendelser i datalogi kommer fra filosofiens verden. Også jeg er blevet grundlæggende påvirket af disse erkendelser.

I mange år var temporallogik, dvs. studiet af de logiske egenskaber ved udsagn om tid, et rent filosofisk område. Det hele begyndte med Aristoteles. Senere gav den newzealandske logiker Arthur N. Prior (hans navn er et fantastisk ordspil – det er i sig selv en temporal modalitet!) præcise matematiske formuleringer af temporallogikkens grundlag. Temporallogik som en tilgang til beskrivelse af programegenskaber skyldes israelske og amerikanske matematikere med nu afdøde Amir Pnueli som en af de helt centrale skikkelser. Temporallogik er et område inden for modallogik, og også modallogik som sådan har fået vigtige anvendelser i datalogi. Mange af de gamle diskussioner om hvorvidt modallogik og temporallogik overhovedet giver mening at beskæftige sig med er blevet lagt døde af de konkrete anvendelser.

Også intuitionisme har været et kontroversielt emne inden for matematik. L.E.J. Brouwers konstruktions-orienterede tilgang til matematik var begrundet i hans filosofiske overvejelser om matematikkens grundlag. Men inden for de seneste 30 år er intuitionistisk typeteori blevet vigtig inden for datalogi. Bindeleddet er den svenske logiker og matematiker Per Martin-Löf. I dag finder findes interaktive bevistjekkere som Isabelle og Coq stor anvendelse både til formalisering af eksisterende matematik og til kontrol af nye resultater. Især inden for programmeringssprogsteori er dette barnebarn af Brouwer blevet et vigtigt redskab. Tidligere har jeg skrevet om hvordan den fransk-canadiske datalog Georges Gonthier har formaliseret store resultater i grafteori ved brug af netop Coq. I kraft af alle disse praktiske anvendelser er mange af de gamle diskussioner om berettigelsen af konstruktiv matematik reelt blevet lagt døde af konkrete anvendelser.

Det, der er sket i begge tilfælde, er samtidig at det er det  matematiske begrebsapparat, der er blevet til, som har vist sig at udgøre berettigelse, ikke den underliggende filosofiske motivation. Samtidig har der i datalogi været forskere med baggrund inden for matematik og filosofisk logik, som har kunnet se forbindelsen – folk som Dana Scott, Robin Milner og Per Martin-Löf har udgjort dette vigtige bindeled.

flattr this!

Hjemme igen

Fotografi den 14-04-14 kl. 19.13

Dagen i dag bød på en lige lovlig spændende hjemrejse fra Grenoble med en solid forsinkelse på det første af de tre hop, turen fra Lyon til Zürich. Det var med nød og næppe, jeg nåede videre til København. Her fik jeg ultrakort hilst på selveste Peter Laugesen (gad vide om han kan huske mig? For snart en del år siden inviterede jeg ham til Aalborg til flere lyrikarrangementer), og så sad jeg i flyet til Aalborg lufthavn, der jo faktisk ligger i Nørresundby.

Det blev en hastig, men også udbytterig tur hvor jeg fik lavet aftaler med flere af mine kolleger derude om at komme og besøge mig i Aalborg senere i år. Det glæder jeg mig til; selv om det kan være spændende at rejse ud og få inspiration til forskningen, er det også rart engang imellem at kunne lade verden komme til mig.

Der var tid nok på alle flyvningerne til at få læst Norwegian Wood af Haruki Murakami – en gave fra min hustru og en bog, jeg har hørt meget godt om. Jeg giver kritikerne ret:  Norwegian Wood er en god roman, som hermed er anbefalet.

flattr this!