Calculabilité [ LINGI1123 ]
4.0 crédits ECTS
30.0 h + 30.0 h
2q
Enseignant(s) |
Deville Yves ;
|
Langue d'enseignement: |
Français
|
Lieu de l'activité |
Louvain-la-Neuve
|
Ressources en ligne |
> http://www.icampus.ucl.ac.be/claroline/course/index.php?cid=INGI1123
|
Préalables |
- Algorithmique et structures de données avancées (p.e. SINF1121)
- Raisonnement en mathématiques discrètes (p.e. INGI1101)
|
Thèmes abordés |
- 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.
|
Acquis d'apprentissage |
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
|
Modes d'évaluation des acquis des étudiants |
- Examen écrit (Septembre, examen oral)
- 2 évaluations formatives (qui n'interviennent pas dans la note finale) durant le quadrimestre
|
Méthodes d'enseignement |
- cours magistraux
- exercices encadré par un assistant
|
Contenu |
- 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é
|
Bibliographie |
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
|
Cycle et année d'étude |
> Bachelier en sciences de l'ingénieur, orientation ingénieur civil
> Année d'études préparatoire au master en sciences informatiques
> Master [120] : ingénieur civil en mathématiques appliquées
> Bachelier en sciences informatiques
> Bachelier en sciences mathématiques
|
Faculté ou entité en charge |
> INFO
|
<<< Page précédente
|