Explications et Exercices sur les Algorithmes
1. Algorithmes de Tri
• Bubble Sort : Compare deux éléments voisins et les échange si nécessaire. Simple mais lent
(O(n²)).
• Selection Sort : Cherche le plus petit élément restant et le place à la bonne position. O(n²).
• Insertion Sort : Insère chaque élément à sa place dans une liste triée. Bon si liste presque triée.
• Merge Sort : Divise en deux, trie puis fusionne. Complexité O(n log n).
• Quick Sort : Choisit un pivot, sépare, trie récursivement. Rapide en moyenne O(n log n).
2. Algorithmes de Graphes
• Dijkstra : Plus court chemin avec poids positifs.
• Bellman-Ford : Plus court chemin même avec poids négatifs.
• Floyd-Warshall : Plus courts chemins entre tous les sommets.
• Prim : Arbre couvrant minimal (MST) en ajoutant les arêtes les moins coûteuses.
• Kruskal : Arbre couvrant minimal en triant toutes les arêtes (évite les cycles).
3. Algorithmes de Recherche
• Linear Search : Parcourt un par un les éléments. O(n).
• Binary Search : Recherche dichotomique dans tableau trié. O(log n).
• Jump Search : Recherche en sautant par blocs dans tableau trié.
• Interpolation Search : Recherche par estimation de position.
• Exponential Search : Double l'indice puis fait un Binary Search.
4. Algorithmes sur Tableaux
• Kadane’s Algo : Sous-séquence avec somme maximale.
• Floyd’s Cycle Detection : Détecte si une liste chaînée contient une boucle.
• KMP : Recherche rapide de sous-chaîne.
• Quick Select : Trouve le k-ième plus petit élément.
• Boyer-Moore Majority Vote : Trouve l’élément majoritaire (> n/2 fois).
5. Algorithmes de Base
• Huffman Coding : Compression de données sans perte.
• Euclid’s Algo : Calcule le PGCD.
• Union-Find : Gère des ensembles disjoints (utilisé dans Kruskal).
Exercices d’Application
i Partie 1 (Tri & Recherche) : - Soit la liste [7, 2, 9, 4, 5, 1, 8]. 1. Trie la liste avec Insertion Sort.
2. Recherche si 5 existe avec Binary Search (après tri).
ii Partie 2 (Tableaux) : - Soit le tableau [-2, 1, -3, 4, -1, 2, 1, -5, 4]. 1. Applique Kadane’s Algo
pour trouver la sous-séquence de somme maximale.
iii Partie 3 (Graphes) : - Graphe : A--4--B, A--2--C, B--3--C, B--2--D, C--4--D 1. Trouve le plus
court chemin de A à D avec Dijkstra. 2. Trouve l’arbre couvrant minimal avec Prim.