Algoritmer och datastrukturer II
5 hp
Kursplan, Grundnivå, 1DL230
Kursen är avvecklad.
- Kod
- 1DL230
- Utbildningsnivå
- Grundnivå
- Huvudområde(n) med fördjupning
- Datavetenskap G1F
- 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, 23 april 2010
- Ansvarig institution
- Institutionen för informationsteknologi
Behörighetskrav
Matematik 15 hp och datavetenskap 30 hp inklusive Algoritmer och datastrukturer I.
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 av 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. Tillämpningar, t.ex. strängmatchning, beräkningsgeometri, och datakomprimering.
Undervisning
Föreläsningar, lektioner och övningar.
Examination
Skriftligt prov (3 hp) samt inlämningsuppgifter (2 hp).