TEN-CODA
ALGORITHME AVANCÉS
BY
✍️ ROGELIO LE SAINT BONHOMME
Mosala moko, sanza ya misato 2025 00:34 GMT +1
Explication Détaillée des Algorithmes avec
Illustrations
📖 Sommaire
1. Prérequis
2. Les Heaps (Tas)
• Min-Heap
• Max-Heap
3. Tables de Hachage
4. Algorithme de Dijkstra (Plus Court Chemin)
5. Algorithme de Kruskal (Arbre couvrant minimal)
6. Coloration des Graphes
7. Ordonnancement des Sommets
✅ Ce document contient des explications claires, des illustrations, et des exemples en
Python pour mieux comprendre chaque algorithme !
🎓 1. Prérequis
Avant d’aborder ces algorithmes, il est recommandé d’avoir des connaissances de base en
:
• Structures de données : Listes, piles, files, arbres binaires.
• Programmation en Python : Notions de variables, boucles, fonctions et classes.
• Complexité algorithmique : Comprendre la notation O(n), O(log n), etc.
• Mathématiques discrètes : Graphes, ensembles, fonctions de hachage.
Si certains de ces concepts te semblent flous, il est conseillé de les réviser avant
d’aller plus loin !
📌 2. Les Heaps (Tas)
🔹 Définition
Un heap (ou tas) est une structure de données arborescente qui respecte une propriété
d'ordre :
✔ Min-Heap : chaque parent est inférieur ou égal à ses enfants.
✔ Max-Heap : chaque parent est supérieur ou égal à ses enfants.
📌 Illustration d’un Min-Heap
Exemple où on insère (10, 5, 20, 1) dans un Min-Heap :
1
/ \
5 20
/
10
✅ Pourquoi 1 est en haut ? Car dans un Min-Heap, la plus petite valeur est toujours à
la racine.
🔹 Algorithme d’Insertion dans un Min-Heap
1. Ajouter l’élément à la fin.
2. Remonter l’élément si son parent est plus grand (heapify up).
Pseudo-code
FONCTION insertMinHeap(heap, valeur):
Ajouter valeur à la fin du heap
i = index de la nouvelle valeur
TANT QUE i > 0 ET parent(i) > heap[i]:
Échanger heap[i] avec heap[parent(i)]
i = parent(i)
import heapq #💻 Code Python
min_heap = []
[Link](min_heap, 10)
[Link](min_heap, 5)
[Link](min_heap, 20)
[Link](min_heap, 1)
print("Min-Heap:", min_heap) # [1, 5, 20, 10]
🎨 Illustration d’un Max-Heap
20
/ \
10 5
/
1
✅ Pourquoi 20 est en haut ? Car dans un Max-Heap, la plus grande valeur est toujours à
la racine.
🔹 Algorithme d’Insertion dans un Max-Heap
1. Ajouter l’élément à la fin.
2. Remonter l’élément si son parent est plus petit (heapify up).
📝 Pseudo-code
FONCTION insertMaxHeap(heap, valeur):
Ajouter valeur à la fin du heap
i = index de la nouvelle valeur
TANT QUE i > 0 ET parent(i) < heap[i]:
Échanger heap[i] avec heap[parent(i)]
i = parent(i)
import heapq #💻 Code Python
max_heap = []
[Link](max_heap, -10)
[Link](max_heap, -5)
[Link](max_heap, -20)
[Link](max_heap, -1)
print("Max-Heap:", [-x for x in max_heap]) # [20, 10, 5, 1]
✅ Complexité : O(log n) car on remonte dans l'arbre.
📌 3. Tables de Hachage
🔹 Définition
Une table de hachage est une structure qui associe des clés à des valeurs pour un accès
rapide.
📌 Illustration
Imaginons une table de taille 5 et nous voulons stocker :
Alice → 25
Bob → 30
Eve → 22
Index Valeur
0 (vide)
1 (Bob, 30)
2 (vide)
3 (Alice, 25)
4 (Eve, 22)
🔹 Fonction de hachage
FONCTION hachage(clé, taille_table):
somme = 0
POUR chaque caractère c dans clé:
somme += valeur ASCII de c
FIN POUR
Retourner somme MOD taille_table
#💻 Code Python
def hachage(cle, taille_table):
return sum(ord(c) for c in cle) % taille_table
print(hachage("Alice", 5)) # Donne 3
📌 4. Algorithme de Dijkstra
🔹 Objectif
Trouver le chemin le plus court dans un graphe pondéré.
📌 Illustration
A --(1)--> B --(2)--> C
\ /
\(4) (3)
\ /
D
✅ Quel est le plus court chemin de A à C ?
✔ A → B (1)
✔ B → C (2)
✔ Total = 3 (au lieu de A → D → B → C = 4+3+2 = 9).
🔹 Algorithme
FONCTION Dijkstra(graphe, départ):
distances[tous les sommets] ← ∞
distances[départ] ← 0
File de priorité ← (0, départ)
TANT QUE file non vide:
sommet_actuel ← extraire_min(file)
POUR chaque voisin du sommet_actuel:
nouvelle_distance ← distance_actuelle + poids de l'arête
SI nouvelle_distance < distances[voisin]:
distances[voisin] ← nouvelle_distance
Ajouter (nouvelle_distance, voisin) dans file
#💻 Code Python
import heapq
def dijkstra(graphe, depart):
distances = {noeud: float('inf') for noeud in graphe}
distances[depart] = 0
pq = [(0, depart)]
while pq:
dist_actuelle, noeud_actuel = [Link](pq)
for voisin, poids in graphe[noeud_actuel].items():
distance = dist_actuelle + poids
if distance < distances[voisin]:
distances[voisin] = distance
[Link](pq, (distance, voisin))
return distances
📌 5. Algorithme de Kruskal (Arbre couvrant minimal)
🔹 Objectif
Construire un arbre couvrant minimal qui connecte tous les sommets avec un coût
minimal.
📌 Illustration
A --(1)--> B
| |
(3) (2)
| |
C --(4)--> D
🔹 Algorithme
FONCTION Kruskal(graphe):
Trier les arêtes par poids croissant
POUR chaque arête (u, v, poids):
SI u et v ne sont pas connectés:
Ajouter (u, v) à l'arbre
Union(u, v)
#💻 Code Python
class Graphe:
def __init__(self, sommets):
[Link] = sommets
[Link]êtes = []
def ajouter_arête(self, u, v, poids):
[Link]ê[Link]((poids, u, v))
def kruskal(self):
[Link]ê[Link]()
arbre_couvrant = []
parent = {sommet: sommet for sommet in [Link]}
def find(s):
if parent[s] != s:
parent[s] = find(parent[s])
return parent[s]
for poids, u, v in [Link]êtes:
if find(u) != find(v):
arbre_couvrant.append((u, v, poids))
parent[find(u)] = find(v)
return arbre_couvrant
📌 6. Coloration des Graphes
🔹 Définition
L’objectif est d’attribuer des couleurs aux sommets d’un graphe de manière à ce que
deux sommets adjacents n’aient pas la même couleur.
🎨 Illustration
A -- B
| |
C -- D
🔹 Algorithme
1. Trier les sommets par degré décroissant.
2. Assigner la plus petite couleur disponible.
3. Répéter pour chaque sommet.
📝 Pseudo-code
FONCTION ColorationGraphe(graphe):
Trier les sommets par degré décroissant
POUR chaque sommet:
Assigner la plus petite couleur non utilisée par ses voisins
💻 Code Python
def coloration_graphe(graphe):
couleurs = {}
for sommet in sorted(graphe, key=lambda x: len(graphe[x]), reverse=True):
couleurs_disponibles = {0, 1, 2, 3} - {[Link](voisin) for voisin in
graphe[sommet]}
couleurs[sommet] = min(couleurs_disponibles)
return couleurs
📌 7. Ordonnancement des Sommets
🔹 Définition
L’objectif est de trouver un ordre linéaire des sommets d’un graphe orienté acyclique
(DAG).
🎨 Illustration
A → B → C
↓
D → E
🔹 Algorithme
1. Trouver les sommets sans prédécesseur.
2. Ajouter ces sommets à l'ordre.
3. Supprimer les arêtes associées et répéter.
📝 Pseudo-code
FONCTION Ordonnancement(graphe):
Initialiser une liste de sommets sans prédécesseur
TANT QUE la liste n'est pas vide:
Ajouter un sommet à l'ordre
Supprimer ses arêtes sortantes
Mettre à jour la liste
💻 Code Python
from collections import deque
def tri_topologique(graphe):
degres_entrant = {sommet: 0 for sommet in graphe}
for voisins in [Link]():
for voisin in voisins:
degres_entrant[voisin] += 1
file = deque([s for s in graphe if degres_entrant[s] == 0])
ordre = []
while file:
sommet = [Link]()
[Link](sommet)
for voisin in graphe[sommet]:
degres_entrant[voisin] -= 1
if degres_entrant[voisin] == 0:
[Link](voisin)
return ordre