Séances (1H)

Cours

TD/TP

1

Concepts préliminaires (1) :

Notation de Landau

Parcours de graphes

O-notation

Graphes

3

Réduction de complexité

Méthode descendante (Diviser pour résoudre)

Méthode ascendante (Programmation dynamique)

Exemples et TP

6

Résolution de problèmes

Backtracking

Hill-Climbing

Best First Search

Branch and Bound

Algorithme A*

Exemples et TP

4

Théorie de la complexité ( Cours détaillé )

Problèmes de décision et langages

Modèles de calcul

Classes de complexité

NP-Complétude

Machine de Turing

Réduction

Np-Complétude

1

Concepts préliminaires (2) :

Théorie du point fixe

Système Formel

5

Programmation impérative

Schémas de programmes

Transformations de programmes

Preuves formelles

Transformation- Preuve

5

Programmation applicative

Lambda-calcul

Lisp et fonctions d'ordre supérieur

Preuves par induction

Interprétation des langages fonctionnels

Lambda-calcul et programmation Lisp

5

Programmation déclarative

Démonstration automatique de théorèmes

Prolog et manipulations symboliques

Interprétation des langages logiques

Résolution et programmation Prolog