Algoritmer, algoritmer
Er du av dem som tror at algoritmer bare er en utspekulert metode som sosiale nettverk og andre nettmanipulatorer bruker for å fore brukerne sine med «tilpasset» reklame og annet lugubert innhold? Det er naturlig, ut fra hvordan algoritmer omtales i mediene (og da tenker jeg først og fremst på de tradisjonelle mediene, aviser og kringkasting).
Men algoritmer er mye mer spennende enn det! En algoritme kan defineres som en nøyaktig, stegvis fremgangsmåte for å løse en presist beskrevet oppgave. Algoritmer er i dag nært forbundet med dataprogrammering — datamaskiner er nettopp avhengige av å få slike arbeidsbeskrivelser for å gjøre det de skal. Men mange av de algoritmene som stadig gjenbrukes i dataprogrammer dag, er faktisk flere hundre år gamle.
Oppgavene, eller «problemene» som skal løses, kan være helt konkrete og situasjonsbestemte, slik som da matematikeren Leonhard Euler prøvde å finne en rute som krysset alle de sju broene i Königsberg én gang hver (et problem som Euler istedenfor beviste ikke er løsbart). Men de algoritmene som brukes i databehandling er ikke bundet til et konkret problem, men en bestemt type problemer – for eksempel å sortere et datasett, uansett hvor mange elementer settet består av og hvilke konkrete verdier disse elementene har.
En veldig viktig egenskap ved databehandlings-algoritmer er effektivitet. Med store datamengder er dette helt grunnleggende. Forskjellen mellom en helt korrekt men ineffektiv algoritme, og en som løser samme problem på en effektiv måte, kan være flere års «tenketid» for datamaskinene. Effektivitetsberegning for algoritmer er blitt en egen vitenskap, kompleksitetsteori.
Mens jeg skriver dette kommer meldingen om at verdens fremste matematikkpris, Abelprisen for 2021 er tildelt László Lovász og Avi Wigderson for deres arbeid med algoritmer og kompleksitetsteori. Fantastisk – vi gratulerer!
Algoritmeoppgaver kan brukes som hjernetrim – så hvis du er lei av kryssord og sudoku, kan du prøve deg på denne lille oppgaven, som verken krever datamaskin eller programmeringsspråk for å løses: I det ikke-eksisterende brettspillet «De syv dødssyndene» brukes det en syvsidet terning (nei, det er selvfølgelig ikke mulig å lage en slik terning fysisk, men når vi leker med algoritmer kan vi operere med slike «umulige» objekter). Men dessverre har vi mistet denne terningen! Vi får imidlertid låne den femsidete terningen som Dagbladet bruker til filmanmeldelser. Nå trenger vi en algoritme for å kunne bruke Dagblad-terningen (som gir et tilfeldig tall mellom én og fem på hvert kast) til å gi oss et tilfeldig tall mellom én og syv i stedet. Det er selvfølgelig helt avgjørende at algoritmen gir like stor sannsynlighet for hvert av tallene. (I parentes bemerket er dette eksempelet en forenklet og konkretisert versjon av en mer generell algoritme, hvor man bruker en x-sidet terning til å simulere en y-sidet.) Hvordan ville du løse det?
Hvis du vil, kan du sende inn løsningsforslag – eller spørsmål. Lykke til!