Dossier complet — Algorithmique et structures de données 2

L1 · S2 · Informatique fondamentale

Dossier pédagogique original Matrice MI. Contenu d’entraînement non officiel; il ne remplace pas le support ou la maquette d’un établissement.

Objectifs d’apprentissage

• Implémenter des listes chaînées, piles et files en C ou Python en respectant leurs invariants.

• Choisir une structure de données selon les opérations dominantes, les coûts et les contraintes mémoire.

• Coder et expliquer les tris par insertion, sélection et fusion sur des séquences variées.

• Analyser des complexités en temps et en espace et relier une récurrence à une borne asymptotique.

• Construire des tests couvrant cas limites, doublons, ordre initial et erreurs de manipulation.

Prérequis

• Variables, fonctions, boucles, tableaux et références ou pointeurs ; bases de C et Python.

• Notions de récursion, tableaux indicés, contrats d’entrée/sortie et tests par assertions.

• Lecture élémentaire de la notation O, Θ et des preuves par invariant.

Cours

1. Listes chaînées

Une liste chaînée est une séquence de nœuds, chaque nœud contenant une valeur et une référence vers le suivant. En C, le pointeur NULL marque la fin :

typedef struct Noeud { int valeur; struct Noeud *suivant; } Noeud;

L’accès au i-ème élément est séquentiel, donc en $O(i)$, tandis que l’insertion en tête est en $O(1)$. La propriété essentielle est l’invariant « tete désigne le premier nœud et chaque lien mène au nœud suivant ». Une erreur fréquente consiste à perdre le pointeur suivant avant de relier le nouveau nœud, ou à déréférencer une liste vide. Exemple guidé : pour insérer 7 devant 4 → 9, on alloue n, met n->valeur=7, puis n->suivant=tete et enfin tete=n; le résultat est 7 → 4 → 9. Pour supprimer la tête, on mémorise l’ancienne tête, avance tete, puis libère l’ancien nœud. Point de contrôle : expliquer pourquoi parcourir n nœuds coûte $O(n)$ et écrire le cas liste vide.

Points-clés

• Un lien doit être sauvegardé avant toute modification de pointeur.
• Insertion en tête : coût constant ; accès par position : coût linéaire.
• Toute suppression doit traiter explicitement la liste vide et libérer la mémoire en C.

2. Piles et files

Une pile suit LIFO (last in, first out) : empiler ajoute au sommet et dépiler retire le dernier élément. Une file suit FIFO (first in, first out) : enfiler ajoute à l’arrière et défiler retire à l’avant. Une pile se code simplement avec un tableau et un indice sommet; une file efficace utilise un tableau circulaire avec tete, queue et un compteur. Les opérations usuelles doivent rester en $O(1)$ : déplacer tous les éléments pour retirer le premier d’un tableau est une mauvaise implémentation de file. Exemple guidé : pile vide, push(3), push(8), pop() renvoie 8, puis 3. File vide, enqueue('A'), enqueue('B'), dequeue() renvoie A. Dans les deux cas, il faut définir le comportement en sous-dépassement (structure vide) et, pour un tableau borné, en débordement. Ces abstractions servent à la récursion, à l’annulation, aux parcours en largeur et à l’ordonnancement. Point de contrôle : simuler une file circulaire de capacité 4 après A, B, retrait de A, puis ajout de C et D.

Points-clés

• LIFO caractérise la pile ; FIFO caractérise la file.
• Une file circulaire réutilise les cases libérées sans décaler les données.
• Tester vide, pleine et séquence de plusieurs opérations est indispensable.

3. Tris et complexité

Le tri fusion applique « diviser pour régner » : couper la séquence en deux, trier récursivement chaque moitié, puis fusionner deux listes triées. La fusion parcourt chaque élément au plus une fois et coûte $\Theta(n)$. La récurrence $T(n)=2T(n/2)+\Theta(n)$ donne $T(n)=\Theta(n\log n)$, avec une mémoire auxiliaire $\Theta(n)$ dans l’implémentation classique. Exemple guidé : [7, 2, 6, 3] devient [7,2] et [6,3], puis [2,7] et [3,6]; la fusion compare 2 et 3, prend 2, puis 3, 6, 7 : [2,3,6,7]. La limite pratique est l’allocation temporaire et le coût des copies ; en C, les indices doivent être contrôlés pour éviter un dépassement. La stabilité est obtenue si, en cas d’égalité, on choisit d’abord l’élément de gauche. Point de contrôle : expliquer pourquoi la fusion est linéaire et calculer la hauteur de récursion pour $n=16$.

