Contenu

• 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, automates,
• Logique des propositions
  
• Théorie de la complexité : classes de complexité, NP-complétude, théorème de Cook, résolution de problèmes NP-complets.

A l'issue de cet enseignement, les étudiants seront en mesure de

• reconnaître, comprendre et identifier les limites du traitement de l’information par un ordinateur;
• comprendre les fondements, les différences et les similitudes des principaux modèles de calculabilité;
• reconnaître, identifier et appréhender les problèmes non calculables ainsi que les problèmes intrinsèquement complexes.

Yves Deville est professeur à l’université UCLouvain, où il mène des recherches dans les domaines de l'intelligence artificielle, de la programmation par contrainte et de l'optimisation. Il est également membre de l'École Polytechnique de Louvain et de l'Institut de recherche ICTEAM (Institute for Information and Communication Technologies, Electronics and Applied Mathematics).  Il enseigne la calculabilité depuis plus de 20 ans.