Algoritmer

En algoritm är en väldefinerad uppsättning instruktioner som tar en eller flera ingångar och omvandlar dem till en eller flera utgångar. Den beskriver hur ett problem löses genom ett ändligt antal steg och ska avslutas för varje giltig indata. En algoritm kan följas manuellt eller implementeras i ett datorprogram.

Namnet algoritm härstammar från den persisk-arabiske matematikern al-Khwarizmi, vars arbete på 800-talet lade grunden för systematiska beräkningar. I datorvetenskap används termen för att beskriva exakta procedurer som kan översättas till mjukvara och köras av en dator eller beskrivas som en teoretisk abstrakt modell.

Algoritmer kan analyseras teoretiskt och mätas i tids- och minneskomplexitet. O-notation används för att beskriva hur beteendet förändras när indata växer. Beroende på egenskaper kan algoritmer vara deterministiska eller probabilistiska och följa olika designparadigm som delning- och erövringsmetoder, dynamisk programmering, girighet och backtracking.

Vanliga algoritmtyper inkluderar sortering (t.ex. quicksort, mergesort), sökning (binär sökning), grafalgoritmer (Dijkstra, Kruskal) och numeriska metoder (Euklides’ algoritm, Newton-Raphson). Kvalitet uppnås genom korrekthet, termination och effektivitet samt verifiering och testning.

Algoritmer används inom nästan alla områden av datoranvändning: mjukvaruutveckling, databaser, nätverk, bildbehandling, bioinformatik och optimering i näringsliv och forskning. De utgör grunden för automatisering och analys i moderna system.