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: 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 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).
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.