Algorithmique L3 ENS Lyon TD5 Corrigé - Anne Benoit
Présentation du document
Ce document est un corrigé de travaux dirigés d'algorithmique rédigé par Anne Benoit, destiné aux étudiants de Licence 3 à l'ENS Lyon. Daté du 25 octobre 2005, il aborde divers problèmes d'algorithmique avancée à travers quatre exercices principaux, allant de la manipulation de tableaux non triés à l'étude d'arbres binaires de recherche optimaux et de nouveaux algorithmes de tri.
Contenu et exercices étudiés
Le document s'ouvre sur un premier exercice intitulé Hors d'œuvre, qui propose quatre questions autour d'un ensemble de n entiers distincts stockés dans un tableau non trié. Les étudiants y explorent la recherche d'éléments maximaux et minimaux, la recherche d'éléments dont la différence est minimale, ainsi que l'optimisation de recherche de paires d'éléments dont la somme atteint une valeur donnée. Une méthode basée sur la médiane est également détaillée pour trouver des paires respectant des contraintes d'écart proportionnelles à l'étendue du tableau.
La deuxième partie est consacrée aux arbres binaires de recherche optimaux. Après un rappel des propriétés fondamentales de ces structures de données, le texte aborde le calcul des coûts de recherche selon les fréquences d'accès des clés, en s'appuyant sur une approche algorithmique par programmation dynamique dont la complexité est évaluée en O(n³).
L'exercice suivant introduit un nouvel algorithme de tri récursif appliqué à un tableau d'entiers distincts. Le corrigé détaille la preuve de correction de cette procédure ainsi que l'analyse de sa complexité en nombre de comparaisons, démontrant son inefficacité relative par rapport à d'autres méthodes classiques vues en cours.
Enfin, le dernier exercice aborde un problème d'appareillage d'écrous et de boulons de diamètres différents. Les questions guident l'étudiant depuis un algorithme simple quadratique jusqu'à une méthode plus efficace pour trouver le plus petit élément, avant de conclure par une preuve de complexité dans le pire des cas basée sur les arbres de décision ternaires.
Intérêt pédagogique pour les révisions
Ce document constitue un support direct pour s'entraîner sur la complexité algorithmique, la récursivité et l'analyse de structures de données arborescentes. La présence de corrections détaillées permet de comprendre les raisonnements mathématiques sous-jacents, notamment l'utilisation du théorème maître pour résoudre les équations de récurrence et l'évaluation de bornes inférieures dans les arbres de décision.
Télécharger Algorithmique L3 ENS Lyon TD5 Corrigé - Anne Benoit pdf
