Schema och detaljschema i ADK, våren 2009
Här finns schemat för kursen.
SU-studenterna redovisar sista labben 20 mars. Labbtiderna därefter är
enbart för teknologerna.
Detaljschema
Kursen består av 22 föreläsningar och 12 övningar.
Följande tabell visar vad som preliminärt kommer att behandlas under
föreläsningarna och övningarna. För varje föreläsning anges vilka sidor
det behandlas i kursböckena. GT=Goodrich-Tamassia, KT=Kleinberg-Tardos,
Moln=Algorithms and Complexity 2007 som användes föregående kursomgångar,
Sup=Supplementet Algorithms and Complexity 2009.
- Period 3: algoritmer och datastrukturer
- F1 19 januari
-
Introduktion, repetition av algoritmanalys, approximation, beräkningsmodeller,
bitkostnad och enhetskostnad. (GT: 3-46, 268-270, 686-688, KT/Moln: 29-56, 214-221)
- F2 22 januari
-
Repetition av sortering och datastrukturer. (GT: 55-130, 141-151, 217-238, KT/Moln: 57-65, 209-214)
- F3 26 januari
-
Effektiv kodning och avlusning. Gästföreläsning av Stefan Nilsson. Se även
länksidan.
- F4 29 januari
-
Datastrukturer: skipplistor, praktiska datastrukturer. (GT: 429-439, Sup: 77-83, KT/Moln: 595-602)
- Ö1 29 januari
-
Algoritmanalys.
- F5 2 februari
-
Datastrukturer: bloomfilter. Tillämpning: rättstavning.
- F6 5 februari
-
Undre gränser. Korrekthetsbevis. (Sup: 17-29, KT/Moln: 535-547)
- Ö2 5 februari
-
Datastrukturer och undre gränser. Teoriredovisning för labb 1.
- F7 9 februari
-
Grafer: sökning, maximala flöden. (GT: 287-334, 381-397, KT/Moln: 73-107, 337-357, 367-373)
- F8 12 februari
-
Giriga grafalgoritmer: minimala spännande träd, kortaste stigar. (GT: 339-353, 360-375, KT/Moln: 137-157)
- Ö3 12 februari
-
Grafalgoritmer.
- F9 16 februari
-
Algoritmkonstruktion: dekomposition, giriga algoritmer, totalsökning. (GT: 257-273, AC: 31-48, KT/Moln: 115-177, 183-188, 221-234, 242-246, Moln: 549-566)
- F10 19 februari
-
Algoritmkonstruktion: dynamisk programmering. (GT: 274-281, 354-359, KT/Moln: 251-311)
- Ö4 19 februari
-
Dekomposition och lådpackning
- Labb 1 19-20 februari
-
Konkordans, redovisning.
- F11 23 februari
-
Algoritmkonstruktion: mer dynamisk programmering, geometriska algoritmer. (GT: 572-586)
- F12 26 februari
-
Algoritmkonstruktion: sortering i linjär tid, textsökning. (GT: 241-244, Sup: 1-16, Moln: 519-534)
- Ö5 26 februari
-
Dynamisk programmering. Teoriredovisning för labb 2.
- F13 2 mars
-
Algoritmkonstruktion: polynomberäkningar och FFT. (GT: 488-507, KT/Moln: 234-242)
- Mästarprov 1, senast måndag 2 mars klockan 10.15
-
Algoritmer.
- Ö6 5 mars
-
Algoritmkonstruktion.
- Period 4: komplexitet
- F14 16 mars
-
Reduktioner. (KT: 451-459, Moln: 375-383)
- Ö7 19 mars
-
Genomgång av lösning till mästarprov 1.
Reduktioner.
- Labb 2 19-20 mars
-
Flöden och matchningar, sista redovisningstillfälle.
- F15 23 mars
-
Introduktion till komplexitet. (GT: 592-599, KT: 463-466, Moln: 387-390)
- F16 26 mars
-
Oavgörbarhet. (Sup: 49-73, Moln: 567-590)
- Ö8 26 mars
-
Oavgörbarhet. Teoriredovisning för labb 3.
- F17 30 mars
-
Turingmaskiner och Cooks sats. (GT: 600-602)
- F18 2 april
-
NP-fullständighetsbevis. (GT: 603-609, KT: 466-495, Moln: 390-419)
- Ö9 2 april
-
NP-fullständighetsbevis.
- Labb 3 2-3 april
-
Ordkedjor, redovisning.
- F19 16 april
-
NP-fullständighetsreduktioner. (GT: 610-617, KT: 459-463, 497-505, Moln: 383-387, 421-429)
- Ö10 16 april
-
NP-fullständiga problem. Teoriredovisning för labb 4.
- F20 20 april
-
Approximationsalgoritmer. (GT: 618-626, KT: 599-630, Moln: 477-508)
- Ö11 23 april
-
Approximationsalgoritmer.
- Labb 4 23 april
-
NP-fullständighetsreduktioner, redovisning.
- F21 27 april
-
Heuristiska algoritmer, komplexitetsklasser. (KT: 495-497, 531-534, 661-670, Moln: 419-421, 455-471, 509-518)
- Mästarprov 2, senast 27 april klockan 10.15
-
Komplexitet.
- F22 4 maj
-
Repetition.
- Ö12 7 maj
-
Komplexitetsklasser och repetition.
- Teoritenta 25 maj klockan 9-12 i sal F1
Handledarschema
|