This page in English

Beräkningskomplexitetsteori, 3 hp

Kursuppgifter

Forskarutbildningsämne

  • Datavetenskap

Kursplan

Kursplan

Kontaktpersoner

  • Federico Pecora, Universitetslektor
    019 303319 This is an email address
  • Josefin Unander-Scharin, Utbildnings- och forskningsadministratör
    019 303909 This is an email address

Course content

This course examines the basic principles of complexity theory. It refreshes the basics of algorithm analysis (the analysis of resource usage of given algorithms) and of the principal formal properties of algorithms (correctness, completeness, optimality). Specifically, it gives an overview of the principal notations and methods for characterizing non-recursive and recursive algorithms. The course also provides an overview of the main issues problem complexity, that is, the study of the cost of solving interesting problems, given a suitable model of computation. Within this topic, we overview the principal models of computation used to characterize problem complexity (e.g., Turing Machines), their equivalence to computable functions (Church-Turing Thesis), and the principal problem complexity classes (NL, LOG, P, NP, PSPACE, EXPTIME, EXPSPACE).

Course information

Course period: May 16 - May 31, 2022. The course will be in form of virtual workshops with intense lectures as follows: 

May 16: 10:15-12:00, lunch break, 13:15-15:00

May 17: 10:15-12:00, lunch break, 13:15-15:00 

Study/assignment

May 30: 10:15-12:00, lunch break, 13:15-15:00

May 31: 10:15-12:00, lunch break, 13:15-15:00

How to sign up

Send an e-mail to the research administration no later than May 13, 2022: This is an email address