]
]
]
]
Cours 2012
IHDC B331 - Méthodes de programmation (2e partie)
Enseignant(s)
Encadrement des TP/Exercices
Abdelkader HENI
Objectifs
Apprendre une démarche rigoureuse de construction de programmes efficaces: l'algorithmique.
Contenu
Toutes les méthodes reposent sur la démarche de spécification formelle, implémentation et preuve.
L'évaluation de l'efficacité d'un problème est basée sur un calcul du temps d'éxécution et de consommation de la mémoire (théorie de la complexité)
La récursion sert de base à ce cours.
Nous utilisons d'abord des structures de données récursives:
arbres, arbres rouges-noirs, listes, etc.
Ensuite, des méthodes systématiques de construction de programmes efficaces seront présentées:
1- la méthode "diviser pour régner"
2- les méthodes de mémorisation, dont la programmation dynamique
3- la méthodes gloutonne
4- la méthode générer/tester
5- la méthode des contraintes
6- les méthodes heuristiques
Donné en
Année(s) d'études |
Quadrimestre |
Théorie (h) |
Exercices (h) |
Crédits |
|
|---|---|---|---|---|---|
|
Année préparatoire au 2e cycle en sciences informatiques à horaire décalé |
1er |
30 |
30 |
8 |
|
|
3e année de bachelier en sciences informatiques (horaire décalé) |
1er |
30 |
30 |
8 |
|
Table des matières
Partie I.
Spécification par pré et et post-conditions, preuves par invariants et variants.
Evaluation du temps d'éxécution.
Récursion.
Structures de données récursives:
arbres, arbres rouges-noirs, listes, etc.
Partie II. Méthodes de construction de programmes.
1- la méthode "diviser pour régner"
2- les méthodes de mémorisation, dont la programmation dynamique
3- la méthodes gloutonne
4- la méthode générer/tester
5- la méthode des contraintes
6- les méthodes heuristiques
Description des TP/Exercices
Les séances d'exercices sont organisées selon un triple perspective.
1- Consolidation des prérequis:
- écriture de spécifications;
- construction d'algorithmes par la technique de l'invariant;
- types abstraits (liste chaînée, liste doublement chaînée, arbre binaire,...).
2- Appropriation des méthodes vues au cours théorique:
- construction d'algorithmes par les différentes méthodes;
- calcul de la complexité des algorithmes construits.
3- Introduction au langage C:
- les différents algorithmes construits sont implémentés en C.
Méthode d'enseignement
Un cours magistral illustré de nombreux exemples, plus des travaux pratiques.
Les étudiants sont également invités à faire des exercices à domicile.
Evaluation
Examen écrit. La question principale demande de résoudre efficacement un problème nouveau.
Prérequis
Connaissance de la programmation impérative, des pré- et post-conditions, des invariants.
Cette matière est donnée p.ex. par INFO1131, ou IHDC2004 et IHDC2005.
