OBS: Detta schema avviker från det som
schemageneratorn ger, och det är
detta schema som gäller. Blir det ändringar under kursens gång
kommer detta schema att uppdateras.
Kursen är valfri och vänder sig i första hand till D4
och F4 samt MD-linjen på SU, men även andra med nödvändiga
förkunskaper är välkomna.
Den förutsätter att man har förkunskaper motsvarande
någon av kurserna, Algoritmer och komplexitet eller Algoritmer
datastrukturer och komplexitet.
Nadas studerandeexpedition finns på Osquars backe 2 plan 2. Den har öppet må-fr
9.45-11.30 och må-to 12.45-14.15. Kursbunten säljs på studentexpeditionen. Där
kan du också hämta ut din tenta.
Delfi är Nadas systemgrupps mottagning som har hand om konton och passerkort.
Delfi har öppet må--fr 10--12 och må--to 13--15.
Administration. Introduktion till komplexitetsteori och
komplexitetsklasser. Beräkningsbarhet och
beräkningsmodeller. Tids- och minneskomplexitet. (Kapitel 1-3)
F4-9
Komplexitetsklasser (P, NP, coNP, L, NL, PSPACE), reduktioner
och fullständiga problem (kapitel 7-10 i ordning samt
Theorem 19.1, ej 8.3),
F10-12
Algoritmer med slump (kapitel 11), approximationsalgoritmer och
approximerbarhet (kapitel 13).
F13-15
Fördjupning inom några områden, förslagsvis
parallell komplexitet och
interaktiva bevis. Kom gärna med egna förslag och
önskemål!
