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-03-08
- Reviderad av: Teknisk-naturvetenskapliga fakultetsnämnden
- Gäller från: HT 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, 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).
Versioner av kursplanen
Litteratur
Litteraturlista
Gäller från: HT 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.