Théorie de la calculabilité: cours spécialisé (Complexité avancée)
8 ECTS, semestre 2, 12 semaines
| Validation | CC+examen |
| Enseignant | Hervé Fournier et Guillaume Malod |
| Horaires hebdomadaires | 4.0 h CM |
| Années | Master Logique Mathématique et Fondements de l'Informatique |
Syllabus
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ésenteront certaines bornes inférieures et les techniques de rang qui permettent de les obtenir.