Poäng: 5.0 Betygskala: TH Valfri för: D4 Kursansvarig: Rolf Karlsson Förkunskapskrav: godkänt betyg i EDA025 Algoritmer och datastrukturer. Prestationsbedömning: Slutbetyget baseras på dels en skriftlig tentamen dels fem inlämningsuppgifter. Övrigt: Kursen ges i samarbete med Datavetenskap, mat. nat. fak.

OBS! 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.