🎯 Ce que vous saurez faire
À la fin de cette leçon, vous pourrez distinguer un problème, une instance, un algorithme et un programme ; identifier entrées et sorties ; puis justifier la correction et la terminaison d'une procédure simple.
🧠 Les notions fondamentales
Problème
Question générale portant sur une famille d'entrées. Exemple : « Un entier naturel donné est-il divisible par 10 ? »
Instance
Choix concret des données d'entrée. Exemple : n = 120 ou n = 123.
Algorithme
Suite finie d'instructions précises qui produit la réponse attendue pour les entrées de son domaine et termine.
Programme
Implémentation d'un algorithme dans un langage exécutable, avec ses types, sa syntaxe et son environnement.
🔍 Exemple fil rouge : divisibilité par 10
Entrée : un entier naturel n. Sortie : « oui » si n est divisible par 10, « non » sinon.
Algorithme DivisiblePar10(n) r ← n modulo 10 si r = 0 alors retourner VRAI sinon retourner FAUX
| Instance | Reste modulo 10 | Réponse |
|---|---|---|
| n = 120 | 0 | Oui |
| n = 123 | 3 | Non |
| n = 0 | 0 | Oui |
Remarque : 0 est divisible par 10, puisque 0 = 10 × 0.
⚡ Laboratoire interactif : exécution pas à pas
Changez l'instance et observez la transformation des données en résultat. Le simulateur utilise des entiers sûrs en JavaScript.
📐 Correction, terminaison et complexité
Correction
Pour d > 0, la division euclidienne donne n = qd + r, avec 0 ≤ r < d. Donc d divise n si et seulement si r = 0.
Terminaison
Le calcul effectue un modulo, un test et un retour, sans boucle ni récursion : il termine pour toute entrée valide.
Trois questions de vérification
- Quelles entrées l'algorithme accepte-t-il ?
- Pourquoi sa réponse est-elle correcte pour chacune ?
- Pourquoi ne peut-il pas s'exécuter indéfiniment ?
📝 Exercices de type partiel
Exercice 1 — Problème ou instance ?
Classez : « déterminer si un entier est pair » ; « tester 42 » ; « trier une liste » ; « trier [5, 2, 9] ».
Correction : problèmes : déterminer la parité, trier une liste. Instances : tester 42, trier [5, 2, 9].
Exercice 2 — Spécifier un maximum
Donnez l'entrée, la sortie et une précondition pour « retourner le maximum d'une liste ».
Correction : entrée : liste finie d'entiers ; précondition : liste non vide ; sortie : un entier appartenant à la liste et supérieur ou égal à tous ses éléments.
Exercice 3 — Un contre-exemple suffit-il ?
Un algorithme prétend tester si un nombre est divisible par 10 en vérifiant uniquement si son dernier chiffre est 0. Est-il correct pour les entiers naturels en écriture décimale ?
Correction : oui, pour cette représentation, car n = 10q + u où u est le dernier chiffre, et n est divisible par 10 exactement lorsque u = 0.
🏆 Mini-QCM de révision
Une seule bonne réponse par question. Validez pour obtenir votre score et les explications.