Examen corrigé d'algorithmique M1 : Routage, Diviser pour régner, Backtracking et Programmation dynamique
Présentation du document
Ce document propose un sujet d'examen corrigé d'algorithmique destiné aux étudiants de niveau Master 1 (M1). Rédigé pour l'Université Paris Diderot, il est daté du 11 janvier 2011 et s'intitule « Examen du 11/1/11 - corrigé ». Il couvre quatre grands thèmes fondamentaux de l'algorithmique moderne à travers des exercices pratiques accompagnés de leurs corrections détaillées.
Contenu et exercices abordés
Le document s'articule autour de quatre exercices indépendants, chacun explorant une problématique algorithmique précise et proposant une méthode de résolution rigoureuse :
- Exercice 1 – Routage : Ce problème modélise le téléchargement d'un fichier volumineux d'un serveur vers une machine à travers un réseau doté de nœuds intermédiaires et de capacités de connexion limitées. L'exercice amène à identifier le problème du flot maximum dans un réseau et à appliquer pas à pas l'algorithme de Ford-Fulkerson pour déterminer le débit optimal et le routage associé.
- Exercice 2 – Valeur encadrée : Basé sur un tableau trié d'entiers et deux bornes, cet exercice demande de concevoir un algorithme de type « diviser-pour-régner » pour trouver un élément compris dans l'intervalle spécifié. La correction fournit le pseudocode récursif et analyse la complexité via le théorème maître pour aboutir à une efficacité en O(log n).
- Exercice 3 – Premier puzzle (Backtracking) : Cet exercice s'intéresse à la manipulation de dominos contenant des lettres et à la recherche d'une permutation formant une chaîne valide selon des règles de coïncidence des caractères voisins. La solution développe un algorithme de recherche en profondeur par retour arrière (backtracking), formalise la fonction de compatibilité et illustre le déroulement de l'arbre de recherche.
- Exercice 4 – Deuxième puzzle (Programmation dynamique) : Prolongeant le problème précédent, cette partie cherche à extraire la plus longue sous-séquence de dominos formant une chaîne valide. L'approche par programmation dynamique est mise en œuvre à l'aide d'une équation de récurrence, d'un algorithme itératif en O(n²), et d'une méthode de mémorisation pour reconstituer la solution optimale.
Intérêt pédagogique et utilisation pour les révisions
Ce sujet corrigé constitue un support de travail précieux pour les étudiants abordant la conception d'algorithmes avancés. La présence de corrections rédigées pas à pas permet non seulement de vérifier les résultats obtenus, mais aussi de comprendre la démarche méthodologique, qu'il s'agisse de modéliser un réseau sous forme de graphe, de concevoir une fonction récursive ou de structurer un tableau de programmation dynamique. L'analyse de la complexité temporelle de chaque algorithme renforce la compréhension théorique indispensable à ce niveau d'études.
Questions fréquentes
Quel est le niveau académique concerné par ce document ?
Ce document s'adresse à des étudiants en Master 1 (M1) d'informatique ou d'algorithmique.
Quelle institution a délivré cet examen ?
L'examen provient de l'Université Paris Diderot et est daté du 11 janvier 2011.
Quels algorithmes principaux sont appliqués dans les exercices ?
Le document met en œuvre l'algorithme de Ford-Fulkerson pour les flots, une méthode récursive de type diviser-pour-régner, un algorithme de backtracking pour les permutations, ainsi qu'une approche par programmation dynamique pour l'optimisation de sous-séquences.
Testez vos connaissances
Question 1
Quel problème algorithmique permet de résoudre la question du routage maximisant le débit dans un réseau de communications ?
- Le problème du plus court chemin de Dijkstra
- Le problème de l'arbre couvrant minimal
- Le problème de flot maximum dans un réseau
- Le problème du voyageur de commerce
Réponse correcte : Le problème de flot maximum dans un réseau
Explication : La correction indique explicitement que le problème de routage modélisé par des capacités de connexions entre des nœuds correspond au problème de flot maximum, résolu par l'algorithme de Ford-Fulkerson.
Question 2
Quelle est la complexité temporelle de l'algorithme « diviser-pour-régner » proposé pour l'exercice de la valeur encadrée ?
- O(n)
- O(n log n)
- O(log n)
- O(n²)
Réponse correcte : O(log n)
Explication : L'analyse de la complexité montre que le problème de taille n est réduit à un seul problème de taille n/2 avec des calculs en O(1), ce qui donne T(n) = T(n/2) + O(1), soit O(log n) par le théorème maître.
Question 3
Quelle méthode algorithmique est utilisée pour résoudre le deuxième puzzle consistant à trouver la plus longue sous-séquence de dominos formant une chaîne ?
- La programmation dynamique
- Le parcours en largeur
- L'algorithme glouton
- La dichotomie
Réponse correcte : La programmation dynamique
Explication : L'exercice 4 est explicitement consacré à la programmation dynamique, utilisant une fonction de récurrence c(i) et un remplissage itératif de tableau en O(n²).
