Cours d’Algorithmique et
Structures de données
Destiné aux étudiants de troisième année en Informatique
Animateur
Professeur
Ruffin-Benoît Ngoie Mpoy est professeur à l'Institut Supérieur
Pédagogique de Mbanza-Ngungu.
Expertise
Il est spécialisé dans le domaine des mathématiques appliquées, avec un doctorat et un
diplôme d'études approfondies en mathématiques appliquées.
Contact
Vous pouvez le contacter par email à l'adresse benoitmpoy@[Link] ou par telephone
au +243 89 71 11 489.
Contenu du cours
• Structures de données complexes (heaps, hash tables)
• Algorithmes de graphe (Kruskal, Coloration, Dijkstra, etc.)
• Algorithmes de recherche et d'optimisation
• Analyse avancée de la complexité
• Introduction à la recherche opérationnelle
Objectifs du cours
Objectif général :
• Synthétiser et évaluer des algorithmes et des structures de données
avancées
Objectifs intermédiaires :
• Optimiser des structures de données complexes
• Concevoir et évaluer des algorithmes optimisés
Objectifs spécifiques :
• Résoudre des problèmes complexes avec des algorithmes avancés
• Évaluer l'efficacité et l'optimalité des solutions proposées
Instruments de mesure et d’évaluation
• Quiz et examens écrits
• Exercices pratiques
• Travaux pratiques
• Projets de fin d'année
• Présentations orales
• Travaux de recherche
Compétence à développer
Concevoir et évaluer des algorithmes avancés pour résoudre
des problèmes complexes
Savoirs :
• Structures de données complexes, algorithmes de graphe, recherche
opérationnelle
Savoir-faire :
• Analyse et optimisation d'algorithmes, résolution de problèmes complexes
Savoir-être :
• Leadership, esprit critique, autonomie
Structures de données complexes
Comment organiser les données à utiliser par un algorithme
Introduction aux heaps
Définition
Un heap (tas) est une structure de données arborescente
spéciale qui satisfait la propriété de heap. Il existe deux types
principaux de heaps : min-heaps et max-heaps.
A quoi servent les heaps ?
Les heaps sont utilisés dans des algorithmes comme le tri par
tas, les files de priorité, et pour trouver rapidement les plus
grands ou les plus petits éléments d'un ensemble.
Principes des heaps
Min-Heap
Chaque nœud parent a une valeur inférieure ou égale à celle de
ses enfants.
Max-Heap
Chaque nœud parent a une valeur supérieure ou égale à celle
de ses enfants.
Exemples pratiques sur les heaps
Insertion dans un Min-Heap
fonction insertMinHeap(heap, valeur):
ajouter valeur à la fin du heap
i = taille(heap) - 1
tandis que i > 0 et heap[parent(i)] > heap[i]:
échanger heap[i] avec heap[parent(i)]
i = parent(i)
fonction parent(i):
retourner (i - 1) // 2
Fin Procédure
Exemples pratiques sur les heaps
Suppression de la racine dans un Min-Heap
fonction removeMin(heap):
si taille(heap) == 0:
retourner None
si taille(heap) == 1:
retourner [Link]()
root = heap[0]
heap[0] = [Link]()
heapifyMin(heap, 0)
retourner root
fonction heapifyMin(heap, i):
smallest = i
gauche = 2 * i + 1
droite = 2 * i + 2
si gauche < taille(heap) et heap[gauche] < heap[smallest]:
smallest = gauche
si droite < taille(heap) et heap[droite] < heap[smallest]:
smallest = droite
si smallest != i:
échanger heap[i] avec heap[smallest]
heapifyMin(heap, smallest)
Exemples pratiques sur les heaps
Insertion dans un Max-Heap
fonction insertMaxHeap(heap, valeur):
ajouter valeur à la fin du heap
i = taille(heap) - 1
tandis que i > 0 et heap[parent(i)] < heap[i]:
échanger heap[i] avec heap[parent(i)]
i = parent(i)
fonction parent(i):
retourner (i - 1) // 2
Exemples pratiques sur les heaps
Suppression de la racine dans un Max-Heap
fonction removeMax(heap):
si taille(heap) == 0:
retourner None
si taille(heap) == 1:
retourner [Link]()
root = heap[0]
heap[0] = [Link]()
heapifyMax(heap, 0)
retourner root
fonction heapifyMax(heap, i):
largest = i
gauche = 2 * i + 1
droite = 2 * i + 2
si gauche < taille(heap) et heap[gauche] > heap[largest]:
largest = gauche
si droite < taille(heap) et heap[droite] > heap[largest]:
largest = droite
si largest != i:
échanger heap[i] avec heap[largest]
heapifyMax(heap, largest)
Introduction aux hash tables
Définition
Une table de hachage (hash tables) est une structure de
données qui mappe les clés à leurs valeurs associées à l'aide
d'une fonction de hachage.
A quoi servent les hash tables ?
Les tables de hachage sont utilisées pour implémenter des
structures de données associatives telles que des dictionnaires
et des ensembles. Elles permettent des opérations de
recherche, d'insertion et de suppression très rapides.
Principes des hash tables
Fonction de hashage
Convertit une clé en un indice dans la table.
Gestion des collisions
Techniques pour gérer les situations où deux clés différentes
produisent le même indice.
Exemples de fonctions de hachage simples
Somme de valeurs ASCII
Cette fonction ajoute les valeurs ASCII de chaque caractère de la
clé et prend le reste de la division par la taille de la table de
hachage.
Algorithme
fonction hachageASCII(clé, tailleTable):
somme = 0
pour chaque caractère c dans clé:
somme += ord(c)
retourner somme % tailleTable
Exemples de fonctions de hachage simples
Polynomial Rolling Hash
Cette fonction utilise une base (généralement un petit nombre
premier) pour calculer une somme pondérée des caractères, et
prend le reste de la division par un grand nombre premier.
Algorithme
fonction polynomialHash(clé, tailleTable, base=31, mod=1e9+9):
hashValue = 0
puissance = 1
pour chaque caractère c dans clé:
hashValue = (hashValue + (ord(c) * puissance) % mod) % mod
puissance = (puissance * base) % mod
retourner hashValue % tailleTable
retourner somme % tailleTable
Exemples de fonctions de hachage simples
Techniques de chaînage
Les collisions se produisent lorsque deux clés différentes
produisent le même indice. Le chaînage est une technique pour
gérer ces collisions en utilisant des listes liées.
Principe de chaînage
• À chaque indice du tableau de hachage, au lieu de stocker
directement une valeur, on stocke une liste (ou chaîne) de
paires clé-valeur.
• Lorsque plusieurs clés hachent au même indice, leurs paires
clé-valeur sont ajoutées à la liste à cet indice.
Exemples pratiques sur les hash tables
Table de hachage avec chaînage
classe TableHachage:
initialiser():
taille = 10
table = [[] pour _ dans gamme(taille)]
fonction hachage(clé):
retourner somme(ord(c) pour c dans clé) % taille
fonction insérer(clé, valeur):
index = hachage(clé)
trouvé = faux
pour i, (k, v) dans énumérer(table[index]):
si k == clé:
table[index][i] = (clé, valeur)
trouvé = vrai
pause
si non trouvé:
table[index].append((clé, valeur))
fonction chercher(clé):
index = hachage(clé)
pour k, v dans table[index]:
si k == clé:
retourner v
retourner None
fonction supprimer(clé):
index = hachage(clé)
pour i, (k, v) dans énumérer(table[index]):
si k == clé:
del table[index][i]
del table[index][i]
Algorithmes sur les graphes
Modéliser et résoudre des problèmes avec des points et des lignes
Arbre couvrant de poids minimal
Problème
Trouver un sous-ensemble d'arêtes d'un graphe connecté et non
orienté qui connecte tous les sommets du graphe sans former de
cycles et avec la somme des poids des arêtes la plus faible possible.
Contextes
Réseaux de communication, conception de circuits.
Exemple
Algorithmes de Kruskal et de Prim.
Plus court chemin
Problème
Trouver le chemin le plus court entre deux sommets dans un
graphe pondéré, c'est-à-dire le chemin avec la somme des poids
des arêtes la plus faible.
Contextes
Systèmes de navigation, réseaux de transport.
Exemple
Algorithmes de Dijkstra et Bellman-Ford.
Ordre des sommets dans un graphe
Problème
Donner un ordre linéaire des sommets d'un graphe orienté
acyclique (DAG) tel que pour chaque arête (u, v), u précède v dans
l'ordre.
Contextes
Planification de tâches, ordonnancement de projets.
Exemple
Algorithmes des descendants directs, des ascendants directs, de
Demoucron.
Coloration des graphes
Problème
Attribuer des couleurs aux sommets d'un graphe de manière à ce
que deux sommets adjacents n'aient pas la même couleur, en
utilisant le nombre minimal de couleurs.
Contextes
Planification des horaires, Attribution des fréquences.
Exemple
Algorithmes de Welsh-Powell, First-Fit, Max-Stable.
Détermination des chemins de longueur k
Problème
Trouver s'il existe un chemin de longueur exactement k entre deux
sommets dans un graphe.
Contextes
Recherche d'itinéraires, vérification de contraintes.
Exemple
Algorithmes de Kauffmann-Malgrange, DFS modifié.
Travaux pratiques
Pour aller plus loin…
Travaux en groupe
Travaux demandés
1. Se documenter sur les problèmes vus (sur les graphes) et en
discuter en groupes. Choisir un membre pour présenter le
problème et les méthodes (algorithmes) pour les résoudre.
2. Analyser les différents algorithmes présentés et en discuter en
groupe.
3. Implémenter ces algorithmes dans un langage de
programmation au choix.