Module Fondements de l'informatique

Programme

Calculabilité

Modélisation du calcul - Thèse de Church-Turing (1936)
Fonctions et problémes calculables
Exemples de fonction non calculables et de problémes indécidables
Réductions entre fonctions et problémes

Complexité

Théorie de la complexité algorithmique
Quelques classes de complexité algorithmique
Le probléme P = NP
Importance des heuristiques

Modélisation des algorithmes - Thèse de Gurevich (1984)

Structure du premier ordre
Abstract State Machine

Bibliographie sommaire