Föreläsning 13: Labb 8,9,10 + info om betyg C och A

  • DD1326: Etikmomentet
  • Syntaxträd
  • Labb 8
  • Labb 9
  • Labb 10
  • Info om labbar och munta för högre betyg
  • Repetition
  • Instuderingstips
  • Extentor: se Tentabanken
  • pip install

DD1326: Etikmomentet

  • Två föreläsningar
  • Lämna in preliminär version av etikuppsatsen
  • Gruppövning
  • Peer review
  • Slutlig inlämning av etikuppsatsen

Labb 8, 9, 10

Laborationerna

I labb 8 och 9 ska du skriva ett program som kollar att molekyler som användaren matar in via tangentbordet följer en given syntax.

I labb 10 ska du bygga vidare på programmet från labb 9 så att det även skapar ett syntaxträd (och ritar upp det med hjälp av en färdig grafikmodul, molgrafik.py).

 

Labb 8: En enkel syntax

Här finns det fyra testfall i Kattis. De första två är synliga i labblydelsen, men testfall 3 och 4 är hemliga.
Enligt labblydelsen:
För varje inmatad rad ska programmet skriva ut ett omdöme, antingen "Formeln är syntaktiskt korrekt" eller någon av felutskrifterna "Saknad stor bokstav vid radslutet" och "För litet tal vid radslutet"  följt av en utskrift av den del av inmatningen som är kvar efter det tecken där felet påträffades.
Om vi tittar på exemplen på felaktiga indata ser vi att utskriften av "den del av imatningen som är kvar" ser lite olika ut i de olika exemplen. Här är två exempel:
cr12 Saknad stor bokstav vid radslutet cr12
För detta fall kan man tjuvtitta (med peek()) på första tecknet och direkt se att det inte är en stor bokstav - man behöver inte plocka ut det ur kön. Därför skrivs hela "cr12" ut i felutskriften.
Men för att veta om det är fel räcker det inte alltid att bara titta ett tecken framåt. Betrakta följande exempel:
Pb1 För litet tal vid radslutet
Ett tal kan bestå av flera siffror, och hade det stått "Pb12" så hade det varit godkänt. Vår extrametod peek() i queue kan bara titta på ett tecken i taget, så vi kommer att behöva plocka ut siffran "1" ur kön för att se vad som kommer efter det innan vi kan avgöra om det är OK eller inte. Och då finns "1" inte kvar i kön och skrivs alltså inte ut.

Vad ska då utskriften bli för inmatningen "Pb05"?

Labb 9: Formelkoll

Denna labb fortsätter direkt på labb 8. Syntaxen är utbyggd för att kunna kontrollera längre molekylformler, t ex "Zn5H3" eller "Li(Fe2S4)5Ag"

<formel>::= <mol> \n
<mol>   ::= <group> | <group><mol>
<group> ::= <atom> |<atom><num> | (<mol>) <num>
<atom>  ::= <LETTER> | <LETTER><letter>
<LETTER>::= A | B | C | ... | Z
<letter>::= a | b | c | ... | z
<num>   ::= 2 | 3 | 4 | ...

Du ska också kontrollera att atomerna är verkliga atomer (från en given lista), men du ska inte kontrollera om molekylen är rimlig ur kemisk synvinkel.

Några nya felutskrifter tillkommer:

  • Okänd atom vid radslutet
  • Saknad högerparentes vid radslutet
  • Felaktig gruppstart vid radslutet

 

Denna labb brukar upplevas som den svåraste i kursen. Goda råd:

  • Följ syntaxen strikt. Varje funktion ska ha sin egen uppgift, och funktionerna ska inte bli långa.
  • Använd bara de utskrifter som är givna i uppgiften (Kattis förstår inte annars).
  • Hitta på många egna testfall. Download Övning: testfall
  • Skriv ett unittest-program för testfallen, så går det snabbare för dig att provköra.

Det program du skickar in till Kattis ska läsa all indata från stdin, se programmet nedan. Om du vill provköra med en fil kan du tillfälligt sätta om stdin med stdin = open("indata1.txt") Men glöm inte att kommentera bort den raden innan du skickar in till Kattis.

Huvudprogram

