 | |
| INFO0212-2 | Algorithmique et calculabilité
 |
|
| Durée : | 20h Th, 20h Pr |
|
| Crédits/ECTS : |
|
|
| Titulaire(s) : | Michel Rigo |
|
| Langue : | Langue française |
|
| Aperçu général : | 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. |
|
| Objectif du cours : | Présenter aux étudiants les notions fondamentales de la calculabilité et de la complexité. On y définit de manière rigoureuse la notion de fonction calculable. Il est également intéressant de montrer que certains problèmes ne présentent pas de solution algorithmique. |
|
| Pré-requis : | Maîtriser les concepts de base de la théorie des graphes. Aucune connaissance informatique n'est nécessaire. |
|
| Organisation : | Le cours 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. |
|
| Notes de cours : | Des notes seront distribuées aux étudiants lors du premier cours. |
|
| Evaluation : | L'examen en session comporte uniquement une partie orale. Cet examen porte sur la théorie et ses applications directes (on pourra par exemple demander de résoudre au tableau un petit exercice). La matière de l'examen et les modalités d'interrogation seront précisées par un affichage aux valves. |
|
| Contacts : | M. Rigo
Institut de Mathématique (B37) - Grande Traverse 12 - Sart Tilman, 4000 Liège
Tél. : (04) 366.94.87 - E-mail : M.Rigo@ulg.ac.be |
|
| Remarques : | Des compléments d'information (en particulier, les notes de cours) sont disponibles sur
http://www.discmath.ulg.ac.be/ |
|
|
| |