Points-clés

• La division crée des sous-problèmes indépendants de taille voisine.
• La fusion linéaire mène à une complexité globale en $\Theta(n\log n)$.
• La mémoire auxiliaire et la gestion des égalités influencent l’implémentation.

4. Tris élémentaires : insertion et sélection

Le tri par insertion maintient un préfixe déjà trié et insère chaque nouvelle valeur à sa place. Pour une entrée de taille $n$, son coût est $O(n^2)$ au pire, mais il devient proche de $O(n)$ si la séquence est presque triée. Le tri par sélection cherche le minimum restant puis l’échange avec la première position libre ; il effectue $O(n^2)$ comparaisons, même sur une entrée favorable. Exemple guidé sur [5, 2, 4, 1] : insertion de 2 donne [2,5,4,1], puis 4 donne [2,4,5,1], puis 1 donne [1,2,4,5]. Pour sélection, le minimum 1 est échangé avec 5, puis le minimum de [2,4,5] est 2, etc. Un invariant utile pour insertion est « avant l’itération i, les positions 0 à i−1 sont triées ». Attention aux bornes et au décalage des éléments : un échange isolé ne suffit pas à préserver l’ordre relatif. Point de contrôle : compter les comparaisons sur [3,1,2] et dire quel tri est préférable si les données arrivent presque ordonnées.

Points-clés

• Insertion décale les valeurs et exploite les séquences presque triées.
• Sélection choisit un minimum par tour et reste quadratique en comparaisons.
• Un invariant de préfixe facilite la preuve de correction.

5. Comparer, tester et choisir une structure

Comparer des algorithmes demande de distinguer coût asymptotique, mémoire, stabilité, travail réel et contraintes d’usage. Une recherche dans une liste chaînée est $O(n)$ ; une insertion en tête est $O(1)$, mais l’accès aléatoire reste coûteux. Un tri par insertion consomme peu de mémoire et peut être excellent pour de petites séquences ; le tri fusion offre une garantie $O(n\log n)$ au prix d’un tampon. La notation $O$ borne un ordre de grandeur, elle ne prédit pas seule le temps sur une machine. Exemple guidé : pour 1 024 éléments, un tri fusion a environ 10 niveaux de division, alors qu’un tri quadratique peut examiner de l’ordre de $10^6$ paires. On complète l’analyse par des tests : cas vide, un élément, doublons, valeurs déjà triées, ordre inverse et valeurs négatives. En Python, des tests assert vérifient rapidement le contrat ; en C, Valgrind ou les sanitizers aident à détecter fuites et accès invalides. Point de contrôle : proposer une structure pour traiter des tâches dans leur ordre d’arrivée et justifier chaque opération en complexité.

Points-clés

• Le choix dépend du contrat, des opérations dominantes et des contraintes mémoire.
• Les cas limites révèlent souvent les erreurs de pointeurs et d’indices.
• Une mesure expérimentale complète l’analyse théorique sans la remplacer.

Exercices corrigés

Exercice 1 · Fondamental

Écrire inserer_tete(tete, x) en pseudo-code puis simuler son effet sur la liste 4 → 9 → 12 avec x = 2. Indiquer les coûts et les cas limites.

Correction détaillée

On crée un nouveau nœud n, on place x dans n, on affecte n.suivant = tete, puis on retourne n comme nouvelle tête. Simulation : n vaut 2 et pointe vers 4 ; la liste devient 2 → 4 → 9 → 12. Si la liste est vide, tete vaut NULL et n devient l’unique nœud. Le coût en temps est Θ(1), car aucun parcours n’est requis ; l’espace supplémentaire est Θ(1) hors nœud créé. Il faut vérifier l’allocation en C et ne jamais lire tete->suivant lorsque tete vaut NULL.

Exercice 2 · Fondamental

Une file bornée de capacité 5 contient, dans l’ordre logique, A, B, C. Effectuer dequeue, puis enqueue(D), enqueue(E), enqueue(F). Donner la séquence finale et expliquer l’usage d’un tableau circulaire.

Correction détaillée

