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.