| TDDB41 | Komplexitetsteori, 3 poäng /Computability and Complexity Theory/ För: C3, C4 | |
| Utbildningsområde: Teknik Ämnesgrupp: Datalogi | ||
| Fördjupningsnivå: D | ||
| Klassning för datavetenskaplig examen: Datavetenskap, datalogi. | ||
| Mål: Att presentera några av de viktigaste resultaten inom komplexitetsteori. Förkunskaper: TATM 90 Diskret matematik och logik samt någon kurs i konstruktion och analys av algoritmer och datastrukturer.Grundläggande kunskaper i sannolikets- och optimeringslära.Organisation: Materialet presenteras av kursledare och deltagare under föreläsningarna. Kursinnehåll: Grundläggande beräkningsbarhet, komplexitetsklasser (P, NP, och högre), komplexitetsklasser map minnesbehov, approximerbarhet och probabilistiska algoritmer.Kurslitteratur: Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice-Hall, 1994. | ||
| UPG1 | Obligatoriska inlämningsuppgifter, 3 p. | |
Undervisningsspråk är svenska.