KTH

Skolan för datavetenskap och kommunikation

   
   

     
  arrow rigth  
     
     
     
     
     
     
     
     

 

   

2D1446 Komplexitetsteori

KursPM med schema

Ett officiellt kursPM delas ut separat.

Nedan hittar du information om

Schema Kursledare Vem får läsa kursen?
Mål Kurslitteratur Studentexpedition
Kursuppläggning Examination

Ändringar i kursPM kommer att meddelas under nyheter.


Schema

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.

 F ti 15-17 v 12-14,18-21   E52 
 F on 10-12 v 12-14,18-20   D34 
 F on 10-12 v 21   E3 
 F fr 13-15 v 12   E3 
 F fr 13-15 v 13   E2 

topp>>

Kursledare

Mikael Goldmann, <migo@nada.kth.se>, 790 6813, rum 1444, mottagningstid: måndagar 10.00-11.00 eller enligt överenskommelse.

Mikael nås enklast via epost.

topp>>

Vem får läsa kursen

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.

topp>>

Kursens mål

Kursens mål är att

  • ge en utförlig orientering om modern komplexitetsteori
för att studenterna ska
  • förstå begreppen komplexitetsklasser och fullständighetsproblem för sådana,
  • kunna bevisa påståenden inom komplexitetsteorin, t.ex. fullständighet hos ett problem,
  • kunna läsa (relativt enkla) forskningsartiklar inom området komplexitetsteori.

topp>>

Kurslitteratur

Bok

  • C. H. Papadimitriou: Computational complexity, Addison Wesley, 1994.

topp>>

Studentexpedition och Delfi

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.

Kursuppläggning

En preliminär planering av kursen är

F1-3 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!

topp>>

Examination

Examinationen består av tre omgångar inlämningsuppgifter som redovisas både skriftligt och muntligt.

För all examination vid Nada tillämpas en hederskodex.

Förändringar sedan förra kursomgången

Muntliga redovisningar är individuella.

topp>>

 


 
Sidansvarig: Mikael Goldmann <migo@nada.kth.se>
Uppdaterad: 2004-06-04