from sys import stdin


def main():
    #stdin = open("indata1.txt") #Lätt att ändra för att testa indata från fil
    rad = stdin.readline()
    while rad[0] != "#":
        q = LinkedQ()
        for tkn in rad:
            q.enqueue(tkn)
        try:
            readformel(q)
            print("Formeln är syntaktiskt korrekt")
        except Syntaxfel as felet:
            rest = str(q).strip()
            print(felet, "vid radslutet", rest)
        rad = stdin.readline()

main()

 

Labb 10: Syntaxträd

När man använder en syntax för att tolka text (indata, programkod etc) brukar man skapa ett syntaxträd som datastruktur för den parsade texten.

Ett syntaxträd är ett allmänt träd, där de inre noderna är icke-slutsymboler och löven slutsymboler.

Välkänt exempel:
Språket som består av meningar av typen
JAG VET ATT DU TROR ATT JAG VET OCH JAG TROR ATT DU VET ATT JAG TROR har följande syntax:


<Mening> ::= <Sats> | <Sats><Konj><Mening>
<Konj> ::= ATT | OCH
<Sats> ::= <Subj> <Pred>
<Subj> ::= JAG | DU
<Pred> ::= VET | TROR

Vi kan skapa ett syntaxträd för en given mening genom att parsa meningen och identifiera delarna. Exempel:
JAG VET
är en <Mening>, som i sin tur är en <Sats>, som är <Subj> följt av <Pred>, där <Subj> är JAG och <Pred> är VET. 

SyntaxträdJAGVET-1.jpeg

För den lite längre meningen JAG VET OCH DU TROR ATT DU VET får vi:

SyntaxträdJAGVETOCH.jpeg


Hur blir syntaxträdet för syntaxen i labb 9?

<formel>::= <mol> \n
<mol>   ::= <group> | <group><mol>
<group> ::= <atom> |<atom><num> | (<mol>) <num>
<atom>  ::= <LETTER> | <LETTER><letter>
<LETTER>::= A | B | C | ... | Z
<letter>::= a | b | c | ... | z
<num>   ::= 2 | 3 | 4 | ...

 

I labb10 ska syntaxträdet representeras av ett allmänt träd där varje nod (motsvarar en ruta i bilden nedan) kan representeras med ett objekt av klassen Ruta nedan:

class Ruta:          
    def __init__(self):
       self.atom = "( )"
       self.num = 1    
       self.next = None
       self.down = None

Molekylen Si(C3(COOH)2)4(H2O)7 får följande utseende:

Si(C3(COOH)2)4(H2O)7

 

Klassen Molgrafik är given, och låter dig rita upp syntaxträdet enligt ovan. Vi tar ett litet exempel: molekylen C(OH)2. Det fullständiga syntaxträdet ser ut så här:

Fullständigt syntaxträd för C(OH)2

Vi förenklar i två steg genom att

  1. Ta bort inre noder
  2. Göra om till ett allmänt träd:

Syntaxträd C(OH)2 Förenkling Allmänt Träd

 

Det allmänna trädet är alltså uppbyggt av Ruta-noder med down- och next-pekare på följande vis:

Syntaxträd C(OH)2 med Ruta

#Demonstrerar klasserna Ruta och Molgrafik
from molgrafik import *

class Ruta:
def __init__(self, atom="( )", num=1):
self.atom = atom
self.num = num
self.next = None
self.down = None

#Bygger upp träd för "C(OH)2"
ruta1 = Ruta("C")
ruta2 = Ruta(num=2)
ruta1.next = ruta2
ruta3 = Ruta("O")
ruta2.down = ruta3
ruta4 = Ruta("H")
ruta3.next = ruta4

molekyl = ruta1

mg = Molgrafik()
mg.show(molekyl)

 

Sist i laboration 10 ska du också beräkna molekylernas vikt. 

Labbar för högre betyg på LABD

När du blivit godkänd på labb 1-10 får du betyg E på kursens labbdel LABD.

Om du redovisat labbarna i tid så får du tillgång till labb C, och har möjlighet att höja betyget.

När du redovisat labb C får du tillgång till labb A. 

 


Betyg C

Ur kursens betygskriterier:

