Révisions — Algorithmique & Programmation

Chargement…

Tutoriels d'utilisation

Comment exploiter chaque application pour réviser efficacement les algorithmes de référence.

📘 Tris

Cette application visualise les deux tris fondamentaux de référence : le tri par insertion et le tri fusion.

Vue d'ensemble de l'écran

L'écran est divisé en trois zones :

Colonne de gauche : les paramètres (tableau à trier) et des exemples prédéfinis.
Centre : la visualisation du tableau (barres) et, pour le tri fusion, les sous-listes intermédiaires L1, L2, R.
Colonne de droite : le choix de l'algorithme, les boutons de navigation pas-à-pas, le pseudo-code synchronisé et les notes de complexité.

Comment l'utiliser

Étape 1. Choisis l'algorithme dans le menu déroulant en haut à droite (insertion ou fusion).

Étape 2. Modifie le tableau dans la colonne de gauche, ou clique sur un exemple prédéfini.

Étape 3. Clique sur Étape suivante → pour avancer pas-à-pas. Le pseudo-code surligne automatiquement la ligne en cours d'exécution.

Tri par insertion

L'algorithme prend chaque élément à partir du deuxième et l'insère à sa place dans la partie triée (à gauche). Pour bien comprendre :

Observe la barre orange : c'est l'élément en cours d'insertion (la "carte" qu'on tient en main).
Les comparaisons décalent les éléments plus grands vers la droite jusqu'à trouver la bonne position.
Complexité : O(n²) dans le pire cas, O(n) si déjà trié.

Essaie d'abord un tableau de 5 éléments pour suivre toutes les étapes. Le tri par insertion est intuitif si tu l'imagines comme trier un jeu de cartes en main.

Tri fusion (merge sort)

L'algorithme utilise la stratégie "diviser pour régner" : il scinde la liste en deux, trie chaque moitié récursivement, puis fusionne les deux moitiés triées.

Tu vois apparaître L1 et L2 (les deux moitiés) puis R (le résultat fusionné).
L'interclassement compare en parallèle le premier élément de chaque liste et prend toujours le plus petit.
Complexité : O(n log n) dans tous les cas. Meilleur que l'insertion pour les grands tableaux.

Le tri fusion est récursif. La visualisation linéarise les appels — pense que chaque "Résultat partiel R" correspond à la sortie d'un appel récursif qui se termine.

Points-clés à retenir

Tri	Idée	Complexité	Stable ?
Insertion	Insérer un à un dans la partie triée	O(n²)	Oui
Fusion	Diviser, trier, fusionner	O(n log n)	Oui

📘 Récursivité & Programmation dynamique

Cette application couvre les grands classiques de la récursivité et de la programmation dynamique : factorielle, exponentiation rapide, tours de Hanoï, Fibonacci (trois versions) et le rendu de monnaie.

Comment l'utiliser

L'interface est la même que les autres apps : paramètres à gauche, visualisation au centre, contrôles à droite.

Choisis l'algorithme dans le menu déroulant. Modifie les paramètres (n, exposant, nombre de disques, somme à rendre…) puis avance pas-à-pas.

Factorielle & exponentiation rapide

Deux algorithmes récursifs simples qui illustrent la pile d'appels.

Factorielle : fact(n) = n × fact(n-1). Complexité O(n).
Exponentiation rapide : xⁿ = (x²)^n/2 si n pair, sinon x · x^n-1. Complexité O(log n) au lieu de O(n) pour la méthode naïve.

Pour l'exponentiation rapide, essaie x=2, n=10. Tu verras qu'au lieu de 10 multiplications, l'algo n'en fait que 4 environ (log₂(10) ≈ 3,3).

Tours de Hanoï

L'algorithme récursif classique : déplacer n disques d'une tour A vers une tour C en passant par B, avec la règle qu'on ne peut jamais poser un grand disque sur un petit.

L'idée : pour déplacer n disques de A → C, on déplace d'abord (n-1) disques de A → B, puis le grand de A → C, puis (n-1) de B → C.
Complexité : 2ⁿ - 1 déplacements (exponentielle).

Avec n=4, on a déjà 15 déplacements à suivre. La visualisation montre la flèche du déplacement en cours — essaie d'anticiper le suivant.

Fibonacci : les trois versions

Le même problème, trois implémentations différentes pour illustrer la programmation dynamique.

Naïf récursif : fib(n) = fib(n-1) + fib(n-2). Très lent : O(φⁿ). On voit l'arbre d'appels exploser en taille.
Mémoïsation (top-down) : on mémorise les résultats déjà calculés. O(n).
Itératif (bottom-up) : on calcule du plus petit au plus grand. O(n), sans pile d'appels.

