This is a draft of a description of the field algorithms I was asked to do for the Swedish Research Council (Vetenskapsrådet). The section structure is given. All kinds of feedback (in particular from native Swedish speakers about my clunky grammar) are welcome.

Beskrivning av forskning inom ämnet

Studiet av algoritmer är en central del av datavetenskapen som behandlar konstruktion och analys av metoder för resursmedveten beräkning. I föreliggande beskrivning omfattar ämnet även stora delar av beräkningsteorin, inklusive teorin för beräkningskomplexitet.

De mest väletablerade delarna av ämnet, konstruktion och analys av algoritmer samt beräkningskomplexitet är av matematisk natur och har starka kopplingar till olika matematiska discipliner som grafteori, kombinatorik, logik och sannolikhetsteori. Det huvudsakliga målet är att systematiskt studera beräkning med syftet att etablera allmängiltiga utsagor om grundläggande beräkningsproblem i olika beräkningsmodeller. Bidraget till praktiska beräkningar är i form av den allmänna förståelsen för beräkn­ingsproblem samt utvecklandet av nya metoder för att lösa dessa.

Mer tillämpad forskning inom ämnet fokuserar på konstruktion och analys av algoritmer från områden både inom och utanför datavetenskapen, t ex biologi, ekonomi, signalbehandling, och WWW. Forskningen kring dessa algoritmer innehåller även empiriska studier av deras beteende, ingenjörsaspekter av deras utveckling och återkoppling till modelleringsaspekter i användningsområdet. Med ökad algoritmisering av i princip alla datadrivna vetenskaper är potentialen för synergier med andra discipliner enorm.

Alla delar av algoritmisk forskning påverkas av nya beräknings- och datamodeller som motiveras av aktuella utvecklingar inom informationteknologin, t ex massiva datamängder, parallella och distribuerade arkitekturer, strömmad data, energieffektiva beräkningar, säkerhets- och integritetsaspekter, och experimentella teknologier som kvantdatorer.

Styrkor och svagheter

Trots att datavetenskapen bara är drygt 50 år gammal, så har många algoritmiska resultat spridits till andra vetenskaper och undervisas i grundläggande kurser. Områdets styrka är ett starkt matematisk fundament, en tradition för att betrakta problem på många abstraktionsnivåer och teknologisk lyhördhet och samutveckling med informationsteknologin. Internationellt finns det ett mycket starkt utbyte både med andra vetenskaper och programvaruindustrin.

Vill man peka på områdets svagheter, så skapar en del av teoribildningen – i likhet med annan grundforskning och tillämpad matematik – ibland rent internt motiverade frågeställningar som visar sig vara ofruktbara. Vissa resultat är ej direkt applicerbara på de beräkningsproblem som uppstår i olika tillämpningar. En annan utmaning är den starka ställningen som analysen av algoritmers värstafallsbeteende har – denna dominerar områdets kvalitetskriterier på bekostnad av indatamodeller som är svårare att definiera stringent, men som i några tillämpningar vore mera relevanta. Behovet av matematisk stringens och teknologisk flexibilitet leder också till att profilen för kandidater till forskning i algoritmik är attraktiv för många andra riktningar både inom och utanför akademin, vilket skapar ett visst rekryteringsproblem.

Specifikt svenska svagheter i området behandlas nedan.

Trender, utvecklingstendenser och utvecklingspotential

Den grundläggande forskningen inom teoretisk datavetenskap, såsom algoritmteori, är bland de äldsta ämnen i datavetenskapen och har mognats till en matematisk disciplin med rik teoribildning och starka resultat. Det traditionella syftet är att skapa, analysera, och resonera kring algoritmer för problem på diskreta strukturer med avseende på stringenta värstafallsgarantier för algoritmers asymptotiska resursförbrukning och lösningskvalitet som funktion av problemstorleken. Man kan idag påstå att de allra flesta naturliga beräkningsproblemen är, grovt sett, klassificerade med avseende på beräknings­komplexitet. Pågående forskning har flyttat fokus till mer specialiserade problem och sofistikerade frågeställningar, som ofta är inomvetenskapligt motiverade.

