email Admissions
fr
Menu
email

Complexité

Description du cours

  • Rappels sur les graphes/arbres
  • Langages et grammaires formelles
  • Fonctions booléennes, logique propositionnelle, prédicats, premier théorème d’incomplétude
  • Automates finis et langages réguliers
  • Langages non-réguliers et machines de Turing
  • Classes de complexité
  • Si le temps le permet, stochasticité, complexité de Kolmogorov, entropie

Compétences à acquérir

Acquérir les notions de base en théorie de la complexité et des classes de complexité.

Mots-clés

Langages, grammaires, automates, Turing, complexité.

Biographie de l’enseignant

Vincent Guirardel est professeur à l’Université de Rennes ancien membre de l’Institut universitaire de France et directeur du Centre Henri Lebesgue.