School / Prep
ENSEIRB-MATMECA
Internal code
EIN8-IFON1
Description
This module introduces the main concepts of computability and complexity.
Plan
Computability concepts
Formal definition: words, language, problem
Turing machine, Universal TM
Existence of non-computable functions
Examples of undecidable problems
Principle of reduction
Complexity classes
Examples of NP-complete problems
Teaching hours
- CMLectures10,66h
- TDTutorial16h
- TIIndividual work10h
Mandatory prerequisites
Algorithms, automata and complexity.
Syllabus
Notions of computability
Formal definition: words, language, problem
Turing machine, universal TM
Existence of non-computable functions
Examples of undecidable problems
Reduction principle
Complexity classes
Examples of NP-complete problems
Assessment of knowledge
Initial assessment / Main session - Tests
Type of assessment | Type of test | Duration (in minutes) | Number of tests | Test coefficient | Eliminatory mark in the test | Remarks |
---|---|---|---|---|---|---|
Integral Continuous Control | Continuous control | 1 |