bild
Skolan för
elektroteknik
och datavetenskap

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

  • Repetition
    • Datalogi
    • Abstraktion
    • Datastrukturer
    • Algoritmer
  • Instuderingstips
  • Tentan
  • Kursutvärdering

Repetition

Detta är en repetitionsföreläsning. Den täcker inte hela kursen, men går igenom stora delar av den. 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 i princip motiveras, ofta på flera olika 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 SAOB (Svenska akademiens ordbok) kan man bland annat hitta följande utdrag:
  • Abstrahera: "Att låta ett föremål falla ur medvetandet, och icke rikta sin uppmärksamhet derpå, kallas abstrahera deraf."
  • Abstraktion: "Genom det man bortlemnar kännemärken, (kan man) ifrån lägre begrepp uppstiga till högre, hvilket kallas logisk Abstraktion."
Källa: "Tuderus, JW. Kiesewetter, JGCC, Lärobok i logiken. Övers. Åbo 1806."

I datalogi:

  • I definitionen av en abstrakt datatyp (ADT) anger man vilka operationer som finns (t ex insert(x), exists(x)), dvs man definerar ett gränssnitt.
  • Gör det lättare för programmerare att samarbeta i ett projekt.
  • Den som skriver ADT:en kan förändra lösningen, så länge funktionen inte påverkas.
  • Den som använder ADT:en behöver inte bry sig om hur den är konstruerad. Behöver bara förstå gränssnittet. Implementationen döljs - abstraktion.
  • Förenklar kodåtervinning (jämför labb 4).
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 labb3 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 mha ett bloomfilter.






Datastrukturer

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

  • Små objekt för egendefinierade saker (t ex Noder av olika slag)
  • Länkade listor
  • Stack (implementeras mha en länkad lista)
  • Kö (implementeras mha en länkad lista)
  • Allmänna träd
  • Binära träd, tex binärt sökträd
  • Hashtabeller
  • Booleska hashtabeller och bloomfilter
  • Trappa (heap)
  • Prioritetsköer (implementeras mha en trappa)

Vi har definerat dessa datastrukturer abstrakt - vi är överrens 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 förstå 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 åtmionstonde följande algoritmer tagits upp:

  • Sökning, tex:
    • Linjärsökning
    • Binärsökning
    • Problemträdssökning, tex:
      • Breddenförstsökning
      • Djupetförstsökning
      • Bästaförstsökning
  • Rekursiva algoritmer i olika sammanhang, tex:
    • Listrekursion
    • Trädrekursion
    • Binärträdssökning, -utskrift
    • Rekursiv medåkning för syntaxkontroll
  • Sortering, tex:
    • Urvalssortering
    • Insättningssortering
    • Räknesortering (Distribution count)
    • Radixsotering (Hålkortssortering)
    • Damernaförstsortering
    • Kvicksortering (Quicksort)
    • Samsortering (Mergesort)
    • Trappsortering (Heapsort)
  • Hashning, tex:
    • Rättstavning
    • Bloomfilter
  • Textsökning, tex:
    • KMP-automat för textsökning
    • Boyer-Moore
    • Rabin-Karp
    • Reguljära uttryck (vi har iofs inte talat om någon algoritm)
  • Komprimeringsalgoritmer, tex
    • Följdlängdskodning (RLE)
    • Huffmankodning
    • Lempel-Ziv-kodning (LZ), speciellt LZW

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 som 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 kunna resonera för varför det är så.

Komplexitet, O(.) Algoritmer
n^2 enkla sorteringsalgoritmer, quicksort
n*log(n) mergesort, heapsort, quicksort
nlinjärsökning, distributionsort, bubblesort
n/2linjärsökning
log(n)binärsökning, sökning och insättning i binärträd
log(n)-1sökning i binärträd
1+insättning och sökning i hashtabell
1en addition, en multiplikation, en jämförelse

Naturligtvis är ju tex 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 tex 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 nedersta noden. Då blir värsta fallet: log(n)-1 och snittet ungefär: log(n)-2. Detta uppstår aldrig i binära sökträd som vi definerat dem...

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 det sökta finns eller inte...









Instuderingstips

För varje datastruktur och algoritm gäller att åtminstonde kunna:
  • Förstå
    • Abstrakt: hur använder man den?
    • Konkret: i detalj hur funkar det? Kunna beskriva i ord (och implementera).
  • Analysera
    • Hur snabb/effektiv är den? Komplexitet bland annat.
    • Vad har den för fördelar/nackdelar? Begränsningar?
    • När är den lämplig/olämplig? (jämfört med andra algoritmer/datastrukturer)


Tentan

Mest problemfrågor, tex:
  • Hur löser man problemet?
  • Vilken algoritm/datastruktur passar?
  • Varför är just den algoritmen mer lämplig i sammanhanget?
Kom ihåg:
  • Viktigt att motivera svaren!
  • Viktigt att motiveringar är tydliga.
  • Inte viktigt att skriva programkod.
  • Rita gärna, så blir det lättare för oss rättare.

Bonus och hjälpmedel

  • Max fem bonuspoäng från labbarna 2-6.
  • Max fem bonuspoäng från hemtalen 1-6.
  • Enstaka labbar och hemtal ger enstaka bonuspoäng.
  • Skriv på tentaomslaget hur många bonuspoäng du tror att du har, uppdelat på bonuspoäng från labbar och hemtal.
  • Hjälpmedel:
    • Det med bläck handskrivna formelbladet. Man får skriva precis vad man vill på det!
    • En valfri algoritmbok

Tid och plats:

  • Ordinarietenta måndag 23 oktober kl 8-13 i salarna Q24-25, Q31-34
  • Tentan återlämnas på föreläsningen tisdag 31 oktober kl 8-10 i sal K1.
  • Omtenta efter jul.

Kursutvärdering

En "mittkursutvärdering" har genomförts.

Så småningom kommer en kursenkät läggas upp på hemsidan. Gör den när du är klar med kursen. Kursenkäten och mittkursutvärderingen kommer att ligga till grund för kursanalysen som kursledaren gör när kursen är slut. Denna kommer i sin tur att påverka utformningen av nästa års kursomgång. Förra årets kursanalys finns på kurshemsidan.


Sidansvarig: Magnus Rosell <rosell@csc.kth.se>
Uppdaterad 2006-10-10