Föreläsning 20 - Repetition inför tentan

Vad var datalogi igen?

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.

Nedan är en skiss med de övergripande begreppen i kursen och hur de hänger ihop. datalogibegrepp

Datastrukturer

Datastrukturer används för att strukturera och abstrahera data. Olika datastrukturer används till olika saker. I kursen har följande datastrukturer i tur och ordning tagits upp:

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 i tur och ordning tagits upp:

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.

Tänk på vilken komplexitet en viss algoritm har. Måste du t ex ta hänsyn till att trädet/hashtabellen/listan/kön/vektorn måste byggas upp innan du kan börja?

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.

I verkliga livet använder vi människor abstraktion hela tiden; vi lär oss begrepp och associerar till samma saker då begreppen utnyttjas och slipper således hela tiden beskriva detaljer. En köpare/användare säger mycket troligare "snygg bil" än "snygg pryl med kaross och innanmäte med motor och läcker inredning där kaross är något som..., med motor menar jag...". Begreppet bil är så väletablerat att detaljerna inte behövs.

Det finns uppenbara fördelar med abstraktion:

Med ovanstående i åtanke finns det inga nackdelar med abstraktion!

^ Upp till kurssidan.


Sidansvarig: <vahid@nada.kth.se>
Senast ändrad 30 september 2003
Tekniskt stöd: <webmaster@nada.kth.se>