DD1320 Tillämpad datalogi

Repetition inför tentan

Repetition

Detta är en repetitionsföreläsning. Den täcker inte hela kursen, men är en snabbgenomgång av det mesta. Kursen kan sägas bestå av en teori- och en praktikdel. Teoridelen täcks av föreläsningsanteckningar och kursbok. Praktikdelen av kursen går ut på att kunna tillämpa de "metoder" som beskrivits. Mängden tillämpningar är obegränsad. All tillämpning bör motiveras - man måste kunna tala om varför man valt att göra på ett visst sätt.

Datalogi

Vad var datalogi nu igen? Datalogi är läran om datastrukturer och algoritmer, dvs 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.

Ytterligare ett centralt begrepp i kursen är abstraktion.

Abstraktion

I Nationalencyklopedin står det så här:

I datalogi:

Ett exempel: en abstrakt ordlista kan tex defineras med ett gränssnitt bestående av två operationer: insert(x), exists(x). Vi har sett åtminstonde två implementationer av detta under kursen. I labb 3 använde ni ett binärt sökträd för att implementera en abstrakt ordlista. På föreläsning 6 om hashning talade vi om en ordlista implementerad med hjälp av ett bloomfilter.

Datastrukturer

Datastrukturer används för att lagra och använda data. I kursen har åtminstonde följande datastrukturer tagits upp:

Vi har definerat dessa datastrukturer abstrakt - vi är överens om hur de bör funka. Dessutom har vi implementerat dem. Sedan har vi använt dem på ett abstrakt vis - utan att behöva bry oss om hur de var implementerade. I kursen ingår både och - att förstå hur de funkar och använda dem på ett abstrakt plan.

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. I kursen har åtminstonde följande algoritmer 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 och så vidare. Hur man sätter in något i en datastruktur kan ju också beskrivas med en algoritm!

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)). Här är en på intet sätt uttömmande tabell över några algoritmer och deras tidskomplexitet. Kom ihåg att det inte räcker att kunna dessa utantill - man måste även kunna resonera om varför det är så, och när det inte gäller.

Komplexitet Algoritmer
O(n2) enkla sorteringsalgoritmer, quicksort
O(n*log(n)) mergesort, heapsort, quicksort
O(n) linjärsökning, räknesortering
O(log(n)) binärsökning, sökning och insättning i binärträd
O(1) insättning och sökning i hashtabell
1en addition, en multiplikation, en jämförelse

När man anger ordoklassen behöver man bara ta med den största termen, och kan strunta i multplikation eller division med konstant, t ex är O(log(n)-1) = O(log(n)).

Man mäter komplexitet i enkla operationer (tex: en addition, en multiplikation eller en jämförelse). Man måste naturligtvis definera vad man menar med de i uttrycket ingående variablerna och vilka förutsättningar som gäller.

Samma algoritm har olika tidskomplexitet vid olika förutsättningar. Ofta (men inte alltid) är man intresserad av det värsta fallet, de förutsättningar som gör att algoritmen tar längst tid. Här är en tabell över hur lång tid det tar (hur många jämförelser det går åt) för att hitta ett värde i ett binärt sökträd i några olika fall:
Sökning i balanserat binärträd Tidsåtgång
Om det sökta finns, i bästa fall 1
Om det sökta finns, i värsta fall log(n)
Om det sökta finns, i snitt log(n)-1
Om det sökta ej finns log(n)

Om man vet att det sökta finns och bara vill konstatera var i trädet det finns behöver man inte kontrollera den sista noden. Då blir värsta fallet: log(n)-1 och snittet ungefär: log(n)-2.

Men om insättningen i det binära trädet gick dåligt ligger alla värden i en tarm och då blir sökningen som i en enkellänkad lista:
Sökning i enkellänkad lista Tidsåtgång
Om det sökta finns, i bästa fall 1
Om det sökta finns, i värsta fall n
Om det sökta finns, i snitt n/2
Om det sökta ej finns n

Om man vet att det sökta finns och bara vill konstatera var i listan det finns behöver man inte kontrollera den nedersta noden. Då blir värsta fallet: n-1 och snittet: (n-1)/2.

OBS. Oftast har man ingen aning om huruvida det sökta finns eller inte...

Instuderingstips

För varje datastruktur och algoritm gäller att åtminstonde kunna: 



Betygskriterier



För betyg E
 ska man kunna avgöra vilken algoritm som löser ett givet problem, kunna beskriva algoritmen och demonstrera den steg för steg med givna data, samt implementera den. Motsvarande gäller för datastrukturer.


För betyg C
 ska kraven för betyg E vara uppfyllda, och dessutom ska man kunna jämföra algoritmer och datastrukturer och bedöma dessas lämplighet för ett givet problem. Här ställs också krav på tidsplanering.


För betyg A
 ska kraven för betyg C vara uppfyllda, och man ska dessutom kunna modifiera/kombinera algoritmer och datastrukturer för att lösa nya problem. Här ställs också höga krav på tydlighet i algoritmbeskrivningar.


Tentan



Mest problemfrågor, tex: 

Men också teorifrågor.



Kom ihåg:





Bonus och hjälpmedel








Tid och plats: