Algorithmes, structures de données et calculabilité
Algorithmes et complexité
© Emmanuel Chimi,
echimi_udla@[Link]
Unité 3: Techniques de design d’algorithmes
Algorithmes et complexité NOTES
CONTENU
3 Techniques de design d’algorithmes ............................................................... 3
3.1 Conception d’algorithmes ........................................................................ 3
3.1.1 Rédaction d’un algorithme ................................................................ 3
3.1.2 Qualité d’un bon algorithme ............................................................. 4
3.2 Techniques de conception d'algorithmes................................................. 5
3.2.1 Approche ‘’Diviser pour maîtriser’’ ................................................... 6
3.2.2 Technique gloutonne ........................................................................ 6
3.2.3 Programmation dynamique .............................................................. 7
3.2.4 Branch-and-Bound ............................................................................ 8
3.2.5 Technique de backtracking................................................................ 8
3.2.6 Technique randomisée .................................................................... 10
3.3 Questions ................................................................................................ 11
IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 2
Algorithmes et complexité NOTES
3 Techniques de design d’algorithmes
3.1 Conception d’algorithmes
La conception de tout algorithme nécessite une certaine planification car il existe
différentes techniques, stratégies ou paradigmes de conception qui peuvent être
adoptés en fonction du domaine du problème et d'une meilleure
compréhension par le concepteur. Certaines de ces techniques peuvent
également être combinées tandis que le comportement limitant de l'algorithme
peut être représenté par une analyse asymptotique.
Dans ce chapitre nous aller examiner des exemples de techniques de conception
d'algorithmes et de notations asymptotiques. Mais avant cela il convient de
parler de la façon donc un algorithme doit être présenté et des qualités qui
doivent être visées et leur de la conception d'un algorithme.
3.1.1 Rédaction d’un algorithme
Il n'existe pas de standards bien définies pour l'écriture d'algorithmes. Il s'agit
cependant d'un problème qui dépend des ressources. Les algorithmes ne sont
jamais écrits avec un langage de programmation spécifique à l'esprit (Un autre
aspect de la généralité d’un algorithme).
Aujourd'hui tous les langages de programmation disposent des structures
algorithmiques de base de contrôle de flux telles que les boucles comme do, for,
while et les sélections comme if-else, etc. Un algorithme peut être écrit en
utilisant ces constructions communes.
Les algorithmes sont généralement écrits étape par étape, mais ce n'est pas
toujours le cas. La rédaction d'algorithmes est un processus qui intervient après
que le domaine du problème a été bien défini. Autrement dit, on doit être
conscient du domaine du problème pour lequel on développe une solution
algorithmique.
EXEMPLE 3.1
IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 3
Algorithmes et complexité NOTES
Les algorithmes instruisent les programmeurs comment écrire du code. Ainsi, un
algorithme peut être écrit de la façon suivante:
Dans la conception et l'analyse d'algorithmes, cette méthode est généralement
utilisée pour décrire un algorithme. Elle permet à l'analyste d'analyser
l'algorithme tout en ignorant facilement toutes les définitions indésirables. Elle
permet de voir quelles opérations sont utilisées et comment le processus
progresse.
Il est facultatif d'écrire les numéros d'étape. Pour résoudre un problème donné,
vous créez un algorithme au terme de votre travail de recherche de solution.
Cependant, un problème peut être résolu de différentes manières, comme
l’illustre la Figure 3.1. Il est ainsi possible de déduire plusieurs algorithmes de
résolution d'un problème donné. L'étape suivante consiste à évaluer les
algorithmes de résolution proposés et à mettre en œuvre la solution la plus
appropriée.
Figure 3.1
3.1.2 Qualité d’un bon algorithme
Nous avons présenté les propriétés caractéristiques d'un algorithme. Celles-ci
doivent être considérées comme un non négociables lors de la conception d'un
algorithme. En plus de ces propriétés il y a un certain nombre d’autres propriétés
qui doivent être visées lors du design d'un algorithme:
1. Modularité: On aboutit à un algorithme en décomposant le problème de
départ en petits modules ou petites étapes et en élaborant des algorithmes
pour ces sous-problèmes. L’algorithme global (modulaire) est donc une
fusion structurée des algorithmes de sous-problèmes.
IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 4
Algorithmes et complexité NOTES
2. Maintenabilité: L’algorithme doit être conçu de manière simple et structurée
afin qu’aucun changement significatif ne soit apporté à l'algorithme lorsque
l’on doit le redéfinir.
3. Fonctionnalité: L’algorithme prend en compte différentes étapes logiques
pour résoudre un problème du monde réel.
4. Robustesse: La robustesse fait référence à la capacité d'un algorithme à
définir clairement le problème à résoudre. Un algorithme robuste est capable
de gérer des entrées ou des erreurs inattendues avec élégance sans planter.
5. Convivialité (User-friendly) et clarté: Si l’algorithme est difficile à
comprendre, le programmeur ne va probablement pas comprendre
exactement ce que le concepteur à fait. Ce qui ouvre la porte à des codes qui
ne résolvent le problèmes qu’approximativement ou contenant des bugs. En
somme, l’algorithme doit être facile à comprendre et à assimiler (clarté), ce
qui le rend maintenable et modifiable.
6. Extensibilité: L’algorithme doit être extensible en général, et notamment si
un autre concepteur ou programmeur d’algorithme souhaite l’utiliser.
7. Évolutivité (Scalability): L’algorithme doit fonctionner pour des ensembles
de données et des tailles de problèmes plus volumineux sans diminution
significative des performances.
8. Fiabilité: L’algorithme doit fournir systématiquement des résultats corrects
dans différentes conditions et environnements.
9. Optimalité: Recherche de la solution la plus efficace dans les limites du
problème donné.
10. Adaptabilité: Idéalement, l’algorithme doit pouvoir être applicable à une
gamme de problèmes connexes avec des ajustements minimes.
11. Simplicité: Garder l’algorithme aussi simple que possible tout en répondant à
ses exigences, en évitant toute complexité inutile.
3.2 Techniques de conception d'algorithmes
Une technique de conception d'algorithme (ou stratégie ou paradigme) est une
approche générale de résolution de problèmes par algorithme qui s'applique à
une variété de problèmes de différents domaines de l'informatique.
L'apprentissage de ces techniques est de la plus haute importance pour les
raisons suivantes:
1. Elles fournissent un guide et de l’inspiration pour la conception
d’algorithmes pour de nouveaux problèmes, c’est-à-dire des problèmes pour
lesquels il n’existe pas d’algorithme satisfaisant connu.
2. Les algorithmes sont la pierre angulaire de l’informatique. Chaque science
s’intéresse à la classification de son sujet principal, et l’informatique ne fait
IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 5
Algorithmes et complexité NOTES
pas exception. Les techniques de conception d’algorithmes permettent de
classer les algorithmes selon une idée de conception sous-jacente; elles
peuvent donc servir de moyen naturel pour catégoriser et étudier les
algorithmes.
Bien que les techniques de conception d'algorithmes fournissent un ensemble
puissant d'approches générales pour la résolution algorithmique de problèmes,
la conception d'un algorithme pour un problème particulier peut toujours être
une tâche difficile. Certaines techniques de conception peuvent être tout
simplement inapplicables au problème en question. Parfois, plusieurs techniques
doivent être combinées, et il existe des algorithmes qu'il est difficile d'identifier
comme des applications des techniques de conception connues.
Sous les prochains titres nous allons découvrir une liste de plusieurs approches
de conception populaires.
3.2.1 Approche ‘’Diviser pour maîtriser’’
Le paradigme ‘’diviser pour maîtriser (Divide-and-Conquer) aide souvent à
découvrir des algorithmes efficaces. Il s'agit d'une approche descendante (top-
down approach). Les algorithmes qui suivent les techniques diviser pour
maîtriser impliquent trois étapes:
1. Diviser le problème original en un ensemble de sous-problèmes.
2. Résoudre chaque sous-problème individuellement, de manière récursive.
3. Combiner les solutions des sous-problèmes en une solution du problème
original dans son ensemble.
Voici quelques algorithmes standards basés sur la technique de diviser pour
maîtriser.
• La recherche binaire est un algorithme de recherche. ...
• Quicksort (Tri rapide) est un algorithme de tri. ...
• Merge Sort (Tri fusion) est également un algorithme de tri.
• Couple de points le plus proche: Le problème est de trouver le couple de
points le plus proche dans un ensemble de points dans le plan xy. ...
3.2.2 Technique gloutonne
La méthode ou technique gloutonne (Greedy technique) est un paradigme
algorithmique qui construit une solution pièce par pièce, en choisissant toujours
la pièce suivante qui offre l'avantage le plus évident et le plus immédiat. Ainsi,
les problèmes où le choix d'une solution optimale localement conduit également
à une solution globale sont les mieux adaptés pour l’application de cette
IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 6
Algorithmes et complexité NOTES
technique. Les algorithmes basés sur cette technique sont aussi appelés
algorithmes gloutons (Greedy algorithms).
La méthode Greedy est utilisée essentiellement pour résoudre les problèmes
d'optimisation. Un problème d'optimisation est un problème dans lequel on
nous donne un ensemble de valeurs d'entrée, qui doivent être maximisées ou
minimisées (ce qu'on appelle objectif), c'est-à-dire certaines contraintes ou
conditions.
• Un algorithme glouton fait toujours le choix (critère glouton) qui semble
le meilleur à l'instant actuel (position actuelle de la progression), pour
optimiser un objectif donné.
• Un algorithme glouton ne garantit pas toujours la solution optimale,
mais il produit généralement une solution dont la valeur est très proche
de la solution optimale.
Exemples d'algorithmes gloutons:
• Algorithme d'arbre couvrant minimal (Minimal Spanning Tree) de Prim.
• Problème du voyageur de commerce (Travelling Salesman)
• Graphes - Coloriage de carte.
• Algorithme d'arbre couvrant minimal de Kruskal.
• Algorithme d'arbre couvrant minimal de Dijkstra.
• Graphes - Couverture des sommets.
• Problème de sac à dos (Knapsack Problem).
• Problème d’ordonnancement (ou de planification) de tâches.
3.2.3 Programmation dynamique
La programmation dynamique (Dynamic Programming, DP) est une technique
algorithmique permettant de résoudre un problème d'optimisation en le
décomposant en sous-problèmes plus simples et en utilisant le fait que la
solution optimale au problème global dépend de la solution optimale à ses sous-
problèmes.
La programmation dynamique est à la fois une méthode d'optimisation
mathématique et une méthode de programmation informatique. La méthode a
été développée par Richard Bellman dans les années 1950 et a trouvé des
applications dans de nombreux domaines, de l'ingénierie aérospatiale à
l'économie.
La programmation dynamique est utilisée lorsque nous avons des problèmes qui
peuvent être divisés en sous-problèmes similaires, de sorte que leurs résultats
peuvent être réutilisés. La plupart du temps, ces algorithmes sont utilisés pour
l'optimisation. Avant de résoudre le sous-problème en cours, l'algorithme
IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 7
Algorithmes et complexité NOTES
dynamique essaiera d'examiner les résultats des sous-problèmes précédemment
résolus.
Voici quelques exemples de programmation dynamique:
• Tour de Hanoi,
• Le chemin le plus court (Shortest Path) de Dijkstra
• Suite de Fibonacci
• Multiplication de matrices en chaîne
3.2.4 Branch-and-Bound
La méthode de branch-and-bound (B&B) est une approche de résolution de
problème qui partitionne l'espace de solutions réalisables en sous-ensembles
plus petits de solutions. Le nombre de ces sous-ensembles peut être supposé
comme étant n'importe quelle valeur entière supérieure ou égale à zéro, c'est ce
qui donne à ce modèle sa désignation de modèle entier total.
La technique de B&B est utilisée pour résoudre les problèmes d'optimisation et
les problèmes de minimisation. En fait, si le problème de départ est un problème
de minimisation, nous pouvons le résoudre utilisant la technique de Branch-and-
bound en convertissant simplement le problème au préalable en un problème de
maximisation.
Un avantage important des algorithmes de type branch-and-bound est que nous
pouvons contrôler la qualité de la solution attendue, même si elle n'est pas
encore trouvée. Le coût d'une solution optimale n'est que légèrement inférieur à
celui de la meilleure solution calculée. Branch-and-bound est un paradigme de
conception d'algorithme généralement utilisé pour résoudre les problèmes
d'optimisation combinatoire.
Voici quelques exemples de problèmes de branch-and-bound:
• Problèmes de sac à dos
• Problème du voyageur de commerce
• Problème d'ordonnancement des tâches (du travail).
3.2.5 Technique de backtracking
Un algorithme de backtracking ou rétroaction est un algorithme de résolution
de problèmes qui utilise une approche de force brute pour trouver le résultat
souhaité. L'approche de force brute essaie toutes les solutions possibles et
choisit les solutions souhaitées/meilleures.
Le backtracking est un algorithme général permettant de trouver des solutions à
certains problèmes de calcul, notamment les problèmes de satisfaction de
IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 8
Algorithmes et complexité NOTES
contraintes, qui construit progressivement des candidats aux solutions et
abandonne un candidat (‘’backtracks’’) dès qu'il détermine que le candidat ne
peut pas être complété par une solution valide.
L'algorithme fonctionne comme suit :
Backtrack(s)
Si ce n'est pas une solution, renvoie false
Si c'est une nouvelle solution, ajoute à la liste de
solutions
Sacktrack(expand s)
Cet algorithme résout le problème en construisant une solution étape par étape,
en augmentant les niveaux au fil du temps, en utilisant des appels récursifs. Un
arbre de recherche appelé arbre d'espace d'état (state-space tree) est utilisé
pour trouver ces solutions. Chaque branche d'un arbre d'espace d'état
représente une variable et chaque niveau représente une solution.
Un algorithme de backtracking utilise la méthode de recherche en profondeur
(depth-first search). Lorsque l'algorithme commence à explorer les solutions, la
fonction d'optimisation/sélection est appliquée afin que l'algorithme puisse
déterminer si la solution proposée satisfait aux contraintes. Si c'est le cas, il
continue à chercher. Si ce n'est pas le cas, la branche est supprimée et
l'algorithme revient au niveau précédent.
Dans tout algorithme de rétroaction, l'algorithme cherche un chemin vers une
solution réalisable qui inclut des points de contrôle intermédiaires. Si les points
de contrôle ne conduisent pas à une solution viable, le processus de recherche
peut revenir aux points de contrôle et emprunter un autre chemin pour trouver
une solution
Il existe les scénarios suivants dans lesquels on peut avoir recours au
backtracking:
• Il peut être utilisé pour résoudre une grande variété de problèmes. Nous
pouvons l'utiliser, par exemple, pour trouver une solution réalisable à un
problème de prise de décision.
• Les algorithmes de rétroaction se sont également révélés très efficaces
pour résoudre les problèmes d’optimisation.
• Dans certains cas, il est utilisé pour trouver toutes les solutions possibles
au problème de dénombrement.
• En revanche, le backtracking n'est pas considéré comme une technique
optimale de résolution de problèmes. Il est utile lorsque la solution d'un
problème n'a pas de contrainte de temps.
IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 9
Algorithmes et complexité NOTES
3.2.6 Technique randomisée
Un algorithme randomisé (Randomized algorithm) ou probabiliste est un
algorithme qui utilise un certain degré de hasard dans sa logique ou sa
procédure. Dans certains cas, les algorithmes probabilistes sont le seul moyen
pratique de résoudre un problème.
La sortie d'un algorithme randomisé sur une entrée donnée est une variable
aléatoire. Il peut donc y avoir une probabilité positive que le résultat soit
incorrect. Cependfant, tant que la probabilité d'erreur est faible pour chaque
entrée possible de l'algorithme, cela ne pose pas de problème.
Il existe deux principaux types d'algorithmes randomisés: Les algorithmes de
Las Vegas et les algorithmes de Monte-Carlo.
EXEMPLE 3.2
1. Dans le tri rapide, utiliser un nombre aléatoire pour choisir un pivot.
2. Essayer de factoriser un grand nombre en choisissant un nombre aléatoire
comme diviseur possible.
IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 10
Algorithmes et complexité NOTES
3.3 Questions
1. Qu'entend-on par paradigme de conception d'algorithme?
2. Comment fonctionne la Technique gloutonne? Donnez-en un exemple?
3. Donnez une différence entre les techniques d'algorithmes de rétroaction et
de randomisation.
IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 11
