d'enseignement
en ligne
Au sein du programme SINF1BA : LSINF1101
Au sein du programme FSA1BA : LFSAB1101, LFSAB1102, LFSAB1202, LFSAB1202, LFSAB1301, LFSAB1401
Le(s) prérequis de cette Unité d’enseignement (UE) sont précisés à la fin de cette fiche, en regard des programmes/formations qui proposent cette UE.- 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.
d'apprentissage
Eu égard au référentiel AA du programme « Bachelier ingénieur civil », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :
- AA1.1, AA1.2
- AA2.4
Eu égard au référentiel AA du programme « Bachelier en sciences informatiques », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :
- S1.I3, S1.G1
- S2.2
Les étudiants ayant suivi avec fruit ce cours seront capables de
- reconnaître, expliquer et identifier les limites du traitement de l'information par un ordinateur;
- expliquer et exploiter à bon escient les principaux modèles de calculabilité en explicitant leurs fondements, leurs différences et leurs similitudes;
- reconnaître, identifier et appréhender les problèmes non calculables ainsi que les problèmes intrinsèquement complexes.
Les étudiants auront développé des compétences méthodologiques et opérationnelles. En particulier, ils auront développé leur capacité à
- avoir un regard critique sur les performances et la capacité des systèmes informatiques
La contribution de cette UE au développement et à la maîtrise des compétences et acquis du (des) programme(s) est accessible à la fin de cette fiche, dans la partie « Programmes/formations proposant cette unité d’enseignement (UE) ».
des acquis des étudiants
- Examen écrit (Septembre, examen oral)
- cours magistraux
- exercices encadré par un assistant
- Introduction
- Concepts : demonstration et raisonnement, ensembes, diagonalisation de Cantor
- Calculabilité: résultats fondamentaux
- Modèles de calculabilité
- Analyse de la thèse de Church-Turing
- Introduction à la complexité algorithmique
- Classes de complexité
Transparents en ligne
Livres de référence
- O. Ridoux, G. Lesventes. Calculateurs, calculs, calculabilité. Dunod Collection Sciences Sup, 224 pages, 2008.
- P. Wolper Introduction à la calculabilité 2nd Edition, Dunod, 2001.
- Sipser M. Introduction to the Theory of Computation PWS Publishing Company, 1997
Préalables:
- Algorithmique et structures de données (p.e. SINF1121)
en charge
Programmes / formations proposant cette unité d'enseignement (UE)
d'apprentissage