Le premier dequeue retire A : il reste B, C. Les trois ajouts placent D, E, F derrière C, donc la séquence logique finale est B, C, D, E, F. Dans un tableau circulaire, l’indice d’insertion avance modulo 5 ; si la case 0 a été libérée par A, elle peut accueillir F après retour de l’indice en début de tableau. Un compteur de taille distingue une file vide d’une file pleine. Chaque opération est Θ(1). Une erreur serait de décaler B, C, D, E à chaque retrait, ce qui rendrait dequeue linéaire.

Exercice 3 · Intermédiaire

Appliquer le tri par insertion à [8, 3, 5, 1, 4]. Présenter l’état après chaque insertion et donner le nombre de décalages effectués.

Correction détaillée

Préfixe initial : [8]. Insertion de 3 : [3,8,5,1,4], un décalage (8). Insertion de 5 : [3,5,8,1,4], un décalage (8). Insertion de 1 : [1,3,5,8,4], trois décalages (8,5,3). Insertion de 4 : [1,3,4,5,8], deux décalages (8,5). Total : 7 décalages. Chaque étape conserve l’invariant d’un préfixe trié. Le résultat est croissant. Le coût observé est Θ(n²) dans cette configuration, même si l’algorithme peut être plus rapide sur une liste presque triée.

Exercice 4 · Intermédiaire

Écrire la récurrence du tri fusion pour n = 16 et détailler les niveaux de fusion. Calculer le nombre total d’éléments traités par niveau, en ignorant les constantes de comparaison.

Correction détaillée

La récurrence est T(n)=2T(n/2)+cn, avec T(1)=d. Pour 16, le niveau des sous-listes de taille 1 traite 16 éléments au total ; le niveau de taille 2 traite encore 16 ; puis tailles 4, 8 et 16, toujours 16 par niveau. Il y a log2(16)=4 niveaux de fusion (ou 5 niveaux si l’on compte le niveau des feuilles). Le travail de fusion est donc proportionnel à 16 × 4, soit Θ(16 log2 16)=Θ(64), plus les constantes de base. L’espace auxiliaire est Θ(16) pour un tampon réutilisé. La fusion doit comparer les têtes et recopier le reliquat quand une moitié est épuisée.

Exercice 5 · Avancé

Concevoir une file de tâches priorisées par deux files chaînées : une file urgente et une file normale. Décrire les invariants, les opérations et analyser le coût amorti d’un traitement qui prend toujours l’urgent disponible en premier.

Correction détaillée

On maintient quatre pointeurs : tête et queue pour chaque file, avec l’invariant que chaque chaîne est correctement terminée par NULL et que les tâches restent dans leur ordre d’arrivée à priorité égale. ajouter(t) choisit la chaîne selon la priorité et enfile en queue en Θ(1). traiter() dépile la tête urgente si elle existe, sinon la tête normale, donc Θ(1) ; si les deux sont vides, il signale l’absence de tâche. L’ordre global est « toutes les urgentes présentes avant une normale », sans réordonner les chaînes. Une implémentation robuste vérifie l’allocation, remet queue à NULL lors du retrait du dernier nœud et libère la tâche. Sur m ajouts et k traitements, le coût total est Θ(m+k), donc Θ(1) amorti par opération. La limite est la famine possible des tâches normales si les urgentes arrivent sans interruption ; on peut ajouter un compteur ou une règle de vieillissement, mais cela modifie le contrat.

Quiz d’autoévaluation

Question 1

Quelle discipline décrit une pile ?

• FIFO ✓ LIFO • Accès aléatoire garanti • Tri stable

Explication : Une pile retire le dernier élément ajouté : c’est LIFO, pour last in, first out.

Question 2

Quel est le coût d’une insertion en tête d’une liste chaînée, si la tête est connue ?

✓ Θ(1) • Θ(log n) • Θ(n) • Θ(n²)

Explication : Il suffit de relier le nouveau nœud à l’ancienne tête puis de déplacer le pointeur de tête.

Question 3

Quelle structure retire normalement le plus ancien élément ?

✓ Une file FIFO • Une pile LIFO • Un tableau non trié • Un arbre binaire quelconque

Explication : FIFO signifie first in, first out : l’élément arrivé en premier est retiré en premier.

Question 4

Quelle complexité est garantie par le tri fusion classique ?

• Θ(1) • Θ(log n) • Θ(n) ✓ Θ(n log n)

Explication : La division récursive et les fusions linéaires donnent Θ(n log n) pour toutes les entrées.

Question 5

