Algorithmes, structures de données et calculabilité

Algorithmes et complexité
© Emmanuel Chimi,
echimi_udla@[Link]
Unité 1: Introduction – Algorithmes et leur complexité et performance
 Algorithmes et complexité NOTES

CONTENU
1 Introduction ..................................................................................................... 3
1.1 Algorithme et ses propriétés .................................................................... 3
1.1.1 Notion d’algorithme .......................................................................... 3
1.1.2 Propriétés d’un algorithme ............................................................... 3
1.1.3 Exactitude, robustesse et vérification d’un algorithme .................... 4
1.1.4 Types d’algorithmes .......................................................................... 5
1.2 Complexité et performance d’un algorithme ........................................... 6
1.2.1 Notion de complexité ........................................................................ 6
1.2.2 Performance et analyse de performance d’un algorithme ............... 7
1.3 Théorie de la complexité .......................................................................... 7
1.4 Algorithme en tant qu’une technologie ................................................... 8
1.5 Avantages et inconvénients de l’informatique algorithme ...................... 9
1.6 Questions ................................................................................................ 10

IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 2

 Algorithmes et complexité NOTES

1 Introduction

1.1 Algorithme et ses propriétés

1.1.1 Notion d’algorithme

Un algorithme est une suite finie d'instructions mathématiquement rigoureuses,
utilisée dans l’ordre fixé pour résoudre une classe de problèmes donnée ou pour
effectuer un calcul ou une activité1. En informatique les algorithmes sont utilisés
comme spécifications pour effectuer des calculs ou des traitements sur des
données.
La compréhension et l'élaboration d'algorithmes (algorithmique) sont
essentielles à la compréhension de la tâche de programmation et chaque
étudiant en informatique doit s'imprégner des concepts d'algorithmes. En fait,
les algorithmes sont la clé de base pour comprendre la théorie et la pratique de
l'informatique.

1.1.2 Propriétés d’un algorithme

Parmi les propriétés caractéristiques d'un algorithme on cite:
1. Exactitude (Correctness): L'exactitude d'un algorithme est définie comme le
fait que les entrées fournies produisent la sortie souhaitée, ce qui indique
que l'algorithme a été conçu correctement. Elle indique aussi que l’analyse
de l’algorithme a été réalisée correctement.
2. Précision (Definiteness) – Chaque instruction doit être bien définie, c'est-à-
dire qu’elle doit être claire et sans ambiguïté.
3. Finitude (Finiteness) – L’algorithme doit se terminer après un nombre fini
d’étapes.
4. Efficacité (Effectiveness) – L’efficacité ou performance se mesure en termes
de temps et d'espace requis par un algorithme pour son exécution. Ainsi, un
algorithme doit prendre moins de temps et moins d'espace mémoire que
possible pour pour produire le résultat (output).
Les trois premières propriétés sont des propriétés logiques intrinsèques sans
lesquelles on ne saurait parler d’algorithme, tandis que l’efficacité est une
propriété quantifiable. L'exactitude est la propriété qui indique si l’algorithme

1
Même en déhors de l’informatique et des mathématiques
IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 3
 Algorithmes et complexité NOTES

résout le problème énoncé ou pas: Le output qu’il produit pour un input donné
est-il juste/correct? Quand à la précision elle indique la qualité technique avec
laquelle l'algorithme résout le problème.

1.1.3 Exactitude, robustesse et vérification d’un algorithme

Les algorithmes étant utilisés dans des systèmes critiques tels que les
équipements médicaux, les systèmes de transport (aérien et autres) ou les
systèmes financiers, il est important qu'ils soient fiables. En d'autres termes, ils
doivent produire une sortie correcte pour toute entrée valide. Des algorithmes
incorrects peuvent produire des résultats inexacts, voire dangereux. Ainsi,
l'exactitude est une propriété obligatoire et sensible pour un algorithme et qui
peut être particulièrement délicate dans certains contextes.
Un algorithme est dit correct s'il produit la sortie attendue pour chaque entrée
valide. Le processus de preuve de la correcteté ou exactitude d'un algorithme est
appelé vérification ou validation d'algorithme.
Pour vérifier l'exactitude d'un algorithme, nous utilisons généralement deux
méthodes: Les tests et la vérification formelle. Les tests impliquent
l'implémentation et l'exécution de l'algorithme sur différentes valeurs d'entrée
et la comparaison de la sortie avec le résultat attendu. Cette approche peut aider
à identifier les bugs ou les erreurs dans l'algorithme, mais elle ne garantit pas
l'exactitude pour toutes les entrées possibles (car il n'est pas possible de tester
toutes les entrées possibles).
La vérification formelle, en revanche, consiste à prouver mathématiquement
que l'algorithme est correct pour toutes les entrées possibles. Cette méthode
nécessite une spécification formelle des exigences de l'algorithme et une preuve
formelle de son exactitude à l'aide de techniques mathématiques telles que
l'induction, la preuve par contradiction ou l'identification d'une propriété
invariante qui est vraie avant et après chaque étape de l'algorithme. Les
techniques de preuve et de vérification représentent un sujet central de
l’informatique théorique.
Pour atteindre la fiabilité d’un algorithme l’exactitude va généralement avec la
robustesse. La robustesse d'un algorithme désigne sa capacité à fonctionner de
manière fiable et efficace dans diverses conditions et entrées, y compris dans le
cas de données d’entrée erronées. Un algorithme robuste est capable de gérer
des scénarios inattendus et des valeurs aberrantes sans impact significatif sur ses
performances. Cela est important dans les applications du monde réel où les
erreurs de données et d’utilisation sont inévitables. En d’autres termes, un

IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 4

 Algorithmes et complexité NOTES

algorithme robuste doit produire un état de sortie déterminée même dans des
situations inattendues.

1.1.4 Types d’algorithmes

Les algorithmes recensés jusqu'à présent en informatique peuvent être classés
dans l'une des catégories suivantes:
1. Algorithmes de force brute: Adoptent une approche simple qui essaie de
manière exhaustive toutes les solutions possibles. Cette approche est
applicable à de petits problèmes mais elle peut devenir impraticable pour les
plus grands en raison de sa grande complexité temporelle.
2. Algorithmes récursifs: Basés sur la méthode de récursion qui divise un
problème en sous-problèmes plus petits et similaires et s'applique de
manière répétée pour les résoudre jusqu'à atteindre un cas de base, ce qui le
rend efficace pour les tâches avec des structures récursives.
3. Algorithmes d’encryptage: Utilisés pour transformer les données en une
forme sécurisée et illisible à l'aide de techniques cryptographiques,
garantissant la confidentialité et la protection de la vie privée dans les
communications et transactions numériques.
4. Algorithmes de rétroaction (Backtracking): Basés sur une technique d'essais
et d'erreurs utilisée pour explorer des solutions potentielles en annulant les
choix lorsqu'ils conduisent à un résultat incorrect. Ils sont couramment
utilisés dans les énigmes et les problèmes d'optimisation.
5. Algorithmes de recherche: Conçus pour trouver une cible spécifique (clé)
dans un ensemble de données, permettant une récupération2 efficace des
informations à partir de collections triées ou non triées.
6. Algorithmes de tri: Ils visent à organiser les éléments dans un ordre
spécifique, comme numérique ou alphabétique, pour améliorer
l'organisation et la récupération des données.
7. Algorithmes de hachage: Convertissent les données en une valeur de
hachage de taille fixe, permettant un accès et une récupération rapides des
données dans les tables de hachage. Ils sont couramment utilisés dans les
bases de données et le stockage de mots de passe.
8. Algorithmes du ‘’Diviser pour maîtriser’’ (Divide and Conquer): Basés sur
une technique qui divise un problème complexe en sous-problèmes plus
petits, les résout indépendamment, puis combine (fusionne) leurs solutions
pour résoudre efficacement le problème d'origine.
9. Algorithmes gloutons (Greedy algorithm): Ils effectuent des choix
localement optimaux à chaque étape dans l'espoir de trouver un optimum

2
Rappel → Retrieval
IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 5
 Algorithmes et complexité NOTES

global, utile pour les problèmes d'optimisation mais ne conduisant pas

toujours à la meilleure solution.
10. Algorithmes de programmation dynamique: Ils stockent et réutilisent les
résultats intermédiaires pour éviter les calculs redondants, améliorant ainsi
l'efficacité de la résolution de problèmes complexes.
11. Algorithmes randomisés: Utilisent le caractère aléatoire (randomness) dans
ses étapes pour parvenir à une solution. Ces algorithmes sont souvent
utilisée dans les situations où une réponse approximative ou probabiliste
suffit.

1.2 Complexité et performance d’un algorithme

1.2.1 Notion de complexité

