06a Introduction à l’algorithmique
Table des matières
L'algorithmique regroupe l'ensemble des règles et techniques permettant de concevoir et de structurer des algorithmes. Ces derniers sont au cœur de l'informatique, mais aussi présents dans de nombreux autres domaines : mathématiques, logistique, intelligence artificielle, etc.
Définition : Un algorithme est une suite finie et ordonnée d’instructions permettant de résoudre un problème.
📚 Sources : Stéphane Grandcolas, Didier Müller, Wikipedia
1. Un peu d’histoire
⚓︎
📜 Le mot "algorithme" provient du nom du mathématicien perse Al Khwarizmi (780 – 850), auteur d’un ouvrage fondamental sur la résolution des équations linéaires et quadratiques. Ce livre a posé les bases du calcul numérique et de l’algèbre moderne.
💡 Évolution des algorithmes :
-
Moyen Âge : Utilisation dans des méthodes mathématiques et astronomiques.
-
17ᵉ siècle : Développement de la machine de Pascal et du calcul différentiel (Leibniz).
-
19ᵉ siècle : Ada Lovelace conçoit le premier programme pour la machine analytique de Charles Babbage.
-
20ᵉ siècle : Alan Turing formalise les algorithmes avec sa "machine de Turing".
-
Aujourd’hui : Algorithmes avancés en intelligence artificielle, cryptographie et optimisation.
⚡ Exemples d’algorithmes célèbres :
-
Algorithme d’Euclide (calcul du PGCD).
-
Tri rapide (QuickSort).
-
Recherche binaire.
-
Algorithme de Dijkstra (plus court chemin dans un graphe).
2. Efficacité d’un algorithme
⚓︎
Un algorithme efficace doit être capable de résoudre un problème en un temps raisonnable, même lorsque la taille des données d'entrée augmente.
💭 Exemple concret :
Imaginez qu’un moteur de recherche prenne plusieurs heures pour afficher des résultats. Un algorithme inefficace est inutilisable en pratique.
💡 Comparaison d'algorithmes
🔍 Cas du comptage des pages d’un livre :
On cherche à déterminer le nombre total de pages d’un livre.
| Méthode | Description | Nombre d’opérations |
|---|---|---|
| 📖 Méthode 1 | Compter les pages une à une | N opérations |
| 📑 Méthode 2 | Regarder directement le numéro de la dernière page | 1 opération |
✅ Observation :
-
La méthode 2 est N fois plus rapide que la méthode 1.
-
Si N = 1000 pages, la méthode 1 prend 1000 fois plus de temps que la seconde.
📊 Pourquoi mesurer l’efficacité d’un algorithme ?
Le temps d'exécution d’un programme dépend de plusieurs facteurs :
✔️ La complexité de l’algorithme.
✔️ La puissance du processeur utilisé.
✔️ La qualité de l'implémentation du programme.
✔️ La quantité de mémoire disponible.
✔️ Les autres tâches en arrière-plan.
⚠ Problème : Comparer des temps d’exécution bruts (ex. en secondes) est peu fiable car ces facteurs varient d’un ordinateur à l’autre.
📈 Comment comparer deux algorithmes ?
Plutôt que de mesurer le temps d'exécution, on compte le nombre d’opérations effectuées.
➡ On obtient ainsi une mesure généralisable et indépendante du matériel.
3. Création d’un algorithme
⚓︎
Les algorithmes sont au cœur des systèmes informatiques et doivent être correctement décrits, conçus et validés avant d’être implémentés dans un langage de programmation.
3.1. Le pseudo-code
⚓︎
Le pseudo-code est une manière d’écrire un algorithme de façon simple, avec une syntaxe proche du langage naturel.
Il n’impose pas un langage de programmation spécifique et permet de :
✔ Décrire clairement la logique de l’algorithme.
✔ Faciliter la compréhension entre programmeurs utilisant différents langages.
✔ Rédiger un plan structuré avant l’implémentation en code.
📌 Exemple :
Début
Demander un nombre à l’utilisateur
Si le nombre est positif alors
Afficher "Nombre positif"
Sinon
Afficher "Nombre négatif"
Fin
3.2. Règles d’écriture d’un algorithme
⚓︎
Un algorithme clair et bien structuré est plus facile à comprendre, à déboguer et à améliorer.
Lors de son exécution, il est souvent utile de suivre l’évolution des variables sous forme d’un tableau.
🔍 Exemple : Algorithme de calcul de racine carrée⚓︎
Début
Entrer un nombre n
Initialiser r à 0
Tant que r*r ≤ n faire
r ← r + 1
r ← r - 1
Afficher r
Fin
Pour faire une trace d’exécution, il est recommandé de numéroter les lignes, afin de repérer les retours de boucle.
📊 Trace de l’exécution avec n = 5
| #Ligne | n | r | Commentaire |
|---|---|---|---|
| 1 | 5 | 0 | Initialisation |
| 2 | 5 | 0 | Vérification : 0×0 ≤ 5 |
| 3 | 5 | 1 | Incrémentation de r |
| 2 | 5 | 1 | Vérification : 1×1 ≤ 5 |
| 3 | 5 | 2 | Incrémentation de r |
| 2 | 5 | 2 | Vérification : 2×2 ≤ 5 |
| 3 | 5 | 3 | Incrémentation de r |
| 2 | 5 | 3 | Vérification : 3×3 > 5 (fin de boucle) |
| 4 | 5 | 2 | Correction de r |
✅ Résultat : La racine entière de 5 est 2.
3.3. Définition du processus itératif
⚓︎
Un processus itératif est une méthode qui répète une action jusqu’à une condition d’arrêt.
Pour concevoir un algorithme itératif, il faut :
1️⃣ Identifier l’itération appliquée au problème.
2️⃣ Déterminer si le nombre d’itérations est connu ou non.
3️⃣ Définir les conditions initiales et les critères d’arrêt.
4️⃣ Vérifier que la condition d’arrêt est bien atteinte.
📌 Exemple : Dérive d’un iceberg
Un iceberg de 25 tonnes perd 10 % de sa masse chaque jour.
On veut savoir après combien de jours il restera moins d’une tonne.
💡 Algorithme :
Début
nombre_de_jours ← 0
masse_restante ← 25
Tant que masse_restante > 1 faire
masse_restante ← masse_restante * 0.9
nombre_de_jours ← nombre_de_jours + 1
Afficher nombre_de_jours
Fin
-
L’algorithme réduit la masse de l’iceberg chaque jour.
-
Boucle tant que la masse restante est > 1 tonne.
-
Nombre de jours nécessaire affiché en sortie.
3.4. Correction
⚓︎
Un algorithme correct doit respecter deux conditions :
1️⃣ Terminaison → Il doit toujours s’arrêter après un certain nombre d’opérations.
2️⃣ Correction partielle → Le résultat obtenu doit correspondre au problème posé.
👉 Correction Totale = Correction Partielle + Terminaison
🔍 Exemples d’erreurs courantes :
❌ Boucle infinie : Un algorithme sans condition d’arrêt.
❌ Erreur de logique : L’algorithme donne un mauvais résultat.
❌ Dépassement de mémoire : Mauvaise gestion des boucles et des tableaux.
4. Complexité
⚓︎
L'efficacité d’un algorithme peut être mesurée selon deux critères :
✔ La complexité temporelle : nombre d'opérations nécessaires pour exécuter l'algorithme.
✔ La complexité spatiale : quantité de mémoire utilisée par l'algorithme.
L'objectif est de trouver les algorithmes les plus rapides et les plus économes en ressources pour résoudre un problème donné.
4.1. Complexité temporelle
⚓︎
4.1.1. Règles de calcul
⚓︎
💡 Comment mesurer le coût d’un algorithme ?
⚠️ On utilise ici un modèle simplifié de coût : l’objectif est de comparer des algorithmes entre eux, pas d’obtenir un temps réel exact.
Chaque instruction d’un programme prend du temps pour s’exécuter.
On va attribuer un coût à chaque opération de base :
| Opération | Exemple | Coût |
|---|---|---|
| Affectation | a = 2 |
1 |
| Comparaison | 2 < 3 |
1 |
| Accès mémoire | Lire a |
1 |
| Affichage | print(a) |
2 |
| Opération arithmétique | 3 + 2 |
1 |
💡 Exemple simple
Analysons le coût de la ligne de code suivante :
a = a + 1
-
a + 1→ 1 opération d'addition -
Accès à
a→ 1 lecture mémoire -
Stockage du résultat dans
a→ 1 affectation
📝 Coût total : 1 + 1 + 1 = 3 unités de temps
🎯 Règle importante :
On ne compte pas la définition des fonctions ou des variables. On ne compte que leur exécution !
4.1.2. Algorithmes sans structure de contrôle
⚓︎
Activité n°1 : Calcul du coût T(n) d'un algorithme
Analyser le code suivant et calculer son coût :
def conversion(n: float) -> tuple :
h = n // 3600
m = (n - 3600 * h) // 60
s = n % 60
return h, m, s
Total des opérations
`h = n // 3600`
- 1 accès mémoire (lecture de `n`)
- 1 division entière (`//`)
- 1 affectation
Coût = 3
`m = (n - 3600 * h) // 60`
Détail de `(n - 3600 * h)` :
- 1 accès mémoire (lecture de `n`)
- 1 accès mémoire (lecture de `h`)
- 1 multiplication (`*`)
- 1 soustraction (`-`)
Puis `(... ) // 60` :
- 1 division entière (`//`)
Puis affectation :
- 1 affectation
Total ligne m : 2 accès mémoire + 3 opérations + 1 affectation = 6
`s = n % 60`
- 1 accès mémoire (lecture de `n`)
- 1 modulo (`%`)
- 1 affectation
Coût = 3
`return h, m, s`
- 3 accès mémoire (lecture de `h`, `m`, `s`)
Coût = 3
T(n) = 3 + 6 + 3 + 3 = 15 (constante)
La complexité étant constante, on note O(1) en notation de Landau.
4.1.3. Algorithmes sans structure conditionnelle
⚓︎
Activité n°2 : Calcul du coût T(n) d'un algorithme
Analyser le code suivant et calculer son coût :
def puissanceMoinsUn(n: int) -> int:
if n % 2 == 0:
res = 1
else:
res = -1
return res
Total des opérations
`if n % 2 == 0:`
- 1 accès mémoire (lecture de `n`)
- 1 modulo (`%`)
- 1 comparaison (`==`)
Coût = 3
`res = 1` (ou `res = -1`)
- 1 affectation
Coût = 1
`return res`
- 1 accès mémoire (lecture de `res`)
Coût = 1
T(n) = 3 + 1 + 1 = 5 (constante)
La complexité étant constante, on note O(1) en notation de Landau.
4.1.4. Algorithmes avec structure itérative
⚓︎
Activité n°3 : Calcul du coût T(n) d'un algorithme
Analyser le code suivant et calculer son coût :
def sommeEntiers(n):
somme = 0
for i in range(n + 1):
somme += i
return somme
Total des opérations
`somme = 0`
- 1 affectation
Coût = 1
`for i in range(n + 1):`
Calcul de `n + 1` (fait une seule fois au démarrage de la boucle) :
- 1 accès mémoire (lecture de `n`)
- 1 addition (`+`)
Coût = 2
À chaque itération, la boucle fournit une nouvelle valeur à `i` :
- 1 affectation (mise à jour de `i`)
Coût par itération = 1
`somme += i` (exécuté n+1 fois)
- 1 accès mémoire (lecture de `somme`)
- 1 accès mémoire (lecture de `i`)
- 1 addition (`+`)
- 1 affectation (écriture dans `somme`)
Coût par itération = 4
`return somme`
- 1 accès mémoire (lecture de `somme`)
Coût = 1
T(n) = 1 + 2 + (n+1) * (1 + 4) + 1
= 1 + 2 + 5(n+1) + 1
= 5n + 9 (linéaire)
La complexité de cet algorithme est dite linéaire.
Ce sera le cas de tous les algorithmes avec un coût du type : T(n) = an + b, où a et b sont des constantes.
Ici, le coût dépend linéairement du nombre d’éléments à traiter. On le note O(n).
4.1.5. Algorithmes avec deux structures itératives imbriquées
⚓︎
Activité n°4 : Calcul du coût T(n) d'un algorithme
Analyser le code suivant et calculer son coût :
def trouvemot(mots: list, fichier_test: list) -> list:
resultat = []
for mot in mots:
for ligne in fichier_test:
if mot in ligne:
resultat.append(mot)
return resultat
Total des opérations
`resultat = []`
- 1 affectation
Coût = 1
`for mot in mots:` (n itérations)
À chaque itération :
- 1 affectation (mise à jour de `mot`)
Coût par itération = 1
`for ligne in fichier_test:` (m itérations pour chaque mot)
À chaque itération :
- 1 affectation (mise à jour de `ligne`)
Coût par itération = 1
`if mot in ligne:` (test exécuté n*m fois)
- 1 accès mémoire (lecture de `mot`)
- 1 accès mémoire (lecture de `ligne`)
- 1 opération d’appartenance (`in`)
Coût par test = 3
`resultat.append(mot)` (exécuté k fois, avec 0 ≤ k ≤ n*m)
- 1 accès mémoire (lecture de `resultat`)
- 1 accès mémoire (lecture de `mot`)
- 1 opération d’ajout (`append`)
Coût par ajout = 3
`return resultat`
- 1 accès mémoire (lecture de `resultat`)
Coût = 1
T(n,m) = 1
+ n * [ 1 + m * ( 1 + 3 + (éventuellement 3 si append) ) ]
+ 1
Si on prend le pire cas (append à chaque test, donc k = n*m) :
T(n,m) = 1 + n * [ 1 + m * (1 + 3 + 3) ] + 1
= 2 + n * [ 1 + 7m ]
= 2 + n + 7nm
Cas particulier : si m ≈ n, alors T(n) = = 2 + n + 7n²
La complexité de cet algorithme est dite quadratique.
Ce sera le cas de tous les algorithmes avec un coût du type : T(n) = an² + bn + c, où a, b et c sont des constantes.
Le coût est fonction du carré du nombre d’éléments à traiter. On le note O(n²).
4.2. Complexité en espace
⚓︎
La complexité en espace est une mesure de l'espace utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. L'espace compte le nombre maximum de cases mémoire utilisées simultanément pendant un calcul.
4.3. Echelle de comparaisons
⚓︎
L'étude des différents algorithmes proposés dans la suite des activités (Tris, Recherche, Knn,...) permettra de mettre en évidence les différents ordres de grandeur suivants.
| Ordre de complexité | Exemples | Type de complexité |
|---|---|---|
| O(1) | Ici la complexité ne dépend pas des données. Accès à une cellule d'un tableau. | constante |
| O(log(n)) | Algorithme divisant le problème par une constante k. O(log(n)) pour la recherche dichotomique | Logarithmique |
| O(n) | Parcours de liste. | linéaire |
| O(n.log(n)) | Algorithme divisant le problème en nombre de sous-problèmes constants, dont les résultats sont réutilisés par recombinaison (Ex Tri fusion). | quasi-linéaire |
| O(n²) | Algorithme traitant généralement de couples de données (boucles imbriquées). Parcours d'une matrice de pixels. | quadratique |
Comparaison des temps d’exécution d’algorithmes de différentes complexités
| Taille | Complexité | 1 | log₂(n) | n | n log₂(n) | n² | n³ | 2ⁿ |
|---|---|---|---|---|---|---|---|---|
| n = 10² | ≃ 1µs | 6,6µs | 0,1ms | 0,6ms | 10ms | 1s | 4 × 10¹⁶a | |
| n = 10³ | ≃ 1µs | 9,9µs | 1ms | 9,9ms | 1s | 16,6mn | ∞ | |
| n = 10⁴ | ≃ 1µs | 13,3µs | 10ms | 0,1s | 100s | 11,5j | ∞ | |
| n = 10⁵ | ≃ 1µs | 16,6µs | 0,1s | 1,6s | 2,7h | 31,7a | ∞ | |
| n = 10⁶ | ≃ 1µs | 19,9µs | 1s | 19,9s | 11,5j | 31,7 × 10³a | ∞ |
Si on double la taille d’un tableau :
- Pour un algorithme de complexité n, le temps d’exécution est doublé
- Pour un algorithme de complexité n², le temps d’exécution est quadruplé
- Pour un algorithme de complexité log2(n), le temps d’exécution prend une unité car log2(2n). = log2(n) + 1
RESSOURCES :
- Vidéo (définition de la complexité) : https://www.youtube.com/watch?v=exaHKrP6RsA
- Vidéo (calcul de complexités) : https://www.youtube.com/watch?v=clZ4q5zPBlE
5. Exercices
⚓︎
=> CAPYTALE Le code vous sera donné par votre enseignant
Exercice 1 :
Calculer le coût de cet algorithme
largeur <- LireEntier()
longueur <- LireEntier()
aire <- largeur * longueur
perimetre <- (largeur + longueur) * 2
Afficher aire
Afficher perimetre
Exercice 2 :
Calculer le coût de cet algorithme
nbLivres <- LireEntier()
Si nbLivres < 10
prix <- nbLivres * 10
Sinon
prix <- nbLivres * 9
Afficher prix
Exercice 3 :
Calculer le coût de cet algorithme
X <- 1
Tant que X <= 100
Afficher "Bonjour !"
X <- X + 1
Exercice 4 :
Calculer le coût de cet algorithme
total <- 0
i <- 1
Tant que i <= 100
total <- total + i
i <- i + 1
Afficher total
Exercice 5 :
Calculer le coût de cet algorithme
iMax <- LireEntier()
total <- 0
i <- 1
Tant que i <= iMax
total <- total + i
i <- i + 1
Afficher total
Exercice 6 :
Calculer le coût de cet algorithme
iMax <- LireEntier()
total <- 0
Tant que iMax > 0
total <- total + iMax
iMax <- iMax - 1
Afficher total
Exercice 7 :
Calculer le coût de cet algorithme
taille <- LireEntier() 1
X <- 0 2
Tant que X < taille 3
Y <- 0 4
Tant que Y < taille 5
Si X = Y 6
Afficher "X" 7
Sinon 8
Afficher "." 9
Y <- Y + 1 10
Retour à la ligne 11
X <- X + 1 12