Quel invariant caractérise le tri par insertion ?

• Le suffixe est toujours inversé ✓ Le préfixe déjà parcouru est trié • Toutes les valeurs sont distinctes • La taille diminue à chaque échange

Explication : Avant chaque insertion, le préfixe traité est trié ; l’étape suivante y insère une valeur.

Question 6

Pourquoi utiliser une file circulaire ?

• Pour rendre un tri stable ✓ Pour réutiliser les cases libérées • Pour supprimer toute limite de capacité • Pour accéder en O(log n)

Explication : Le modulo permet à l’indice de revenir au début et d’utiliser l’espace libéré sans décalage.

Question 7

Quel cas doit être testé explicitement lors d’une suppression en tête ?

✓ Une liste vide • Uniquement une liste de taille paire • Une liste déjà triée seulement • Une valeur positive

Explication : Sur une liste vide, il n’existe aucun nœud à déréférencer ou libérer.

Question 8

Quelle limite est typique du tri fusion avec tableau auxiliaire ?

• Il ne termine jamais ✓ Il exige Θ(n) mémoire supplémentaire • Il ne compare aucune valeur • Il ne fonctionne que sur des entiers

Explication : La fusion classique recopie les éléments dans un tampon de taille proportionnelle à n.

Glossaire

• Liste chaînée — Séquence de nœuds reliés par des références, avec accès séquentiel et insertions locales efficaces.
• Nœud — Cellule qui contient une donnée et un ou plusieurs liens vers d’autres cellules.
• Pile — Structure LIFO où insertion et retrait se font au même sommet.
• File — Structure FIFO où l’ajout se fait à l’arrière et le retrait à l’avant.
• Tri stable — Tri qui conserve l’ordre relatif de deux éléments ayant la même clé.
• Diviser pour régner — Méthode qui découpe un problème, résout récursivement les sous-problèmes et combine leurs résultats.
• Invariant — Propriété vraie avant et après chaque étape d’une boucle ou d’une opération.
• Complexité asymptotique — Description de l’évolution du temps ou de l’espace quand la taille n de l’entrée grandit.

TP · Gestionnaire de tâches avec file FIFO et historique sur pile

Une petite équipe veut traiter ses tâches dans l’ordre d’arrivée et conserver les trois dernières tâches terminées pour une annulation simple. Réaliser une version console en Python ou C, sans bibliothèque de file prête à l’emploi.

Objectifs

• Modéliser une file FIFO par une structure dédiée.

• Implémenter empiler et dépiler pour l’historique.

• Tester les cas vide, pleine si capacité fixée, et doublons.

• Comparer le coût des opérations et justifier les choix.

Étapes

1. Définir la tâche (identifiant, libellé, priorité facultative) et les invariants de la file.

2. Coder ajouter, traiter, est_vide et une pile d’historique ; documenter les erreurs.

3. Écrire au moins six tests : file vide, une tâche, plusieurs tâches, retrait complet, doublon, annulation.

4. Exécuter une démonstration avec dix tâches et relever le temps ou le nombre d’opérations.

5. Rédiger une courte analyse des coûts, limites et améliorations possibles.

Livrables attendus

• Code source commenté et instructions d’exécution.

• Jeu de tests reproductible avec sorties attendues.

• Note de 1 à 2 pages incluant invariants, complexités et limites.

Critères d’évaluation

• Fonctionnalité : FIFO et historique conformes aux scénarios.

• Robustesse : cas limites, erreurs et libération des ressources traités.

• Justification : complexités et invariants correctement argumentés.

• Qualité : code lisible, tests nommés et résultats reproductibles.

Piste de résolution

Utiliser deux extrémités pour la file afin que l’ajout en queue et le retrait en tête soient Θ(1). La pile d’historique conserve les tâches traitées ; pour limiter à trois éléments, dépiler le plus ancien exigerait une seconde structure ou une petite liste circulaire. Vérifier les transitions vide/non vide et séparer logique, affichage et tests.

Sujets originaux d’entraînement (non officiels)

Sujet original de préparation — session normale

Sujet d’entraînement original, non officiel : il ne s’agit jamais d’une épreuve d’une année passée ni d’un document institutionnel. Justifier les complexités et traiter les cas limites.

Exercice 1

Donner un pseudo-code de suppression de la tête d’une liste chaînée et l’appliquer à 6 → 10 → 13, puis au cas d’une liste à un seul nœud.

