X5I0020 : Etude des algorithmes
C 20 ; TD 28
-
Analyse de problèmes de décision : présentation des notions de décidabilité, introduction des classes de complexité P, NP et Pspace. Présentation la Karp-réduction et de problèmes NP-Dur et NP-Complets.
-
Vérification de programme
-
Vérification dynamiques : aléatoire ; fonctionnelle ; structurelle
-
Vérification statique : informelle ; formelle (Hoare et Dijkstra) : correction, terminaison.
-
-
Preuve et analyse en complexité temporelle de programmes itératifs et récursifs
Compétences acquises :
-
savoir classer des problèmes de décision
-
savoir choisir les types vérifications à réaliser en fonction des programmes
-
savoir choisir des propriétés à vérifier pour prouver un algorithme et établir sa complexité temporelle