Till KTH:s startsida Till KTH:s startsida

Visa version

Version skapad av Viggo Kann 2013-08-23 15:14

Visa < föregående | nästa >
Jämför < föregående | nästa >

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ökningbreddenfö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. 

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

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)

  • F21 9 oktober

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

  • F22 11 oktober

Formella definitioner, turingmaskiner.

  • Ö7 11 oktober

Probabilistiska algoritmer. Reduktioner.

Period 2

  • F23 22 oktober

Oavgörbarhet. (Sup: 49-73)

  • F24 23 oktober

Cooks sats.

  • Ö8 25 oktober

Genomgång av lösning till mästarprov 1. Oavgörbarhet.

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.

  • F27 1 november

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

  • Ö9 2 november

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

  • F28 5 november

Mer NP-fullständighetsreduktioner.

  • F29 7 november

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

NP-fullständiga problem.

NP-fullständighetsreduktioner, redovisning.

  • F30 12 november

Mer approximationsalgoritmer.

  • F31 14 november

Heuristiska algoritmerSimulated annealing. (KT: 661-670)

Approximationsalgoritmer.

  • Mästarprov 2, senast 19 november klockan 15.00

Komplexitet.

  • F32 21 november

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

  • F33 27 november

Repetition. Kursens betygssystem.

Genomgång av lösning till mästarprov 2. Komplexitetsklasser och repetition.

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