Cours d’Informatique
Introduction aux algorithmes – Structures, exemples et complexité
1. Qu’est-ce qu’un algorithme ?
Un algorithme est une suite finie, ordonnée et non ambiguë d’instructions permettant de résoudre un
problème ou d’obtenir un résultat déterminé. Le mot vient du nom du mathématicien perse Al-Khwarizmi (IXe
siècle). On trouve des algorithmes bien au-delà de l’informatique : une recette de cuisine, un mode d’emploi,
une procédure administrative ou une méthode de calcul mental sont des algorithmes.
En informatique, l’algorithme précède le programme. On conçoit d’abord la méthode de résolution
(l’algorithme), puis on la traduit dans un langage de programmation (Python, Java, C, etc.) pour qu’elle
puisse être exécutée par une machine.
2. Propriétés d’un bon algorithme
• Finitude : l’algorithme doit se terminer après un nombre fini d’étapes pour toute entrée valide.
• Précision / non-ambiguïté : chaque instruction doit être clairement définie, sans interprétation possible.
• Entrées : il accepte zéro ou plusieurs données d’entrée.
• Sorties : il produit au moins un résultat.
• Efficacité : il doit utiliser un temps et une mémoire raisonnables.
• Généralité : il doit fonctionner pour une classe de problèmes, pas seulement pour un cas particulier.
3. Représentation des algorithmes
On peut décrire un algorithme de plusieurs façons :
• En langage naturel (phrases).
• En pseudo-code (langage intermédiaire, proche du code mais indépendant d’un langage particulier).
• Sous forme d’organigramme (diagramme de flux avec symboles normalisés).
• Directement dans un langage de programmation.
Le pseudo-code est particulièrement utile en phase de conception car il permet de se concentrer sur la
logique sans se soucier de la syntaxe d’un langage précis.
4. Les structures de contrôle fondamentales
Tout algorithme peut être construit à partir de trois structures de base (théorème de Böhm-Jacopini) :
4.1 La séquence
Les instructions s’exécutent les unes après les autres, dans l’ordre où elles sont écrites. C’est la structure la
plus simple.
4.2 La sélection (conditionnelle)
On évalue une condition (vraie ou fausse) et on exécute un bloc d’instructions ou un autre selon le résultat.
Formes courantes :
• si condition alors instructions
• si condition alors instructions1 sinon instructions2
• selon la valeur de variable faire … (switch/case)
4.3 L’itération (boucle)
On répète un bloc d’instructions. Principales formes :
• Tant que (while) : on teste la condition avant chaque itération. Le bloc peut ne jamais s’exécuter.
• Répéter jusqu’à (do…while) : le bloc s’exécute au moins une fois, puis on teste.
Cours éducatif – Document pédagogique Page 1
• Pour (for) : on répète un nombre connu de fois, avec un compteur.
5. Variables, types et expressions
Une variable est un emplacement mémoire nommé qui stocke une valeur. On lui associe généralement un
type (entier, réel, booléen, chaîne de caractères, etc.). Les expressions combinent des variables, des
constantes et des opérateurs pour produire une nouvelle valeur.
Les opérateurs classiques comprennent les opérateurs arithmétiques (+, −, *, /, %), relationnels (==, !=, <, >,
≤, ≥) et logiques (ET, OU, NON).
6. Exemples d’algorithmes classiques
6.1 Somme des n premiers entiers
Algorithme Somme(n)
Entrée : entier n ≥ 1
Sortie : somme S = 1 + 2 + … + n
S←0
Pour i de 1 à n faire
S←S+i
Fin Pour
Retourner S
Remarque : on peut aussi utiliser la formule fermée S = n(n+1)/2, beaucoup plus efficace.
6.2 Factorielle
Algorithme Factorielle(n)
Entrée : entier n ≥ 0
Sortie : n ! = 1 × 2 × … × n (avec 0 ! = 1)
Si n = 0 ou n = 1 alors
Retourner 1
Sinon
f←1
Pour i de 2 à n faire
f←f×i
Fin Pour
Retourner f
Fin Si
6.3 Recherche du maximum dans un tableau
Algorithme Maximum(T, n)
Entrée : tableau T de n éléments
Sortie : la plus grande valeur du tableau
max ← T[1]
Pour i de 2 à n faire
Si T[i] > max alors
max ← T[i]
Fin Si
Fin Pour
Retourner max
6.4 Test de primalité simple
Cours éducatif – Document pédagogique Page 2
Algorithme EstPremier(n)
Entrée : entier n ≥ 2
Sortie : vrai si n est premier, faux sinon
Pour i de 2 à √n faire
Si n mod i = 0 alors
Retourner faux
Fin Si
Fin Pour
Retourner vrai
7. Notion de complexité algorithmique
La complexité mesure les ressources (principalement le temps d’exécution et la mémoire) nécessaires en
fonction de la taille n des données. On s’intéresse souvent au pire cas et on utilise la notation grand O.
Exemples courants :
• O(1) : temps constant (accès à un élément de tableau).
• O(log n) : recherche dichotomique dans un tableau trié.
• O(n) : parcours simple d’un tableau.
• O(n log n) : tris efficaces (tri fusion, tri rapide en moyenne).
• O(n²) : tris naïfs (tri à bulles, tri par insertion).
• O(2■) : algorithmes exponentiels (souvent impraticables pour de grandes valeurs de n).
Choisir un algorithme de complexité inférieure peut faire la différence entre un programme qui répond en une
seconde et un programme qui met des heures ou des jours.
8. Algorithmes de tri (aperçu)
Le tri est un problème fondamental. Parmi les algorithmes les plus connus :
• Tri à bulles : compare les éléments adjacents et les échange si nécessaire. Simple mais O(n²).
• Tri par insertion : construit progressivement une portion triée. Efficace sur de petites listes ou des listes
presque triées.
• Tri fusion : divise pour régner, complexité O(n log n) garantie.
• Tri rapide (quicksort) : aussi basé sur diviser pour régner, très rapide en moyenne (O(n log n)) mais
O(n²) dans le pire cas.
9. Récursivité
Un algorithme récursif est un algorithme qui s’appelle lui-même. Il comporte toujours un cas de base
(condition d’arrêt) et un cas récursif qui se rapproche du cas de base. La factorielle et le calcul de la suite de
Fibonacci sont des exemples classiques.
La récursivité est élégante mais peut consommer beaucoup de mémoire (pile d’appels) et être moins efficace
qu’une version itérative si elle n’est pas optimisée (mémoïsation, tail recursion…).
10. Conseils pour concevoir un algorithme
1. Bien comprendre le problème et identifier clairement les entrées et les sorties attendues.
2. Traiter d’abord des exemples concrets à la main.
3. Décomposer le problème en sous-problèmes plus simples.
4. Écrire l’algorithme en pseudo-code avant de coder.
5. Tester avec des cas limites (liste vide, n = 0, n = 1, valeurs négatives, etc.).
6. Analyser la complexité et chercher d’éventuelles améliorations.
11. Exercices
Cours éducatif – Document pédagogique Page 3
1. Écrire un algorithme qui lit un entier et affiche « pair » ou « impair ».
2. Écrire un algorithme qui calcule la somme des éléments d’un tableau.
3. Écrire un algorithme qui compte le nombre d’occurrences d’une valeur donnée dans un tableau.
4. Écrire la version récursive et la version itérative du calcul de n !.
5. Pourquoi un algorithme qui ne se termine jamais n’est-il pas valide ? Donnez un exemple.
6. Quelle est la complexité du parcours d’un tableau de n éléments ? Et d’un algorithme qui compare
chaque élément avec tous les autres ?
12. Conclusion
Maîtriser les algorithmes, c’est apprendre à résoudre des problèmes de façon structurée et efficace.
C’est une compétence transversale qui dépasse largement le cadre de l’informatique. Que vous
programmiez, que vous analysiez des données ou que vous organisiez un processus complexe, la
pensée algorithmique vous sera précieuse.
Les notions présentées ici constituent les fondations. Les étapes suivantes pourront porter sur les structures
de données (listes, piles, files, arbres, graphes, tables de hachage), les algorithmes avancés (plus courts
chemins, programmation dynamique, algorithmes gloutons) et la preuve de correction des algorithmes.
Cours éducatif – Document pédagogique Page 4