| TDDB45 | BERÄKNINGSBARHET OCH 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 | ||
| Mål: Att presentera de viktigaste resultaten inom beräkningsbarhet och komplexitetsteori. Förkunskaper: TATM90 Diskret matematik och logik samt någon kurs i konstruktion och analys av algoritmer och datastrukturer.Organisation: Teorin presenteras på föreläsningar. Inlämningsuppgifter syftar till att fördjupa förståelsen av teorin. Kursen ges endast vartannat läsår (första gången läsåret 1995/96).Kursinnehåll: Grundläggande beräkningsbarhet, komplexitetsklasser (P, NP, och högre), komplexitetsklasser map minnesbehov, approximerbarhet, probabilistiska algoritmer och komplexitetsklasser, interaktiva bevissystem, parallell komplexitetsteori.Kurslitteratur: Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice-Hall, 1994. | ||
| UPG1 | Obligatoriska inlämningsuppgifter | |