Un algorithme est une méthode permettant de résoudre une classe de
problèmes sur un ordinateur. La complexité d'un algorithme correspond au coût
de l'utilisation de l'algorithme pour résoudre l'un de ces problèmes. Ce coût est
mesuré en temps d'exécution et en espace de stockage ou en toute autre unité
pertinente. Dans la pratique on utilise le temps et l'espace et on dit que la
complexité a deux dimensions:
• La dimension temporelle ou complexité temporelle, et
• La dimension spatiale ou complexité spatiale.
La complexité temporelle (Time complexity ou computational time complexity)
est la complexité de calcul qui décrit la quantité de temps de traitement
nécessaire pour exécuter un algorithme. La complexité temporelle est
généralement estimée en comptant le nombre d'opérations élémentaires
effectuées par l'algorithme, en supposant que chaque opération élémentaire
prend un temps fixe. Ainsi, le temps nécessaire et le nombre d'opérations
élémentaires effectuées par l'algorithme sont considérés comme étant liés par
un facteur constant.
La complexité spatiale d'un algorithme correspond à la quantité d'espace
mémoire nécessaire pour utiliser l’algorithme dans la résolution du problème de
calcul en fonction de la taille des données d'entrée (input). Il s'agit de la quantité
de mémoire requise par un algorithme jusqu'à ce qu'il s'exécute complètement.
Cette quantité comprend l'espace mémoire (en mémoire principale de
l’ordinateur ou sur des mémoires secondaires) utilisé par les données d’entrée,
aussi appelé espace d'entrée, et toute autre mémoire (auxiliaire) que
l’algorithme utilise pendant l'exécution, appelée espace auxiliaire.

IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 6

 Algorithmes et complexité NOTES

1.2.2 Performance et analyse de performance d’un algorithme

En informatique, il existe parfois plusieurs algorithmes pour résoudre un
problème. Lorsque nous avons plusieurs algorithmes pour résoudre un
problème, nous devons sélectionner le meilleur, c'est-à-dire l’algorithme
présentant la meilleure performance: Algorithme optimal.
La performance d'un algorithme est déterminée par de plusieurs critères, parmi
lequels on peut citer les suivants:
• L'algorithme fournit-il la solution exacte au problème?
• L’algorithme est-il facile à comprendre?
• L’algorithme est-il facile à implémenter?
• Combien d'espace (mémoire) faut-il à l’algorithme pour résoudre le
problème posé?
• Combien de temps faut-il à l’algorithme pour résoudre le problème?
Nous pouvons définir la performance comme la mesure de la qualité de
l'algorithme. Elle est en relation directe avec la complexité: L'algorithme le plus
performant est celui qui a la plus petite complexité.
Complexité croît (↗ )  Performance décroît (↘)
L'analyse de performance nous aide à sélectionner le meilleur algorithme parmi
plusieurs algorithmes pour résoudre un problème. Nous pouvons dire que:
L’analyse de performance d’un algorithme est un processus de jugement
évaluatif sur les algorithmes.

1.3 Théorie de la complexité

L'analyse de performance des algorithmes que nous venons d’introduire repose
sur la théorie de la complexité. Cette théorie est une branche de l'informatique
théorique (theory of computation) qui étudie les ressources nécessaires pour
résoudre des problèmes en informatique, notamment en termes de temps et
d'espace mémoire. Elle vise deux grands objectifs: Classer les problèmes en
fonction de leur difficulté et déterminer les limites des algorithmes en tant que
moyen de résolution de problèmes. En d’autres termes la théorie de la
complexité se concentre sur les questions suivantes:
1. Quel est le temps et l'espace mémoire nécessaires pour résoudre un
problème?
2. Quels sont les problèmes qui peuvent être résolus efficacement et ceux
qui sont trop complexes pour être résolus en pratique?
3. Existe-t-il des limites fondamentales à la performance des algorithmes
pour résoudre certains problèmes?

IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 7

 Algorithmes et complexité NOTES

Parmi les démarches utilisées par la théorie de la complexité on a notamment les

classes de complexité et la réduction. La classification des algorithmes selon leur
complexité a permis à cette théorie d’adopter les classes de complexité
suivantes: P (problèmes résolubles en temps (au trop) polynomial), NP
(problèmes résolubles en temps non déterministe polynomial), NP-complet
(problèmes les plus difficiles de NP), etc. La réduction c’est la transformation
d'un problème en un autre problème pour montrer leur équivalence en termes
de difficulté.
La théorie de la complexité a des applications dans la programmation
informatique en général, et en particulier dans des domaines tels que:

• Cryptographie: Conception de systèmes cryptographiques sécurisés

(Idéalement incassables).
• Optimisation: Résolution de problèmes d'optimisation complexes.
• Intelligence artificielle: Développement d'algorithmes efficaces pour
l'apprentissage automatique (Machine learning) la robotique.
• Théorie des graphes: Etude des propriétés des graphes et de leurs
applications.
Les chercheurs en théorie de la complexité sont guidés par l’objectif de mieux
comprendre les limites des algorithmes et à développer de nouvelles techniques
pour résoudre des problèmes complexes.

1.4 Algorithme en tant qu’une technologie

