Complexité

• Problématique des automates finis et de machines de Turing et leur relation avec les langages et les grammaires formelles
• Problématique autour de la complexité algorithmique et de classes de complexité

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

Langages, grammaires, automates, Turing, complexité.

Dimitri Petritis est professeur à l’Institut de recherche mathématique de Rennes. Il fait également partie de l’équipe de théorie ergodique.