Göm menyn

TDDD20 Konstruktion och analys av algoritmer

Kursinformation


Allmänt

Kursens mål är att presentera ett antal metoder för att konstruera och analysera algoritmer. Fokus kommer att ligga på algoritmkonstruktion. Teorin illustreras med exempel hämtade från, bland annat, grafalgoritmer, probabilistiska algoritmer, approximationsalgoritmer, algoritmer för CSP-problem, algoritmer för matematiska problem samt NP-fullständighet. Nedan ges en översikt av kursens innehåll.

Kursboken heter "Introduction to Algorithms" och är skriven av Cormen, Leiserson, Rivest och Stern. Finns i flera upplagor och alla kan användas som kursbok. Referenserna nedan gäller upplaga 2. Observera att läsanvisningarna bara är förslag på delar av boken som kan vara extra intressanta. Glöm inte att skumma hela boken för att få en överblick av vad som gjorts på området. På nätet finns lösningsförslag till en stor del av övningsuppgifterna: Förläggarens "officiella" lösningar finns här och lösningsförslag sammanställda av Philip Bille finns här.

Examinationen består av en skriftlig tentamen på 40 poäng och för att bli godkänd krävs minst 16 poäng. Första tentamenstillfälle är 1:e november 2013, 8-13, och andra tentamenstillfälle är 10:e januari 2014, 8-13. Ett antal gamla tentor finns att hämta här: 991020, 000114, 000822, Exempeltenta med facit. Undervisningsspråk på kursen är svenska men examinationen kan göras på engelska om så önskas - kontakta i så fall examinator minst en vecka före tentamenstillfället.


[Notera: Fö må v38 är flyttad.]

Vecka 36-39: Grunder


Fö 1 (må v36, 15-17, P42): Introduktion. Matematiska grunder. Analys av algoritmer.
Fö 2 (fr v36, 15-17, P42): Giriga algoritmer (2-färgning av grafer, algoritmer för täckningar, urvalsproblem)
Fö 3 (må v37, 15-17, R41): Rekursiv nedbrytning (majoritetsproblem, snabb multiplikation, MAX SAT steg 1)
Fö 4: (må v39, 15-17, R41): Dynamisk programmering (stabil blandning, delsummor, kortaste vägar)
Fö 5 (fr v39, 15-17, P42): Resurstillfälle 1 Uppgifter

Repetitionsläsning
För att göra de första föreläsningarna enklare att förstå rekommenderas följande:


1. Läs på om datastrukturer och algoritmer, t.ex. genom att skumma DALGens kursbok. Speciellt är det mycket nyttigt att studera hur man analyserar algoritmers tidskomplexitet.

2. Repetera grundläggande diskret matematik och logik. Grafteori och propositionslogik används flitigt i kursen.

3. Repetera matematisk bevisföring. En utgångspunkt kan vara följande websida. En annan utgångspunkt är Wikipedias bevisföringssida.


Att läsa i kursboken:
kap. 15-16 (dynamisk programmering och giriga algoritmer)
kap. 22-26 (grafalgoritmer)
kap. 28.2 (matrismultiplikation)
kap. 33.4 (exempel på söndra-och-härska)

Extraläsning:
Giriga algoritmer och urvalsproblem (ursprunglig länk)
Läsvärd bok.


Vecka 40: NP-fullständighet


Fö 6 (må v40, 15-17, R41): Introduktion till NP-fullständighet.
Fö 7 (on v40, 17-19, P42): Algoritmer för NP-fullständiga problem.
Fö 8 (fr v40, 15-17, P42): Resurstillfälle 2 Uppgifter

Att läsa i kursboken:
kap. 34 (NP-fullständighet)

Extra läsning:
M.R. Garey och D.S. Johnson har skrivit en bok som heter "Computers and Intractability: A Guide to the Theory of NP-Completeness". Innehåller mycket material om NP-fullständighet men också en hel del om approximationsalgoritmer och annat som tas upp senare i kursen.


Vecka 41: Inexakta metoder


Fö 9 (må v41, 15-17, A35): Approximationsalgoritmer (nodhölje, handelsresandeproblem)
Fö 10 (on v41, 17-19, P42): Randomiserade algoritmer (Min Cut, kontroll av matrismultiplikation)
Fö 11 (fr v41, 15-17, P42): Randomisering+Approximation (MAX SAT steg 2)

Repetitionsläsning: Grunderna i sannolikhetslära.

Att läsa i kursboken:
kap. 7.4.2 (randomiserad analys av Quicksort)
kap. 35 (approximationsalgoritmer)
kap. 9.2 (kombinerar randomisering och söndra/härska på ett kul sätt)
kap. 31.8 (randomiserad primtalstestning, halvsvårt)

Extra läsning:
"Randomized Algorithms" av S. Motwani och P. Raghavan.

Vecka 42: Diverse

Fö 12 (må v42, 15-17, P42): CSP (Constraint Satisfaction Problems).
Fö 13 (on v42, 17-19, R41): Resurstillfälle. Uppgifter
Fö 14 (fr v42, 15-17, P42): Resurstillfälle. Övningstentamen.
Fö 15 (tid beslutas senare): Frågestund inför tentamen.


Sidansvarig: Peter Jonsson
Senast uppdaterad: 2013-08-12