Vad är en algoritm?

I sin mest allmänna mening är en algoritm en uppsättning detaljerade instruktioner som resulterar i ett förutsägbart sluttillstånd från en känd början. Algoritmer är dock bara så bra som instruktionerna som ges, och resultatet blir felaktigt om algoritmen inte är korrekt definierad.

Exempel på algoritmer

Ett vanligt exempel på en algoritm skulle vara instruktioner för att montera ett modellflygplan. Med tanke på startuppsättningen av ett antal markerade pjäser, kan man följa instruktionerna som ges för att resultera i ett förutsägbart sluttillstånd: det färdiga flygplanet. Tryckfel i instruktionerna, eller underlåtenhet att följa ett steg korrekt, kommer att resultera i en felaktig slutprodukt.

Ett datorprogram är ett annat genomgripande exempel. Varje datorprogram är helt enkelt en serie instruktioner, som kan variera i komplexitet, och är listade i en specifik ordning, utformade för att utföra en specifik uppgift. Matematik använder också algoritmer för att lösa ekvationer för hand, utan att använda en miniräknare. Ett sista exempel är den mänskliga hjärnan: de flesta föreställningar om den mänskliga hjärnan definierar allt beteende – från förvärvet av mat till att bli kär – som ett resultat av en komplex algoritm.

Klasser av algoritmer
Även om det inte finns någon allmänt accepterad uppdelning för de olika typerna av algoritmer, finns det vanliga klasser som algoritmer ofta är överens om att tillhöra. Bland dessa är:

Dynamiska programmeringsalgoritmer: Denna klass kommer ihåg äldre resultat och försöker använda detta för att påskynda processen att hitta nya resultat.

Giriga algoritmer: Giriga algoritmer försöker inte bara hitta en lösning, utan att hitta den idealiska lösningen på ett givet problem.

Brute Force-algoritmer: Brute Force-metoden börjar vid någon slumpmässig punkt och itererar genom alla möjligheter tills den hittar lösningen.

Randomiserade algoritmer: Denna klass inkluderar alla algoritmer som använder ett slumptal när som helst under processen.

Gren och bundna algoritmer: Gren och bundna algoritmer bildar ett träd av delproblem till det primära problemet, efter varje gren tills det antingen löses eller klumpas ihop med en annan gren.

Enkla rekursiva algoritmer: Denna typ går för en direkt lösning omedelbart och backar sedan för att hitta en enklare lösning.

Backtracking-algoritmer: Backtracking-algoritmer testar för en lösning; om en lösning hittas har algoritmen löst, om inte återkommer den en gång och testar igen, fortsätter tills en lösning hittas.

Dela och erövra algoritmer: En dividera och erövra algoritm liknar en gren och bunden algoritm, förutom att den använder backtracking-metoden för återkommande samtidigt som den delar upp ett problem i delproblem.

Seriella och parallella algoritmer
Utöver dessa allmänna klasser kan algoritmer också delas in i två primära grupper: seriella algoritmer, som är designade för seriell exekvering, där varje operation utförs i en linjär ordning; och parallella algoritmer, som används med datorer som kör parallella processorer, varvid ett antal operationer körs parallellt med varandra. Parallella algoritmer finns även i den naturliga världen vid till exempel genetisk mutation över en art.