Kursplan för

Algoritmer, datastrukturer och komplexitet
Algorithms, Data Structures and Complexity

EDAF05, 5 högskolepoäng, G2 (Grundnivå, fördjupad)

Gäller för: Läsåret 2013/14
Beslutad av: Utbildningsnämnd A
Beslutsdatum: 2013-04-15

Allmänna uppgifter

Huvudområde: Teknik.
Obligatorisk för: D2, Pi4-pv
Valfri för: E4, F4, F4-tf, F4-pv, Pi4
Undervisningsspråk: Kursen ges på svenska

Syfte

Algoritmer och datastrukturer spelar en fundamental roll inom datavetenskap. Datastrukturer används för att modellera verkligheten och valet av representation påverkar algoritmers effektivitet. Ett syfte med kursen är att ge kunskap om ett antal avancerade datastrukturer för några av de abstrakta modeller som ingått i tidigare kurser samt om datastrukturer för ytterligare modeller såsom grafer. Ett annat syfte är att ge utökade kunskaper om algoritmer, framför allt grafalgoritmer. Vidare skall kursen ge goda kunskaper i hur man analyserar en algoritm med avseende på effektivitet.

Mål

Kunskap och förståelse
För godkänd kurs skall studenten

Färdighet och förmåga
För godkänd kurs skall studenten

Värderingsförmåga och förhållningssätt
För godkänd kurs skall studenten

Kursinnehåll

Grafer och grafalgoritmer. Datastrukturer för representation av grafer. Strategier för problemlösning såsom söndra-och-härska, giriga algoritmer och brute force. Tekniker för att analysera algoritmers tidskomplexitet. Orientering om komplexxitetsklasserna P och NP. Orientering om beräkningsbarhet och Church-Turings tes.

Kursens examination

Betygsskala: TH
Prestationsbedömning: Skriftlig tentamen. För godkänt betyg på kursen krävs att de obligatoriska momenten i kursen redovisats med godkänt resultat. Slutbetyg i kursen bestäms av resultatet på den skriftliga tentamen.

Delmoment
Kod: 0109. Benämning: Tentamen.
Antal högskolepoäng: 3. Betygsskala: TH. Prestationsbedömning: Slutbetyg på hela kursen baseras på resultatet på den skriftliga tentamen.
Kod: 0209. Benämning: Obligatoriska moment.
Antal högskolepoäng: 2. Betygsskala: UG. Prestationsbedömning: För godkänt betyg på hela kursen krävs att de obligatoriska momenten resovisats med godkänt resultat. Delmomentet omfattar: Laborationer och inlämningsuppgift.

Antagningsuppgifter

Förkunskapskrav:

Begränsat antal platser: Nej
Kursen överlappar följande kurser: EDA027, EDA690

Kurslitteratur

Kontaktinfo och övrigt

Kursansvarig: Docent Thore Husfeldt, Thore.Husfeldt@cs.lth.se
Hemsida: http://cs.lth.se/edaf05