BERÄKNINGSKOMPLEXITET | EDA 152 |
Computational Complexity
Antal poäng: 5.0. Valfri för: D4. Kursansvarig: Rolf Karlsson Förkunskapskrav: godkänt betyg i EDA 025 Algoritmer och datastrukturer. Prestationsbedömning: Slutbetyget baseras på dels en skriftlig tentamen dels fem inlämningsuppgifter. Övrigt: Kursen ges i samarbete med Datalogi och numerisk analys, mat. nat. fak.
Jfr EDA 153, det lägre poängtalet erhålls när också EDA 140 Formella språk och automater ingår i examen.
Innehåll
Syfte. Att ge kunskap om den matematisk-logiska grund som utvecklats för förståelse och analys av datorers möjligheter och begränsningar vid problemlösning. Komplexitet betraktas som samspelet mellan beräkning (komplexitetsklasser) och tillämpningar (problem).
Turingmaskiner och oavgörbarhet. Komplexitetsklasser. Reduktioner och fullständighet. NP-fullständiga problem. Randomiserad beräkning. Interaktiva bevis. Approximationsalgoritmer. Polynomiska hierarkin. PSPACE och spelkomplexitet.
Litteratur
Papadimitriou, C. H.: Computational Complexity. Addison-Wesley 1994.