 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
Autres crédits de l'activité dans les programmes
|
FSA13BA
|
Troisième année de bachelier en sciences de l'ingénieur, orientation ingénieur civil
|
(4 crédits)
| |
|
MAP22
|
Deuxième année du programme conduisant au grade d'ingénieur civil en mathématiques appliquées
|
(4 crédits)
| |
|
MATH22/G
|
Deuxième licence en sciences mathématiques
|
(4 crédits)
|
Obligatoire
|
|
SINF13BA
|
Troisième année d'études de bachelier en sciences informatiques
|
(4 crédits)
| |
|
SINF1PM
|
Année d'études préparatoires au master en sciences informatiques (60 et 120)
|
(4 crédits)
| |
|
