Algorithmique intermédiaire : Travaux pratiques
Travaux pratiques Structures de données et méthodes de résolution 8 TP progressifs avec énoncés, jeux d’essai et corrections détaillées COMPLEXITÉ • LISTES • PILES & FILES • HACHAGE • ARBRES • TRIS • CONCEPTION • GRAPHES |
Présentation générale des travaux pratiques
Ce recueil accompagne le cours « Algorithmique intermédiaire — Structures de données et méthodes de résolution ». Les activités proposées conduisent progressivement l’étudiant de l’analyse théorique d’un algorithme à l’implémentation de structures de données et de méthodes de conception plus élaborées.
Objectifs généraux
• appliquer les notions du cours à des problèmes concrets ;
• concevoir des algorithmes modulaires et correctement documentés ;
• choisir une structure de données adaptée ;
• produire des jeux d’essai pertinents ;
• analyser la complexité temporelle et spatiale ;
• comparer plusieurs solutions par des mesures expérimentales ;
• développer l’autonomie dans la résolution de problèmes.
Organisation recommandée
TP | Thème | Durée indicative | Production principale |
|---|---|---|---|
| 1 | Analyse de complexité | 3 à 4 h | Tableaux de comptage et mesures de temps |
| 2 | Listes chaînées | 4 h | Bibliothèque de listes simplement chaînées |
| 3 | Piles et files | 4 h | Analyseur d’expressions et simulateur |
| 4 | Hachage | 4 h | Dictionnaire clé-valeur |
| 5 | Arbres | 5 h | Bibliothèque d’arbres et ABR |
| 6 | Tris avancés | 4 à 5 h | Tri fusion, tri rapide et benchmark |
| 7 | Méthodes de conception | 5 h | Comparaison de quatre paradigmes |
| 8 | Graphes | 5 h | Représentations, DFS et BFS |
Consignes communes • Écrire d’abord le pseudo-code avant l’implémentation. • Valider chaque module avec des cas normaux, limites et incorrects. • Justifier les structures de données et les choix algorithmiques. • Présenter les résultats dans un compte rendu clair. • Les corrections proposées constituent une solution de référence, non l’unique solution possible. |
TP 1 — Analyse de complexité
Ce TP apprend à relier le code, le nombre d’opérations et le temps observé expérimentalement.
Durée | Prérequis | Livrable |
|---|---|---|
| 3 à 4 h | Boucles, fonctions, notation O, Ω et Θ | Code/pseudo-code, jeux d’essai, analyse et compte rendu |
Objectifs
• compter les opérations dominantes d’un algorithme
• comparer des boucles successives et imbriquées
• mesurer des temps d’exécution de manière reproductible
• interpréter les écarts entre théorie et expérimentation
Partie A — Comptage des opérations
Exercice 1 — Somme d’un tableau
On considère un tableau T de n nombres. Concevoir un algorithme qui calcule la somme de ses éléments.
Travail demandé :
• identifier les affectations, additions, comparaisons et incrémentations ;
• établir une expression C(n) du nombre d’opérations principales ;
• donner la complexité asymptotique.
Exercice 2 — Recherche de doublons
Écrire une méthode naïve qui indique si un tableau contient au moins deux valeurs égales.
Travail demandé :
• utiliser deux boucles imbriquées ;
• distinguer le meilleur et le pire cas ;
• proposer un jeu de données pour chacun de ces cas.
Partie B — Comparaison de boucles
Exercice 3 — Boucles successives et imbriquées
Analyser trois fragments : deux parcours successifs, un parcours imbriqué n × n et une boucle dont l’indice est doublé à chaque itération.
Travail demandé :
• compter approximativement les itérations ;
• associer O(n), O(n²) ou O(log n) ;
• expliquer le terme dominant.
Partie C — Mesure expérimentale
Exercice 4 — Protocole de benchmark
Comparer expérimentalement une recherche séquentielle et une recherche dichotomique sur des tableaux triés de tailles croissantes.
Travail demandé :
• utiliser plusieurs tailles n ;
• répéter chaque mesure ;
• calculer une moyenne ou médiane ;
• présenter les résultats dans un tableau ;
• commenter les limites de la mesure.
Correction du TP 1
Correction 1 — Somme d’un tableau
ZONE DE PSEUDO-CODE — Somme et compteur d’opérations Fonction SommeEtCompter(T, n) : somme ← 0 operations ← 1 // affectation Pour i allant de 0 à n - 1 Faire somme ← somme + T[i] operations ← operations + 3 // lecture, addition, affectation FinPour Retourner (somme, operations) FinFonction Le détail exact dépend du modèle de coût. Le terme dominant reste proportionnel à n : Θ(n). |
Élément compté | Nombre approximatif |
|---|---|
| Initialisation | 1 |
| Comparaisons de boucle | n + 1 |
| Incrémentations | n |
| Additions / affectations de la somme | 2n |
| Total | 4n + 2, donc Θ(n) |
Correction 2 — Détection naïve de doublons
ZONE DE PSEUDO-CODE — Doublons par comparaison de toutes les paires Fonction ContientDoublon(T, n) : Pour i allant de 0 à n - 2 Faire Pour j allant de i + 1 à n - 1 Faire Si T[i] = T[j] Alors Retourner Vrai FinSi FinPour FinPour Retourner Faux FinFonction Meilleur cas : Θ(1) si les deux premières valeurs sont égales. Pire cas : Θ(n²). |
Correction 3 — Classes de croissance
Fragment | Nombre d’itérations | Complexité |
|---|---|---|
| Deux boucles successives de n itérations | n + n = 2n | Θ(n) |
| Deux boucles imbriquées | n × n | Θ(n²) |
| i ← 1 puis i ← 2i | ⌊log₂ n⌋ + 1 | Θ(log n) |
Correction 4 — Protocole de benchmark
1. Préparer des tableaux triés de tailles 1 000, 10 000, 100 000 et 1 000 000.
2. Choisir une valeur absente ou située vers la fin pour éviter un meilleur cas artificiel.
3. Effectuer une phase d’échauffement.
4. Mesurer chaque algorithme au moins 20 fois.
5. Utiliser une horloge monotone à haute résolution.
6. Calculer la médiane des temps et présenter le rapport entre les deux méthodes.
Résultat attendu • La recherche séquentielle croît approximativement comme n. • La recherche dichotomique croît comme log₂(n). • Pour les petites tailles, le bruit de mesure peut masquer la différence. • Les résultats dépendent du langage, du compilateur, du cache et du matériel. |
TP 2 — Listes chaînées
Le TP conduit à construire une petite bibliothèque de listes simplement chaînées et à vérifier ses invariants.
Durée | Prérequis | Livrable |
|---|---|---|
| 4 h | Pointeurs/références, enregistrements, fonctions et complexité | Code/pseudo-code, jeux d’essai, analyse et compte rendu |
Objectifs
• définir un nœud et une tête de liste
• implémenter ajout, suppression et recherche
• inverser une liste sans créer de nouvelle liste
• analyser la complexité des opérations
Structure de données
ZONE DE PSEUDO-CODE — Types utilisés Type Noeud : valeur : Élément suivant : Référence vers Noeud FinType
Type Liste : tete : Référence vers Noeud taille : Entier FinType |
Exercice 1 — Ajout
Implémenter l’ajout en tête, en fin et après une valeur donnée.
Travail demandé :
• gérer la liste vide ;
• mettre à jour la taille ;
• indiquer la complexité de chaque opération.
Exercice 2 — Recherche
Écrire une fonction qui retourne la première position d’une valeur ou -1 si elle est absente.
Exercice 3 — Suppression
Supprimer la première occurrence d’une valeur et libérer le nœud supprimé.
Travail demandé :
• traiter la suppression de la tête ;
• traiter une valeur absente ;
• conserver la liste cohérente.
Exercice 4 — Inversion
Inverser la liste en place avec trois références : precedent, courant et suivant.
Correction du TP 2
Ajout en tête et en fin
ZONE DE PSEUDO-CODE — Ajouter en tête Procédure AjouterTete(L, x) : nouveau ← NouveauNoeud(x) nouveau.suivant ← L.tete L.tete ← nouveau L.taille ← L.taille + 1 FinProcédure |
ZONE DE PSEUDO-CODE — Ajouter en fin Procédure AjouterFin(L, x) : nouveau ← NouveauNoeud(x) Si L.tete = NUL Alors L.tete ← nouveau Sinon p ← L.tete TantQue p.suivant ≠ NUL Faire p ← p.suivant FinTantQue p.suivant ← nouveau FinSi L.taille ← L.taille + 1 FinProcédure Sans pointeur de fin, cette opération est en Θ(n). Avec une référence vers le dernier nœud, elle devient Θ(1). |
Recherche et suppression
ZONE DE PSEUDO-CODE — Rechercher une valeur Fonction Rechercher(L, x) : p ← L.tete position ← 0 TantQue p ≠ NUL Faire Si p.valeur = x Alors Retourner position FinSi p ← p.suivant position ← position + 1 FinTantQue Retourner -1 FinFonction |
ZONE DE PSEUDO-CODE — Supprimer la première occurrence Fonction Supprimer(L, x) : precedent ← NUL courant ← L.tete TantQue courant ≠ NUL ET courant.valeur ≠ x Faire precedent ← courant courant ← courant.suivant FinTantQue Si courant = NUL Alors Retourner Faux FinSi Si precedent = NUL Alors L.tete ← courant.suivant Sinon precedent.suivant ← courant.suivant FinSi Libérer(courant) L.taille ← L.taille - 1 Retourner Vrai FinFonction |
Inversion en place
ZONE DE PSEUDO-CODE — Inverser une liste Procédure Inverser(L) : precedent ← NUL courant ← L.tete TantQue courant ≠ NUL Faire suivant ← courant.suivant courant.suivant ← precedent precedent ← courant courant ← suivant FinTantQue L.tete ← precedent FinProcédure Temps Θ(n), mémoire auxiliaire Θ(1). |
Opération | Sans pointeur fin | Avec pointeur fin |
|---|---|---|
| Ajout en tête | Θ(1) | Θ(1) |
| Ajout en fin | Θ(n) | Θ(1) |
| Recherche | Θ(n) | Θ(n) |
| Suppression après recherche | Θ(n) | Θ(n) |
| Inversion | Θ(n) | Θ(n) |
TP 3 — Piles et files
Trois applications permettent de mobiliser les principes LIFO et FIFO.
Durée | Prérequis | Livrable |
|---|---|---|
| 4 h | Piles, files, chaînes, expressions et simulation | Code/pseudo-code, jeux d’essai, analyse et compte rendu |
Objectifs
• vérifier l’équilibrage de symboles
• implémenter un mécanisme d’annulation
• simuler une file d’attente
• justifier l’usage d’une pile ou d’une file
Exercice 1 — Vérification d’expressions
Vérifier que les parenthèses (), crochets [] et accolades {} d’une expression sont correctement appariés et imbriqués.
Exercice 2 — Historique et annulation
Modéliser un éditeur simple avec une pile Annuler et une pile Rétablir.
Travail demandé :
• enregistrer chaque action ;
• annuler la dernière action ;
• rétablir une action annulée ;
• vider la pile Rétablir après une nouvelle action.
Exercice 3 — Simulation d’une file d’attente
Simuler un guichet unique. Chaque client possède une heure d’arrivée et une durée de service.
Travail demandé :
• calculer le début et la fin de service ;
• calculer le temps d’attente ;
• déterminer l’attente moyenne et maximale.
Correction du TP 3
Vérification des délimiteurs
ZONE DE PSEUDO-CODE — Expression bien parenthésée Fonction BienFormee(expression) : P ← PileVide() Pour chaque caractère c de expression Faire Si c ∈ {"(", "[", "{"} Alors Empiler(P, c) SinonSi c ∈ {")", "]", "}"} Alors Si EstVide(P) Alors Retourner Faux FinSi ouvrant ← Dépiler(P) Si NonCorrespondants(ouvrant, c) Alors Retourner Faux FinSi FinSi FinPour Retourner EstVide(P) FinFonction Temps Θ(n), mémoire O(n) dans le pire cas. |
Historique avec annuler / rétablir
ZONE DE PSEUDO-CODE — Gestion des deux piles Procédure Executer(action) : Appliquer(action) Empiler(Annuler, action) Vider(Retablir) FinProcédure
Procédure AnnulerDerniere() : Si Non EstVide(Annuler) Alors a ← Dépiler(Annuler) AppliquerInverse(a) Empiler(Retablir, a) FinSi FinProcédure
Procédure RetablirDerniere() : Si Non EstVide(Retablir) Alors a ← Dépiler(Retablir) Appliquer(a) Empiler(Annuler, a) FinSi FinProcédure |
Simulation du guichet
ZONE DE PSEUDO-CODE — Calcul des temps d’attente Fonction Simuler(clients triés par arrivée) : finServeur ← 0 sommeAttente ← 0 attenteMax ← 0 Pour chaque client c Faire debut ← Max(c.arrivee, finServeur) attente ← debut - c.arrivee finServeur ← debut + c.duree sommeAttente ← sommeAttente + attente attenteMax ← Max(attenteMax, attente) FinPour Retourner (sommeAttente / NombreClients, attenteMax) FinFonction |
Client | Arrivée | Durée | Début | Fin | Attente |
|---|---|---|---|---|---|
| C1 | 0 | 4 | 0 | 4 | 0 |
| C2 | 1 | 3 | 4 | 7 | 3 |
| C3 | 5 | 2 | 7 | 9 | 2 |
| C4 | 6 | 5 | 9 | 14 | 3 |
TP 4 — Hachage
Le TP consiste à développer un dictionnaire clé-valeur avec gestion des collisions et à l’utiliser pour compter des occurrences.
Durée | Prérequis | Livrable |
|---|---|---|
| 4 h | Fonctions, tableaux, listes, chaînes et facteur de charge | Code/pseudo-code, jeux d’essai, analyse et compte rendu |
Objectifs
• concevoir une fonction de hachage
• gérer les collisions par chaînage
• implémenter insertion, recherche et suppression
• utiliser le dictionnaire pour compter des fréquences
Spécifications
Opération | Comportement attendu |
|---|---|
| Inserer(cle, valeur) | Ajoute la paire ou remplace la valeur existante. |
| Chercher(cle) | Retourne la valeur ou signale l’absence. |
| Supprimer(cle) | Supprime la paire et retourne un booléen. |
| Contient(cle) | Teste la présence de la clé. |
| Taille() | Retourne le nombre de paires. |
Exercice 1 — Fonction de hachage
Pour une clé textuelle, concevoir une fonction polynomiale utilisant une base b et la taille m de la table.
Exercice 2 — Chaînage séparé
Implémenter les opérations du dictionnaire avec un tableau de listes chaînées.
Exercice 3 — Collisions et facteur de charge
Instrumenter le dictionnaire afin de compter le nombre de collisions et la longueur maximale d’une chaîne.
Exercice 4 — Comptage d’occurrences
À partir d’un texte, produire le dictionnaire des fréquences de mots, puis afficher les mots les plus fréquents.
Correction du TP 4
Fonction de hachage polynomiale
ZONE DE PSEUDO-CODE — Hachage d’une chaîne Fonction Hacher(chaine, m) : h ← 0 Pour chaque caractère c de chaine Faire h ← (h × 31 + Code(c)) mod m FinPour Retourner h FinFonction |
Dictionnaire par chaînage
ZONE DE PSEUDO-CODE — Insertion ou mise à jour Procédure Inserer(D, cle, valeur) : i ← Hacher(cle, D.capacite) p ← D.seaux[i].tete TantQue p ≠ NUL Faire Si p.cle = cle Alors p.valeur ← valeur Retourner FinSi p ← p.suivant FinTantQue AjouterTete(D.seaux[i], Paire(cle, valeur)) D.taille ← D.taille + 1 Si D.taille / D.capacite > 0,75 Alors Redimensionner(D) FinSi FinProcédure |
ZONE DE PSEUDO-CODE — Recherche Fonction Chercher(D, cle) : i ← Hacher(cle, D.capacite) Pour chaque paire p de D.seaux[i] Faire Si p.cle = cle Alors Retourner p.valeur FinSi FinPour Lever ErreurCleAbsente FinFonction |
Comptage des mots
ZONE DE PSEUDO-CODE — Fréquences par dictionnaire Fonction Frequences(texte) : D ← DictionnaireVide() mots ← NormaliserEtDecouper(texte) Pour chaque mot de mots Faire Si Contient(D, mot) Alors Inserer(D, mot, Chercher(D, mot) + 1) Sinon Inserer(D, mot, 1) FinSi FinPour Retourner D FinFonction |
Analyse • Sous une bonne répartition, insertion et recherche sont en temps moyen O(1). • Dans le pire cas, toutes les clés tombent dans le même seau : O(n). • Le redimensionnement est coûteux ponctuellement, mais son coût amorti reste acceptable. |
TP 5 — Arbres
Ce TP rassemble les parcours d’arbres binaires et les opérations fondamentales d’un arbre binaire de recherche.
Durée | Prérequis | Livrable |
|---|---|---|
| 5 h | Récursivité, files, arbres binaires et ABR | Code/pseudo-code, jeux d’essai, analyse et compte rendu |
Objectifs
• créer un arbre binaire
• réaliser les parcours préfixe, infixe, postfixe et en largeur
• insérer et rechercher dans un ABR
• supprimer un nœud en traitant les trois cas
Structure proposée
ZONE DE PSEUDO-CODE — Nœud d’arbre Type NoeudArbre : cle : Clé valeur : Donnée gauche : Référence vers NoeudArbre droite : Référence vers NoeudArbre FinType |
Exercice 1 — Création et parcours
Construire un arbre à partir d’une séquence de clés, puis produire les quatre parcours.
Exercice 2 — Recherche et insertion dans un ABR
Implémenter les versions itératives ou récursives.
Exercice 3 — Minimum, maximum et hauteur
Calculer ces propriétés et déterminer si l’arbre est équilibré selon la différence des hauteurs.
Exercice 4 — Suppression
Supprimer successivement une feuille, un nœud avec un enfant et un nœud avec deux enfants.
Correction du TP 5
Parcours
ZONE DE PSEUDO-CODE — Parcours récursifs Procédure Prefixe(r) : Si r = NUL Alors Retourner FinSi Visiter(r) Prefixe(r.gauche) Prefixe(r.droite) FinProcédure
Procédure Infixe(r) : Si r = NUL Alors Retourner FinSi Infixe(r.gauche) Visiter(r) Infixe(r.droite) FinProcédure
Procédure Postfixe(r) : Si r = NUL Alors Retourner FinSi Postfixe(r.gauche) Postfixe(r.droite) Visiter(r) FinProcédure |
ZONE DE PSEUDO-CODE — Parcours en largeur Procédure Largeur(racine) : Si racine = NUL Alors Retourner FinSi F ← FileVide() Enfiler(F, racine) TantQue Non EstVide(F) Faire r ← Defiler(F) Visiter(r) Si r.gauche ≠ NUL Alors Enfiler(F, r.gauche) FinSi Si r.droite ≠ NUL Alors Enfiler(F, r.droite) FinSi FinTantQue FinProcédure |
Insertion et recherche
ZONE DE PSEUDO-CODE — Insertion dans un ABR Fonction Inserer(r, cle, valeur) : Si r = NUL Alors Retourner NouveauNoeud(cle, valeur) FinSi Si cle < r.cle Alors r.gauche ← Inserer(r.gauche, cle, valeur) SinonSi cle > r.cle Alors r.droite ← Inserer(r.droite, cle, valeur) Sinon r.valeur ← valeur FinSi Retourner r FinFonction |
ZONE DE PSEUDO-CODE — Recherche dans un ABR Fonction Rechercher(r, cle) : TantQue r ≠ NUL ET r.cle ≠ cle Faire Si cle < r.cle Alors r ← r.gauche Sinon r ← r.droite FinSi FinTantQue Retourner r FinFonction |
Suppression
ZONE DE PSEUDO-CODE — Supprimer une clé Fonction Supprimer(r, cle) : Si r = NUL Alors Retourner NUL FinSi Si cle < r.cle Alors r.gauche ← Supprimer(r.gauche, cle) SinonSi cle > r.cle Alors r.droite ← Supprimer(r.droite, cle) Sinon Si r.gauche = NUL Alors Retourner r.droite FinSi Si r.droite = NUL Alors Retourner r.gauche FinSi s ← Minimum(r.droite) r.cle ← s.cle r.valeur ← s.valeur r.droite ← Supprimer(r.droite, s.cle) FinSi Retourner r FinFonction |
Opération | Arbre équilibré | Arbre dégénéré |
|---|---|---|
| Recherche | O(log n) | O(n) |
| Insertion | O(log n) | O(n) |
| Suppression | O(log n) | O(n) |
| Parcours complet | Θ(n) | Θ(n) |
TP 6 — Tris avancés
Le TP compare le tri fusion et le tri rapide sur différents profils de données.
Durée | Prérequis | Livrable |
|---|---|---|
| 4 à 5 h | Récursivité, tableaux, complexité et mesure du temps | Code/pseudo-code, jeux d’essai, analyse et compte rendu |
Objectifs
• implémenter le tri fusion
• implémenter le tri rapide
• instrumenter comparaisons et déplacements
• étudier l’influence de l’ordre initial des données
Exercice 1 — Tri fusion
Implémenter la fusion de deux sous-tableaux puis le tri fusion complet.
Exercice 2 — Tri rapide
Implémenter une partition de Lomuto avec pivot final, puis une variante à pivot aléatoire.
Exercice 3 — Comparaison expérimentale
Comparer les deux tris sur des tableaux aléatoires, triés, inversés et presque triés.
Travail demandé :
• mesurer le temps ;
• compter les comparaisons ;
• compter les échanges ou copies ;
• répéter les expériences.
Correction du TP 6
Tri fusion
ZONE DE PSEUDO-CODE — Fusion Procédure Fusionner(T, gauche, milieu, droite) : G ← Copie(T[gauche..milieu]) D ← Copie(T[milieu+1..droite]) i ← 0 ; j ← 0 ; k ← gauche TantQue i < Taille(G) ET j < Taille(D) Faire Si G[i] ≤ D[j] Alors T[k] ← G[i] ; i ← i + 1 Sinon T[k] ← D[j] ; j ← j + 1 FinSi k ← k + 1 FinTantQue Copier les éléments restants de G puis de D FinProcédure |
ZONE DE PSEUDO-CODE — Tri fusion récursif Procédure TriFusion(T, gauche, droite) : Si gauche ≥ droite Alors Retourner FinSi milieu ← (gauche + droite) div 2 TriFusion(T, gauche, milieu) TriFusion(T, milieu + 1, droite) Fusionner(T, gauche, milieu, droite) FinProcédure |
Tri rapide
ZONE DE PSEUDO-CODE — Partition de Lomuto Fonction Partition(T, bas, haut) : pivot ← T[haut] i ← bas - 1 Pour j allant de bas à haut - 1 Faire Si T[j] ≤ pivot Alors i ← i + 1 Echanger(T[i], T[j]) FinSi FinPour Echanger(T[i + 1], T[haut]) Retourner i + 1 FinFonction |
ZONE DE PSEUDO-CODE — Tri rapide Procédure TriRapide(T, bas, haut) : Si bas < haut Alors p ← Partition(T, bas, haut) TriRapide(T, bas, p - 1) TriRapide(T, p + 1, haut) FinSi FinProcédure |
Critère | Tri fusion | Tri rapide |
|---|---|---|
| Temps garanti | Θ(n log n) | Pire cas Θ(n²) |
| Temps moyen | Θ(n log n) | Θ(n log n) |
| Mémoire | O(n) | O(log n) moyen |
| Stabilité | Oui | Non en général |
| Données déjà triées | Peu d’effet | Mauvais avec pivot extrême |
Interprétation attendue • Le tri fusion présente des performances régulières mais utilise un tableau auxiliaire. • Le tri rapide est souvent très efficace en pratique, mais dépend fortement du pivot. • La randomisation du pivot réduit la probabilité d’un comportement quadratique systématique. |
TP 7 — Méthodes de conception
Quatre petits problèmes permettent de mettre en évidence diviser pour régner, glouton, retour sur trace et programmation dynamique.
Durée | Prérequis | Livrable |
|---|---|---|
| 5 h | Récursivité, complexité, tris et tableaux | Code/pseudo-code, jeux d’essai, analyse et compte rendu |
Objectifs
• identifier un paradigme de conception adapté
• décrire les sous-problèmes et les décisions
• mettre en évidence les limites d’une stratégie
• comparer solution exacte, heuristique et coût de calcul
Partie A — Diviser pour régner
Exercice 1 — Maximum par division
Trouver le maximum d’un tableau en divisant récursivement l’intervalle en deux parties.
Partie B — Algorithme glouton
Exercice 2 — Sélection d’activités
Choisir un nombre maximal d’activités compatibles à partir de leurs heures de début et de fin.
Partie C — Retour sur trace
Exercice 3 — Somme de sous-ensembles
Déterminer s’il existe un sous-ensemble de valeurs positives dont la somme vaut une cible donnée.
Partie D — Programmation dynamique
Exercice 4 — Rendu de monnaie optimal
Calculer le nombre minimal de pièces nécessaire pour obtenir un montant, pour un système de pièces quelconque.
Correction du TP 7
Maximum par division
ZONE DE PSEUDO-CODE — Maximum récursif Fonction MaximumDC(T, g, d) : Si g = d Alors Retourner T[g] FinSi m ← (g + d) div 2 maxG ← MaximumDC(T, g, m) maxD ← MaximumDC(T, m + 1, d) Retourner Max(maxG, maxD) FinFonction Récurrence T(n) = 2T(n/2) + Θ(1), donc Θ(n). |
Sélection d’activités
ZONE DE PSEUDO-CODE — Stratégie gloutonne Fonction Selectionner(activites) : Trier activites par heure de fin croissante solution ← ListeVide() finDerniere ← -∞ Pour chaque activité a Faire Si a.debut ≥ finDerniere Alors Ajouter(solution, a) finDerniere ← a.fin FinSi FinPour Retourner solution FinFonction |
Somme de sous-ensembles
ZONE DE PSEUDO-CODE — Retour sur trace Fonction SousEnsemble(T, i, reste, choix) : Si reste = 0 Alors Retourner Vrai FinSi Si i = Taille(T) OU reste < 0 Alors Retourner Faux FinSi Ajouter(choix, T[i]) Si SousEnsemble(T, i + 1, reste - T[i], choix) Alors Retourner Vrai FinSi RetirerDernier(choix) Retourner SousEnsemble(T, i + 1, reste, choix) FinFonction Le pire cas explore jusqu’à 2ⁿ sous-ensembles. |
Rendu de monnaie optimal
ZONE DE PSEUDO-CODE — Tabulation Fonction MonnaieMin(pieces, montant) : dp[0] ← 0 Pour x allant de 1 à montant Faire dp[x] ← +∞ FinPour Pour x allant de 1 à montant Faire Pour chaque piece p Faire Si p ≤ x ET dp[x - p] ≠ +∞ Alors dp[x] ← Min(dp[x], dp[x - p] + 1) FinSi FinPour FinPour Retourner dp[montant] FinFonction |
Méthode | Décision principale | Complexité typique | Garantie |
|---|---|---|---|
| Diviser pour régner | Décomposer en sous-problèmes indépendants | Dépend de la récurrence | Exacte |
| Glouton | Prendre le meilleur choix local | Souvent polynomiale | Exacte seulement si propriété prouvée |
| Retour sur trace | Explorer et annuler | Souvent exponentielle | Exacte |
| Programmation dynamique | Mémoriser les sous-problèmes | Pseudo-polynomiale ou polynomiale | Exacte |
TP 8 — Graphes
Le dernier TP construit un petit module de graphes, puis implémente DFS et BFS.
Durée | Prérequis | Livrable |
|---|---|---|
| 5 h | Graphes, matrices/listes d’adjacence, piles, files et récursivité | Code/pseudo-code, jeux d’essai, analyse et compte rendu |
Objectifs
• représenter un graphe par matrice et liste d’adjacence
• convertir une représentation vers l’autre
• implémenter DFS et BFS
• rechercher un chemin et calculer les composantes connexes
Graphe de test
Utiliser un graphe non orienté de sommets A, B, C, D, E, F et d’arêtes : AB, AC, BC, BD, CE, DE, DF et EF.
Exercice 1 — Représentations
Construire la matrice d’adjacence et la liste d’adjacence. Écrire les fonctions AjouterSommet, AjouterArete et SontAdjacents.
Exercice 2 — Parcours en profondeur
Implémenter un DFS récursif puis itératif. Afficher l’ordre de visite.
Exercice 3 — Parcours en largeur
Implémenter BFS, calculer les distances depuis A et enregistrer les prédécesseurs.
Exercice 4 — Applications
Rechercher un chemin de A à F, tester la connexité et calculer les composantes après suppression de certaines arêtes.
Correction du TP 8
Liste d’adjacence du graphe
Sommet | Voisins |
|---|---|
| A | B, C |
| B | A, C, D |
| C | A, B, E |
| D | B, E, F |
| E | C, D, F |
| F | D, E |
DFS récursif
ZONE DE PSEUDO-CODE — Parcours en profondeur Procédure DFS(G, s, visite) : visite[s] ← Vrai Afficher(s) Pour chaque voisin v de s Faire Si Non visite[v] Alors DFS(G, v, visite) FinSi FinPour FinProcédure |
BFS avec distances et prédécesseurs
ZONE DE PSEUDO-CODE — Parcours en largeur Procédure BFS(G, source) : Pour chaque sommet v Faire visite[v] ← Faux distance[v] ← +∞ precedent[v] ← NUL FinPour F ← FileVide() visite[source] ← Vrai distance[source] ← 0 Enfiler(F, source) TantQue Non EstVide(F) Faire u ← Defiler(F) Pour chaque voisin v de u Faire Si Non visite[v] Alors visite[v] ← Vrai distance[v] ← distance[u] + 1 precedent[v] ← u Enfiler(F, v) FinSi FinPour FinTantQue FinProcédure |
ZONE DE PSEUDO-CODE — Reconstruire un chemin Fonction Chemin(precedent, source, cible) : Si cible ≠ source ET precedent[cible] = NUL Alors Retourner ListeVide() FinSi P ← PileVide() v ← cible TantQue v ≠ NUL Faire Empiler(P, v) v ← precedent[v] FinTantQue chemin ← ListeVide() TantQue Non EstVide(P) Faire AjouterFin(chemin, Depiler(P)) FinTantQue Retourner chemin FinFonction |
Composantes connexes
ZONE DE PSEUDO-CODE — Compter les composantes Fonction Composantes(G) : visite ← TableauFaux(NombreSommets(G)) nombre ← 0 Pour chaque sommet s Faire Si Non visite[s] Alors nombre ← nombre + 1 DFS(G, s, visite) FinSi FinPour Retourner nombre FinFonction Avec une liste d’adjacence, DFS et BFS ont une complexité Θ(|V| + |E|). |
Grille d’évaluation globale
Critère | Indicateurs | Pondération |
|---|---|---|
| Analyse du problème | Entrées, sorties, contraintes et cas particuliers correctement identifiés. | 10 % |
| Conception algorithmique | Pseudo-code clair, modulaire et cohérent. | 20 % |
| Correction fonctionnelle | Résultats corrects sur les jeux d’essai. | 25 % |
| Structures de données | Choix adapté et invariants respectés. | 15 % |
| Tests | Cas normaux, limites, erreurs et résultats attendus documentés. | 10 % |
| Complexité | Analyse temporelle et spatiale pertinente. | 10 % |
| Qualité du compte rendu | Présentation, explications et commentaires utiles. | 10 % |
Checklist de remise
• énoncé reformulé et hypothèses précisées ;
• pseudo-code dans une zone dédiée ;
• implémentation exécutable ;
• jeux d’essai et résultats attendus ;
• captures ou tableaux de résultats lorsque pertinent ;
• analyse de complexité ;
• discussion des limites et améliorations possibles ;
• code commenté sans commentaires redondants.
Synthèse des compétences
Compétence | TP principalement concernés |
|---|---|
| Analyser la complexité | TP 1, TP 6, TP 7, TP 8 |
| Manipuler des structures dynamiques | TP 2, TP 3, TP 4, TP 5 |
| Concevoir des algorithmes récursifs | TP 5, TP 6, TP 7, TP 8 |
| Comparer plusieurs solutions | TP 1, TP 6, TP 7 |
| Mettre en œuvre des graphes | TP 8 |
| Tester et documenter un programme | Tous les TP |