Kursplan för Algoritmer och datastrukturer I

Algorithms and Data Structures I

Det finns en senare version av kursplanen.

Kursplan

  • 5 högskolepoäng
  • Kurskod: 1DL210
  • Utbildningsnivå: Grundnivå
  • Huvudområde(n) och successiv fördjupning: Datavetenskap G1F, Teknik G1F

    Förklaring av koder

    Koden visar kursens utbildningsnivå och fördjupning i förhållande till andra kurser inom huvudområdet och examensfordringarna för generella examina:

    Grundnivå
    G1N: har endast gymnasiala förkunskapskrav
    G1F: har mindre än 60 hp kurs/er på grundnivå som förkunskapskrav
    G1E: innehåller särskilt utformat examensarbete för högskoleexamen
    G2F: har minst 60 hp kurs/er på grundnivå som förkunskapskrav
    G2E: har minst 60 hp kurs/er på grundnivå som förkunskapskrav, innehåller examensarbete för kandidatexamen
    GXX: kursens fördjupning kan inte klassificeras.

    Avancerad nivå
    A1N: har endast kurs/er på grundnivå som förkunskapskrav
    A1F: har kurs/er på avancerad nivå som förkunskapskrav
    A1E: innehåller examensarbete för magisterexamen
    A2E: innehåller examensarbete för masterexamen
    AXX: kursens fördjupning kan inte klassificeras.

  • Betygsskala: Underkänd (U), godkänd (3), icke utan beröm godkänd (4), med beröm godkänd (5)
  • Inrättad: 2007-03-19
  • Inrättad av: Teknisk-naturvetenskapliga fakultetsnämnden
  • Gäller från: vecka 27, 2007
  • Behörighet: Programkonstruktion 1DL200 eller motsvarande
  • Ansvarig institution: Institutionen för informationsteknologi

Mål

För godkänt betyg ska studenten kunna


  • analysera körtiden för en (enkel) algoritm/program i relation till indatats storlek, i bästa, sämsta, och genomsnittliga fall,

  • besvara frågor för att utvärdera algoritm/program: vad händer med körtiden om indata blir dubbelt så stor? Vilka algoritmer/program ska man välja bland olika alternativ för samma specifikation? Med vilka datastrukturer ska man implementera en algoritm, med tanke på operationerna (lägga till, ändra, ta bort, söka, sortera) på datat. Spelar det någon roll (för stora indata) att byta ut en del av algoritmen/programmet mot ett annat?

  • i detalj ange antaganden som ligger till grund för denna analys.

  • analysera körtiden för operationerna (lägga till, ändra, ta bort, söka, sortera) för vanliga datastrukturer (listor, arrayer, köer, prioritetsköer, stackar, träd, och heaps).

  • förklara fördelar och nackdelar med "giriga algoritmer" (som gör lokalt optimala val utan att ångra sig) för optimeringsproblem som generellt kräver för lång körtid för vanliga indata.

Innehåll

Matematiska grunder: asymptotisk notation,
summationer, rekursionsformler.
Datastrukturer: stackar, köer, träd, prioritetsköer, "heaps". Sökmetoder: binära sökträd, balanserade sökträd, hashtabeller.
Sorteringsmetoder. Enkla grafalgoritmer och "giriga algoritmer". Implementering i ett funktionellt språk (ML).

Undervisning

Föreläsningar, lektioner, laborationer och
obligatoriska inlämningsuppgifter.

Examination

Skriftligt prov (4 hp) samt inlämningsuppgifter (1 hp).

Övriga föreskrifter

Kursen kan inte räknas in i examen med Programkonstruktion II (1IT022) eller
Datastrukturer MN1 (1DL009, 1TD191, 1MB026).

Litteratur

Litteraturlista

Gäller från: vecka 27, 2007

I bibliotekets söktjänst kan du se om en titel finns elektroniskt.

Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Introduction to Algorithms. 2nd ed. MIT Press, 2001.