Compare le nombre d'étapes entre fib(8) naïf (≈ 67 appels) et fib(8) mémoïsé (8 appels effectifs). C'est l'illustration parfaite de la DP.

Rendu de monnaie

Problème : avec un système de pièces (par exemple {1, 2, 5, 10}), rendre une somme S en utilisant le minimum de pièces possible.

Version DP : construit une table M[0..S] où M[k] = nombre minimal de pièces pour rendre k. Optimal en toutes circonstances.
Version gloutonne : prend toujours la plus grosse pièce possible. Plus simple, plus rapide, mais peut être sous-optimale selon le système de pièces.

Teste les deux versions avec le système {1, 3, 4} et la somme 6 : la gloutonne donne 4+1+1=3 pièces, la DP trouve 3+3=2 pièces. Démonstration que la gloutonne n'est pas toujours optimale !

📘 Algorithmes de recherche & Hachage

Cette application couvre les algorithmes de recherche dans un tableau (séquentielle, dichotomique, interpolation), les tables de hachage avec chaînage, et la recherche de motif dans une chaîne (naïve et Rabin-Karp).

Recherche dans un tableau

Algorithme	Hypothèse	Complexité
Séquentielle	Tableau quelconque	O(n)
Dichotomique	Tableau trié	O(log n)
Interpolation	Tableau trié et distribution uniforme	O(log log n) en moyenne

Recherche dichotomique

L'algorithme phare : à chaque étape, on regarde l'élément au milieu et on élimine la moitié du tableau où la cible ne peut pas être.

Les bornes g (gauche) et d (droite) sont affichées en bleu.
L'élément du milieu m est surligné. S'il est égal à la cible, c'est trouvé. Sinon, on déplace une borne.

Avec un tableau de 16 éléments, la dichotomie trouve n'importe quelle valeur en au plus 4 comparaisons (log₂(16) = 4).

Interpolation

