Calculabilité et décidabilité (ICC), MAIN4, 2021-2022


Nouvelles fraîches

Description de l'UE

De nombreuses réalisations informatiques allant du parser aux systèmes embarqués, sont basées sur des modèles de calcul plus ou moins complexes.

Dans cette unité d'enseignement, nous abordons les différents modèles de calculateurs classiques via la théorie des automates (finis, à pile, etc.), puis les machines de Turing. Nous caractérisons les problèmes pouvant ou non être résolus par chacun de ces modèles. En outre, ils seront illustrés par une application classique en informatique. Sur la base de ces constructions, nous introduisons la notion de complexité et en étudions les grandes classes.

Programme indicatif par semaine

  1. Notions de base (alphabets, automates)
  2. Langages réguliers (automates à états finis, grammaires, lemme de pompage)
  3. Langages hors-contexte : automates à pile déterministe et non déterministe, grammaires hors-contexte
  4. Langages hors-contexte (suite) : équivalence APN et grammaires hors-contexte
  5. Langages récursivement énumérables: Machines de Turing déterministes. Modification de la machine. Machines de Turing non-déterministes
  6. Langages récursivement énumérables (suite) : Grammaires sans restriction, langage sensible hors-contexte
  7. Calculabilité : de l'hypothèse de Church à la machine universelle
  8. Calculabilité : Exemples de problèmes indécidables. Théorèmes de Rice. Problème de correspondance de Post
  9. Complexité : Notions de base et propriétés
  10. Complexité : Hiérarchie des langages et rapports entre classes de complexité, classes et réductions polynomiales. Premier problème NP-complet

Équipe pédagogique

Horaire

Examens et notations

La note de module est composée de la moyenne des 3 interrogations.

Documents disponibles

Logiciels

Pour simuler des automates, expressions regulières, automates à piles, grammaires et machines de Turing, vous pouvez utiliser les outils suivants :

Interrogations

Interrogations des années précédentes

Bibliographie


Valid HTML 4.01! Valid CSS! Stef Graillat
(Dernière modification : juillet 2021)