UGA

L3 Informatique

Modèles de Calcul - Machines de Turing

Pour toutes question n'hésitez pas à me contacter par mail : Frederic.Prost@univ-grenoble-alpes.fr

• Organisation des cours et TD en distanciel

Jusqu'à ce que la situation sanitaire évolue les cours et les TD seront en distanciels. Les cours se feront par zoom et seront enregistrés. Les TD se feront par Discord. Pour vous connecter je vous demande d'utiliser des identifiants clairs, c'est à dire nom/prénom. Les liens sont les suivants:
• Cours MCAL - Mardi 15h15/16h45

• Serveur Discord pour les TD.

  Des canaux textes ont été créées pour chaque groupe. Quand vous vous connectez rendez-vous sur le canal associée à votre groupe. Des salles de travail (canaux audios "salle-de-travail-x") ont été ouvertes où vous pourrez travailler en groupe.

• Projet

  • Lien du projet sur les automates cellulaires
  • Si vous choisissez le projet Machine de Turing envoyez moi un mail avec la composition du binôme à frederic.prost@univ-grenoble-alpes.fr avant le 20/3/2021. Une moitié des binômes fera le projet en Machine de Turing et l'autre en lambda-calcul. L'algorithme de répartition sera dans l'ordre:
    1. Choix personnel.
    2. Premier arrivé, premier servi (si l'équilibre entre MT et lambda-calcul n'est pas correct).
  • Liste des binômes inscrits
  • Planning des soutenances

• Enregistrement des Cours

  • Cours 1 - Définition du modèle des Machines de Turing- 19/1/2021
  • Cours 2 - Universalités - 26/1/2021
  • Cours 3 - Problèmes Insolubles - 2/2/2021
  • Cours 4 - Semi-décidabilité - Ensembles Récursivement Enumérables - 9/2/2021
  • Cours 5 - Complexités - Temporelle, spatiale, Kolmogorov, profondeur logique - 23/2/2021
  • Cours 6 - Stabilités et retour sur la semi-décidabilité - 2/3/2021
  • Cours 7 - Hiérarchie Arithmétique, calculabilité relative - 1 - 9/3/2021
  • Cours 8 - Hiérarchie Arithmétique, calculabilité relative - 2 - 16/3/2021

• Transparents de Cours

  • Transparents du cours

• Notes de Cours

  • Notes de Cours

• Fiches d'exercice de TD

  • Fiche de TD 1, machines de Turing - Programmation
  • Fiche de TD 2, modèles de calcul - équivalences
  • Fiche de TD 3, Calculabilité
  • Fiche de TD 4, Enumérabilité Récursive

• Annales années précédentes

  • Quick Février 2020

• Bibliographie et ressources pédagogiques diverses

  • "Theory of Recursive Functions and Effective Computability" (MIT Press) – 1987, Hartley Rogers. Livre très complet et théorique, plus à voir comme référence que pour l'initiation et les intuitions.
  • "The Language of Machines: An Introduction to Computability and Formal Languages" (W.H.Freeman & Co Ltd ) – 1993, Robert W. Floyd et Richard Beigel, chapitres 1, 2, 3, 7 et 8. Plus accessible que le Rogers mais moins formel.
  • "Introduction to the Theory of Computation" (PWS publishing Company) - 1997, M. Sipser. Deuxième partie, plus accessible que le Rogers également (mais moins formel).
  • "Langages formels Calculabilité et complexité" (Vuibert) - 2014, Olivier Carton et Dominique Perrin. La référence en francais, moins complet que les autres (notamment moins sur la théorie de la récursivité.
  • Algorithmic Information Theory (Cambridge University Press) - 1987, La base de la complexité basée sur la taille minimale d'un programme pour produire un résultat particulier.