Hoppa till huvudinnehållet

DD2445 Komplexitetsteori 7,5 hp

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.

Kursomgångar saknas för tidigare och kommande terminer, samt för innevarande termin.
Rubriker med innehåll från kursplan DD2445 (VT 2019–) är markerade med en asterisk ( )

Innehåll och lärandemål

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

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.

Kursupplägg

Ingen information tillagd

Kurslitteratur och förberedelser

Särskild behörighet

Ingen information tillagd

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.

Utrustning

Ingen information tillagd

Kurslitteratur

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 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 - Övningsuppgifter, 7,5 hp, betygsskala: A, B, C, D, E, FX, F

Examinator beslutar, baserat på rekommendation från KTH:s handläggare av stöd till studenter med 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.

  • Ö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.

Övriga krav för slutbetyg

Inlämningsuppgifter (ÖVN1; 7,5 hp).

Möjlighet till komplettering

Ingen information tillagd

Möjlighet till plussning

Ingen information tillagd

Examinator

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 DD2445

Ges av

Huvudområde

Datalogi och datateknik

Utbildningsnivå

Avancerad nivå

Påbyggnad

Ingen information tillagd

Kontaktperson

Johan Håstad (johanh@kth.se)

Övrig information

I denna kurs tillämpas EECS hederskodex, se:
http://www.kth.se/eecs/utbildning/hederskodex