Datalogi är läran om datastrukturer och algoritmer, d v s hur man kan
organisera och hålla reda på data samt hur dessa data kan utnyttjas
enligt en steg-för-steg-beskrivning för att (effektivt) lösa
något problem.
Datastrukturer
Datastrukturer används för att strukturera och abstrahera data. Olika
datastrukturer används till olika saker. I kursen har följande
datastrukturer tagits upp:
Textobjekt
Små objekt för egendefinierade saker (t ex noder av olika slag)
Stackar
Köer
Länkade listor
Allmänna träd
Binära träd
Hashtabeller
Booleska hashtabeller
Prioritetsköer
Trappor (Heaps)
Algoritmer
Algoritmer används för att lösa problem. En algoritm utnyttjar en
eller flera olika typer av datastrukturer och det är rätt datastruktur
i kombination med rätt algoritm som gör algoritmen effektiv.
Algoritmer jämförs genom antalet operationer som måste utföras givet
ett antal element eller mer grovt med komplexitetsberäkningar, där
komplexiteten anges med en funktion av viss storleksordning, Ordo, O(f(N)).
I kursen har följande algoritmer tagits upp:
Linjärsökning
Binärsökning
Rekursion
Problemträdssökning
Breddenförstsökning
Djupetförstsökning
Listrekursion
Trädrekursion
Binärträdssökning
Urvalssortering
Insättningssortering
Räknesortering (Distribution count)
Damernaförstsortering
Kvicksortering (Quicksort)
Samsortering (Mergesort)
Positionssortering (Radix sort)
Hashning
Rättstavning
Bloomfilter
Bästaförstsökning
Heapsort
KMP-automat för textsökning
Rekursiv medåkning för syntaxkontroll
Följdlängdskodning (RLE)
Huffmankodning
Lempel-Ziv-kodning (LZ)
Dijkstras kortaste väg
Prims billigaste spännande träd
Kruskals billigaste spännande skog
Det finns också en mängd namnlösa småalgoritmer som ingår i de
ovanstående. Givetvis är det viktigt att förstå hur ett binärt träd
byggs upp innan man kan söka i det, hur en hashtabell eller en boolesk
hashtabell fylls i innan sökning kan ske o s v.
Abstraktion
Abstraktion innebär att dölja detaljer. En användare behöver inte
känna till detaljer för att kunna utnyttja en datastruktur eller
algoritm och en konstruktör behöver inte veta vad informationen kommer
ifrån eller vad resultaten ska utnyttjas till. Några fördelar med abstraktion:
Gränssnittet säger allt. Användaren och konstruktören kommer
överens om vad som ska kunna göras och vilka data som ska utnyttjas (d
v s ett gränssnitt). Allt annat är detaljer som bara användaren
alternativt bara konstruktören behöver bry sig om.
Användaren kan inte missbruka detaljinformation och därmed inte
misstolka konstruktörens avsikter.
Konstruktören kan anpassa den abstrakta datatypen/algoritmen till
olika användare utan förstöra en bra konstruktion.
Konstruktören kan förbättra konstruktionen utan att användarens
användning behöver ändras.