Algoritmisering och datorisering

Algoritmteorin utmanas ständigt av nya beräkningsmodeller motiverad av aktuell informationsteknologi och nya frågeställningar från andra vetenskaper och samhället. Ett numera klassiskt exempel är beräkningsbiologin, som idag är ett separat forskningsområde med egna utbildningar, publikationsfora och anslag, men som fortfarande utgör en rik källa till algoritmiska frågeställningar; algoritmik bidrar både till effektiv problemlösning t. ex. av olika proteinviknings- eller sekventieringsproblem, men också till modellering. Till exempel är synen på evolution under den algoritmiska linsen att DNA är en algoritm som exekveras av proteiner. Härvid betonas fenomenets process- och informationsaspekter, vilket supplerar t ex elektrokemiska eller zoologiska perspektiv på evolution.

Ett exempel på en teknologisk påverkan är den pågående utvecklingen inom minnesteknologi och sensorer, där mängden av data som insamlas och behöver analyseras överstiger utvecklingen i beräkningskraft. Man kan säga att moderna datorer bliver allt långsammare i relation till sina arbetsuppgifter. Behovet för och effekten av algoritmer för analys av massiva datamängder är nu för tiden enorm, inte bara i vetenskapliga tillämpningar, men också i samhället, där algoritmer används till att reglera grundläggande demokratiska mekanismer som tillgång till information. Detta skapar stort behov av stringenta analyser och nya lösningar.

Det algoritmiska perspektivet fortsätter att ha konceptuell påverkan på traditionellt icke-datalogiska discipliner, när dessa utvecklar modeller som tar hänsyn till processers effektivitet och resursförbrukning. Ett exempel är statsvetenskap och ekonomi, där algoritmisk spelteori, algoritmisk mekanismkonstruktion och computational social choice är aktuella ämnen som uppfattar ekonomins individbegrepp som resursbegränsade agenter vars val inte bara är individuellt optimala men även skall kunna fattas av en effektiv process. Dylika utvecklingar har åtnjutit stor internationell uppmärksamhet och har rik potential för tvärvetenskaplig korsbefruktning.

Några trender

Några konkreta aktuella trender inom algoritmforskning med stor internationell uppmärksamhet är:

• Nya tekniker och modeller för konstruktion och analys av algoritmer utöver deterministisk och sekventiell beräkning: randomiserad, algebraisk, approximativ, exakt, on-line, strömmande, energisnål, parallell, fördelad, olika minnesarkiteturer, olika programspråksparadigm såsom constraint eller map–reduce, alternativa beräkningsmodeller som kvantdatorer.
• Tillämpad algoritmik inom andra delar av datavetenskapen och relaterade tekniska vetenskaper: artificiell intelligens, programspråksteori, databaser, datorsyn och -grafik, robotik, sociala nätverk, sensornätverk, signalbehandling, etc.
  Ramverk för empirisk analys af algoritmer.
• Algoritmiska metoder och modeller i andra, icke-datalogiska discipliner: algoritmisk spelteori (ekonomi), sociala nätverk (sociologi), computational finance, datoriserade bevis i matematik, beräkningskemi, etc.
• Algoritmiska aspekter av datasäkerhet: främst kryptologi inklusive protokoll och beräkningskomplexitet, sekretess, integritet, säkerhet, autentisering, etc.
• Nya modeller och tekniker för beräknings- och kommunikationskomplexitet, avrandomisering, undre gränser, icke-appproximerbarhet, kvantitativ komplexitet av svåra problem, parameteriserad komplexitet och andra flervariata analysmått.
• Datastrukturer och algoritmer för analys och behandling av massiva datamängder, maskininläring, dataanalys och klassificering av ostrukturerad data.
  Konstruktion och analys av algebraiska, diskreta, och symboliska algoritmer för vetenskapliga beräkningar.
