DD3445 Komplexitetsteori 7,5 hp

Complexity Theory

  • Utbildningsnivå

    Forskarnivå
  • Huvudområde

  • Betygsskala

    P, F

Det finns inget planerat kurstillfälle.

Lärandemål

Efter avslutad kurs ska studenten kunna:

• Definiera och motivera grundläggande begrepp inom komplexitetsteori och förklara hur de hänger ihop.

• Beskriva några av de viktigaste resultaten inom modern komplexitetsteori.

• Använda etablerade verktyg och metoder inom komplexitetsteori för att bevisa grundläggande satser och självständigt lösa problem som kan angripas med dessa metoder.

• Presentera komplexitetsteoretiska argument med matematisk stringens muntligen och skriftligen.

• Läsa och förstå en forskningsartikel inom området komplexitetsteori och visa läsförståelse genom att ge en muntlig presentation av artikeln.

Kursens huvudsakliga innehåll

Målet med denna kurs att ge en introduktion till komplexitetsteori, presentera en översikt över några av de viktigaste forskningsresultaten, och diskutera några av de öppna frågor som studeras intensivt inom området idag.

Behörighet

Rekommenderade förkunskaper

DD1352 eller DD2352 eller motsvarande kurser på andra universitet.

Litteratur

Computational Complexity: A Modern Approach av Sanjeev Arora och Boaz Barak

Examination

  • EXA1 - Examination, 7,5, betygsskala: P, F

Krav för slutbetyg

Inlämniingsuppgifter och muntlig presentation.

Ges av

EECS/Teoretisk datalogi

Examinator

Jakob Nordström <jakobn@kth.se>

Johan Håstad <johanh@kth.se>

Versionsinformation

Kursplan gäller från och med HT2015.
Examinationsinformation gäller från och med VT2019.