In English

DD2446 Komplexitetsteori 6,0 hp

Complexity Theory

En avancerad kurs i datalogi som behandlar modern komplexitetsteori.

  • Utbildningsnivå

    Avancerad nivå

  • Kursnivå (A-D)

    D

  • Huvudområde

    Informationsteknik

  • Betygsskala

    A, B, C, D, E, FX, F

Kurstillfällen/kursomgångar

HT13 kplx13 för programstuderande

Lärandemål

Efter genomgången kurs ska en elev kunna

  • definiera grundläggande komplexitetsklasser såsom P, NP, PSPACE, L, NL, och NC.
  • formulera fullständiga problem för respektive komplexitetsklass och visa problem fullständiga med hjälp av reduktioner.
  • bevisa grundläggande satser om komplexitetsmått samt resonera om komplexitetsteoretiska begrepp.
  • läsa forskningsartiklar inom området i detaljnivå motsvarande att förstå bidraget i stort men inte nödvändigtvis förstå alla detaljer.

Kursens huvudsakliga innehåll

Det grundläggande målet inom komplexitetsteorin är att klassificera problem med avseende på hur mycket resurser som krävs för att lösa dem. Komplexitetsklasser är klasser av problem som i något avseende kräver "lika" mycket resurser för att lösa. De mest grundläggande resurserna som studeras är beräkningstid och minnesutrymme. Ett fullständigt problem för en komplexitetsklass är ett problem som kan ses som det svåraste inom klassen.

Följande områden behandlas: Komplexitetsklasserna L, NL, P, NP, PSPACE, etc. Reduktion och fullständighet. Cooks' sats. Approximerbarhet. Probabilistiska algoritmer. Interaktiva bevis (IP).

Behörighet

Rekommenderade förkunskaper

Motsvarande en av kurserna 2D1352/DD1352 Algoritmer, datastrukturer och komplexitet eller 2D1354/DD2354 Algoritmer och komplexitet.

Litteratur

Meddelas senast 4 veckor före kursstart på kursens hemsida. Läsåret 07/08 användes. S. Arora and B. Barak Computational Complexity: A Modern Approach, Cambridge University Press.

Examination

  • ÖVN1 - Inlämningsuppgifter, 6,0 hp, betygsskala: A, B, C, D, E, FX, F

I denna kurs tillämpas skolans hederskodex, se: http://www.kth.se/csc/student/hederskodex.

Krav för slutbetyg

Inlämningsuppgifter (ÖVN1; 6 hp).

Ges av

CSC/Datalogi

Kontaktperson

Jakob Nordström, http://www.csc.kth.se/~jakobn/

Examinator

Jakob Nordström

Övrig information

Kursen ges normalt på engelska om inte samtliga kursdeltagare kan svenska.
Kursen ges vartannat år.

Påbyggnad

Diskuteras med kursledaren.

Versionsinformation

Kursplan giltig från och med HT09.
Examinationsinformation giltig från och med HT07.