För betyg C ska kraven för betyg E vara uppfyllda, och dessutom ska du kunna jämföra algoritmer och datastrukturer och bedöma dessas lämplighet för ett givet problem.

Betyg A

Ur kursens betygskriterier:

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.

 

Labbar och munta för betyg C och A kan handla om alla områden i kursen.


Individuellt arbete

OBS! Det här är individuella moment. Otillåtet samarbete anmäls till disciplinnämnden. 


Högrebetygslabbar

Endast den som har blivit godkänd på labb 1-10 i tid kan se C-labben (ni läggs in manuellt för att få åtkomst). Den som blivit godkänd på C-labben läggs in på A-labben.

Endast för den som redovisat alla E-labbar i tid. Denna labb är individuell och får inte göras i grupp, eller i samarbete med någon annan. Läs hederskodex innan du börjar med uppgiften.

 

C-labben

Ett krav för betyg C är att man ska kunna jämföra algoritmer och datastrukturer och bedöma dessas lämplighet för ett givet problem. Din uppgift är att göra en jämförelse....

Jämförelsen måste innehålla både egna experiment och teoretiska resonemang. Du får använda dig av både programkod och data från andra källor. Ange alltid dina källor, både när det gäller programkod och teori.

Du ska skriva en kort rapport (max tre sidor + appendix) där du redogör för dina resultat och hur du kom fram till dom.

Redovisning

Rapporten lämnas in i Canvas och redovisas muntligt (på en bokad redovisningstid).

Vid den muntliga redovisningen ska du kunna

  • Beskriva översiktligt hur datastrukturerna fungerar, och hur de kan användas.
  • Motivera de val du gjort när du lagt upp jämförelserna mellan funktionerna.
  • Analysera resultaten.

När du är godkänd på C-labben får du tillgång till A-labben.

Laboration för betyg A

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. Din uppgift är att lösa följande problem...

Redovisning

Rapporten lämnas in i Canvas och redovisas muntligt (på en bokad redovisningstid).

Vid den muntliga redovisningen ska du kunna

  • Förklara din algoritmbeskrivning,
  • Redogöra för hur ditt program fungerar i detalj,
  • Visa att du fått godkänt i Kattis,
  • Motivera vilken tidskomplexitet din algoritm har,
  • Visa upp tre nya uppsättningar testdata.

Munta för betyg C och A

Görs muntligt på KTH.

Problemfrågor, t ex:

  • Demonstrera en algoritm för givna data.
  • Visa hur en operation i en datastruktur fungerar för givna data.
  • Berätta vilka algoritmer/datastrukturer från kursen som kan användas.
  • Resonera om varför en viss algoritm/datastruktur är lämplig i sammanhanget.
  • Beskriv en algoritm som löser ett givet problem.
  • Uppskatta tidskomplexiteten för din algoritm.

Men också teorifrågor, t ex:

  • Vilken tidskomplexitet har algoritmen xxx?
  • Vad är viktigt att tänka på när en använder datastrukturen yyy?

Kom ihåg:

  • Viktigt att motivera svaren!
  • Viktigt att motiveringar är tydliga.

Muntan genomförs på plats på KTH:

  • Du kan boka tid för munta även om du inte gjort högrebetygslabbar.
  • C-munta och A-munta bokas samtidigt, men du kan välja att bara göra C-munta.
  • Vilken typ av frågor är det?
    • Frågorna liknar de frågor som finns i tentabanken  på C- respektive A-nivå och är formulerade m h t kursPM, avsnitt "Betyg/betygskriterier". De är dock anpassade till den begränsade tiden samt för att kunna besvaras muntligt.
  • Vilka hjälpmedel är tillåtna? Se nedan.
  • Vilket av kursinnehållet ingår?
    • Allt

Muntan går till så här

    1. Boka en tid på bokningssidan (tiderna läggs upp en vecka i förväg).
    2. Vid den bokade tiden får du ca 20 min ( 30 min för Funka R1) attlösa problemet.
    3. En lärare/assistent hämtar dig från salen och du får c:a 5 minuters presentationstid. Det är ditt eget ansvar att kunna besvara frågan utöver att ha löst den. Du får rita på papper och visa men frågorna är utformade så att de kan besvaras endast muntligt. Läraren/assistenten meddelar dig avslutningsvis betyg. Du får inte en lösningsgenomgång efter presentationen.

