Calculabilité : outils classiques

Code APOGÉE : MA2DE200 | 6 ECTS | Enseignants : Hervé Fournier et Guillaume Malod | Validation : CC + examen
Horaires hebdomadaires : 4h CM | Mutualisé avec : M2 LMFI

Titre complet : Théorie de la calculabilité : cours spécialisé (Complexité avancée)

Nous aborderons différents thèmes de complexité. En complexité booléenne, nous parlerons en particulier de complexité de comptage et de complexité de communication. Nous étudierons aussi la complexité algébrique, sur laquelle s’appuient certains efforts récents pour résoudre le problème P vs. NP. En plus d’une présentation générale, nous explorerons des régimes calculatoires restreints, notamment les calculs non-commutatifs, et présenterons certaines bornes inférieures et les techniques de rang qui permettent de les obtenir.

Sujets abordés

• Complexité booléenne :
  • Complexité de comptage
  • Complexité de communication
• Complexité algébrique :
  • Approches pour résoudre le problème P vs. NP
  • Techniques de rang
• Régimes calculatoires restreints :
  • Calculs non-commutatifs
  • Bornes inférieures