Calculabilité [T8IS333M]

Calculabilité [T8IS333M]

En pratique

Nature
Elément constitutif
Volume horaire de TP
4
Volume horaire de TD
8
Volume horaire de CM
8
Volume horaire de travail personnel
14
Langue d'enseignement
Français

Description du contenu de l'enseignement

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é.


Give notions about the computability and complexity of problems, make the difference with the complexity of algorithms and give the first tools to study and get around this complexity.

Organisation

Modalités d'organisation et de suivi

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.


The course is divided into two parts: one on computability, the other on the theory of the algorithmic complexity of problems.

In the first part, we introduce the decidability by showing that it is independent of the "computer" artifact using Turing machines. The reduction method is proposed for the proof of the decidability or the undecidability of a problem. Formal and practical examples of undecidable problems and non-calculable functions are given.

In a second part, we are interested in decidable problems and we propose an awareness of the concerns related to the complexity of the problems through concrete examples of crippling calculation times. We introduce the notions of complexity classes of problems (P, NP, PSPACE), and in particular NP-completeness and the method of polynomial reduction from one problem to another. Again, evidence is offered on concrete examples representative of the Engineer's concerns.

The practical work part will be the opportunity to experiment with generic heuristics (genetic algorithms, Taboo search, simulated annealing, etc.) on an NP-complete problem.

Informations pédagogiques

Compétences à acquérir

  • Identifier la complexité d'un problème
  • Réduire un problème en un autre
  • Construire des algorithmes adaptés aux différentes classes de complexité

  • Identify the complexity of a problem
  • Reduce one problem to another
  • Build algorithms adapted to different classes of complexity

Pré-requis recommandés

  • Notions de théorie des langages (symbole, mot, langage, automate à états fini)
  • Base de complexité des algorithmes

  • Language theory basics (symbols, word, language, finite-state automaton)
  • Algorithms complexity notions

Bibliographie, lectures recommandées

[1] Introduction à la calculabilité, 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, Bibliothèque Pour la Science, Diffusion Belin.

Dernière modification : mer, 06/01/2021 - 16:42