• Stringent analys av optimeringsalgoritmer in linjär och icke-linjär programmering under olika fördelningar av indata.
• Algoritmer och samhället: analys och metoder för informationssäkerhet, transparens.

Att stora delar av natur- och teknikvetenskaparna just nu upplevar en ökad algoritmisering av både tekniker och tankesätt betonar behovet för både algoritmisk kompetens på den icke-datalogiska sidan och ökad domänkunskap på den datalogiska sidan.

Ämnets ställning i Sverige och internationellt

Internationellt

Ur internationellt akademiskt perspektiv står forskning om algoritmer som ett centralt och stort ämne inom datavetenskap. Till exempel är Algorithms and Theory det datavetenskapliga ämnet med flest professorer vid amerikanska toppuniversitet. Även de teoretiska aspekterna är utomordentligt välfinansierade; till exempel grundades Simons Institute for the Theory of Computing vid UC Berkeley i år 2012 med ett anslag på 60 miljoner USD.

Algoritmiska kompetenser uppfattas numera som nödvändiga för många andra discipliner. Till exempel läser mer än var fjärde av samtliga studenter på Princeton University grundkursen i algoritmer och datastrukturer. Algoritmiskt tänkande är numera ett grundskoleämne i Storbritannien. På arbetsmarknaden är algoritmisk kompetens starkt efterfrågad av attraktiva programvaruföretag som Google.

I Sverige

Undervisning inom algoritmer och datastrukturer uppfattas som central datalogisk verksamhet på ett flertal universitet och högskolor och ingår i grundutbildningen på många datavetenskapliga och -tekniska program. Däremot är kurser i beräkningskomplexitet och -teori mer sällsynta och gruppen av svenska studenter utanför datavetenskapliga och -tekniska program i som uppnår algoritmisk kompetens är försumbar.

Nivån för svensk forskning inom ämnet är av internationell toppklass, men storleken av de flesta forskningsgrupperna i Sverige inom är under kritisk nivå.

Studiet av effektiva algoritmer har i Sverige inte utvecklats på ett så positivt som man kunde hoppats och en förväntad expansion har inte kommit till stånd. Kontrasten är extra oroande när man jämför med utlandet. Om området ej uppnår kritisk nivå kan detta ha negativa effekter på kunskapsnivån i landet. Det finns högst ett par starka grupper inom algoritmforskning och kompetensen är otillräcklig för att ens på ett adekvat sätt klara av behovet av avancerade kurser. Beräkningskomplexitet är än mer glest representerat. Denna negativa utveckling påverkar både den datavetenskapliga forskningen och andra datadrivna vetenskaper som upplever ett starkt behov av algoritmisk kompetens samt stora delar av innovativ programvaruproduktion, inte minst i relation till stora datamängder; aktuella modeord är Big Data och Cloud Computing).

Särskilda behov av forskningsinfrastruktur

Forskning inom algoritmer skapar inte självt något behov av forskningsinfrastruktur utöver de beräknings- och datalagringsresurser som krävs av ett eventuellt tillämpningsområde. Några utmaningar som datadrivna vetenskaper kommer att möta i samband med analys och förvaltning av data (skalbarhet, tillgänglighet, effektivitet, visualisering, integritet, tolkning, etc.) adresseras dock av just algoritmforskningen varigenom det kan uppstå behov för realistisk infrastruktur för validering och simulering av sådana lösningar.

(Ursprungligt publicerad 28 april 2013 på Sydsvenskan)

Det är en enorm skillnad mellan att shoppa, deklarera och sköta sina bankaffärer via nätet och att rösta i ett demokratiskt val. Det skriver Thore Husfeldt, professor i datalogi, och tar avstånd från vallagskommitténs förslag om e-röstning.
En majoritet i vallagskommittén har föreslagit att elektronisk röstning ska ske på försök i ett antal svenska kommuner under valet 2018. Allt annat på nätet sägs ju fungera utmärkt och smidigt, så varför ska vi inte e-rösta? Vi kan ju e-deklarera, e-handla och e-banka.

