Schema och detaljschema i ADK, våren 2010
Här finns schemat för kursen.
SU-studenterna redovisar sista labben 25 mars. Labbtiderna därefter är
enbart för teknologerna.
Detaljschema
Kursen består av 31 föreläsningar och 12 övningar. Alla föreläsningar utom tre
är entimmesföreläsningar.
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 18 januari (2 timmar)
-
Introduktion till kursen.
Effektiv kodning och avlusning. Gästföreläsning av Stefan Nilsson. Se även
länksidan.
- F2 21 januari (2 timmar)
-
Repetition av algoritmanalys, beräkningsmodeller,
bitkostnad, enhetskostnad. Repetition av sortering (merge sort).
(GT: 3-46, 217-238, 268-270, 686-688, KT/Moln: 29-56, 209-221)
- F3 25 januari
-
Datastrukturer: repetition, hashning, praktiska datastrukturer,
trie
(animering).
(GT: 55-130, 141-151, 429-438, KT/Moln: 57-65)
- F4 28 januari
-
Datastrukturer: latmanshashning,
skipplistor. (Sup: 77-83, Moln: 595-602)
- Ö1 28 januari
-
Algoritmanalys.
- F5 29 januari OBS! kl 11.00-11.45
-
Datastrukturer: bloomfilter. Tillämpning: rättstavning.
- F6 1 februari
-
Undre gränser. (Sup: 17-29, Moln: 535-547)
- F7 4 februari
-
Korrekthetsbevis.
- Ö2 4 februari
-
Datastrukturer och undre gränser. Teoriredovisning för labb 1.
- F8 8 februari (2 timmar)
-
Grafer: djupetförstsökning, breddenförstsökning, minimala spännande träd, kortaste stigar. (GT: 287-334, 339-353, 360-375, KT/Moln: 73-107, 137-157)
- F9 11 februari
-
Grafer: maximala flöden. (GT: 381-397, KT/Moln: 337-357, 367-373)
- Ö3 11 februari
-
Grafalgoritmer.
- F10 12 februari
-
Algoritmkonstruktion: dekomposition. (GT: 263-273, KT/Moln: 221-234, 242-246)
- F11 15 februari
-
Algoritmkonstruktion: giriga algoritmer, totalsökning. (GT: 257-262, Sup: 31-48, KT/Moln: 115-177, 183-188, Moln: 549-566)
- F12 18 februari
-
Algoritmkonstruktion: dynamisk programmering. (GT: 274-281, KT/Moln: 251-290)
- Ö4 18 februari
-
Dekomposition och lådpackning
- Labb 1 18-19 februari
-
Konkordans, redovisning.
- F13 19 februari
-
Algoritmkonstruktion: mer dynamisk programmering. (GT: 354-359, KT/Moln: 290-311)
- F14 22 februari
-
Algoritmkonstruktion: geometriska algoritmer,
Grahamscan. (GT: 572-586)
- F15 25 februari
-
Algoritmkonstruktion: sortering i linjär tid.
Räknesortering
(GT: 241-244, Sup: 1-6, Moln: 519-524)
- Ö5 25 februari
-
Dynamisk programmering. Teoriredovisning för labb 2.
- F16 26 februari
-
Algoritmkonstruktion: textsökning. (Sup: 7-16, Moln: 525-534, Pythonkramaren II: 46-48)
- F17 1 mars
-
Algoritmkonstruktion: polynomberäkningar och FFT. (GT: 488-507, KT/Moln: 234-242)
- Mästarprov 1, senast måndag 1 mars klockan 11.15!
-
Algoritmer.
- Ö6 4 mars
-
Algoritmkonstruktion.
Sammanfattning av alla algoritmer hittills i kursen
- Period 4: komplexitet
- F18 22 mars
-
Reduktioner. (KT: 451-459, Moln: 375-383)
- F19 25 mars
-
Introduktion till komplexitet. (GT: 592, KT: 463-466, Moln: 387-390)
- Ö7 25 mars
-
Genomgång av lösning till mästarprov 1.
Reduktioner.
- Labb 2 25-26 mars
-
Flöden och matchningar, sista redovisningstillfälle.
- F20 29 mars
-
Formella definitioner, turingmaskiner. (GT: 593-599)
- F21 1 april
-
Oavgörbarhet. (Sup: 49-73, Moln: 567-590)
- Ö8 1 april
-
Oavgörbarhet. Teoriredovisning för labb 3.
- F22 12 april
-
Cooks sats. (GT: 600-602)
- F23 15 april
-
NP-fullständighetsbevis. (GT: 603-609, KT: 466-495, Moln: 390-419)
- Ö9 15 april
-
NP-fullständighetsbevis.
- F24 19 april
-
NP-fullständighetsreduktioner. (GT: 610-617, KT: 459-463, 497-505, Moln: 383-387, 421-429)
- F25 22 april
-
Mer NP-fullständighetsreduktioner. Knuths terminologi
- Ö10 22 april
-
NP-fullständiga problem. Teoriredovisning för labb 4.
- Labb 3 22-23 april
-
Ordkedjor, redovisning.
- F26 26 april
-
Approximationsalgoritmer. (GT: 618-626, KT: 599-630, Moln: 477-508)
- F27 29 april
-
Mer approximationsalgoritmer.
- Ö11 29 april
-
Approximationsalgoritmer.
- F28 3 maj
-
Heuristiska algoritmer.
Simulated annealing.
(KT: 661-670, Moln: 509-518)
- Labb 4 6-7 maj
-
NP-fullständighetsreduktioner, redovisning.
- F29 10 maj
-
Komplexitetsklasser. (KT: 495-497, 531-547, Moln: 419-421, 455-471)
- Mästarprov 2, senast 10 maj klockan 11.15
-
Komplexitet.
- F30 17 maj
-
Överraskning: programmeringstävlingsverksamheten. Kommer inte på tentan.
- F31 20 maj
-
Repetition.
- Ö12 20 maj
-
Genomgång av lösning till mästarprov 2.
Komplexitetsklasser och repetition.
- Teoritenta 27 maj klockan 9-12 i sal F1
Handledarschema
|