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
  • Gäller från: vecka 27, 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

För godkänt betyg 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, beräkningsgeometri och flödesnätverk.

Innehåll

Funktioners tillväxt, komplexitet av rekursiva algoritmer. 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, beräkningsgeometri, och datakomprimering.

Undervisning

Föreläsningar, lektioner och övningar.

Examination

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

Litteratur

Litteraturlista

Gäller från: vecka 27, 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.