Une amélioration de la dichotomie : au lieu de toujours prendre le milieu, on estime la position attendue de la cible en fonction des valeurs aux bornes (comme chercher un mot dans un dictionnaire — on n'ouvre pas pile au milieu).

Très efficace si la distribution est uniforme. Devient O(n) dans le pire cas (distribution non uniforme).

Table de hachage avec chaînage

Une structure qui permet d'insérer et rechercher en O(1) en moyenne. Chaque clé est transformée par une fonction de hachage en un indice de tableau ; les collisions sont gérées par une liste chaînée à chaque case.

L'application montre la fonction de hachage utilisée (par défaut : clé mod m).
Les collisions sont visibles : plusieurs clés tombent dans la même case et sont chaînées.

Essaie d'insérer plusieurs clés avec le même reste modulo m pour voir le chaînage se construire.

Recherche de motif

Trouver une chaîne P de longueur m dans un texte T de longueur n.

Algorithme naïf : on essaie toutes les positions de départ. O(n·m) au pire.
Rabin-Karp : on compare des empreintes de hachage au lieu de comparer caractère par caractère. O(n+m) en moyenne.

Rabin-Karp utilise un hachage "roulant" : quand on glisse d'un caractère, on calcule le nouveau hachage en O(1) à partir de l'ancien. C'est cette astuce qui fait toute l'efficacité.

📘 Arbres binaires & Tas

Cette application visualise les parcours d'arbre (infixe, préfixe, postfixe, en largeur), les arbres binaires de recherche (ABR), les tas (heaps) et le tri par tas.

Définitions essentielles

ABR (Arbre Binaire de Recherche) : arbre binaire dans lequel, pour chaque nœud, toutes les clés du sous-arbre gauche sont strictement plus petites et toutes celles du sous-arbre droit sont plus grandes (ou égales).
Tas (heap) min : arbre binaire parfait (rempli niveau par niveau, de gauche à droite) où la clé de chaque nœud est ≤ aux clés de ses enfants. La racine contient donc toujours le minimum.
Représentation tableau du tas : le nœud d'indice i a ses enfants en 2i+1 et 2i+2.

Parcours d'arbre

Quatre façons de visiter tous les nœuds d'un arbre :

Infixe (gauche → racine → droite) : pour un ABR, donne les clés en ordre croissant.
Préfixe (racine → gauche → droite) : utile pour cloner ou sérialiser un arbre.
Postfixe (gauche → droite → racine) : utile pour libérer la mémoire (les fils avant le parent).
Largeur (BFS) : visite niveau par niveau, utilise une file FIFO.

Les flèches orange pointillées matérialisent les retours récursifs (backtrack) — c'est-à-dire quand on remonte d'un fils vers son parent. Très utile pour comprendre l'ordre exact de visite.

ABR : insertion et recherche

Insertion : à chaque nœud, on compare ; si plus petit on va à gauche, sinon à droite. Le nouveau nœud devient toujours une feuille. O(h) où h = hauteur.
Recherche : même logique, on élimine la moitié du sous-arbre à chaque comparaison.

Tas : insertion, suppression du min, tri par tas

L'opération clé du tas est la percolation.

Insertion (percolation ↑) : on ajoute la nouvelle clé comme feuille à la fin, puis on la fait remonter tant qu'elle est plus petite que son parent.
Suppression du min (percolation ↓) : on retire la racine, on met la dernière feuille à la place, puis on la fait descendre tant qu'elle est plus grande que son plus petit enfant.
Tri par tas : phase 1, on construit le tas (n insertions). Phase 2, on extrait le min n fois. Complexité O(n log n).

Dans la visualisation de la percolation, deux couleurs d'arêtes :

Orange pointillé fin = chemin prévu que va parcourir la valeur (annoncé dès l'ajout de la feuille).
Rouge pointillé épais = échange en cours.

Le chemin orange se rétrécit à chaque échange jusqu'à disparaître quand la percolation se termine.

📘 Graphes

L'application la plus riche : elle couvre les parcours de graphes (BFS, DFS), les composantes connexes, le tri topologique, l'algorithme de Kosaraju (composantes fortement connexes), la détection de cycle, les plus courts chemins (Dijkstra, Bellman-Ford) et les arbres couvrants de poids minimum (Prim, Kruskal).

Comment construire un graphe

Option 1. Choisis un exemple dans le menu déroulant en haut à gauche.

Option 2. Tape directement le graphe dans la zone de texte : une arête par ligne, format A B (non pondéré), A B w (pondéré) ou A B 3 → (orienté).

Tu peux zoomer sur le graphe avec la molette et déplacer la vue à la souris.

Parcours : BFS et DFS

BFS (parcours en largeur) : utilise une file FIFO, visite niveau par niveau. Calcule la distance non-pondérée depuis la source.
DFS (parcours en profondeur) : récursif, va le plus loin possible avant de remonter. Visualisation avec arêtes de retour récursif en pointillés orange.

DFS sert de brique pour de nombreux algorithmes : composantes connexes, tri topologique, Kosaraju, détection de cycle. Quand tu vois "DFS" mentionné ailleurs, c'est le même mécanisme.

Composantes connexes & tri topologique

Composantes connexes (graphe non orienté) : on lance un DFS depuis chaque sommet non visité ; chaque DFS forme une composante.
Tri topologique (graphe orienté acyclique) : on ordonne les sommets de telle sorte que pour toute arête u → v, u apparaisse avant v. Méthode : DFS + ordre postfixe inversé.
Kosaraju : trouve les composantes fortement connexes en deux DFS (un sur G, un sur G transposé).

Plus courts chemins

Algorithme	Type d'arêtes	Complexité
Dijkstra	Poids ≥ 0 uniquement	O((n+m) log n)
Bellman-Ford	Poids négatifs autorisés (sans cycle négatif)	O(n·m)

Dijkstra : choisit à chaque étape le sommet non visité de plus petite distance, puis relâche ses voisins. Visualisé avec un tableau d'évolution des distances.
Bellman-Ford : relâche toutes les arêtes n-1 fois. Plus lent mais accepte les poids négatifs et détecte les cycles négatifs.

Si tu utilises Dijkstra sur un graphe avec un poids négatif, le résultat est faux ! C'est pour ça qu'il faut Bellman-Ford dans ce cas.

ACPM (Arbre Couvrant de Poids Minimum)

Prim : commence par un sommet, ajoute à chaque étape l'arête de poids minimum reliant un sommet "dedans" à un sommet "dehors". Similaire à Dijkstra dans l'esprit.
Kruskal : trie toutes les arêtes par poids croissant, ajoute chaque arête sauf si elle crée un cycle. Utilise la structure Union-Find pour détecter les cycles efficacement.

La visualisation de Kruskal montre la structure Union-Find en action : chaque sommet a un "représentant", et fusionner deux composantes revient à pointer un représentant vers l'autre.

Détection de cycle

Pour un graphe orienté, un cycle existe si pendant un DFS on rencontre une arête vers un nœud actuellement en cours de traitement (arête arrière). L'application matérialise cela en surlignant les nœuds dans la pile d'appels.

Tableau récapitulatif

Catégorie	Algorithmes
Parcours	BFS, DFS
Connexité	Composantes, Kosaraju, tri topo, cycle
Plus courts chemins	Dijkstra, Bellman-Ford
ACPM	Prim, Kruskal