Nada

Faktiskt innehåll i 2D1352, Algoritmer, datastrukturer och komplexitet 2000

Tid

Kursen gick i period 3-4 1999/2000, dvs januari-maj 2000.

Lärare

Kursledare och föreläsare var Viggo Kann, lektor på Nada, datorpost viggo@nada.kth.se. Övningsassistenter: Lars Ivansson, Johan Karlander, Stefan Nilsson, Jonas Holmerin (alla lärare eller doktorander i teoretisk datalogi)

Kurslitteratur

Ausiello m fl: Complexity and Approximation - Combinatorial optimization problems and their approximability properties, Springer Verlag.

Läsanvisning

NivåKapitel/avsnitt
3 CA 1
2 CA 2.1-2.4
3 CA 2.5-2.7
2 CA 3
2 CA 5.1-5.2
2 CA 6.1
2 CA 10
1 CA appendix A.1-A.6
3 CA appendix A.7-A.8
3 Harel, kapitel 8 Noncomputability and undecidability
2 Pugh, artikel om skipplistor
1. Läs som repetition.

2. Läs igenom, men detaljer och bevis är inte väsentliga.

3. Läs i detalj.

Kursbunt

Kursinnehåll

Kursen består av 24 föreläsningar och 12 övningar. Följande tabell visar vad som behandlades under föreläsningarna och övningarna.
Period 3
F1 18 januari
Introduktion, repetition av algoritmanalys, approximation, beräkningsmodeller, bitkostnad och enhetskostnad. (CA 1.1)
F2 19 januari
Repetition av sortering, undre gräns för sortering, korrekthet. (repetition)
Ö1 19 januari
Algoritmanalys.
F3 25 januari
Repetition av datastrukturer (heapar, binära träd), balanserade träd. (repetition, även Biggs 9.2)
F4 26 januari
Grafer: sökning, maximala flöden. (Biggs 9.4,9.5,11)
Ö2 26 januari
Grafalgoritmer.
F5 1 februari
Grafalgoritmer: minimala spännande träd, kortaste stigar. (Biggs 9.3,9.6)
F6 2 februari
Algoritmkonstruktion: dekomposition och giriga algoritmer. (CA 2.1)
Ö3 2 februari
Dekomposition och partitioneringsproblem. (CA 2.2)
F7 15 februari
Algoritmkonstruktion: totalsökning, lokalsökning, linjärprogrammering. (CA 2.3-2.4, A.7)
F8 16 februari
Algoritmkonstruktion: dynamisk programmering. (CA 2.5, även Biggs 12.4-12.6)
Ö4 16 februari
Dynamisk programmering.
Labb 1 16 och 18 februari
Flöden och matchningar, redovisning.
F9 22 februari
Algoritmkonstruktion: Mer dynamisk programmering, probabilistiska algoritmer, sortering i linjär tid. (CA 2.5-2.7)
F10 23 februari
Algoritmkonstruktion: Heurestiker. (CA 10)
Ö5 23 februari
Algoritmkonstruktion.
Hemtal 1, senast tisdag 29 februari klockan 14.00 Postscript och PDF.
Algoritmer.
F11 29 februari
Datastrukturer: skipplistor, praktiska datastrukturer. (Pugh, artikel i kursbunten)
F12 1 mars
Datastrukturer: bloomfilter. Tillämpning: rättstavning.
Ö6 1 mars
Datastrukturer.
Period 4
F13 13 mars
Introduktion till komplexitet. (CA 1.2)
F14 15 mars
Reduktioner. (CA 1.3-1.4)
Ö7 15 mars
Reduktioner.
F15 20 mars
Oavgörbarhet. (Harel, artikel i kursbunten)
F16 22 mars
Deterministiska och ickedeterministiska turingmaskiner och deras kraftfullhet. (CA 6.1-6.1.3)
Ö8 22 mars
Oavgörbarhet.
Labb 2 22 och 24 mars
Optimering av ordkedja, redovisning.
F17 27 mars
Formell definition av NP och co-NP, polynomisk reduktion, Cooks sats. (CA 6.1.4-6.1.5)
F18 29 mars
NP-fullständighetsbevis.
Ö9 29 mars
NP-fullständighetsbevis.
F19 3 april
NP-fullständighetsreduktioner.
F20 5 april
Komplexitetsklasser. (CA 1.2)
Ö10 5 april
NP-fullständighetsbevis.
F21 10 april
Approximationsklasser. (CA 3.1)
F22 12 april
Approximationsscheman. (CA 3.2)
Ö11 12 april
Komplexitetsklasser, approximationsalgoritmer.
Labb 3 12 och 15 april
Konkordans, redovisning.
F23 9 maj
Probabilistiska algoritmer. (CA 5.1-5.2)
F24 10 maj
Repetition.
Ö12 10 maj
Repetition.
Hemtal 2, senast måndag 15 maj Postscript och PDF.
Komplexitet.

^ Upp till kursomgångar.


Sidansvarig: <viggo@nada.kth.se>
Senast ändrad 6 juli 2000
Tekniskt stöd: <webmaster@nada.kth.se>