Correction : Si la tête est NULL, signaler une liste vide. Sinon mémoriser ancienne = tête, faire tête = tête.suivant, puis libérer ancienne et retourner tête. Sur 6 → 10 → 13, le résultat est 10 → 13. Sur un seul nœud, la nouvelle tête vaut NULL et la queue logique est vide. Le coût est Θ(1).

Exercice 2

Comparer insertion et sélection sur une séquence déjà triée de n éléments : donner leur ordre de grandeur et indiquer lequel choisir si la mémoire auxiliaire doit rester constante.

Correction : Le tri par insertion effectue environ n−1 comparaisons et aucun décalage important : Θ(n) dans ce cas favorable. La sélection cherche encore un minimum à chaque tour : Θ(n²) comparaisons. Les deux peuvent être codés en mémoire Θ(1), mais insertion est préférable pour cette entrée car elle exploite l’ordre existant. Il faut distinguer complexité favorable et pire cas.

Exercice 3

Expliquer la fusion de [1, 5, 9] et [2, 4, 10], en donnant les comparaisons et le résultat.

Correction : Comparer 1 et 2, recopier 1 ; comparer 5 et 2, recopier 2 ; comparer 5 et 4, recopier 4 ; comparer 5 et 10, recopier 5 ; comparer 9 et 10, recopier 9 ; la première liste étant épuisée, recopier 10. Résultat [1,2,4,5,9,10]. Chaque élément est considéré au plus une fois côté tête, donc la fusion est linéaire en la somme des tailles. La stabilité se conserve en prenant à gauche en cas d’égalité.

Sujet original de préparation — seconde session

Sujet d’entraînement original, non officiel : ce contenu n’est jamais une épreuve d’une année passée et ne prétend pas reproduire un sujet institutionnel. Présenter une démarche vérifiable.

Exercice 1

Simuler une pile initialement vide après push(4), push(7), pop(), push(2), pop(), puis donner la valeur restante.

Correction : Après push(4) : [4]. Après push(7) : [4,7] avec 7 au sommet. Le premier pop renvoie 7 et laisse [4]. Push(2) donne [4,2]. Le second pop renvoie 2 et laisse [4]. La valeur restante est donc 4. Chaque opération est Θ(1) avec un tableau ou une liste munie d’un sommet.

Exercice 2

Pour une file circulaire de capacité 4, donner les indices logiques après ajout de A, B, C, retrait de A, puis ajout de D et E. Signaler si une opération est impossible.

Correction : Après A, B, C, la file contient A,B,C et occupe trois cases. Le retrait de A libère sa case : B,C. L’ajout de D donne B,C,D. L’ajout de E donne B,C,D,E ; la file est pleine. Avec un compteur de taille, aucune opération n’est impossible dans cette séquence. L’indice d’arrière revient au début grâce au modulo 4. Un cinquième ajout serait refusé tant qu’aucun retrait n’a lieu.

Exercice 3

Proposer un test de non-régression qui différencie un tri non stable d’un tri stable, puis expliquer le résultat attendu.

Correction : Créer des enregistrements (clé, nom) : (2,A),(1,X),(2,B). Après tri par clé, un tri stable doit produire (1,X),(2,A),(2,B) : A reste avant B comme dans l’entrée. Un tri non stable peut produire (1,X),(2,B),(2,A) tout en étant correctement ordonné par clé. Le test compare donc l’ordre complet des enregistrements, pas seulement les clés. Pour un tri fusion qui choisit l’élément de gauche lorsque les clés sont égales, le résultat attendu est stable.

Parcours de révision sur quatre semaines

Semaine 1 · Listes chaînées et invariants

Dessiner les liens de cinq listes, coder insertion/suppression en tête, puis tester vide, singleton et doublons. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 2 · Piles et files

Implémenter une pile et une file circulaire ; simuler dix opérations sur papier et vérifier les coûts Θ(1). Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 3 · Tris élémentaires

Tracer insertion et sélection sur trois tableaux ; rédiger l’invariant et comparer meilleur, moyen et pire cas. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.

Semaine 4 · Tri fusion et synthèse

Coder fusion, résoudre sa récurrence, exécuter le TP ou un sujet de préparation en temps limité, puis corriger avec les cas limites. Avant de terminer, reformule les notions sans tes notes, vérifie les résultats dans le cours et note une difficulté précise à reprendre la semaine suivante.