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 31:e oktober 2014, 8-13, och andra tentamenstillfälle är 10:e januari 2015, 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.


Vecka 36-38: Grunder


Fö 1 (to v36, 13-15, S26): Introduktion. Matematiska grunder. Analys av algoritmer.
Fö 2 (fr v36, 15-17, R41): Giriga algoritmer (2-färgning av grafer, algoritmer för täckningar, urvalsproblem)
Fö 3 (to v37, 13-15, S26): Rekursiv nedbrytning (majoritetsproblem, snabb multiplikation, MAX SAT steg 1)
Fö 4: (fr v37, 15-17, R41): Dynamisk programmering (stabil blandning, delsummor, kortaste vägar)
Fö 5 (to v38, 13-15, S26): 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 av Dasgupta, Papadimtriou och Vazirani.


Vecka 38-40: NP-fullständighet


Fö 6 (fr v38, 15-17, R41): Beräkningskomplexitet I (Översikt)
Fö 7 (to v39, 13-15, S26): Beräkningskomplexitet II (NP-fullständighet och reduktioner)
Fö 8 (fr v39, 15-17, T2): Algoritmer för NP-fullständiga problem.
Fö 9 (to v40, 13-15, S26): 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.
Kortfattat om NP-fullständighet (ursprunglig länk.)


Vecka 40-41: Inexakta metoder


Fö 10 (fr v40, 15-17, R41): Approximationsalgoritmer (nodhölje, handelsresandeproblem)
Fö 11 (to v41, 13-15, S26): Randomiserade algoritmer (Min Cut, kontroll av matrismultiplikation)
Fö 12 (fr v41, 15-17, R41): 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 42: Diverse

Fö 13 (ti v42, 10-12, S26): Resurstillfälle 3. Uppgifter
Fö 14 (to v42, 13-15, S26): Resurstillfälle 4. Övningstentamen.
Fö 15 (ti v44, 10-12, Alan Turing, hus E, IDA): Frågestund inför tentamen. (Kommer att flyttas.)


Sidansvarig: Peter Jonsson
Senast uppdaterad: 2014-10-23