Organisation de MIF09 - 2016/17

  • Cours par Sylvain Brandel
  • 4 groupes de TD, 10 séances de 1.5h de TD. J'encadre le groupe xx

Documents

Un peu de biblio classée par thème

  • Quelques liens utiles pour des démos sur les Machines de Turing :
    • Un automate à pile pour les palindromes. À adapter pour en faire une Machine de Tuting.
  • Pour les fonctions primitives récursives, le Chapitre 8 poly de Patrick Dehornoy est une bonne référence, avec énormément d'exemples à l'intérieur. Attention, les notations ne sont pas tout à fait les mêmes que celles du cours. On notera le résultat très intéressant donné par le Corollaire 1.22 page 232. Un examen qui montre des résultats très intéressants sur les fonctions primitives récursives
  • Modèles de calcul. Le poly de cours d'Eugène Asarin fait une bonne référence. Lire notamment l'introduction (Chapitre 0) et la partie sur les modèles de calcul plus simples que les MT : automates à deux piles et automates à compteur (Chapitre 3). Sur les machines à compteur le td de Victor Poupet décrit les étapes pour simuler une machine de Turing avec une Machine à 3 compteurs.
  • Sur l'indécidabilité et les réductions on pourra lire les transparents d'Emmanuel Filiot, où sont décrits les 3 problèmes indécidables les plus courants que sont l'arrêt d'une MT, le problème de correspondance de Post (PCP) et le dixième problème de Hilbert. On pourra aussi se reporter aux pages Wikipedia qui correspondent. Le Chapitre 3 du poly de Serge Haddad fournit quelques rédactions. Les transparents d'Anca Muscholl sont aussi très intéressants.

  • La notion de réduction (polynomiale) est par exemple décrite sur les transparents de Marie-Pierre Béal (avec quelques exemples).
  • Sur la classe NP et les problèmes NP-complets :