Kursplan för läsåret 2001/2002
BERÄKNINGSKOMPLEXITETEDA152
Computational Complexity

Poäng: 5.0 Betygskala: TH. Valfri för: D4. Kursansvarig: Universitetslektor Rolf Karlsson, Rolf.Karlsson@cs.lth.se. Förkunskapskrav: Godkänt betyg i EDA025 Algoritmer och datastrukturer.. Prestationsbedömning: Slutbetyget baseras på dels en skriftlig tentamen dels fem inlämningsuppgifter. Webbsida: http://www.cs.lth.se Övrigt: Kursen ges i samarbete med Datavetenskap, mat. nat. fak. Jfr EDA153: 4,0 poäng erhålls när också EDA140 Formella språk och automater ingår i examen.

Mål:
Att ge en introduktion till beräkningsbarhet och komplexitetsteori, som behandlar följande centrala frågor: Vad kan beräknas? Varför är vissa problem beräkningsmässigt svåra och andra lätta?

Innehåll:
Oavgörbarhet. Komplexitetsklasser. Reduktioner. NP-kompletta problem. Approximationsalgoritmer. Polynomiska hierarkin. Polynomiskt utrymme och vinnande spelstrategier. Interaktiva bevis.

Litteratur:
Papadimitriou C. H.: Computational Complexity. Addison-Wesley, 1994.