Calculabilité [ LINGI1123 ]

• Algorithmique et structures de données avancées (p.e. SINF1121)
• Raisonnement en mathématiques discrètes (p.e. INGI1101)

• Théorie de la calculabilité : problèmes et algorithmes, fonctions calculables et non calculables, réduction, classes de problèmes indécidables (théorème de Rice) , théorème du point fixe, thèse de Church-Turing,
• Principaux modèles de calculabilité : machine de Turing, fonctions récursives, lambda-calcul, automates,
• Théorie de la complexité : classes de complexité, NP-complétude, théorème de Cook, résolution de problèmes NP-complets.

Les étudiants ayant suivi avec fruit ce cours seront capables de

• reconnaître, expliquer et identifier les limites du traitement de l'information par un ordinateur;
• expliquer et exploiter à bon escient les principaux modèles de calculabilité en explicitant  leurs fondements, leurs différences et leurs similitudes;
• reconnaître, identifier et appréhender les problèmes non calculables ainsi que les problèmes intrinsèquement complexes.

Les étudiants auront développé des compétences méthodologiques et opérationnelles.  En particulier, ils auront développé leur capacité à

• avoir un regard critique sur les performances et la capacité des systèmes informatiques

• Examen écrit (Septembre, examen oral)
• 2 évaluations formatives (qui n'interviennent pas dans la note finale) durant le quadrimestre

• cours magistraux
• exercices encadré par un assistant

• Introduction
• Concepts : demonstration et raisonnement, ensembes, diagonalisation de Cantor
• Calculabilité: résultats fondamentaux
• Modèles de calculabilité
• Analyse de la thèse de Church-Turing
• Introduction à la complexité algorithmique
• Classes de complexité

Transparents en ligne

Livres de référence

• O. Ridoux, G. Lesventes.  Calculateurs, calculs, calculabilité. Dunod  Collection Sciences Sup, 224 pages, 2008.
• P. Wolper Introduction à la calculabilité 2nd Edition, Dunod, 2001.
• Sipser M. Introduction to the Theory of Computation PWS Publishing Company, 1997