Schema och detaljschema i ADK, hösten 2012

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öckerna. KT=Kleinberg-Tardos, Sup=Supplementet Algorithms and Complexity.

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. (KT: 29-56, 209-221)
F3 30 augusti (2 timmar): Datastrukturer: repetition, hashning, praktiska datastrukturer, trie (animering). (KT: 57-65); Datastrukturer: latmanshashning, skipp listor. (Sup: 77-83)
Ö1 30 augusti: Algoritmanalys.
F4 3 september: Datastrukturer: bloomfilter. Tillämpning: rättstavning.
F5 5 september: Korrekthetsbevis.
F6 6 september: Grafer: djupetförstsökning, breddenförstsökning. (KT: 73-107)
Ö2 6 september: Datastrukturer och grafer. Teoriredovisning för labb 1.
F7 10 september: Algoritmkonstruktion: giriga algoritmer, totalsökning. (Sup: 31-48, KT: 115-177, 183-188)
F8 13 september: Algoritmkonstruktion: dekomposition. (KT: 221-234, 242-246)
F9 13 september: Algoritmkonstruktion: dynamisk programmering, del 1. (KT: 251-290)
Visualiseringar: Fibonaccitalen.
Ö3 14 september: Dekomposition och dynamisk programmering.
Labb 1 14 september: Konkordans, redovisning.
F10 17 september: Algoritmkonstruktion: dynamisk programmering, del 2. (KT: 290-311)
F11 18 september: Grafer: minimala spännande träd (Prim och Kruskal), kortaste stigar (Dijkstra). (KT: 137-157)
F12 19 september: Grafer: maximala flöden. (KT: 337-357, 367-373)
Ö4 20 september: Dynamisk programmering. Teoriredovisning för labb 2.
F13 24 september: Undre gränser. (Sup: 17-29)
F14 26 september: Algoritmkonstruktion: geometriska algoritmer, Grahamscan.
F15 27 september: Algoritmkonstruktion: sortering i linjär tid. Räknesortering (Sup: 1-6)
Ö5 27 september: Grafalgoritmer och undre gränser
Labb 2 28 september: Rättstavning, redovisning.
F16 1 oktober: Algoritmkonstruktion: textsökning. (Sup: 7-16, Pythonkramaren II: 46-48)
F17 2 oktober: Algoritmkonstruktion: polynomberäkningar och FFT. (KT: 234-242)
F18 3 oktober: Probabilistiska algoritmer. (KT: 707-724)
Ö6 4 oktober: Algoritmkonstruktion. Teoriredovisning för labb 3.
Sammanfattning av alla algoritmer hittills i kursen
Mästarprov 1, senast måndag 8 oktober klockan 11.15!: Algoritmer.
F19 8 oktober: Reduktioner. (KT: 451-459)
F20 9 oktober: Introduktion till komplexitet, motivering. (KT: 463-466)
F21 11 oktober: Formella definitioner, turingmaskiner.
Ö7 11 oktober: Probabilistiska algoritmer. Reduktioner.
Period 2
F22 22 oktober: Oavgörbarhet. (Sup: 49-73)
Extra visualiseringsföreläsning 22 oktober kl 14-15 i sal K1: 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.; Reduktionen av 3-cnfsat till hörntäckning visualiserad med Alvie och sparad som Flash och Quicktime.
F23 23 oktober: Cooks sats.
Ö8 25 oktober: Genomgång av lösning till mästarprov 1. Oavgörbarhet.
Labb 3 26 oktober: Flöden och matchningar, sista redovisningstillfälle.
F24 29 oktober: NP-fullständighetsbevis. (KT: 466-495)
F25 1 november: NP-fullständighetsreduktioner. (KT: 459-463, 497-505)
Ö9 2 november: NP-fullständighetsbevis. Teoriredovisning för labb 4.
F26 5 november: Mer NP-fullständighetsreduktioner.
F27 7 november: Approximationsalgoritmer. (KT: 599-630, 724-727)
Ö10 8 november: NP-fullständiga problem.
Labb 4 9 november: NP-fullständighetsreduktioner, redovisning.
F28 12 november: Mer approximationsalgoritmer.
F29 14 november: Heuristiska algoritmer. Simulated annealing. (KT: 661-670)
Ö11 15 november: Approximationsalgoritmer.
Mästarprov 2, senast 19 november klockan 15.00: Komplexitet.
F30 20 november: Spelteori. Gästföreläsning av Jonas Sjöstrand.
F31 21 november: Komplexitetsklasser. (KT: 495-497, 531-547)
F32 27 november: Repetition. Kursens betygssystem.
Ö12 29 november: Genomgång av lösning till mästarprov 2. Komplexitetsklasser och repetition.
Teoritenta 13 december klockan 9-12 i sal F1
Extralabb: Heuristik för rollbesättningsproblemet, redovisning av frivillig labb, 17 december klockan 9-12 i Spelhallen och Sporthallen
Frivillig munta för högre betyg, 17-19 december

Handledarschema