AccueilMasterInformatiqueEnseignementsComplexity and computability

Master InformatiqueUE Complexity and computability

Contenu

When we define neatly and consider the set of « algorithms » (Turing machines) and the set of « things an algorithm may compute » (functions), we can notice, thanks to an argument from the 19th century (Cantor's diagonal), that there are strictly more « things to compute » than « algorithms to compute them ». Then what are these things a computer cannot compute ?

This course will teach the basics of computational complexity and answer to the following questions : within the set of computable things, how to define the hardness of a « thing to compute » (aka problem) ? When defined neatly (again some maths), these questions raise fundamental open problems of our century, such as the famous 1,000,000 usd question mark : does P equal NP ?

You will also be given the tools to say : « this problem is reasonably solvable on a computer » (in P) or « this one is not » (NP-hard).

Langue utilisée

Langue principale utilisée par cet enseignement : Anglais.

Volume des enseignements

  • Cours magistraux : 12 heures
  • Travaux dirigés : 12 heures
  • Travaux pratiques : 12 heures

Code APOGÉE

SCMAU09L.

Les formations qui utilisent cet enseignement