bild
Skolan för
elektroteknik
och datavetenskap

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

Copyright © Sidansvarig: Viggo Kann <viggo@nada.kth.se>
Uppdaterad 2007-02-22