Compléments de Théorie de la Complexité

ULB-INFO039 -- J. Drabbe -- 15-0-0 -- Cours de 3ème cycle

Objectif

Etude de méthodes de la théorie de la complexité

Prérequis

Notions générales de théorie de la récursivité:
FUNDP-INFO-2203: Calculabilité et complexité
ULG-INFO-016: Introduction à la calculabilité

Contenu

1. Mesures de complexité
2. Le speed-up theorem
3. Classes de complexité
4. Le Gap theorem
5. Etude approfondie d'une question de la théorie de la complexité à déterminer en fonction des intérêts des participants

Pédagogie

Mode d'examen : à définir chaque année (en fonction des participants).

Références

21
Handbook of Theoretical Computer Science Volume A : Algorithms and Complexity North-Holland 1990