M.C.P - 4

Méthodes de Conception et Construction de Programmes

Cours déstiné aux étudiants de 4e année Ingénieur- INI

Plan :

Première Partie : Conception de solutions.

1. Concepts préliminaires

a) complexité algorithmique (pdf - 686k)
b) Graphe et Arbres (pdf - 492k)
c) Les Problèmes NP-Complets (pdf - 451k)

2. Diviser pour Résoudre (pdf - 483k)

3. Programmation Dynamique (pdf - 625k)

4. Exploration de Graphes (pdf - 857k)

a) Recherche en Profondeur (Depht First Search ou Backtracking)
b) Application aux arbres de jeux (Minmax et Elagage Alpha/Beta)
c) Recherche en Largeur (Breadth First Search)

5. Heuristiques (pdf - 619k)

a) Introduction et définition
b) Algorithmes Voraces
c) Recherches guidées (Hill-climbing, Best First Search, Branch and Bound, A*)

Deuxième Partie : Construction de Programmes

1. Concepts Préliminaires

a) Les Systèmes Formels
b) Théorie du Point Fixe

2. Programmation Procédurale

a) Schémas de programme
b) Transformation de programmes
c) Preuves de Programmes
d) Le projet : Concorde

3. Programmation Orientée Objet

a) Notions d'objet
b) Le Langage C++
c) Le Framework QT
- petite présentation (pdf 62k)
- exemples de programmes

4. Programmation fonctionnelle

a) Le Lambda-Calcul
b) Le langage LISP
c) Preuves de programmes fonctionnels

5. Programmation Logique

a) La Logique du 1er ordre
b) Démonstrateur automatique de théorèmes
c) présentation de Prolog

6. Les Spécifications

TP 2009/2010 :

1. PVC avec "Branch and Bound" (pdf 42k)

Corrigés d'examens :

Emd1 2009/2010(pdf 55k)

Emd2 2009/2010(pdf 38k)

Emd1 2008/2009(pdf 69k)

Emd2 2008/2009(pdf 37k)

Emd1 2007/2008(pdf 85k)

Emd2 2007/2008 (pdf 74k)