 | | |
| INFO0212-2 | Algorithmique et calculabilité
|
|
| Durée : | 30h Th, 30h Pr |
|
| Nombre de crédits : |
|
|
| Nom du professeur : | Emilie Charlier |
|
Langue(s) du cours :
|
| Langue française |
|
Organisation et évaluation :
|
| Enseignement au deuxième quadrimestre |
|
Contenus du cours :
|
| Dans ce cours, on développe des pistes liées à la question fondamentale suivante : tout problème (en admettant, au préalable, qu'il puisse être codé par un ordinateur) peut-il être résolu par un programme informatique ?
Pour formaliser cette question, les notions d'algorithme et de fonction calculable sont définies de façon rigoureuse au moyen des machines de Turing. On abordera principalement les thèmes suivants : fonctions primitives récursives, fonctions récursives, fonctions calculables, machines de Turing, machines universelles, thèse de Church-Turing, problèmes décidables, le problème de l'arrêt, réduction, langages décidables et acceptables, le théorème de Cook, la théorie de la complexité, problèmes NP-complets,...
Le cours se termine par la présentation de quelques problèmes NP-complets bien connus dans d'autres branches des mathématiques (optimisation, théorie des graphes, ...) comme par exemple, le problème du voyageur de commerce. |
|
Acquis d'apprentissage (objectifs d'apprentissage) du cours :
|
| Au terme de ce cours, l'étudiant maîtrisera les notions fondamentales issues de la théorie de la calculabilité et de la complexité ainsi que les preuves sous-jacentes. L'étudiant aura, en particulier, intégré les concepts de fonction calculable et de problème de décision. Il/elle sera capable d'expliquer, au moyen de réductions ad hoc, que certains problèmes ne présentent pas de solution algorithmique. Il/elle sera à même de construire des machines de Turing simples et de prouver la NP-complétude de problèmes classiques. |
|
Prérequis et corequis / Modules de cours optionnels recommandés :
|
| Aucune connaissance informatique n'est nécessaire. |
|
Activités d'apprentissage prévues et méthodes d'enseignement :
|
| Cours théorique avec "tableau et craies" en interaction avec les étudiants. Dans les séances d'exercices, les étudiants sont face à des exercices qu'ils doivent résoudre. |
|
Mode d'enseignement (présentiel ; enseignement à distance) :
|
| Le cours ("craie et tableau" en interaction avec les étudiants) est consacré principalement aux aspects théoriques des machines de Turing et de la complexité. Les séances de répétition permettent de présenter la résolution d'exercices mais surtout l'illustration et la concrétisation des concepts vus au cours. L'horaire des cours et des séances d'exercices sera communiqué en début d'année. |
|
Lectures recommandées ou obligatoires et notes de cours :
|
| Le cours se basera librement sur les notes de cours de M. Rigo, année académique 2009-2010. Celles-ci sont disponibles en ligne sur www.discmath.ulg.ac.be Quelques sources d'information possibles :
- R. Cori, D. Lascar, Logique Mathématique, Dunod (1993).
- M. R. Garey, D. S. Johnson, Computers and Intractability, A guide to the Theory of
NP-Completeness, W. H. Freeman and Company, (1979).
- H. R. Lewis, C. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, (1981).
- A. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, Proc. London Math. Society. Second Series 42, 230-265, (1936).
- P. Wolper, Introduction à la calculabilité, Dunod (2006).
|
|
Modalités d'évaluation et critères :
|
| L'examen, en session, comporte une partie orale et une partie écrite. L'examen oral porte sur la théorie et ses applications directes (on pourra par exemple demander de résoudre au tableau ou sur feuille un petit exercice). L'examen écrit porte sur la matière des répétitions. |
|
Stage(s) :
|
| |
|
Remarques organisationnelles :
|
| Des compléments d'information sont disponibles sur
http://www.discmath.ulg.ac.be/ |
|
Contacts :
|
| Émilie Charlier
Institut de Mathématique (B37) - Grande Traverse 12 - Sart Tilman, 4000 Liège
Tél. : (04) 366.93.84 - E-mail : echarlier@ulg.ac.be |
|
|
| |