Tillåtet hjälpmedel på muntan är:

  • Ett egenhändigt skrivet formelblad, fyra A4 (eller två dubbelsidiga ark om du skrivit ut på papper).
    • Du får skriva precis vad du vill på formelbladen, men fontstorleken måste vara rimlig (inte mindre än 10).
    • Du får inte använda ett formelblad som någon annan har författat.
    • Om du kopierat från t ex föreläsningsanteckningarna - skriv en referens.

Beskriva en algoritm

Hur beskriver man en algoritm?

Skilj på att förklara hur en algoritm fungerar och att konstruera en algoritm.

  • Vad är indata till algoritmen?
  • Vad är utdata?
  • Punktvis (inte löptext). Ordningen är viktig!
  • När avslutas algoritmen?

Dijkstra's algoritm

Bästaförstsökning är exempel på en girig algoritm, där man i varje steg väljer den väg som verkar bäst för stunden, utan att reflektera över vad konsekvenserna blir i längden. Ofta ger giriga algoritmer inte den bästa lösningen, men i just det här fallet fungerar det faktiskt! Algoritmen kallas Dijkstra's algoritm (efter den holländske datalogen Edsger W. Dijkstra) och att den fungerar bevisas i fortsättningskursen DD2350 Algoritmer, datastrukturer och komplexitet

Det finns flera varianter på Dijkstra's algoritm. Nedan en variant för att räkna ut billigaste vägen från en startnod till en slutnod i en graf med kostnader.

Startnoden ligger nu först i kön. I fortsättningen kan noder mitt i prioritetskön behöva omprioriteras. Ett sätt att omprioritera är att införa en remove-funktion som tar bort en nod ur en prioritetskö. Det får inte bli ett "hål" utan i princip sker en upp- och nertrappning på ungefär samma sätt som vid insättning och urtagning från en prioritetskö.

Algoritm version 1

Stoppa in startnoden i en min-prioritetskö. Plocka ut en nod p från prioritetskön. Undersök noden p:s barn ett och ett. Räkna ut kostnaden att gå från p till barnet. Om kostnaden är billigare än barnets nuvarande prioritet (från början var kostnaden ∞) så sätt om barnets prioritet till den nya kostnadenoch sätt föräldrapekaren att peka på p. Omprioritera barnet genom att plocka bort barnet ur prioritetskön och stoppa in barnet i prioritetskön. Skriv ut billigaste vägen genom att följa föräldrapekarna från slutnoden till startnoden.

Svårläst? Titta på denna variant.

Algoritm version 2

För att förklara algoritmen börjar vi med de första stegen. 

  1. Sätt alla noders prioritet/kostnad till ∞ (i praktiken något maximalt värde, t ex float("inf") i Python))
  2. Sätt startnodens prioritet till 0. 
  3. Stoppa in startnoden i en min-prioritetskö.

Den fortsatta algoritmen för att hitta billigaste vägen:

  1. Plocka ut en nod p från prioritetskön.
  2. Undersök noden p:s barn ett och ett
    1. Räkna ut kostnaden att gå från p till barnet.
    2. Om kostnaden är billigare än barnets nuvarande prioritet (från början var kostnaden ∞) 
      1. sätt om barnets prioritet till den nya kostnaden
      2. sätt föräldrapekaren att peka på p
      3. Omprioritera barnet genom att
        1. plocka bort barnet ur prioritetskön 
        2. stoppa in barnet i prioritetskön 
  3. Upprepa från 1. tills prioritetskön är tom (det går att avbryta tidigare när bättre vägar inte finns)
  4. Skriv ut billigaste vägen genom att följa föräldrapekarna från slutnoden till startnoden.

Vilka skillnader finns? Vad gör den andra versionen bättre?

 

pip install

För C-labben och A-labben kan du behöva använda externa paket, som du behöver installera med pip install. Gör så här:

Windows: Öppna Windows PowerShell

Mac: Öppna Terminal

Unix/Ubuntu: Öppna terminalfönstret

