Chapitre 2 : preuve et complexité d’algorithmes
Jeannette Wing est une professeure d'informatique à l'Université Carnegie-Mellon (sur une chaire intitulée professeur du président). Elle est directrice du département d'informatique. Ses domaines d'intérêt sont les systèmes de spécification et de vérification, concurrents et répartis, ainsi que les langages de programmation.
Lorsque l’on écrit un algorithme, il faut pouvoir s’assurer qu’il s’exécute correctement dans toutes les situations. Un simple jeu de tests ne suffit pas à assurer que le programme se termine et produit le résultat attendu à tous les coups. Dans certaines applications industrielles, comme par exemple les programmes contrôlant la conduite des lignes de mêtro automatiques, il est même vital de démontrer qu’un programme est correct.
Par ailleurs, si plusieurs programmes permettent de répondre à un même problème, il faut être capable de les comparer afin de savoir lequel (ou lesquels) sont les plus efficaces.
Le but de ce second chapitre dédié à l'algorithmique est de présenter les méthodes mises en oeuvre pour répondre à ces deux problématiques qui sont les preuves d'algorithmes et la complexité.
On propose le déroulé suivant :
- un point de cours (paragraphe 1) présentant la notion de preuve algorithmique. On introduit en particulier les notions de terminaison avec le variant de boucle et de correction partielle avec l'invariant de boucle, et on illustre ces deux notions sur des exemples simples ;
- des exercices d'entraînement (exercices 1 à 4) pour manipuler les variants et invariants de boucle ;
- un point de cours (paragraphe 2) pour introduire sur un exemple simple la notion de complexité algorithmique. On définit en particulier une échelle de comparaison et on présente quelques résultats sur les temps de calcul ;
- un exercice d'entraînement (exercice 5) pour manipuler le concept de complexité.
Afficher le cours
Afficher les exercices
Il n'y a pas de ressources à télécharger.