 Objectifs (en termes de compétences)
- 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
Objet de l'activité (principaux thèmes à aborder)
- 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.
Résumé : Contenu et Méthodes
voir "Objet de l'activité"
Autres informations (Pré-requis, Evaluation, Support, ...)
- Pré-requis:
LINF2121 Algorithmique et structures de données - P. Dupont
- Références
Ouvrage(s) recommandé(s)
(1) P. Wolper, "Introduction à la calculabilité" , InterEditions, 1991.
(2) M. Sipser, "Introduction to the Theory of Computation" , WS Publishing Company, 1997.
Pour plus d'informations :
http://www.ucl.ac.be/etudes/cours/ingi2123.htm
|
