Schema och detaljschema i ADK, våren 2007
Här finns schemat för kursen.
SU-studenterna redovisar sista labben 15 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 vilket avsnitt
i kursboken som behandlas.
- Period 3: algoritmer och datastrukturer
- F1 17 januari
-
Introduktion, repetition av algoritmanalys, approximation, beräkningsmodeller,
bitkostnad och enhetskostnad. (s 29-56, 214-221)
- F2 18 januari
-
Effektiv kodning och avlusning. Gästföreläsning av Stefan Nilsson.
- F3 22 januari
-
Repetition av sortering och datastrukturer. (s 57-65, 209-214)
- F4 25 januari
-
Datastrukturer: skipplistor, praktiska datastrukturer. (s 595-602)
- Ö1 25 januari
-
Algoritmanalys.
- F5 29 januari
-
Datastrukturer: bloomfilter. Tillämpning: rättstavning.
- F6 1 februari
-
Undre gränser. Korrekthetsbevis. (s 535-547)
- Ö2 1 februari
-
Datastrukturer och undre gränser. Teoriredovisning för labb 1.
- F7 5 februari
-
Grafer: sökning, maximala flöden. (s 73-107, 337-357, 367-373)
- F8 8 februari
-
Giriga grafalgoritmer: minimala spännande träd, kortaste stigar. (s 137-157)
- Ö3 8 februari
-
Grafalgoritmer.
- F9 12 februari
-
Algoritmkonstruktion: dekomposition, giriga algoritmer, totalsökning. (s 115-177, 183-188, 221-234, 242-246, 549-566)
- F10 15 februari
-
Algoritmkonstruktion: dynamisk programmering. (s 251-311)
- Ö4 15 februari
-
Dekomposition och lådpackning
- Labb 1 15-16 februari
-
Konkordans, redovisning.
- F11 19 februari
-
Algoritmkonstruktion: mer dynamisk programmering, geometriska algoritmer.
- F12 22 februari
-
Algoritmkonstruktion: sortering i linjär tid, textsökning. (s 519-534)
- Ö5 22 februari
-
Dynamisk programmering. Teoriredovisning för labb 2.
- F13 26 februari
-
Algoritmkonstruktion: polynomberäkningar och FFT. (s 234-242)
- Mästarprov 1, senast måndag 26 februari klockan 10.15
-
Algoritmer.
- Ö6 1 mars
-
Algoritmkonstruktion.
- Period 4: komplexitet
- F14 12 mars
-
Reduktioner. (s 375-383)
- Ö7 15 mars
-
Genomgång av lösning till mästarprov 1.
Reduktioner.
- Labb 2 15-16 mars
-
Flöden och matchningar, sista redovisningstillfälle.
- F15 19 mars
-
Introduktion till komplexitet. (s 387-390)
- F16 22 mars
-
Oavgörbarhet. (s 567-590)
- Ö8 22 mars i sal D32, D35, D41
-
Oavgörbarhet. Teoriredovisning för labb 3.
- F17 28 mars
-
Turingmaskiner och Cooks sats.
- F18 29 mars
-
NP-fullständighetsbevis. (s 390-419)
- Ö9 29 mars
-
NP-fullständighetsbevis.
- Labb 3 12-13 april
-
Ordkedjor, redovisning.
- F19 10 april
-
NP-fullständighetsreduktioner. (s 383-387, 421-429)
- Ö10 12 april
-
NP-fullständiga problem.
- F20 23 april
-
Approximationsalgoritmer. (s 477-508)
- Ö11 26 april
-
Approximationsalgoritmer.
- F21 3 maj i sal D2
-
Heuristiska algoritmer, komplexitetsklasser. (s 509-518, 419-421, 455-474)
- Mästarprov 2, senast 7 maj klockan 10.15
-
Komplexitet.
- F22 7 maj
-
Repetition.
- Ö12 10 maj
-
Komplexitetsklasser och repetition.
- Teoritenta 16 maj klockan 9-13 i sal F1
Handledarschema
|