Algoritmer och datastrukturer II
5 hp
Kursplan, Grundnivå, 1DL231
Det finns en senare version av kursplanen.
- Kod
- 1DL231
- Utbildningsnivå
- Grundnivå
- Huvudområde(n) med fördjupning
- Datavetenskap G2F
- Betygsskala
- Underkänd (U), godkänd (3), icke utan beröm godkänd (4), med beröm godkänd (5)
- Fastställd av
- Teknisk-naturvetenskapliga fakultetsnämnden, 25 april 2012
- Ansvarig institution
- Institutionen för informationsteknologi
Behörighetskrav
60 hp varav minst 15 hp matematik och 30 hp datavetenskap inklusive Algoritmer och datastrukturer I.
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).
Litteraturlista
- Litteraturlista giltig från och med höstterminen 2022, version 2
- Litteraturlista giltig från och med höstterminen 2022, version 1
- Litteraturlista giltig från och med höstterminen 2019
- Litteraturlista giltig från och med höstterminen 2017
- Litteraturlista giltig från och med vårterminen 2013
- Litteraturlista giltig från och med höstterminen 2012, version 3
- Litteraturlista giltig från och med höstterminen 2012, version 2
- Litteraturlista giltig från och med höstterminen 2012, version 1