Objectifs (en termes de compétences)

- concevoir et réaliser un algorithme correct et efficace pour un problème donné

- comprendre, choisir et mettre en oeuvre des méthodes de conception de programmes afin de réaliser et de démontrer l'exactitude d'algorithmes complexes.

Objet de l'activité (principaux thèmes à aborder)

- Méthodes de conception et de preuves de programmes: méthodes de l'invariant, calcul wp, induction structurale

- Transformations de programmes et techniques d'amélioration de l'efficacité

- Schémas de programmes et classes de problèmes: schémas de recherche globale (rétro-parcours; sélection-et-évaluation; recherche binaire), schémas de recherche locale (stratégie vorace; recherche par gradient; recuit simulé), schémas de réduction structurelle (diviser-pour-régner, programmation dynamique; relaxation; contraintes).

Résumé : Contenu et Méthodes

voir "Objet de l'activité"

Autres informations (Pré-requis, Evaluation, Support, ...)

- Pré-requis:
LINF2121 Algorithmique et structures de données P. Dupont

- Références
Ouvrage(s) recommandé(s)
(1) Liskov, B.., "Program Development in Java: Abstraction, Specification, and Object-Oriented Design." , Addison-Wesley, 2001
(2) Goodrich M.T. & Tamassia R, "Data Structure and Algorithms in Java." , Second Edition, John Wiley & Sons, 1997.

Programmes proposant cette activité

Autres crédits de l'activité dans les programmes