Leçon sur les Algorithmes
Par le meilleur prof de maths au monde
1. Qu'est-ce qu'un algorithme ?
Définition : Un algorithme est une suite finie et non ambiguë d'instructions permettant
de résoudre un problème ou d'obtenir un résultat.
En d'autres termes, c'est une recette de cuisine pour résoudre un problème particulier.
Les algorithmes sont partout dans notre vie quotidienne :
Recette de cuisine
Instructions pour assembler un meuble
Itinéraire pour aller d'un point A à un point B
Programmes informatiques
Caractéristiques d'un bon algorithme :
1. Précis : Chaque étape doit être claire et non ambiguë
2. Fini : Il doit se terminer après un nombre fini d'étapes
3. Efficace : Il doit résoudre le problème de manière optimale
4. Général : Il doit fonctionner pour différentes instances du problème
2. Exemple Concret : Algorithme de Cuisine
Prenons l'exemple simple d'une recette de café :
1 Prendre une tasse vide
2 Ajouter une cuillère à café de café moulu
3 Verser de l'eau chaude (pas bouillante) jusqu'à mi-hauteur
4 Mélanger avec une cuillère
5 Compléter avec de l'eau chaude
6 Ajouter du sucre si désiré
7 Mélanger à nouveau
8 Le café est prêt à être bu
Analyse : Cet algorithme respecte toutes les caractéristiques d'un bon algorithme : il est
précis, fini (8 étapes), efficace (produit un café) et général (fonctionne pour différentes
marques de café).
3. Exemple Mathématique : Algorithme d'Euclide
L'algorithme d'Euclide permet de trouver le Plus Grand Commun Diviseur (PGCD) de deux
nombres entiers.
1 Prendre deux nombres entiers a et b (avec a ≥ b > 0)
2 Calculer le reste r de la division de a par b
3 Si r = 0, alors le PGCD est b (STOP)
4 Sinon, remplacer a par b et b par r
5 Revenir à l'étape 2
Exemple : Trouvons le PGCD de 56 et 32
Étape 1: a=56, b=32
Étape 2: 56 ÷ 32 = 1 reste 24 → r=24
Étape 3: r≠0, donc a=32, b=24
Étape 2: 32 ÷ 24 = 1 reste 8 → r=8
Étape 3: r≠0, donc a=24, b=8
Étape 2: 24 ÷ 8 = 3 reste 0 → r=0
Étape 3: r=0 → PGCD = 8
Le PGCD de 56 et 32 est 8.
Voici une implémentation en pseudocode :
fonction PGCD(a, b): tant que b ≠ 0: r ← a mod b a ← b b ←
r fin tant que retourner a fin fonction
4. Exercices Basiques
Exercice 1 : Algorithme de la moyenne
Écrire un algorithme qui calcule la moyenne de trois nombres.
Algorithme :
1. Début
2. Lire trois nombres : a, b, c
3. Calculer la somme : somme = a + b + c
4. Calculer la moyenne : moyenne = somme / 3
5. Afficher la moyenne
6. Fin
Exemple avec a=10, b=15, c=20 :
somme = 10 + 15 + 20 = 45
moyenne = 45 / 3 = 15
Exercice 2 : Algorithme du maximum
Écrire un algorithme qui trouve le plus grand de deux nombres.
Algorithme :
1. Début
2. Lire deux nombres : a, b
3. Si a > b alors afficher "Le maximum est a"
4. Sinon afficher "Le maximum est b"
5. Fin
Exemple avec a=7, b=12 :
a n'est pas supérieur à b, donc on affiche "Le maximum est 12"
Exercice 3 : Algorithme de la factorielle
Écrire un algorithme qui calcule la factorielle d'un nombre entier positif n (n!).
Rappel : n! = 1 × 2 × 3 × ... × n et 0! = 1
Algorithme :
1. Début
2. Lire un nombre entier positif n
3. Initialiser resultat à 1
4. Initialiser i à 1
5. Tant que i ≤ n, faire :
resultat = resultat × i
i=i+1
6. Afficher resultat
7. Fin
Exemple avec n=5 :
resultat = 1 × 1 = 1
resultat = 1 × 2 = 2
resultat = 2 × 3 = 6
resultat = 6 × 4 = 24
resultat = 24 × 5 = 120
Donc 5! = 120
5. Représentation d'Algorithmes
Il existe plusieurs façons de représenter un algorithme :
5.1. En français structuré
C'est la description textuelle comme nous l'avons fait précédemment.
5.2. Organigramme (Flowchart)
Représentation graphique utilisant des symboles standardisés :
Ovale : Début/Fin
Parallélogramme : Entrée/Sortie
Rectangle : Traitement
Losange : Décision (test)
Flèches : Lien entre les étapes
5.3. Pseudocode
Langage intermédiaire entre le langage naturel et le langage de programmation.
Algorithme : Conversion Celsius vers Fahrenheit Début Écrire
"Entrez la température en Celsius :" Lire celsius fahrenheit
← (celsius × 9/5) + 32 Écrire celsius, "°C =", fahrenheit,
"°F" Fin
5.4. Langage de programmation
Implémentation réelle dans un langage comme Python, JavaScript, etc.
// En JavaScript function celsiusToFahrenheit(celsius) {
return (celsius * 9/5) + 32; } // Exemple d'utilisation let
tempC = 25; let tempF = celsiusToFahrenheit(tempC);
[Link](tempC + "°C = " + tempF + "°F");
6. Complexité Algorithmique
La complexité algorithmique mesure l'efficacité d'un algorithme en termes de :
Temps d'exécution (complexité temporelle)
Espace mémoire utilisé (complexité spatiale)
Notation Grand O (Big O)
Permet de classer les algorithmes selon leur croissance en fonction de la taille des données
d'entrée (n) :
Notation Nom Exemple
O(1) Constant Accéder à un élément d'un tableau par son index
O(log n) Logarithmique Recherche dichotomique
O(n) Linéaire Parcourir tous les éléments d'un tableau
O(n²) Quadratique Tri par sélection, algorithmes avec boucles imbriquées
Exemple : Comparaison de complexité pour n = 1000
O(1) : 1 opération
O(log n) : ~10 opérations (car log₂1000 ≈ 10)
O(n) : 1000 opérations
O(n²) : 1 000 000 opérations
On comprend pourquoi on cherche toujours les algorithmes les plus efficaces !
7. Algorithmes Classiques à Connaître
7.1. Algorithmes de tri
Tri à bulles (Bubble Sort) : O(n²) - Simple mais inefficace
Tri par insertion (Insertion Sort) : O(n²) - Efficace pour petites listes
Tri rapide (Quick Sort) : O(n log n) en moyenne - Très utilisé
Tri fusion (Merge Sort) : O(n log n) - Stable et efficace
7.2. Algorithmes de recherche
Recherche linéaire : O(n) - Parcourt tous les éléments
Recherche dichotomique : O(log n) - Nécessite une liste triée
7.3. Algorithmes de parcours de graphes
Parcours en largeur (BFS)
Parcours en profondeur (DFS)
Note pour la conversion en PDF : Pour convertir cette page en PDF, vous pouvez :
1. Utiliser la fonction d'impression de votre navigateur et choisir "Enregistrer au format PDF"
2. Cliquer sur les boutons "Afficher la solution" pour révéler toutes les solutions avant la
conversion
3. Ou utiliser un service en ligne de conversion HTML vers PDF
Leçon créée par le meilleur prof de maths au monde
Rappel : Un algorithme est à la base de toute programmation. Maîtrisez les concepts de base avant de
passer à des notions plus avancées !
© 2023 - Pédagogie Algorithmique