Och visst låter det bra.

Men det är en enorm skillnad mellan att shoppa, deklarera och sköta sina bankaffärer via nätet och att rösta i ett demokratiskt val.

Det är sällan vi dataloger avfärdar informationsteknologi. Men på den här punkten är vi överens:

Öppna och hemliga val är olämpliga föremål för digitalisering, oavsett om det skulle ske via internet eller med hjälp av maskiner i vallokalen.

Varför då? Det finns många anledningar, men låt mig redogöra för två:

Hemlighet och transparens.

Ta banktransaktioner – de går att sköta digitalt eftersom de inte är hemliga. Visst uppstår fel och problem, men både kund och bank får kvitton som de kan jämföra med kontoutdragen. Ingen behöver blint lita på att transaktionen lyckades, eftersom resultatet kan kontrolleras i efterhand. När ett fel uppstår, blir det upptäckt och kan åtgärdas.

Hemliga val är den diametrala motsatsen till banktransaktioner:

Väljaren får inget kvitto (annars vore valet inte fritt) och vallokalen får inget kvitto (annars vore valet inte anonymt).

Kritiken mot e-röstning är alltså domänspecifik och har ingenting med samhällets generella digitala kompetens att göra. Det finns gott om icke-hemliga val, till exempel när riksdagen voterar. Sådana val kan man digitalisera: små lampor i riksdagen visar varje ledamots röst och rösträkningen sker elektroniskt.

Den andra anledningen till att e-röstande är oacceptabelt i en demokrati är bristen på transparens.

Vi litar på nuvarande valsystem eftersom alla kan övertyga sig om att röstningen går rätt till. Hela processen är öppen och observeras av en rad individer: dig, mig, fru Svensson eller en valobservatör. Bland annat visar man upp den tomma valurnan på valmorgonen för att skydda processen mot i förväg påfyllda valurnor.

I många länder används rentav genomskinliga röstlådor – där kan man tala om bokstavlig transparens.

Men hur ser då den digitala motsvarigheten till denna kontroll ut?

Den är betydligt mer komplicerad, i själva verket omöjlig.

Förutsatt att e-röstsystemet använder öppen källkod kan i alla fall den teknologiska eliten, det vill säga ett mycket litet fåtal, läsa koden och se att det står set votecount = 0 på rad 541 548.

Men programvara är ett komplext system. Om jag skulle granska vore jag tvungen att läsa hela programmet för att försäkra mig om att rad 541 548 faktiskt utförs vid rätt tidpunkt, och att ingen annan rad ändrar votecount på något klurigt sätt.

Det är i stort omöjligt att granska så mycket kod. Men även om det vore möjligt, så beror e-röstningssystemets funktion på en massa annat: kompilatorer, operativsystem, drivrutiner, ända ner till hårdvaran.

Det handlar om miljontals rader kod, skriven av tiotusen människor i ett dussin programspråk. Några rader är 40 år gamla, andra ändrades igår. Många innehåller fel på grund av slarv eller illvilja. Varje rad kan ändra votecount.

En armé av dataloger skulle behöva decennier för att granska allt. Men även om vi hade lyckats, skulle vi inte ha någon garanti för att det är det granskade systemet som faktiskt används på valdagen. Det kan ha bytts ut natten innan.

Det är alltså inte så att bara experter kan observera och kontrollera ett elektroniskt val – inte ens experter kan det.

Inga tekniska framsteg kan ändra på detta. Tvärtom blir informationsteknologin mer och mer komplex och den digitala valurnan mer och mer ogenomskinlig.

Så e-röstning är som allt annat på nätet. Det är varken hemligt eller genomskådligt.