Kursplan för Algoritmer och datastrukturer II

Algorithms and Data Structures II

Det finns en senare version av kursplanen.

Kursplan

  • 5 högskolepoäng
  • Kurskod: 1DL231
  • Utbildningsnivå: Grundnivå
  • Huvudområde(n) och successiv fördjupning: Datavetenskap G2F

    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: 2012-03-08
  • Inrättad av: Teknisk-naturvetenskapliga fakultetsnämnden
  • Reviderad: 2012-04-25
  • Reviderad av: Teknisk-naturvetenskapliga fakultetsnämnden
  • Gäller från: vecka 29, 2012
  • Behörighet: 60 hp varav minst 15 hp matematik och 30 hp datavetenskap inklusive Algoritmer och datastrukturer I.
  • Ansvarig institution: Institutionen för informationsteknologi

Mål

Efter godkänd kurs ska studenten kunna

  • använda notationen för asymptotisk tillväxt av funktioner för att beskriva komplexitet hos algoritmer och beräkningsproblem.
  • härleda ekvationer för en algoritms komplexitet och lösa dessa.
  • använda vanliga algoritmiska tekniker som dynamisk programmering, "giriga" algoritmer, etc.
  • lösa enkla problem genom grafalgoritmer, strängmatchning och flödesnätverk.
  • definiera komplexitetsklasserna P och NP och diskutera den öppna frågan om P=NP.

Innehåll

Funktioners tillväxt, rekursiva algoritmers komplexitet. Datastrukturer för disjunkta mängder. Dynamisk programmering, "giriga" algoritmer, grafalgoritmer, t.ex. kortaste vägen och minimalt uppspännande träd. Maximalt-flödesproblem i flödesnätverk. Algoritmer för strängmatchning. Teori för svårlösta problem.

Undervisning

Föreläsningar, lektioner och övningar.

Examination

Skriftligt prov (3 hp) samt inlämningsuppgifter (2 hp).

Litteratur

Litteraturlista

Gäller från: vecka 29, 2012

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. 3rd ed. MIT Press, 2009.