Vous êtes ici

  1. Accueil
  2. Calculabilité

Calculabilité

Calculabilité

En pratique :

Volume horaire de cours : 8
Volume horaire global de TD : 8
Volume horaire global de TP : 4
Langue principale : français

Compétences à acquérir

Donner des notions à propos de la calculabilité et la complexité des problèmes, faire la différence avec la complexité des algorithmes et donner de premiers outils pour étudier et contourner cette complexité.


Modalités d’organisation et de suivi

Description
Le cours se décompose en deux parties : l'une sur la calculabilité, l'autre sur la théorie de la complexité algorithmique des problèmes.
Dans la première partie, nous introduisons la décidabilité en montrant qu'elle est indépendante de l'artefact "ordinateur" en utilisant les machines de Turing. La méthode de réduction est proposée pour la preuve de la décidabilité ou de l'indécidabilité d'un problème. Des exemples formels et pratiques de problèmes indécidables et de fonctions non-calculables sont donnés.
Dans une deuxième partie, nous nous intéressons aux problèmes décidables et nous proposons une sensibilisation aux soucis liés à la complexité des problèmes au travers d'exemples concrets de temps de calculs rédhibitoires. Nous introduisons les notions de classes de complexité des problèmes (P, NP, PSPACE), et en particulier la NP-complétude et la méthode de réduction polynomiale d'un problème à un autre. A nouveau, des preuves sont proposées sur des exemples concrets représentatifs des préoccupations de l’Ingénieur.
La partie travaux pratiques sera l’occasion d’expérimenter des heuristiques génériques (algorithmes génétiques, recherche Tabou, recuit simulé, etc) sur un problème NP-complet.


Bibliographie, lectures recommandées

[1] Introduction a` la cal culabilite´, Pierre Wolper, InterEditions, 1991
[2] Computational Complexity, Christos H. Papadimitriou, Addison Wesley, 1994
[3] Computers and Intractability - A Guide to the Theory of NP-completeness, M. R. Garey and D. S. Johnson, Editor : W. H. Freeman and Company, 1979
[4] Introduction to the theory of computation, Michael Sipser, PWS Publishing Company, 1997
[5] Logique, Informatique et Paradoxes, Jean-Paul Delahaye, Bibliothe`que Pour la Science, Diffusion Belin.


Pré-requis

Pré-requis obligatoires

Quelques notions de théorie des langages (symbole, mot, langage, automate à états fini), base de complexité des algorithmes.