Programme d'études 2002-2003 > FSA > INGI2123

• Objectifs
• Cahier des charges
• Autres informations du cahier des charges
• Programmes proposant cette activité
• Valeurs ECTS de l'activité

Objectifs

* 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

Cahier des charges

* 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.

Autres informations du cahier des charges

* pré-requis:
LINF2121 Algorithmique et structures de données - P. Dupont

* Références
Ouvrage(s) recommandé(s)
P. Wolper, "Introduction à la calculabilité" , InterEditions, 1991.
M. Sipser, "Introduction to the Theory of Computation" , WS Publishing Company, 1997.

* Remarque: voir aussi : http://www.ucl.ac.be/etudes/cours/ingi2123.html

Le cours INGI2123 est mentionné dans les programmes suivants :

Valeurs ECTS de l'activité

Programme d'études 2002-2003 > FSA > INGI2123

Recherche - Aide - Renseignements généraux

[UCL] [Site Web Facultaire] [Pointeurs utiles]

Responsable : Jean-Louis Marchand
Contact : secretaire@fsa.ucl.ac.be