Recommended prerequisite for participation in
the module
The module adds to knowledge obtained in Syntax and Semantics
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
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
See the general description of the types of instruction
described in § 17.
Extent and expected workload
It is expected that the student uses 30 hours per ECTS, which
for this activity means 150 hours
Exam
Exams
Name of exam | Computability and Complexity |
Type of exam | Written or oral exam |
ECTS | 5 |
Assessment | 7-point grading scale |
Type of grading | External examination |
Criteria of assessment | The criteria of assessment are stated in the Examination
Policies and Procedures |
Additional information
Contact: The Study board for Computer Science at
cs-sn@cs.aau.dk or 9940 8854