Complexité et Calculabilité

3 ECTS - 12 CM / 18 TD / 0 TP

Description

• Dénombrabilité, procédé diagonal de Cantor, alphabets, langages.
• Modèles de calcul, machines de Turing, machines à registres.
• Calculabilité. Décidabilité. Problème de l’arrêt.
• Complexité, classes P, NP, problèmes NP-complets, réductions polynomiales, problème SAT.

Objectifs

• Evaluer les performances et analyser des programmes.