Detaljschema

Detaljschema för adk13 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 5 september (2 timmar)
Introduktion till kursen. Repetition av algoritmanalys, beräkningsmodeller, bitkostnad, enhetskostnad.

* F2 6 september(2 timmar)
Repetition av sortering. (KT: 29-56, 209-221)Effektiv kodning och avlusning. Gästföreläsning av Stefan Nilsson. Se även Diverse länkar i kurswebbens vänstermeny.

* F3 6 september (2 timmar)
Datastrukturer: repetition, hashning, praktiska datastrukturer, trie (animering). (KT: 57-65) Datastrukturer: latmanshashning, skipp listor. (Sup: 77-83)

* Ö1 9 september
Algoritmanalys.

* F4 9 september
Datastrukturer: bloomfilter. Tillämpning: rättstavning.

* F5 10 september
Korrekthetsbevis.

* F6 12 september
Grafer: djupetförstsökning, breddenförstsökning. (KT: 73-107)

* Ö2 12 september
Datastrukturer och grafer. Teoriredovisning för labb 1.

* F7 16 september
Algoritmkonstruktion: giriga algoritmer, totalsökning. (Sup: 31-48, KT: 115-177, 183-188)

* F8 17 september
Algoritmkonstruktion: dekomposition. (KT: 221-234, 242-246)

* F9 19 september
Algoritmkonstruktion: dynamisk programmering, del 1. (KT: 251-290) Visualiseringar: Fibonaccitalen.

* Ö3 19 september
Dekomposition och dynamisk programmering.

* Labb 1 20 september
Konkordans, redovisning.

* F10 17 september
Algoritmkonstruktion: dynamisk programmering, del 2. (KT: 290-311)

* F11 18 september
Exempel på motivering av korrekthet: dynamisk programmering

* F12 18 september
Grafer: minimala spännande träd (Prim och Kruskal), kortaste stigar (Dijkstra). (KT: 137-157)

* F13 19 september
Grafer: maximala flöden. (KT: 337-357, 367-373)

* Ö4 20 september
Dynamisk programmering. Teoriredovisning för labb 2.

* F14 24 september
Undre gränser. (Sup: 17-29)

* F15 26 september
Algoritmkonstruktion: geometriska algoritmer, Grahamscan.

* F16 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.

* F17 1 oktober
Algoritmkonstruktion: textsökning. (Sup: 7-16, Pythonkramaren II: 46-48)

* F18 2 oktober
Algoritmkonstruktion: polynomberäkningar och FFT. (KT: 234-242)

* F19 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.

* F20 8 oktober
Reduktioner. (KT: 451-459)

* F201 9 oktober

Introduktion till komplexitet, motivering. (KT: 463-466)

* F212 11 oktober

Formella definitioner, turingmaskiner.

* Ö7 11 oktober

Probabilistiska algoritmer. Reduktioner.

Period 2¶


* F223 22 oktober

Oavgörbarhet. (Sup: 49-73)

Extra visualiseringsföreläsning 22 oktober kl 14-15 i sal K1¶
* F24 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.¶


* F25 29 oktober
NP-fullständighetsbevis. (KT: 466-495)¶


* F26 22 oktober kl 14-15
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)¶
* F257 1 november

NP-fullständighetsreduktioner. (KT: 459-463, 497-505)

* Ö9 2 november

NP-fullständighetsbevis. Teoriredovisning för labb 4.

* F268 5 november

Mer NP-fullständighetsreduktioner.

* F279 7 november

Approximationsalgoritmer. (KT: 599-630, 724-727)

* Ö10 8 november

NP-fullständiga problem.

* Labb 4 9 november

NP-fullständighetsreduktioner, redovisning.

F28
* F30 12 november

Mer approximationsalgoritmer.

F29
* F31 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.¶
* F312 21 november

Komplexitetsklasser. (KT: 495-497, 531-547)

* F323 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, längst ner på sidan.

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