Prerequisite/Recommended prerequisite for participation in the module

Content, progress and pedagogy of the module

Learning objectives

Knowledge

Students should achieve knowledge on the following theories and methods:

Computability:

• deterministic and nondeterministic Turing machines; decidable and recognizable languages ​​and their properties: Church-Turing thesis
• acceptance problem for Turing machines; other undecidable problems for Turing machines; reductions and their properties
   

Complexity theory:

• time complexity of deterministic and nondeterministic Turing machines; time complexity classes, polynomial reductions and their uses; NP-completeness; satisfiability problem (SAT); other NP-complete problems
• space complexity of deterministic and nondeterministic Turing machines; space complexity classes, the relationship between time and space complexity

The course will also involve one or more advanced topics that can be e.g. other models of computation, other results on undecidability or results about further complexity classes.

Skills

• the ability to explain course concepts precisely using the terminology and notations of the discipline for important achievements in the theory of computability and computational complexity, and how and to what extent these results can be used to classify computational problems
• the ability to make use of the necessary writing skills in these contexts

Competences

• be able to apply concepts and techniques from the theory of computability and computational complexity for the analysis of computational problems

Type of instruction

The teaching is organized according to the general teaching methods for the education, cf. chapter 3

Extent and expected workload

It is expected that the student uses 30 hours per ECTS, which for this activity means 150 hours

Exam

Exams

Additional information

Contact: The Study board for Computer Science at cs-sn@cs.aau.dk or 9940 8854