Computability and Complexity

2022/2023

Prerequisite/Recommended prerequisite for participation in the module

The module builds on knowledge gained from the courses: The theoretical basis of Computer Science, Algorithmics and Data Structure as well as Syntax and Semantics.

Content, progress and pedagogy of the module

Disclaimer.
This is an English translation of the module. In case of discrepancy between the translation and the Danish version, the Danish version of the module is valid.

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

The teaching is organized in accordance with the general teaching methods for the education, cf. section 17.

Extent and expected workload

The student is expected to spend 27.5 hours per ECTS, which for this activity means 137.5 hours.

Exam

Exams

Name of examComputability and Complexity
Type of exam
Written or oral exam
ECTS5
Assessment7-point grading scale
Type of gradingExternal examination
Criteria of assessmentThe criteria of assessment are stated in the Examination Policies and Procedures

Additional information

Contact: Study Board for Computer Science via cs-sn@cs.aau.dk or 9940 8854

Facts about the module

Danish titleBeregnelighed og kompleksitet
Module codeDSNDATB613
Module typeCourse
Duration1 semester
SemesterSpring
ECTS5
Language of instructionDanish
Empty-place SchemeYes
Location of the lectureCampus Aalborg
Responsible for the module

Organisation

Study BoardStudy Board of Computer Science
DepartmentDepartment of Computer Science
FacultyTechnical Faculty of IT and Design