Cours d’Algorithmique et
Méthodes de programmation
Destiné aux étudiants de deuxiè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 avancées (listes chaînées, arbres, graphes)
• Programmation récursive
• Techniques de conception d'algorithmes (diviser pour régner,
programmation dynamique, backtracking)
• Algorithmes de recherche et de tri avancés
Objectifs du cours
Objectif général :
• Analyser et appliquer les structures de données et les méthodes de
programmation avancées
• Objectifs intermédiaires :
• Comparer les structures de données avancées
• Appliquer des techniques de conception d'algorithmes
Objectifs spécifiques :
• Implémenter et optimiser des structures de données avancées en code
• Évaluer l'efficacité des algorithmes
Instruments de mesure et d’évaluation
• Quiz et examens écrits
• Exercices pratiques
• Projets de groupe
• Projets de programmation
• Travaux pratiques
Compétence à développer
Analyser et implémenter des structures de données avancées
pour optimiser des algorithmes
Savoirs :
• Structures de données avancées, algorithmes avancés et techniques de
programmation avancées
Savoir-faire :
• Conception et implémentation de structures de données, optimisation
d'algorithmes
Savoir-être :
• Persévérance, curiosité, capacité de travail en équipe
Structures de données avancées
Comment organiser les données à utiliser par un algorithme
Structures de données
Définition
Une structure de données est une manière spécifique
d’organiser et de stocker des données pour qu'elles puissent
être utilisées efficacement.
A quoi sert une structure de données ?
Les structures de données avancées permettent de résoudre
des problèmes complexes de manière plus efficace.
Listes chaînées
Définition
Une liste chaînée est une collection de nœuds où chaque nœud contient des
données et une référence au nœud suivant.
Types
• Liste chaînée simple
• Liste chaînée double
• Liste chaînée circulaire
Opérations
• Insertion
• Suppression
• Parcours
Listes chaînées simples
Particularité
• Chaque nœud contient des données et une référence au nœud
suivant. La liste commence par une référence appelée "tête" et
se termine par un nœud pointant vers null.
Illustration
[Tête] -> [Données|Next] -> [Données|Next] -> ... -> [null]
Listes chaînées simples
Insertion à la tête
Procédure InsertTete(valeur):
nouveauNoeud ← Créer un nouveau nœud
[Link] ← valeur
[Link] ← tête
tête ← nouveauNoeud
Fin Procédure
Listes chaînées simples
Insertion à la fin
Procédure InsertFin(valeur):
nouveauNoeud ← Créer un nouveau nœud
[Link] ← valeur
[Link] ← null
Si tête = null Alors
tête ← nouveauNoeud
Sinon
nœud_courant ← tête
Tant que nœud_courant.suivant ≠ null Faire
nœud_courant ← [Link]
Fin Tant que
[Link] ← nouveauNoeud
Fin Si
Fin Procédure
Listes chaînées simples
Suppression à la tête
Procédure SuprimeTete():
Si tête ≠ null Alors
tête ← tê[Link]
Fin Si
Fin Procédure
Listes chaînées simples
Suppression à la fin
Procédure SupprimeFin():
Si tête = null Alors
Retourner // La liste est vide
Si tê[Link] = null Alors
tête = null // Il n'y a qu'un seul nœud
Sinon
courant ← tête
Tant que [Link] ≠ null Faire
courant ← [Link]
Fin Tant que
[Link] ← null
Fin Procédure
Listes chaînées doubles
Particularité
• Chaque nœud contient des données, une référence au nœud suivant
et une référence au nœud précédent.
Illustration
[null] <- [Préc|Données|Next] <-> [Préc|Données|Next] <-> ... -> [null]
Listes chaînées doubles
Insertion à la tête
Procédure InsererTete(valeur):
nouveauNoeud ← Créer un nouveau nœud
[Link] ← valeur
[Link] ← tête
[Link] ← null
Si tête ≠ null Alors
tê[Link] ← nouveauNoeud
Fin Si
tête ← nouveauNoeud
Fin Procédure
Listes chaînées doubles
Insertion à la fin
Procédure InsererFin(valeur):
nouveauNoeud ← Créer un nouveau nœud
[Link] ← valeur
[Link] ← null
Si tête = null Alors
[Link] ← null
tête ← nouveauNoeud
Sinon
courant ← tête
Tant que [Link] ≠ null Faire
courant ← [Link]
Fin Tant que
[Link] ← nouveauNoeud
[Link] ← courant
Fin Si
Fin Procédure
Listes chaînées doubles
Suppression à la tête
Procédure SupprimeTete():
Si tête ≠ null Alors
tête ← tê[Link]
Si tête ≠ null Alors
tê[Link] ← null
Fin Si
Fin Si
Fin Procédure
Listes chaînées doubles
Suppression à la fin
Procédure SupprimeFin():
Si tête = null Alors
Retourner // La liste est vide
Si tê[Link] = null Alors
tête = null // Il n'y a qu'un seul nœud
Sinon
courant ← tête
Tant que [Link] ≠ null Faire
courant ← [Link]
Fin Tant que
[Link] = null
Fin Procédure
Listes chaînées circulaires
Particularité
• Le nœud final pointe vers le nœud initial, formant un cercle.
Illustration
[Head] -> [Données|Next] -> [Données|Next] -> ... -> [Données|Next] --|
|<--------------------------------------------------------------------|
Listes chaînées circulaires
Insertion à la tête
Procédure InsererTete(valeur):
nouveauNoeud ← Créer un nouveau nœud
[Link] ← valeur
Si tête = null Alors
tête ← nouveauNoeud
[Link] ← tête
Sinon
queue ← tête
Tant que [Link] ≠ tête Faire
queue ← [Link]
Fin Tant que
[Link] ← tête
[Link] ← nouveauNoeud
tête ← nouveauNoeud
Fin Si
Fin Procédure
Listes chaînées circulaires
Insertion à la fin
Procédure InsererFin(valeur):
nouveauNoeud ← Créer un nouveau nœud
[Link] ← valeur
Si tête = null Alors
tête ← nouveauNoeud
[Link] ← tête
Sinon
courant ← tête
Tant que [Link] ≠ tête Faire
courant ← [Link]
Fin Tant que
[Link] ← nouveauNoeud
[Link] ← tête
Fin Si
Fin Procédure
Listes chaînées circulaires
Suppression à la tête
Procédure SupprimeTete():
Si tête ≠ null Alors
Si tête = tê[Link] Alors
tête ← null
Sinon
[Link] ← tê[Link]
tête ← tê[Link]
Fin Si
Fin Si
Fin Procédure
Listes chaînées circulaires
Suppression à la fin
Procédure SupprimeFin():
Si tête = null Alors
Retourner // La liste est vide
Si tê[Link] = tête Alors
tête = null // Il n'y a qu'un seul nœud
Sinon
courant ← tête
Tant que [Link] ≠ tête Faire
courant ← [Link]
Fin Tant que
[Link] ← tête
Fin Procédure
Arbres
Définition
• Un arbre est une structure de données hiérarchique composée
de nœuds reliés par des arêtes. Chaque arbre a un nœud
appelé racine. Les autres nœuds sont appelés nœuds enfants,
et un nœud sans enfant est appelé une feuille.
Arbres
Concepts de base
• Racine : Le nœud principal d'un arbre.
• Nœud : Une structure contenant une valeur ou des données et
des références à ses nœuds enfants.
• Feuille : Un nœud qui n'a pas d'enfant.
• Hauteur : Le nombre de niveaux dans l'arbre.
• Profondeur : La distance du nœud à la racine.
Arbres
Arbres
Particularités
• Les arbres permettent de représenter des relations
hiérarchiques.
• Chaque nœud peut avoir zéro ou plusieurs enfants.
• Les arbres sont souvent utilisés pour modéliser des structures
de données complexes comme les systèmes de fichiers, les
bases de données, etc.
Arbres
Types
• Arbre Binaire : Chaque nœud a au plus deux enfants.
• Arbre Binaire de Recherche (ABR) : Arbre binaire où
pour chaque nœud, les valeurs du sous-arbre gauche
sont inférieures à la valeur du nœud, et les valeurs du
sous-arbre droit sont supérieures.
• Arbre AVL : Un ABR auto-équilibré où la différence de
hauteur entre les sous-arbres gauche et droit d'un
nœud est au plus 1.
Arbres
• AVL signifie Adelson-Velsky et Landis, d'après les noms de leurs
inventeurs, Georgy Adelson-Velsky et Evgenii Landis. Un arbre AVL est un
type d'arbre binaire de recherche qui s'auto-équilibre pour maintenir une
hauteur logarithmique, ce qui assure des opérations de recherche,
insertion et suppression efficaces.
Algorithmes dans un arbre
Insertion dans un Arbre binaire de Recherche (ABR)
Procédure InsertABR(racine, valeur):
Si racine = null Alors
racine ← Créer un nouveau nœud avec valeur
Sinon Si valeur < [Link] Alors
[Link] ← InsertABR([Link], valeur)
Sinon
[Link] ← InsertABR([Link], valeur)
Fin Si
Retourner racine
Fin Procédure
Algorithmes dans un arbre
Suppression dans un Arbre binaire de Recherche (ABR)
Procédure DeleteABR(racine, valeur):
Si racine = null Alors
Retourner racine
Si valeur < [Link] Alors
[Link] ← DeleteABR([Link], valeur)
Sinon Si valeur > [Link] Alors
[Link] ← DeleteABR([Link], valeur)
Sinon
Si [Link] = null Alors
Retourner [Link]
Sinon Si [Link] = null Alors
Retourner [Link]
[Link] ← MinValue([Link])
[Link] ← DeleteABR([Link], [Link])
Fin Si
Retourner racine
Fin Procédure
Algorithmes dans un arbre
Parcours en Pré-ordre
Le parcours en pré-ordre visite les nœuds dans l'ordre suivant :
nœud racine, sous-arbre gauche, sous-arbre droit.
Procédure PreOrder(racine):
Si racine ≠ null Alors
Imprimer [Link]
PreOrder([Link])
PreOrder([Link])
Fin Procédure
Algorithmes dans un arbre
Explication :
• Racine : On visite d'abord le nœud racine.
• Sous-arbre gauche : Ensuite, on visite récursivement tous les
nœuds du sous-arbre gauche.
• Sous-arbre droit : Enfin, on visite récursivement tous les
nœuds du sous-arbre droit.
Utilisation :
Ce type de parcours est utile pour créer une copie de
l'arbre ou pour évaluer des expressions préfixées (par
exemple, en notation polonaise).
Algorithmes dans un arbre
Parcours en En-ordre
Le parcours en en-ordre visite les nœuds dans l'ordre suivant :
sous-arbre gauche, nœud racine, sous-arbre droit.
Procédure InOrder(racine):
Si racine ≠ null Alors
InOrder([Link])
Imprimer [Link]
InOrder([Link])
Fin Procédure
Algorithmes dans un arbre
Explication :
• Sous-arbre gauche : On visite récursivement tous les nœuds
du sous-arbre gauche.
• Racine : On visite d'abord le nœud racine.
• Sous-arbre droit : Enfin, on visite récursivement tous les
nœuds du sous-arbre droit.
Utilisation :
Le parcours en En-ordre est particulièrement utile pour les
arbres binaires de recherche (ABR), car il visite les nœuds
dans l'ordre croissant de leurs valeurs. C'est donc idéal pour
obtenir une liste triée des éléments de l'arbre.
Graphes
Définition
• Un graphe est une structure de données composée de
sommets (ou nœuds) et d'arêtes qui relient des paires de
sommets. Les graphes peuvent être utilisés pour représenter
diverses relations entre les éléments, comme les réseaux
sociaux, les réseaux de transport, etc.
Graphes
Concepts de base
• Sommet : Un point ou nœud dans un graphe.
• Arête : Une connexion entre deux sommets.
Types
• Graphe Dirigé : Les arêtes ont une direction (ex : Twitter, où A
suit B mais B ne suit pas nécessairement A).
• Graphe Non Dirigé : Les arêtes n'ont pas de direction (ex :
Facebook, où l'amitié est mutuelle).
• Graphe Pondéré : Les arêtes ont des poids, représentant des
coûts, des distances, etc.
Graphes
Autres concepts
• Chaîne : Une séquence de sommets reliés par des arêtes et
parcouru sans tenir compte des sens desdits arêtes.
• Chemin : Une séquence de sommets reliés par des arêtes et
parcouru en tenant compte des sens desdits arêtes.
Graphes
Représentation
• Matrice d'Adjacence : Une matrice carrée où les lignes et les
colonnes représentent les sommets. Une cellule (i, j) contient 1
(ou le poids) s'il y a une arête entre les sommets i et j, sinon 0.
• Liste d'Adjacence : Un tableau de listes. Chaque élément du
tableau représente un sommet et contient une liste des
sommets adjacents.
Ajout d’une arête
Matrice d’adjacence
Procédure AjouterArete(matrice, u, v):
matrice[u][v] ← 1
Si graphe est non dirigé Alors
matrice[v][u] ← 1
Fin Procédure
Ajout d’une arête
Liste d’adjacence
Procédure AjouterArete(liste, u, v):
liste[u].ajouter(v)
Si graphe est non dirigé Alors
liste[v].ajouter(u)
Fin Procédure
Suppression d’une arête
Matrice d’adjacence
Procédure SupprimerArete(matrice, u, v):
matrice[u][v] ← 0
Si graphe est non dirigé Alors
matrice[v][u] ← 0
Fin Procédure
Ajout d’une arête
Liste d’adjacence
Procédure SupprimerArete(liste, u, v):
liste[u].enlever(v)
Si graphe est non dirigé Alors
liste[v].enlever(u)
Fin Procédure
Parcours dans un graphe
Parcours en largeur (Breadth-First Search « BFS »)
• Principe : Parcourt les sommets du graphe niveau par niveau,
en commençant par un sommet de départ et en visitant tous
ses voisins avant de passer au niveau suivant.
• Utilisation : Utile pour trouver le chemin le plus court dans un
graphe non pondéré ou pour la recherche de tous les sommets
à une distance donnée du sommet de départ.
Parcours dans un graphe
Parcours en largeur (Breadth-First Search « BFS »)
Procédure BFS(graphe, départ):
file ← FileVide()
visités ← TableauDeBooléens(taille=[Link])
[Link](départ)
visités[départ] ← vrai
Tant que file n'est pas vide Faire
sommet ← [Link]()
Imprimer sommet
Pour chaque voisin de sommet dans graphe Faire
Si visités[voisin] = faux Alors
[Link](voisin)
visités[voisin] ← vrai
Fin Procédure
Parcours dans un graphe
Parcours en profondeur (Depth-First Search « DFS »)
• Principe : Parcourt les sommets en allant le plus loin possible le
long de chaque branche avant de revenir en arrière. Commence
par un sommet de départ et explore aussi loin que possible le
long de chaque branche avant de backtracker.
• Utilisation : Utile pour détecter les cycles dans un graphe,
trouver les composants connectés et résoudre des puzzles
comme les labyrinthes.
Parcours dans un graphe
Parcours en profondeur (Depth-First Search « DFS »)
Procédure DFS(graphe, sommet, visités):
Imprimer sommet
visités[sommet] ← vrai
Pour chaque voisin de sommet dans graphe Faire
Si visités[voisin] = faux Alors
DFS(graphe, voisin, visités)
Fin Procédure
Procédure DémarrerDFS(graphe, départ):
visités ← TableauDeBooléens(taille=[Link])
DFS(graphe, départ, visités)
Fin Procédure
Recherche exponentielle et interpolative
Comment rechercher efficacement une donnée
Recherche exponentielle
Principe
• La recherche exponentielle est utilisée pour trouver un élément
dans une liste triée. Elle combine les avantages de la recherche
binaire et de la recherche par saut en augmentant la taille de la
sous-liste à chaque itération.
Recherche exponentielle
Procédure ExponentialSearch(liste, n, valeur):
Si liste[0] = valeur Alors
Retourner 0
i←1
Tant que i < n et liste[i] ≤ valeur Faire
i←i*2
Retourner BinarySearch(liste, i/2, min(i, n), valeur)
Fin Procédure
Procédure BinarySearch(liste, gauche, droite, valeur):
Tant que gauche ≤ droite Faire
milieu ← gauche + (droite - gauche) / 2
Si liste[milieu] = valeur Alors
Retourner milieu
Sinon Si liste[milieu] < valeur Alors
gauche ← milieu + 1
Sinon
droite ← milieu - 1
Fin Tant que
Retourner -1
Fin Procédure
Recherche interpolative
Principe
• La recherche interpolative est une version améliorée de la
recherche binaire pour les listes triées et réparties
uniformément. Elle estime la position de l'élément cible en
utilisant la valeur de l'élément.
Recherche interpolative
Procédure InterpolationSearch(liste, n, valeur):
gauche ← 0
droite ← n - 1
Tant que gauche ≤ droite et valeur ≥ liste[gauche] et valeur ≤ liste[droite] Faire
Si gauche = droite Alors
Si liste[gauche] = valeur Alors
Retourner gauche
Retourner -1
pos ← gauche + ((valeur - liste[gauche]) * (droite - gauche) / (liste[droite] - liste[gauche]))
Si liste[pos] = valeur Alors
Retourner pos
Si liste[pos] < valeur Alors
gauche ← pos + 1
Sinon
droite ← pos - 1
Fin Tant que
Retourner -1
Fin Procédure
Recherches exponentielle et interpolative
• Recherche Exponentielle : L'avantage de la recherche exponentielle
est qu'elle peut rapidement déterminer la plage où l'élément
recherché pourrait se trouver, puis appliquer une recherche binaire
sur cette plage. C'est particulièrement efficace pour les grandes
listes.
• Recherche Interpolative : La recherche interpolative est très efficace
pour les listes où les éléments sont répartis de manière uniforme. Elle
peut réduire le nombre de comparaisons nécessaires en estimant plus
précisément la position de l'élément recherché.
Ces algorithmes optimisent les opérations de recherche dans des
contextes spécifiques, rendant la recherche beaucoup plus rapide et
efficace que les méthodes linéaires classiques.
Programmation récursive
Simplifier son style de programmation
Principe de la récursivité
Tours d’Annoï
Le jeu est constitué d’une plaquette de bois où sont plantées trois
tiges. Sur ces tiges sont enfilés des disques de diamètres tous
différents. Les seules règles du jeu sont que l’on ne peut déplacer
qu’un seul disque à la fois, et qu’il est interdit de poser un disque sur
un disque plus petit.
Au début tous les disques sont sur la tige de gauche, et à la fin sur celle
de droite.
Principe de la récursivité
Tours d’Annoï
Principe de la récursivité
Tours d’Annoï (Algorithme)
Procédure ToursHanoi(n, source, destination, intermédiaire):
Si n = 1 Alors
Imprimer "Déplacer le disque 1 de" source "à" destination
Retourner
ToursHanoi(n - 1, source, intermédiaire, destination)
Imprimer "Déplacer le disque" n "de" source "à" destination
ToursHanoi(n - 1, intermédiaire, destination, source)
Fin Procédure
Tours d’Annoï
Explication
• Cas de base
Si il n'y a qu'un seul disque (n = 1), déplacer le disque
directement de la source à la destination.
• Appels récursifs
Déplacer n-1 disques de la source à la tour intermédiaire.
Déplacer le disque n de la source à la destination.
Déplacer les n-1 disques de la tour intermédiaire à la
destination.
Principe de la récursivité
Principe
La récursion est une technique de programmation où une
fonction s'appelle elle-même. Les fonctions récursives se
décomposent souvent en deux parties principales :
• Cas de base : La condition d'arrêt qui termine la récursion.
• Appel récursif : La condition dans laquelle la fonction
s'appelle elle-même avec des paramètres modifiés.
Principe de la récursivité
Types de récursion
• Récursivité Simple : Une fonction s'appelle elle-même une
seule fois.
• Récursivité Multiple : Une fonction s'appelle elle-même
plusieurs fois.
• Récursivité Imbriquée : Une fonction s'appelle elle-même à
l'intérieur d'un autre appel récursif.
• Récursivité Mutuelle : Deux fonctions ou plus s'appellent
mutuellement.
Principe de la récursivité
Récursivité simple : Factorielle
Fonction Factorielle(n):
Si n = 0 Alors
Retourner 1
Sinon
Retourner n * Factorielle(n - 1)
Fin Fonction
Principe de la récursivité
Récursivité multiple : Suite de Fibonacci
Fonction Fibonacci(n):
Si n ≤ 1 Alors
Retourner n
Sinon
Retourner Fibonacci(n - 1) + Fibonacci(n - 2)
Fin Fonction
Principe de la récursivité
Récursivité multiple : Fonction de Ackermann
Fonction Ackermann(m, n):
Si m = 0 Alors
Retourner n + 1
Sinon Si m > 0 et n = 0 Alors
Retourner Ackermann(m - 1, 1)
Sinon
Retourner Ackermann(m - 1, Ackermann(m, n - 1))
Fin Fonction
Principe de la récursivité
Récursivité mutuelle : Parité d’un entier positif
Fonction EstPair(n):
Si n = 0 Alors
Retourner vrai
Sinon
Retourner EstImpair(n - 1)
Fin Fonction
Fonction EstImpair(n):
Si n = 0 Alors
Retourner faux
Sinon
Retourner EstPair(n - 1)
Fin Fonction
Principe de la récursivité
Exercices pratiques
1. Récursiver et récursiver des algorithmes à structures répétitives
2. Rechercher l’algorithme de Tri-Fusion et analyser son pseudocode.
Tri-Fusion Procédure TriFusion(tableau):
Si taille(tableau) > 1 Alors
milieu ← taille(tableau) / 2
gauche ← tableau[0..milieu]
droite ← tableau[milieu..fin]
TriFusion(gauche)
TriFusion(droite)
i←0
j←0
k←0
Tant que i < taille(gauche) et j < taille(droite) Faire
Si gauche[i] < droite[j] Alors
tableau[k] ← gauche[i]
i←i+1
Sinon
tableau[k] ← droite[j]
j←j+1
k←k+1
Tant que i < taille(gauche) Faire
tableau[k] ← gauche[i]
i←i+1
k←k+1
Tant que j < taille(droite) Faire
tableau[k] ← droite[j]
j←j+1
k←k+1
Fin Procédure
Paradigme « Diviser pour régner »
Programmer avec élégance et moins d’effort
Principe « Diviser pour régner »
Exemple pratique 1 : Tri fusion (Merge Sort)
Algorithme :
1. Diviser le tableau en deux moitiés.
2. Appliquer récursivement le tri fusion aux sous-tableaux.
3. Fusionner les sous-tableaux triés pour obtenir le tableau trié
final.
Principe « Diviser pour régner »
Exemple pratique 2 : Recherche binaire
Algorithme :
1. Diviser le tableau trié en deux.
2. Comparer l'élément central avec la valeur recherchée.
3. Si elles sont égales, retourner la position.
4. Si la valeur recherchée est plus petite, effectuer la recherche
récursive dans la moitié gauche.
5. Sinon, effectuer la recherche récursive dans la moitié droite.
Principe « Diviser pour régner »
Exemple pratique 3 : Exponentiation rapide
Algorithme :
1. Diviser l'exposant par deux.
2. Multiplier la base par elle-même pour réduire l'exposant de
moitié.
3. Si l'exposant est impair, multiplier une fois de plus par la
base.
Exercices pratiques
1. Implémenter l’algorithme Tri fusion pour trier un
tableau d’entiers
2. Implémenter l’algorithme de la recherche binaire pour
rechercher un élément dans un tableau trié
3. Implémenter l’algorithme d’exponentiation rapide
pour calculer la puissance d’un nombre
Programmation dynamique
Optimiser la solution des problèmes complexes
Programmation dynamique
Définition
La programmation dynamique (DP) est une technique
d'optimisation qui consiste à résoudre un problème complexe en
le décomposant en sous-problèmes plus simples et en stockant
les résultats des sous-problèmes pour éviter les calculs
redondants.
Programmation dynamique
Principes de base
• Stockage des résultats intermédiaires: Utiliser des
structures de données comme des tableaux ou des
matrices pour stocker les résultats des sous-problèmes
déjà résolus.
• Décomposition en sous-problèmes: Diviser le problème
principal en sous-problèmes plus petits et les résoudre
indépendamment.
• Récurrence: Formuler la solution du problème principal
en fonction des solutions des sous-problèmes.
Programmation dynamique
Principes de base (suite)
• Optimalité: Chaque sous-problème doit être résolu de
manière optimale pour garantir la solution optimale du
problème principal.
Essentiellement, la programmation dynamique repose sur
deux approches principales:
• la mémorisation (Top-Down)
• programmation tabulaire (Bottom-Up).
Programmation dynamique
La mémorisation stocke les résultats des appels récursifs
pour éviter de les recalculer, tandis que la
programmation tabulaire remplit un tableau de manière
itérative.
En pratique, ces principes permettent de résoudre
efficacement des problèmes comme le calcul des séries
de Fibonacci, le problème du sac à dos, ou la plus longue
sous-séquence commune, entre autres.
Programmation dynamique
Suite de Fibonacci (version améliorée)
fonction fib(n):
si n <= 1:
retourner n
tableau = [0, 1]
pour i de 2 à n:
tableau[i] = tableau[i-1] + tableau[i-2]
retourner tableau[n]
Programmation dynamique
Problème de sac à dos
Formulation du problème
1. On dispose d'un ensemble d'objets, chacun ayant un poids et
une valeur.
2. On dispose d'un sac à dos qui peut supporter une capacité de
poids maximale.
3. L'objectif est de déterminer la combinaison d'objets qui
permet de maximiser la valeur totale sans dépasser la capacité
du sac.
Programmation dynamique
Problème de sac à dos
Résolution
1. Créer une matrice pour stocker les valeurs maximales
possibles.
2. Remplir la matrice en fonction du poids et de la valeur des
objets.
Programmation dynamique
Problème de sac à dos
fonction knapsack(W, poids, valeurs, n):
créer une matrice K de dimensions (n+1) x (W+1)
pour i de 0 à n:
pour w de 0 à W:
si i == 0 ou w == 0:
K[i][w] = 0
sinon si poids[i-1] <= w:
K[i][w] = maximum(valeurs[i-1] + K[i-1][w-poids[i-1]], K[i-1][w])
sinon:
K[i][w] = K[i-1][w]
retourner K[n][W]
Backtracking
Contourner l’impasse dans la recherche de la solution
Backtracking
Définition
Le backtracking est une technique algorithmique
utilisée pour résoudre des problèmes de manière
exhaustive en essayant de construire une solution
incrémentale et en abandonnant les choix dès
qu'une solution invalide est détectée.
Backtracking
Principe de base
• Construction incrémentale : Commencer par une
solution partielle vide et ajouter des éléments jusqu'à
obtenir une solution complète.
• Validation : Vérifier si la solution partielle est encore
valide après chaque ajout.
• Retour en arrière : Si une solution partielle devient
invalide, revenir en arrière pour essayer d'autres
possibilités.
Backtracking
Exemple pratique : Combinaison des nombres
Algorithme :
• Essayer toutes les combinaisons de nombres pour
atteindre une somme cible.
• Ajouter un nombre à la combinaison partielle et vérifier
si la somme est atteinte.
• Si la somme dépasse la cible, revenir en arrière.
Backtracking
Exemple pratique : Combinaison des nombres
Algorithme :
fonction combinationSum(candidats, cible):
résultats = []
fonction backtrack(combinaison, start, reste):
si reste == 0:
ré[Link](combinaison[:])
retourner
sinon si reste < 0:
retourner
pour i de start à len(candidats):
[Link](candidats[i])
backtrack(combinaison, i, reste - candidats[i])
[Link]()
backtrack([], 0, cible)
retourner résultats
Backtracking
Exemple pratique : Combinaison des nombres
Commentaire :
La fonction pop() est utilisée pour retirer et retourner le dernier
élément d'une liste (ou d'une pile). C'est très utile pour gérer des
structures de données comme les piles (LIFO - Last In, First Out).
Par exemple, si tu as une liste [1, 2, 3] et que tu fais [Link](), le
résultat sera 3 et la liste deviendra [1, 2].
Les algorithmes de tri
Organiser les données de manière croissante ou décroissante
Tri rapide (Quick Sort)
Principe
• Choisir un "pivot" dans le tableau.
• Réarranger le tableau de sorte que les éléments plus petits que
le pivot soient à gauche, et ceux plus grands soient à droite.
• Appliquer récursivement ce processus aux sous-tableaux gauche
et droit.
Tri rapide (Quick Sort)
Algorithme
fonction quickSort(arr, gauche, droite):
si gauche < droite:
pivotIndex = partition(arr, gauche, droite)
quickSort(arr, gauche, pivotIndex - 1)
quickSort(arr, pivotIndex + 1, droite)
fonction partition(arr, gauche, droite):
pivot = arr[droite]
i = gauche - 1
pour j de gauche à droite - 1:
si arr[j] < pivot:
i += 1
échanger arr[i] avec arr[j]
échanger arr[i + 1] avec arr[droite]
retourner i + 1
Tri par insertion (Insertion Sort)
Principe
• Diviser le tableau en une partie triée et une partie non triée.
• Prendre les éléments de la partie non triée un par un et les
insérer dans la position correcte de la partie triée.
Tri par insertion (Insertion Sort)
Algorithme
fonction insertionSort(arr):
pour i de 1 à longueur(arr):
clé = arr[i]
j=i-1
tandis que j >= 0 et arr[j] > clé:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = clé
Tri par tas (Heap Sort)
Principe
• Construire un tas binaire (max-heap) à partir du tableau.
• Répéter les étapes suivantes jusqu'à ce que le tas soit vide:
1. Échanger le premier élément (maximum) avec le dernier
élément non trié.
2. Réduire la taille du tas de 1.
3. Rétablir la propriété de tas sur le tableau réduit.
Tri par tas (Heap Sort)
Algorithme
fonction heapSort(arr):
construire un max-heap à partir de arr
pour i de longueur(arr) - 1 à 1:
échanger arr[0] avec arr[i]
maxHeapify(arr, i, 0)
fonction construireMaxHeap(arr, n):
pour i de n//2 - 1 à 0:
maxHeapify(arr, n, i)
fonction maxHeapify(arr, n, i):
plusGrand = i
gauche = 2*i + 1
droite = 2*i + 2
si gauche < n et arr[gauche] > arr[plusGrand]:
plusGrand = gauche
si droite < n et arr[droite] > arr[plusGrand]:
plusGrand = droite
si plusGrand != i:
échanger arr[i] avec arr[plusGrand]
maxHeapify(arr, n, plusGrand)
