Faktiskt innehåll i 2D1961, Algoritmer och komplexitet 1995

Tid

Kursen gick i period 3 1994/1995, dvs mars-maj 1995 och tentades 24 maj. Tentan var rättad den 29 maj.

Elever

Kursen var obligatorisk för kompetensinriktningarna programsystemteknik (ca 60 elever) och teleinformatik (ca 15 elever) för elever med studiestatus D91. Cirka 20 D-äldre och 5 elever från universitet följde också kursen.

Lärare

Kursledare, föreläsare och assistent var Viggo Kann, lektor på NADA, datorpost viggo@nada.kth.se.

Kurslitteratur

CLR
Cormen, Leiserson, Rivest: Introduction to Algorithms, användes i kursen Programkonstruktion 1993/94.
Har
David Harel: Algorithmics - the spirit of computing.
BDD
Automata and BDDs - new tools in verification and optimization.

Nivåer

0. Ingår inte alls.

1. Läs översiktligt, inga tentafrågor.

2. Ingår, men ingick redan i Programkonstruktion.

3. Ingår i detalj

Läsanvisning

Kapitel/avsnitt    Nivå
=======================
Har 1-5             1
Har 6-9             3
Har 10-11           1
Har 12              0
CLR 1-14            2
CLR 16              3
CLR 17.1-17.3       3
CLR 23-25           2
CLR 26.1            3
CLR 27.1-27.3       3
CLR 31.2            3
CLR 32              3
CLR 36-37           3
CLR övriga avsnitt  0
BDD avsnitt 1-4     3
BDD avsnitt 5-7     1

Kursbunt

Kursinnehåll

Kursen bestod av 15 föreläsningar och 9 övningar. Följande tabell visar vad som behandlades under föreläsningarna och övningarna.
F1
Introduktion, repetition av algoritmanalys, beräkningsmodeller, bitkostnad och enhetskostnad, undre och övre gränser. (CLR 1-10, Har 6)
F2
Formella språk, beslutsproblem, optimeringsproblem, uttrycksfullhet, reduktioner. (BDD 1.1)
Ö1
Algoritmanalys, reduktioner.
F3
Introduktion till komplexitet. (Har 7)
F4
Oavgörbarhet. (Har 8)
Ö2
Oavgörbarhet, reduktioner.
F5
Enkla beräkningsmodeller (turingmaskiner, ändliga automater) och deras kraftfullhet. (Har 9, BDD 1.2)
F6
KMP-automaten, grammatik, reguljära uttryck. (BDD 2-4)
Ö3
Automater och reguljära uttryck, turingmaskiner.
F7
Algoritmkonstruktion: dekomposition, dynamisk programmering och giriga algoritmer. (CLR 16, 17, 31.2, Har 4)
F8
Översikt över algoritmer. (CLR 23-27)
Ö4
Algoritmkonstruktion, grafalgoritmer.
F9
FFT (CLR 32)
F10
Formell definition av NP och co-NP, polynomisk reduktion, Cooks sats. (CLR 36.1-36.3)
Ö5
Grafalgoritmer och FFT.
F11
NP-fullständighetsbevis. (CLR 36.4-36.5)
F12
Approximationsalgoritmer. (CLR 37)
Ö6
NP-fullständighetsbevis.
Ö7
Mer NP-fullständighetsbevis.
F13
Mer om approximation.
Ö8
Approximationsalgoritmer.
F14
Parallella och probabilistiska algoritmer och komplexitet. (Har 10-11)
Ö9
Tentaräkning.
F15
Repetition

Hemtal

Två frivilliga hemtal delades ut under kursen. Dom löstes enskilt. Summan av bonuspoängen adderas till den på tentan uppnådda poängsumman. Detta gäller ett kalenderår räknat från kursstart.

^ Upp till kursomgångar.


Senast ändrad 1995-06-01 <viggo@nada.kth.se>