Algorithmes : puissance, limites et performance

Chapitre 1 — Problèmes, instances et algorithmes

De la question générale à une exécution concrète : comprendre ce qu'un algorithme résout, comment on le spécifie et pourquoi sa terminaison compte.

6 notions clésSimulateur pas à pas5 questions corrigées100 % autonome

🎯 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.

À retenir : un problème n'est pas une instance ; un algorithme doit traiter toutes les instances autorisées, pas seulement un exemple favorable.

🔍 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
InstanceReste modulo 10Réponse
n = 1200Oui
n = 1233Non
n = 00Oui

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.

Prêt à simuler.

📐 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.

Attention aux modèles de coût : sur des entiers de taille machine fixe, le nombre d'opérations est constant, soit O(1). Sur des entiers de longueur arbitraire, le coût en bits dépend de la taille des nombres et de l'implémentation de la division.

Trois questions de vérification

  1. Quelles entrées l'algorithme accepte-t-il ?
  2. Pourquoi sa réponse est-elle correcte pour chacune ?
  3. 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.