Hoppa till huvudinnehållet
Inför kursvalDD2446 Komplexitetsteori 6,0 hpAdministrera Om kursen

En avancerad kurs i datalogi som behandlar modern komplexitetsteori.

Kursomgångar saknas för tidigare och kommande terminer, samt för innevarande termin.
* Informationen tillhör Kursplan DD2446 (HT 2009–)

Innehåll och lärandemål

Kursinnehå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).

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.

Kursupplägg

Ingen information tillagd

Kurslitteratur och förberedelser

Särskild behörighet

Ingen information tillagd

Rekommenderade förkunskaper

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

Utrustning

Ingen information tillagd

Kurslitteratur

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 och slutförande

När kurs inte längre ges har student möjlighet att examineras under ytterligare två läsår.

Betygsskala

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

Examination

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

Examinator beslutar, baserat på rekommendation från KTH:s samordnare för funktionsnedsättning, om eventuell anpassad examination för studenter med dokumenterad, varaktig funktionsnedsättning.

Examinator får medge annan examinationsform vid omexamination av enstaka studenter.

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

Övriga krav för slutbetyg

Inlämningsuppgifter (ÖVN1; 6 hp).

Möjlighet till komplettering

Ingen information tillagd

Möjlighet till plussning

Ingen information tillagd

Examinator

Profile picture Jakob Nordström

Etiskt förhållningssätt

  • Vid grupparbete har alla i gruppen ansvar för gruppens arbete.
  • Vid examination ska varje student ärligt redovisa hjälp som erhållits och källor som använts.
  • Vid muntlig examination ska varje student kunna redogöra för hela uppgiften och hela lösningen.

Ytterligare information

Kurswebb

Ytterligare information om kursen kan hittas på kurswebben via länken nedan. Information på kurswebben kommer framöver flyttas till denna sida.

Kurswebb DD2446

Ges av

CSC/Datalogi

Huvudområde

Datalogi och datateknik, Informations- och kommunikationsteknik, Informationsteknik

Utbildningsnivå

Avancerad nivå

Påbyggnad

Diskuteras med kursledaren.

Kontaktperson

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

Övrig information

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