Kursplan för läsåret 2009/2010
(Genererad 2009-08-11.)
ALGORITMTEORIEDAN05
Algorithm Theory

Antal högskolepoäng: 7,5. Betygskala: TH. Nivå: A (Avancerad nivå). Undervisningsspråk: Kursen ges på engelska. Överlappar följande kurs/kurser: EDA110 och EDA110. Valfri för: D4, D4ps, E4, E4ps, F4, F4tvb, Pi4, Pi4sbs. Kursansvarig: Univ.lektor Rolf Karlsson, Rolf.Karlsson@cs.lth.se, Inst f datavetenskap. Förkunskapskrav: EDAA01 Programmeringsteknik-fördjupningskurs eller EDA027 Algoritmer och datastrukturer. Dessutom FMA420, Linjär algebra. Förutsatta förkunskaper: FMA410 Matematik, endimensionell analys. Prestationsbedömning: Tentamen är skriftlig. Slutbetyg i kursen grundar sig i huvudsak på tentamen men kan påverkas positivt av resultatet på inlämningsuppgifter. För godkänt betyg krävs också slutfört obligatoriskt projekt. Poängsatta delmoment: 2. Övrigt: Kursen ges i samarbete med Datavetenskap, Nat. fak. Hemsida: http://www.cs.lth.se/Education/LTH/.

Syfte
Att ge fördjupade kunskaper i konstruktion och analys av effektiva algoritmer och ge träning i algoritmisk problemlösning

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

Innehåll
Lösningsmetoder för rekursionsekvationer. Ordningsstatistik. Rödsvarta träd. Utökade datastrukturer. Dynamisk programmering. Giriga algoritmer. Kortaste vägar. Geometriska algoritmer. Maxflöde. Sorterande nätverk. Mönstersökning i strängar. Ett obligatoriskt projekt.

Litteratur
Cormen T, Leiserson C, Rivest R & Stein C: Introduction to Algorithms, Second Ed. McGraw-Hill & MIT Press 2001. ISBN: 0-262-53196-8

Poängsatta delmoment

Kod: 0109. Benämning: Algoritmteori.
Antal Högskolepoäng: 6. Betygskala: TH. Prestationsbedömning: Skriftlig tentamen. Slutbetyg på kursen grundar sig i huvudsak på denna tentamen, men kan påverkas positivt av resultaten på inlämningsuppgifter.

Kod: 0209. Benämning: Projekt.
Antal Högskolepoäng: 1,5. Betygskala: TH. Prestationsbedömning: För godkänt betyg på kursen måste projektet vara godkänt.