English web site
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. Lösningar från MIT finns här, lösningsförslag sammanställda av Philip Bille finns här och ytterligare förslag 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. Tentamen ges 2024-03-22 kl. 14-19 och omtentamen ges 2024-06-04 kl. 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.Bilder till föreläsningarna finns här.
Vecka 3-5: Grunder
Fö 1 (ti v3, 13-15, R43): Introduktion. Matematiska grunder. Analys av algoritmer.
Fö 2 (fr v3, 15-17, A34): Giriga algoritmer (2-färgning av grafer, algoritmer för täckningar, urvalsproblem)
Fö 3 (ti v4, 13-15, A34): Rekursiv nedbrytning (majoritetsproblem, snabb multiplikation, MAX SAT steg 1)
Fö 4: (fr v4, 15-17, U10): Dynamisk programmering (stabil blandning, delsummor, kortaste vägar)
Fö 5 (ti v5, 13-15, U15): Resurstillfälle. Uppgifter. Lösningsförslag.
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 av Dasgupta, Papadimitriou och Vazirani. Kapitel 2 behandlar rekursiv nedbrytning, kapitel 5 behandlar giriga algoritmer och kapitel 6 behandlar dynamisk programmering.
Bevis av Kruskals algorithm som på många sätt liknar beviset
för punkt-intervall-täckning.
Vecka 5-7: NP-fullständighet
Fö 6 (fr v5, 15-17, U3): Beräkningskomplexitet I (Översikt)
Fö 7 (ti v6, 13-15, A34): Beräkningskomplexitet II (NP-fullständighet och reduktioner)
Fö 8 (fr v6, 15-17, A34): Algoritmer för NP-fullständiga problem.
Fö 9 (fr v7, 15-17, U11): Resurstillfälle. Uppgifter. Lösningsförslag. 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.
Kortfattat om NP-fullständighet (ursprunglig länk.)
Vecka 8-9: Inexakta metoder
Fö 10 (ti v8, 13-15, U11): Approximationsalgoritmer (nodhölje, handelsresandeproblem)
Fö 11 (fr v8, 15-17, U11): Randomiserade algoritmer (Min Cut, kontroll av matrismultiplikation)
Fö 12 (ti v9, 13-15, A33): 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.
En bok av Vazirani om approximationsalgoritmer.
Vecka 9-10: Diverse
Fö 13 (fr v9, 15-17, U15): Resurstillfälle. Uppgifter. Lösningsförslag. Fö 14 (ti v10, 13-15, KY24): Resurstillfälle. Övningstentamen.
Fö 15 Frågestund inför tentamen. Tid och plats bestäms senare.