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.

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.

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.

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.

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

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

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

Johan Håstad

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

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