Där skriver du

pip install nyttPaket

Efter det kan du importera nyttPaket i dina program (precis som du gör med ett inbyggt paket som random).

Kortfattade instruktioner finns här: Quickstart pip install

Hur vet du att de paket du installerat är säkra? Installera paketet safety och kontrollera detta med

safety check

Exempel på tentaupgift betyg C: Komprimering


Anta att vi vill lagra en lista med namnen på all världens pappor. Namnen ska skrivas med rätt tecken ur respektive skriftspråk (du kan anta att det finns omkring 100 000 olika tecken totalt i skriftspråken).
Listan blir lång, så vi vill komprimera den, kanske med någon av metoderna
Huffmankodning eller Lempel-Ziv (LZW).

a) Skriv upp två egenskaper som är intressanta att jämföra för komprimeringen.

b) Jämför Huffmankodning och Lempel-Ziv för var och en av de två egenskaperna.

Motivera dina slutsatser och illustrera med exempel. Du får göra egna
antaganden om namnlistans innehåll.

Lösning (Men på muntan förväntar vi oss inte en omfattande lösning pga begränsad tid)

Exempel på labbuppgift betyg A: Silhuettproblemet

Om man på håll betraktar en stad i skymningen ser man inte dom enskilda byggnaderna utan bara silhuetten, den yttersta konturen, avteckna sig mot himlen. Hitta på en algoritm som givet varje byggnads kontur beräknar stadssilhuetten.
stadssilhuett

Anta att alla byggnader står på x-axeln, är rektangulära och beskrivs av tripplar(left, height, right) där left är vänsterväggens x-koordinat, right är högerväggens x-koordinat och height är höjden (y-koordinat).

Inmatningen består av n stycken tripplar, ordnade i stigande värden på vänsterväggar, och utmatningen ska vara en rad med x,y-koordinater som från vänster till höger beskriver silhuetten.

x-värdena anger var på x-axeln silhuetten går vertikalt och y anger på vilken höjd silhuetten fortsätter efter x-värdet. Den sista y-koordinaten är alltid noll eftersom alla byggnader står på x-axeln.

Exempel: Om n=8 och inmatningen är
(1,11,5) (2,6,7) (3,13,9) (12,7,16) (14,3,25) (19,18,22) (23,13,29) (24,4,28)
så blir utmatningen

     x= 1  y= 11
     x= 3  y= 13
     x= 9  y= 0
     x= 12 y= 7
     x= 16 y= 3
     x= 19 y= 18
     x= 22 y= 3
     x= 23 y= 13
     x= 29 y= 0

a) Formulera en algoritm som givet varje byggnads kontur beräknar stadssilhuetten. Algoritmen måste beskrivas på ett strukturerat och tydligt sätt.

b) Demonstrera hur din algoritm fungerar med exempel.

c) Uppskatta tidskomplexiteten för din algoritm.

Uppgiften ska lösas enskilt och redovisas skriftligt och muntligt.

Den skriftliga redovisningen ska innehålla

  • uppgiftsnamn och ditt namn,
  • algoritmbeskrivning,
  • program,
  • testdata
  • tidskomplexitet med motivering

Vid den muntliga redovisningen ska du

  • visa upp en tydlig och korrekt algoritmbeskrivning för ditt problem,
  • visa upp tre nya uppsättningar testdata,
  • redogöra för hur ditt program fungerar,
  • visa att du fått godkänt i Kattis,
  • visa vilken tidskomplexitet din algoritm har.

Lösning

 


Repetition

Kursen heter Tillämpad datalogi. 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.

Abstraktion

