email Admissions
en
Menu
email

Complexité

Course description

  • 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

Skills to acquire

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

Keywords

Langages, grammaires, automates, Turing, complexité.

Biography

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