Algoritmer och datastrukturer II
5 hp
Kursplan, Grundnivå, 1DL231
- 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, 24 april 2013
- 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.
- presentera och diskutera material relaterat till kursens innehåll muntligt och skriftligt med för utbildningsnivån lämplig färdighet.
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