DD2445 Komplexitetsteori 7,5 hp

Complexity Theory

Datorer finns överallt idag – på jobbet, i våra bilar, i våra vardagsrum och i våra fickor – och har ändrat vår tillvaro mer än vi kunnat drömma om. Och ändå är dessa tekniska underverk när det kommer till kritan förvånansvärt enkla och dumma: allt de kan göra är att mekaniskt skyffla runt ettor och nollor. Hur kraftfulla är egentligen sådana automatiska beräkningsmaskiner? Och var går gränsen för vad man kan åstadkomma med rent mekaniska beräkningar?

Komplexitetsteori gör det möjligt att översätta dessa djupa och fascinerade filosofiska frågor till exakta matematiska resonemang. Varje uppgift som i princip kan lösas med hjälp av dator, dvs genom att mekaniskt följa en given lista med enkla matematiska instruktioner, definierar ett beräkningsproblem. Inom komplexitetsteori fokuserar man på att klassificera sådana beräkningsproblem med avseende på hur svåra de är och på att relatera olika klasser av problem till varandra. Målet är att förstå potentialen hos datorberäkningar men också – och framför allt – vilka begränsningar som finns för vad som kan lösas med datorer, eller av automatiserade beräkningsprocesser mer generellt. Att ett problem är svårt betyder intuitivt att det kräver mycket stora resurser för att lösas oavsett med vilken metod man försöker angripa det (dvs oavsett vilken algoritm som används). Formellt fångar man denna intuition genom att definiera precisa matematiska modeller för beräkningsmaskiner och visa satser om hur mycket resurser som dessa maskiner behöver för att lösa problemet mätt i t.ex. körtid, minnesåtgång, parallellitet, kommunikationsbandbredd, et cetera.

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. Avsikten är att täcka in komplexitetsteori ganska brett, men ändå med viss tyngdpunkt på delområden där Teorigruppen på KTH har lämnat viktiga bidrag till forskningen.

  • Utbildningsnivå

    Avancerad nivå
  • Huvudområde

    Datalogi och datateknik
  • Betygsskala

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

Kurstillfällen/kursomgångar

HT19 kplx19 för programstuderande

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.
  • För högsta betyg: 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

Datorer finns överallt idag – på jobbet, i våra bilar, i våra vardagsrum och i våra fickor – och har ändrat vår tillvaro mer än vi kunnat drömma om. Och ändå är dessa tekniska underverk när det kommer till kritan förvånansvärt enkla och dumma: allt de kan göra är att mekaniskt skyffla runt ettor och nollor. Hur kraftfulla är egentligen sådana automatiska beräkningsmaskiner? Och var går gränsen för vad man kan åstadkomma med rent mekaniska beräkningar?

Komplexitetsteori gör det möjligt att översätta dessa djupa och fascinerade filosofiska frågor till exakta matematiska resonemang. Varje uppgift som i princip kan lösas med hjälp av dator, dvs genom att mekaniskt följa en given lista med enkla matematiska instruktioner, definierar ett beräkningsproblem. Inom komplexitetsteori fokuserar man på att klassificera sådana beräkningsproblem med avseende på hur svåra de är och på att relatera olika klasser av problem till varandra. Målet är att förstå potentialen hos datorberäkningar men också – och framför allt – vilka begränsningar som finns för vad som kan lösas med datorer, eller av automatiserade beräkningsprocesser mer generellt. Att ett problem är svårt betyder intuitivt att det kräver mycket stora resurser för att lösas oavsett med vilken metod man försöker angripa det (dvs oavsett vilken algoritm som används). Formellt fångar man denna intuition genom att definiera precisa matematiska modeller för beräkningsmaskiner och visa satser om hur mycket resurser som dessa maskiner behöver för att lösa problemet mätt i t.ex. körtid, minnesåtgång, parallellitet, kommunikationsbandbredd, et cetera.

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. Avsikten är att täcka in komplexitetsteori ganska brett, men ändå med viss tyngdpunkt på delområden där Teorigruppen på KTH har lämnat viktiga bidrag till forskningen.

Behörighet

Rekommenderade förkunskaper

Kursen är öppen för alla studenter men den huvudsakliga målgruppen är magisterstudenter i datavetenskap och matematik. Kursen är också lämpligför doktorander i datavetenskap eller matematik som inte tidigare har tagit kurser i beräkningskomplexitet. Du behöver ha läst DD1352 Algoritmer, datastrukturer och komplexitet eller DD2352 Algoritmer och komplexitet eller motsvarande kurs på annat universitet och bör kunna materialet väl. Du behöver också matematisk mognad och beredskap för att kursen kommer att vara krävande (men också rolig!). Föreläsningarna ges på engelska.

Litteratur

Kurslitteratur meddelas senast 4 veckor före kursstart på kursens hemsida. Läsåret 13/14 användes boken ”Computational Complexity: A Modern Approach” av Sanjeev Arora and Boaz Barak utgiven av Cambridge University Press. Delar av kursen baseras också på forskningsartiklar.

Examination

  • ÖVN1 - Övningsuppgifter, 7,5, betygsskala: A, B, C, D, E, FX, F
  • ÖVN1 - Inlämningsuppgifter, 7,5, 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; 7,5 hp).

Ges av

EECS/Datavetenskap

Kontaktperson

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

Examinator

Johan Håstad <johanh@kth.se>

Versionsinformation

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