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

Programmes proposant cette activité

Autres crédits de l'activité dans les programmes