Den effektive algoritme
Selv med superhurtige processorer ville nutidens computere virke langsomme, hvis de ikke brugte effektive algoritmer. Begrebet 'algoritme' er opkaldt efter en arabisk matematiker, der for 1200 år siden bedrev algebra og astronomi i Visdommens Hus.
algoritmens fader al-khwarizmi matematik

Den arabiske matematiker Al-Khwarizmi kunne næppe have forestillet sig, hvordan hans ideer ville blive et nøglebegreb i moderne beregningskunst. (Foto: Shutterstock)

»Der er en ensomhed i det guld.
Nattens måne
er ikke den måne som Adam så.
De mange århundreders
nattevågen
har fyldt hende
med gammel sorg.
Se på hende.
Hun er dit spejl.«

J.L. Borges, 'Månen - for Marma Kodama' i Fireogtyve Samtaler, oversat af Peter Poulsen

Historien kort
  • Vi tænker ikke over det, men algoritmer er en fast bestanddel af vores liv.
  • Faktisk har algoritmen 1200 år på bagen – efter den arabiske matematiker Abu Al-Khwarizmi formulerede begrebet.
  • Softwaren i din telefon, din computer og satellitsystemer er styret af algoritmer, og uden dem var vi ilde stedt.

Månens blanke forside har lyst på nattehimlen, længe før der var mennesker til. Månens bagside havde intet menneskeligt øje set, før satellitter og sonder fløj over den og fotograferede den.

Første gang det skete var 7. oktober 1959, da den russiske sonde Luna 3 fik transmitteret et grynet billede af en del af Månens bagside tilbage til Jorden.

Månens bagside har ligesom forsiden kratere (faktisk i større antal). Særligt bemærkelsesværdige kratere på Månens bagside er ligesom på forsiden blevet navngivet efter store digtere eller videnskabsmænd.

Til tjeneste i Visdommens Hus

Et af kraterne på Månens bagside er blevet opkaldt efter den arabiske matematiker Al-Khwarizmi (cirka 780-850).

Abu Al-Khwarizmi levede og arbejdede i Visdommens Hus i Bagdad under Kaliffen Al-Mamun. Bagdad var dengang hovedstaden i et enormt rige, der strakte sig fra Middelhavet til det nuværende Indien.

Al-Khwarizmi var blandt andet beskæftiget med oversættelse af græske manuskripter, og han skrev selv om (hvad vi i dag kalder) algebra, astronomi og geometri.

Vi ved, at Al-Khwarizmi har set på Månen, beregnet tidspunkterne for dens op- og nedgange og dens faser.

Dijkstra's algoritme matematik tal

Figuren viser et beslutningsdiagram over Dijkstras algoritme, der bruges til at finde den korteste rute mellem to punkter. (Illustration: Poul G. Hjorth)


Det er ikke ofte, at matematikeres navne bliver til begreber i nutidssproget, men det er faktisk tilfældet her.

Når vi i dag taler om 'en algoritme' bruger vi Al-Khwarizmis navn om et begreb, som især i de seneste 50 år er blevet mere og mere relevant for den måde, vi tænker matematik på.

En algoritme er en opskrift på at løse et problem, og derfor er begrebet for eksempel centralt i programmering af computere.

Algoritmer i alt fra Krak til Google og Facebook

Mange elementære problemer i matematik drejer sig om direkte at udtrykke en ubekendt størrelse ved hjælp af kendte eller givne størrelser.

For eksempel kan man finde rødderne i en andengradsligning ved hjælpe af en enkel formel, hvis andengradsligningens koefficienter er givet.

En algoritme er noget mere. Det er en opskrift på løsningen af en opgave med instrukser om, hvor man begynder, og hvordan man skal gå videre til den næste instruks eller beslutning.

Når man følger en algoritme, løser man et komplekst problem, som ikke kan klares med en enkelt matematisk formel eller simpelt gentagne operationer.

I opgaver, hvor man har at gøre med datamængder, der er så store, at det tager alt for lang tid eller er fysisk umuligt at beregne alle muligheder direkte, har man brug for en måde at styre mod løsningen uden at gentage beregninger unødigt og uden at lave overflødige beregninger.

Vejvisere finder den korteste vej med en algoritme

gps navigation algoritme vejviser krak

Matematikeren Al-Khwarizmi har reddet mangen en bilferie. Uden algoritmer til at hjælpe GPS-systemet på vej kunne vi nemt havne på herrens mark. (Foto: Shutterstock)

Når for eksempel Krak eller GPS-vejvisere på meget kort tid finder den korteste vej fra by A til by B blandt en myriade af muligheder, foregår der mere end blot at udregne samtlige muligheder op og vælge den korteste vej blandt disse.

Det ville være alt for tids- og lagerkrævende selv for moderne computere. Sorteringen blandt mulighederne følger en meget effektiv algoritme, der finder de korteste veje i et netværk (her en graf med afstande).

Også den proces, hvormed søgemaskinen Google finder relevante hjemmesider, er baseret på en algoritme, der sorterer og rangerer hjemmesider meget hurtigt. Ligesom Facebooks venneforslag, og hvad der popper op i din nyhedsstrøm, er det. 

Uden algoritmer ville computere virke langsomme

Styrken ved moderne beregninger har to ingredienser: 

Den første af disse, elektronikken, har gjort store fremskridt, lige siden computere begyndte at blive bygget. Mikroprocessorerne er blevet mindre og mindre og kraftigere og kraftigere.

Der er tale om en fordobling af processorstyrken cirka hver 18. måned (den såkaldte Moores lov).

ForskerZonen

Denne artikel er en del af ForskerZonen, som er stedet, hvor forskerne selv kommer direkte til orde. Her skriver de om deres forskning og forskningsfelt, bringer relevant viden ind i den offentlige debat og formidler til et bredt publikum.

ForskerZonen er støttet af Lundbeckfonden.

Men computerne i dag ville virke langsomme, hvis der ikke samtidig med udviklingen i processorkraften var sket en støt forbedring i de algoritmer, som programmerne benytter sig af.

Den 'algoritmiske styrke' har, takket være matematikere, der er fulgt i Al-Khwarizmis fodspor, udviklet sig lige så kraftigt som processorstyrken.

Effektivt matematisk software er den hemmelige, den skjulte del af computerteknologien.

Tilsammen har de to teknologier, elektronikken og matematikken, gjort dagens computere til små beregningsvidundere, som man næppe havde kunnet forestille sig, hvis man i året 815 havde siddet i en gårdhave i Bagdad, set op mod fuldmånens blidt lysende skive og undret sig over, hvordan bagsiden mon så ud. Månens bagside er skjult. Men den var der.