Les algorithmes sont comme une technologie. Nous utilisons tous les
processeurs les plus récents et les plus performants, mais nous devons exécuter
des implémentations de bons algorithmes sur cet ordinateur afin de tirer le
meilleur parti de l'argent que nous avons dépensé pour avoir le processeur le
plus récent.
Rendons cet exemple plus concret en opposant un ordinateur plus rapide
(ordinateur A) exécutant un algorithme de tri dont le temps d'exécution sur n
valeurs croît comme n2 à un ordinateur plus lent (ordinateur B) exécutant un
algorithme de tri dont le temps d'exécution croît comme n log n . Ils doivent
chacun trier un tableau de 10 millions de nombres. Supposons que l'ordinateur A
exécute 10 milliards d'instructions par seconde (plus rapidement que n'importe
quel ordinateur séquentiel au moment de la rédaction de ce support de cours) et
que l'ordinateur B n'exécute que 10 millions d'instructions par seconde. C'est-à-
dire que l'ordinateur A est 1000 fois plus rapide que l'ordinateur B en termes de
puissance de calcul brute.

IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 8

 Algorithmes et complexité NOTES

Pour rendre la différence encore plus spectaculaire, supposons que le

programmeur le plus astucieux du monde code en langage machine pour
l'ordinateur A, et que le code résultant nécessite 2n2 instructions pour trier n
nombres. Supposons en outre qu'un programmeur moyen écrive pour
l'ordinateur B, en utilisant un langage de haut niveau avec un compilateur
inefficace, avec le code résultant prenant 50n log n instructions.

Ordinateur A (Plus rapide) Ordinateur B (Plus lent)

• Le temps d'exécution croît comme n2 • Le temps d'exécution croît comme n log n
• 10 milliards d'instructions par seconde • 10 millions d'instructions par seconde
• 2n instructions pour un problème •
2 50n log n instructions pour un problème
de taille n . de taille n .
• Temps mis pour n = 10 : 7
• Temps mis pour n = 107 :

2 ⋅ (107 ) 50 ⋅ 107 ⋅ log107

2

= 20 000 secondes = 1163 secondes

10 ⋅ 109 10 ⋅ 106
• Moins de 20 minutes
• Soit plus de 5,5 heures de temps

Ainsi, le choix d’un bon algorithme (algorithme avec un taux de croissance plus
lent) tel qu’utilisé par l’ordinateur B a beaucoup d’impact.

1.5 Avantages et inconvénients de l’informatique algorithme

L'approche algorithmique dans la résolution des problèmes est indéniablement
le paradigme central en informatique. On parle aussi de l'informatique
algorithmique (Algorithmic computing), c'est-à-dire l'informatique qui utilise des
algorithmes pour résoudre les problèmes.
L’utilisation d’algorithmes présente les avantages suivants:
• Communication efficace: L’algorithme étant écrit dans un langage naturel
comme l'anglais ou en pseudocode, il devient facile de comprendre la
description étape par étape d'une solution à un problème particulier.
• Débogage facile: Un algorithme bien conçu facilite le débogage pour détecter
les erreurs logiques survenues à l'intérieur du programme.
• Codage facile et efficace: Un algorithme n'est rien d'autre qu'un plan
(Blueprint) d'un programme qui aide à développer un programme.
• Indépendant du langage de programmation: Comme il est indépendant du
langage, il peut être facilement codé en incorporant n'importe quel langage
de haut niveau.
Parmi les inconvénients des algorithmes il faut citer le fait que développer des
algorithmes pour résoudre des problèmes complexes peut prendre
considérablement du temps et peut être difficile à comprendre. Comprendre une
logique complexe à l’aide d’algorithmes est une tâche difficile.
IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 9
 Algorithmes et complexité NOTES

1.6 Questions
1. Qu'est-ce qu'un algorithme?
2. Donnez la différence (ou le lien) entre un algorithme et un pseudo-code?
3. Quels sont les moyens de description (notation) d’un algorithme?
4. En quoi un algorithme est-il similaire et différent d’un programme?
5. Quelles sont les propriétés caractéristiques d’un algorithme?
6. Définissez l’exactitude d’un algorithme!
7. Définissez la robustesse d’un algorithme et mettez cette propriété en relation
avec la fiabilité!
8. Quels sont les moyens de preuve de l’exactitude d’un algorithme?
9. Quelles les situations qui mettent la robustesse d’un algorithme à rude
épreuve?
10. Faites la différence entre l’approche des algorithmes de rétroaction et celle
des algorithmes de diviser-et-maîtriser!
11. Quel est le principe de fonctionnement des algorithmes de hachage?
12. Quel est l’objet de la théorie de complexité?
13. Quelle est la raison d’être de l’analyse de performance des algorithmes?
14. Pourquoi tout bon programmeur informatique doit-il d’abord comprendre le
design des algorithmes?
15. Élaborez un algorithme permettant d'additionner trois nombres A, B et C.
Rédaction académique (Academic writing)
16. Rédigez une présentation sous le titre ‘’Algorithmes de hachage et exemples
d’applications’’ (maximum 4 pages A4)

IT - Informatique | © Emmanuel CHIMI, Draft 11/2024 10