Computability and complexity

School / Prep
ENSEIRB-MATMECA

Internal code

EI8IF228

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

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

Initial assessment / Main session

Type of assessment	Nature of assessment	Duration (in minutes)	Number of tests	Evaluation coefficient	Eliminatory evaluation mark	Remarks
Integral Continuous Control	Continuous control			1

Computability and complexity

School / Prep

Internal code

Description

Teaching hours

Mandatory prerequisites

Syllabus

Assessment of knowledge

Initial assessment / Main session