• Your selection is empty.

    Register the diplomas, courses or lessons of your choice.

Computability and complexity

  • 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


Read more

Teaching hours

  • CMLectures10,66h
  • TDTutorial16h
  • TIIndividual work10h

Mandatory prerequisites

Algorithms, automata and complexity.

Read more

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

Read more

Assessment of knowledge

Initial assessment / Main session - Tests

Type of assessmentType of testDuration (in minutes)Number of testsTest coefficientEliminatory mark in the testRemarks
Integral Continuous ControlContinuous control1