Ytterligare ett centralt begrepp i kursen är abstraktion. I Nationalencyklopedin står det så här:

  • Abstrakt: "En föreställning är abstrakt om den syftar till att fånga det allmängiltiga hos företeelsen i fråga och bortse från eventuella tillfälligheter. Föreställningen om cirkelns begrepp är t.ex. en abstrakt föreställning till skillnad från föreställningen om en enskild cirkel."
  • Abstrakt tänkande: "Abstrakt tänkande är tankeprocesser som grundar sig på abstrakta begrepp och allmänna principer och inte på enskilda föremål eller konkreta företeelser, och där olika begrepp kan sammanställas till nya helheter, i vilka oväsentliga delar utelämnats."

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.
  • Vid konstruktion av algoritmen behöver man inte tänka på implementationen av datastrukturerna.
  • Det här gör det lättare för programmerare att samarbeta i ett projekt:
    • Den som skriver ADT:en kan ändra implementationen, så länge allt fungerar likadant.
    • Den som använder ADT:en behöver inte bry sig om hur den är konstruerad, utan behöver bara förstå gränssnittet.
  • Förenklar kodåtervinning (tänk på labbarna i kursen!).

Ett exempel: en abstrakt ordlista kan defineras med ett gränssnitt bestående av två operationer: insert(x), exists(x).

Du har själv implementerat en sådan datastruktur på två olika sätt

  • I labb 3 - med binärt sökträd
  • I labb 7 - med en hashtabell

När du sedan använde ordlistan i breddenförstsökningen i labb 5 så använde du den abstrakt, utan att reflektera över hur den var implementerad.

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 bestående av noder med en next-pekare
  • Vektor/array (inbegriper pythons inbyggda lista)
  • Stack (implementerad med en länkad lista)
  • Kö (implementerad med en länkad lista)
  • Allmänna träd (implementerade med noder med två pekare)
  • Binära träd (implementerade med noder med två pekare)
  • Hashtabeller (implementerade med en vektor)
  • Booleska hashtabeller och bloomfilter
  • Trappa/heap (implementerad med en vektor som tolkas som ett binärträd)
  • Prioritetskön (implementerad med en trappa)

Vi har definierat 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 följande algoritmer tagits upp:

  • Sökning:
    • Linjärsökning
    • Binärsökning
  • Grafgenomgång/problemträd:
    • Breddenförstsökning
    • Djupetförstsökning
    • Bästaförstsökning
  • Rekursiva algoritmer, tex:
    • Listrekursion
    • Trädrekursion
    • Binärträdssökning, -utskrift
    • Rekursiv medåkning för syntaxkontroll
  • Sortering, tex:
    • Urvalssortering
    • Insättningssortering
    • Bubbelsortering
    • Räknesortering (Distribution count)
    • Damernaförstsortering
    • Quicksort
    • Mergesort
    • Heapsort
  • Hashning, med tillämpningar:
    • En miljon sånger
    • Data för atomer
    • Bloomfilter
    • för att spara lösenord
  • Textsökning:
    • KMP-automat för textsökning
    • Boyer-Moore
    • Rabin-Karp
    • Reguljära uttryck
  • Komprimeringsalgoritmer:
    • Följdlängdskodning (RLE)
    • Huffmankodning
    • Lempel-Ziv-kodning (LZ), speciellt LZW
  • Redundans, korrigering
    • paritetsbit
    • hammingavstånd
    • sista siffran i personnummer
  • Krypteringsalgoritmer, tex
    • TranspositionschifferTitta mest på tentor utan lösning
    • Caesarchiffer
    • rot13
    • Bokchiffer
    • One-time pad
    • Key exchange
    • RSA

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 ett bloomfilter 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!

Tidskomplexitet

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
1 en addition, en multiplikation, en jämförelse

När man anger ordo-klassen behöver man bara ta med den största termen, och kan strunta i multiplikation eller division med konstant, t ex är O(nlogn(n) + 155*log(n) - 1) = O(nlog(n)).

Man mäter komplexitet i enkla operationer (t ex: en addition, en multiplikation eller en jämförelse). Vilken operation man mäter beror på vilken typ av algoritm det är frågan om. Exempelvis innehåller all någon form av jämförelse så där är det naturligt att räkna antal jämförelser snarare än aritmetik.

Man måste naturligtvis definiera 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 och 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 inför muntan

För varje datastruktur och algoritm behöver du kunna:

  • Förstå
    • Abstrakt: hur använder man den?
    • Konkret: hur implementerar man den? (Kunna beskriva i ord.)
  • Analysera
    • Hur snabb/effektiv är den? Tidskomplexitet/minnesåtgång.
    • 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?
  • Titta på C-uppgifter och A-uppgifter på gamla tentor