bild
Skolan för
elektroteknik
och datavetenskap
KTH / CSC / Kurser / DD1352 / adk11 / Schema

Schema och detaljschema i ADK, hösten 2011

Här finns schemat för kursen.

Detaljschema

Kursen består av 32 föreläsningar och 12 övningar. Alla föreläsningar efter första veckans tre föreläsningar ä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 har använts tidigare i kursen, Sup=Supplementet Algorithms and Complexity 2009/2011.
Period 1
F1 29 augusti (2 timmar)
Introduktion till kursen. Effektiv kodning och avlusning. Gästföreläsning av Stefan Nilsson. Se även länksidan.
F2 30 augusti (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 31 augusti (2 timmar)
Datastrukturer: repetition, hashning, praktiska datastrukturer, trie (animering). (GT: 55-130, 141-151, 429-438, KT/Moln: 57-65)
Datastrukturer: latmanshashning, skipplistor. (Sup: 77-83, Moln: 595-602)
Ö1 31 augusti
Algoritmanalys.
F4 5 september
Datastrukturer: bloomfilter. Tillämpning: rättstavning.
F5 7 september
Undre gränser. (GT: 239-240, Sup: 17-29, Moln: 535-547)
F6 8 september
Korrekthetsbevis.
Ö2 8 september
Datastrukturer och undre gränser. Teoriredovisning för labb 1.
F7 12 september
Grafer: djupetförstsökning, breddenförstsökning. (GT: 287-334, KT/Moln: 73-107)
F8 14 september
Grafer: minimala spännande träd (Prim och Kruskal), kortaste stigar (Dijkstra). (GT: 287-334, 339-353, 360-375, KT/Moln: 137-157)
F9 15 september
Grafer: maximala flöden. (GT: 381-397, KT/Moln: 337-357, 367-373)
Ö3 16 september
Grafalgoritmer.
Labb 1 16 september
Konkordans, redovisning.
F10 19 september
Algoritmkonstruktion: dekomposition. (GT: 263-273, KT/Moln: 221-234, 242-246)
F11 20 september
Algoritmkonstruktion: giriga algoritmer, totalsökning. (GT: 257-262, Sup: 31-48, KT/Moln: 115-177, 183-188, Moln: 549-566)
F12 21 september
Algoritmkonstruktion: dynamisk programmering. (GT: 274-281, KT/Moln: 251-290)
Ö4 22 september
Dekomposition och lådpackning. Teoriredovisning för labb 2.
F13 26 september
Algoritmkonstruktion: mer dynamisk programmering. (GT: 354-359, KT/Moln: 290-311)
F14 28 september
Algoritmkonstruktion: geometriska algoritmer, Grahamscan. (GT: 572-586)
F15 29 september
Algoritmkonstruktion: sortering i linjär tid. Räknesortering (GT: 241-244, Sup: 1-6, Moln: 519-524)
Ö5 29 september
Dynamisk programmering.
Labb 2 30 september
Ordkedjor, redovisning.
F16 3 oktober
Algoritmkonstruktion: textsökning. (Sup: 7-16, Moln: 525-534, Pythonkramaren II: 46-48)
F17 4 oktober
Algoritmkonstruktion: polynomberäkningar och FFT. (GT: 488-507, KT/Moln: 234-242)
F18 6 oktober
Probabilistiska algoritmer. (GT: 245-247, KT: 707-724)
Ö6 6 oktober
Algoritmkonstruktion. Teoriredovisning för labb 3.
Sammanfattning av alla algoritmer hittills i kursen
Mästarprov 1, senast måndag 10 oktober klockan 9.15!
Algoritmer.
F19 10 oktober
Reduktioner. (KT: 451-459, Moln: 375-383)
F20 12 oktober
Introduktion till komplexitet, motivering. (GT: 592, KT: 463-466, Moln: 387-390)
F21 13 oktober
Formella definitioner, turingmaskiner. (GT: 593-599)
Ö7 13 oktober
Probabilistiska algoritmer. Reduktioner.
Period 2
F22 24 oktober
Oavgörbarhet. (Sup: 49-73, Moln: 567-590)
Extra visualiseringsföreläsning 24 oktober kl 11-12
NP-reduktionsvisualisering med Alvie (instruktioner)
I Alvie finns reduktioner för delmängdssumma (Subset Sum) och hörntäckning (Vertex Cover) visualiserade och bevisade. Reduktionerna finns implementerade i Java i Teaching machine (klicka på Table of contents, NP-completeness och Run, vänta sedan några sekunder tills maskinen startas; den fungerar ungefär som en grafisk avlusningsmiljö).
Alvie och Teaching machine är utvecklade av Pierluigi Crescenzi.
Reduktionen av 3-cnfsat till delmängdssumma visualiserad med Alvie och sparad som Flash och Quicktime.
F23 25 oktober
Cooks sats. (GT: 600-602)
Ö8 25 oktober
Genomgång av lösning till mästarprov 1. Oavgörbarhet.
Labb 3 28 oktober
Flöden och matchningar, sista redovisningstillfälle.
F24 1 november
NP-fullständighetsbevis. (GT: 603-609, KT: 466-495, Moln: 390-419)
F25 2 november
NP-fullständighetsreduktioner. (GT: 610-617, KT: 459-463, 497-505, Moln: 383-387, 421-429)
Ö9 2 november
NP-fullständighetsbevis. Teoriredovisning för labb 4.
F26 8 november
Mer NP-fullständighetsreduktioner.
Reduktionen av 3-cnfsat till hörntäckning visualiserad med Alvie och sparad som Flash och Quicktime.
F27 9 november
Approximationsalgoritmer. (GT: 618-626, KT: 599-630, 724-727 Moln: 477-508)
Ö10 9 november
NP-fullständiga problem.
Labb 4 11 november
NP-fullständighetsreduktioner, redovisning.
F28 15 november
Mer approximationsalgoritmer.
F29 16 november
Heuristiska algoritmer. Simulated annealing. (KT: 661-670, Moln: 509-518)
Ö11 16 november
Approximationsalgoritmer.
Mästarprov 2, senast 22 november klockan 9.15
Komplexitet.
F30 22 november
Komplexitetsklasser. (KT: 495-497, 531-547, Moln: 419-421, 455-471)
F31 23 november
Föreläsning till förfogande: Fortsättningskurser, Knuths terminologi, komplexitet för parallella beräkningar.
F32 29 november
Repetition. Kursens betygssystem.
Ö12 29 november
Genomgång av lösning till mästarprov 2. Komplexitetsklasser och repetition.
Teoritenta 19 december klockan 9-12 i sal F1
Extralabb 9 och 11 januari 2012
Heuristik för rollbesättningsproblemet, redovisning av frivillig labb.
Frivillig munta för högre betyg, 12 och 13 januari 2012

Handledarschema

Copyright © Sidansvarig: Viggo Kann <viggo@nada.kth.se>
Uppdaterad 2012-08-26