Chapitre 19 — Conception d’un algorithme complet
De l’analyse du besoin à une solution modulaire, testée et validée
Fiche pédagogique du chapitre
Objectifs d’apprentissage
À la fin de ce chapitre, l’étudiant devra être capable de :
- reformuler un besoin exprimé en langage naturel sous une forme précise et exploitable ;
- identifier les données d’entrée, les résultats, les contraintes et les cas particuliers ;
- décomposer un problème complexe en sous-problèmes cohérents ;
- définir les responsabilités, les paramètres et les résultats de chaque module ;
- concevoir une première solution simple puis l’enrichir progressivement ;
- tester séparément les différentes parties d’un algorithme ;
- vérifier la terminaison et la correction d’une solution ;
- construire des jeux d’essai normaux, limites et incorrects ;
- comparer les résultats obtenus avec les résultats attendus ;
- présenter un algorithme complet, lisible et prêt à être programmé.
Prérequis
- variables, types et expressions ;
- conditions et boucles ;
- tableaux et enregistrements ;
- fonctions, procédures et paramètres ;
- tests, tables de trace et jeux d’essai ;
- notions élémentaires de complexité.
Plan du chapitre
Section | Contenu principal |
|---|---|
19.1 | Analyser le problème : besoin, contraintes, données et résultats |
19.2 | Décomposer : sous-problèmes, fonctions et responsabilités |
19.3 | Concevoir progressivement : version minimale, enrichissement et amélioration |
19.4 | Vérifier : terminaison, résultats, cas limites et résultats attendus |
Projet | Gestion complète des résultats d’une classe |
Organisation pédagogique indicative
Activité | Durée | Contenu |
|---|---|---|
Cours | 3 h | Méthode complète de conception |
Travaux dirigés | 4 h | Analyse, décomposition et pseudo-code |
Travaux pratiques | 4 h | Implémentation progressive et tests |
Mini-projet | 3 h | Solution documentée et validée |
Idée centrale : La qualité d’un algorithme dépend autant de la compréhension du problème que de l’écriture du pseudo-code. |
Introduction
Les chapitres précédents ont présenté les outils fondamentaux de l’algorithmique. Concevoir un algorithme complet consiste maintenant à les combiner dans une démarche organisée qui part d’un besoin réel et aboutit à une solution vérifiable.
La difficulté principale ne réside pas toujours dans les instructions. Elle se trouve souvent dans la compréhension du problème, le choix des données utiles, l’identification des cas particuliers et la répartition des traitements entre plusieurs modules.
La conception est un cycle : analyser, décomposer, construire, tester et améliorer. Une erreur découverte pendant les tests peut conduire à préciser une contrainte ou à revoir la décomposition initiale.
Étape | Question | Production |
|---|---|---|
Analyser | Que faut-il réellement résoudre ? | Fiche d’analyse |
Décomposer | Quelles parties peut-on isoler ? | Modules et responsabilités |
Concevoir | Comment construire la solution ? | Pseudo-code progressif |
Vérifier | La solution termine-t-elle et est-elle correcte ? | Jeux d’essai et propriétés |
Améliorer | Peut-on gagner en clarté ou en efficacité ? | Version révisée |
Conseil : Ne pas commencer par une longue suite d’instructions. Une courte phase d’analyse évite souvent une longue phase de correction. |
19.1 Analyse du problème
19.1.1 Reformuler le besoin
Un énoncé peut être ambigu, incomplet ou mélanger plusieurs objectifs. Reformuler le besoin consiste à exprimer clairement ce que l’algorithme doit faire, à partir de quelles informations et dans quelles limites.
Énoncé initial | Reformulation exploitable |
|---|---|
« Faire un programme de notes » | Saisir les notes d’une classe, calculer les moyennes et déterminer la décision de chaque étudiant. |
« Gérer une file » | Ajouter des personnes et les servir dans leur ordre d’arrivée. |
« Calculer une facture » | Calculer le montant net à partir des articles, remises et taxes. |
Questions de clarification
- Quel est l’objectif exact ?
- Qui fournit les données et sous quelle forme ?
- Quels résultats doivent être produits ?
- Quelles règles de gestion s’appliquent ?
- Quelles situations exceptionnelles peuvent se présenter ?
- Quelles hypothèses faut-il expliciter ?
Critère : Une bonne reformulation doit être comprise par une personne qui ne connaît pas encore la solution technique. |
19.1.2 Identifier les contraintes
Une contrainte est une règle qui limite les valeurs, les opérations ou les conditions d’utilisation. Elle peut être fonctionnelle, technique, temporelle ou liée à la qualité des données.
Catégorie | Exemple | Conséquence |
|---|---|---|
Valeurs | Une note est comprise entre 0 et 20 | Valider chaque saisie |
Quantité | Au maximum 200 étudiants | Dimensionner la structure |
Unicité | Numéro d’inscription unique | Rechercher avant tout ajout |
Ordre | Demandes traitées par arrivée | Utiliser une file |
Performance | Recherche rapide sur un grand volume | Choisir une méthode adaptée |
Confidentialité | Certaines données ne sont pas affichées | Limiter les sorties |
Une hypothèse est une condition supposée vraie pour simplifier le problème. Elle doit être explicitée et, lorsqu’elle est importante, transformée en contrôle dans l’algorithme.
19.1.3 Déterminer les données
Pour chaque donnée, il faut définir son nom, son type, son domaine de validité, son origine et son caractère obligatoire ou facultatif.
Donnée | Type | Contrainte | Rôle |
|---|---|---|---|
nombreEtudiants | Entier | 1 à 200 | Nombre d’éléments à traiter |
nom | Chaîne | Non vide | Identifie l’étudiant |
numero | Chaîne | Unique | Identifiant d’inscription |
notes | Tableau de réels | Chaque note dans [0,20] | Calcul de la moyenne |
seuilAdmission | Réel | Dans [0,20] | Détermine la décision |
Bonne pratique : Ne pas demander une donnée qui peut être calculée de manière fiable. La moyenne doit être calculée à partir des notes, et non saisie séparément. |
19.1.4 Déterminer les résultats
Les résultats peuvent être des valeurs, des messages, des listes, des statistiques ou des modifications d’une structure. Ils doivent être observables et vérifiables.
Résultat | Forme | Condition de validité |
|---|---|---|
Moyenne individuelle | Réel | Toutes les notes sont valides |
Décision | Admis ou Ajourné | Conforme au seuil |
Moyenne de classe | Réel | Classe non vide |
Meilleur étudiant | Nom, numéro et moyenne | Maximum correct |
Liste finale | Tableau formaté | Une ligne par étudiant |
19.1.5 Fiche d’analyse
La fiche d’analyse rassemble les éléments essentiels avant la rédaction du pseudo-code. Elle constitue un contrat simplifié entre le besoin et la solution.
Rubrique | Gestion des résultats d’une classe |
|---|---|
Objectif | Enregistrer les étudiants, calculer les moyennes et produire les décisions. |
Entrées | Effectif, nom, numéro et notes. |
Sorties | Moyennes, décisions, moyenne de classe et meilleur étudiant. |
Contraintes | Notes valides, numéro unique, classe non vide, maximum 200. |
Cas particuliers | Note invalide, numéro déjà utilisé, égalité des meilleures moyennes. |
Structures | Enregistrement Étudiant et tableau d’étudiants. |
19.1.6 Exemple guidé : calcul d’une facture
Élément | Analyse |
|---|---|
Données | Quantité, prix unitaire, seuil et taux de remise, taux de taxe |
Contraintes | Quantité positive, prix non négatif, taux dans [0,100] |
Traitements | Total brut, remise, taxe et total net |
Résultats | Montants intermédiaires et montant final |
Cas limites | Total égal au seuil, taux nul, quantité minimale |
Première traduction de l’analyse
Algorithme CalculFacture |
19.2 Décomposition
19.2.1 Diviser le problème en sous-problèmes
La décomposition remplace un problème global par plusieurs problèmes plus petits, plus faciles à comprendre, à développer et à tester. Cette approche est souvent appelée conception descendante.
Problème global | Sous-problèmes possibles |
|---|---|
Gestion des résultats | Saisir, valider, calculer la moyenne, déterminer la décision, trier, afficher et produire des statistiques. |
Gestion d’un stock | Ajouter, rechercher, modifier, supprimer, calculer la valeur et détecter les ruptures. |
Réservation de salles | Vérifier la disponibilité, réserver, annuler, afficher et détecter les conflits. |
Critères d’une bonne décomposition
- chaque sous-problème possède un objectif précis ;
- les dépendances restent limitées ;
- une même opération n’est pas dupliquée ;
- les données échangées sont clairement définies ;
- chaque partie peut être testée séparément ;
- le niveau de détail reste cohérent.
19.2.2 Identifier les fonctions nécessaires
Une fonction est pertinente lorsqu’un traitement produit une valeur ou représente une notion réutilisable. Une procédure convient lorsqu’un traitement modifie des données ou réalise une action sans résultat unique.
Module | Nature | Paramètres | Résultat ou effet |
|---|---|---|---|
LireNoteValide | Fonction | message | Retourne une note dans [0,20] |
NumeroExiste | Fonction | tableau, taille, numéro | Retourne Vrai ou Faux |
CalculerMoyenne | Fonction | notes, nombre | Retourne la moyenne |
DeterminerDecision | Fonction | moyenne, seuil | Retourne la décision |
AfficherEtudiant | Procédure | étudiant | Affiche une ligne |
TrierParMoyenne | Procédure | tableau, taille | Réorganise le tableau |
19.2.3 Définir les responsabilités des modules
Un module doit posséder une responsabilité principale. Une fonction qui lit des données, calcule, trie et affiche devient difficile à comprendre et à tester.
Module trop chargé | Décomposition préférable |
|---|---|
GererEtudiant : saisie + calcul + affichage | SaisirEtudiant, CalculerMoyenne, DeterminerDecision, AfficherEtudiant |
TraiterStock : recherche + modification + statistiques | RechercherProduit, ModifierQuantite, CalculerValeurStock |
Contrat d’un module
Le contrat précise ce que le module attend et ce qu’il garantit : préconditions, paramètres, résultat, postcondition et éventuels effets de bord.
Élément | Exemple pour CalculerMoyenne |
|---|---|
Précondition | n > 0 et chaque note est valide |
Paramètres | notes : tableau de Réel ; n : Entier |
Résultat | Un réel dans [0,20] |
Postcondition | Résultat = somme des n notes / n |
Effet de bord | Aucun : le tableau n’est pas modifié |
Module à responsabilité unique
Fonction CalculerMoyenne(notes : Tableau de Réel, n : Entier) : Réel |
19.2.4 Architecture fonctionnelle
L’architecture fonctionnelle montre les relations entre le programme principal et les modules sans détailler toutes les instructions.
Niveau | Modules |
|---|---|
Programme principal | GestionResultatsClasse |
Saisie et validation | LireEntierValide, LireNoteValide, SaisirEtudiant, NumeroExiste |
Calculs | CalculerMoyenne, DeterminerDecision, CalculerMoyenneClasse, TrouverMeilleur |
Traitements collectifs | TrierParMoyenne, CompterAdmis |
Présentation | AfficherEtudiant, AfficherListe, AfficherStatistiques |
Vue hiérarchique simplifiée
Programme GestionResultatsClasse |
19.2.5 Circulation des données
La décomposition doit préciser quelles données sont reçues, créées ou modifiées. Un flux clair limite l’usage des variables globales.
Module | Données reçues | Données produites ou modifiées |
|---|---|---|
SaisirEtudiant | Classe existante et taille | Un étudiant complet |
CalculerMoyenne | Notes et nombre de notes | Une moyenne |
TrierParMoyenne | Tableau d’étudiants | Même tableau réordonné |
TrouverMeilleur | Tableau d’étudiants | Indice du meilleur |
AfficherRapport | Tableau et statistiques | Affichage uniquement |
Bonne pratique : Les paramètres rendent les dépendances visibles et facilitent les tests indépendants. |
19.3 Conception progressive
19.3.1 Commencer par une solution simple
La première version doit résoudre le cœur du problème avec le minimum de fonctionnalités. Elle valide la compréhension du besoin avant l’ajout des traitements secondaires.
Version | Fonctionnalités | Objectif |
|---|---|---|
V1 | Un étudiant et sa moyenne | Valider la formule |
V2 | Plusieurs étudiants | Valider tableaux et boucles |
V3 | Décisions | Valider les règles |
V4 | Statistiques de classe | Valider les calculs collectifs |
V5 | Tri et rapport | Valider la présentation finale |
19.3.2 Première version : un étudiant
Version minimale
Algorithme MoyenneUnEtudiant |
Avec les notes 10, 12 et 14, la moyenne attendue est 12. Ce test simple valide la formule avant d’introduire d’autres fonctionnalités.
19.3.3 Ajouter progressivement les traitements
Chaque fonctionnalité est ajoutée sur une base déjà fonctionnelle. Après chaque modification, les tests précédents sont réexécutés afin de détecter les régressions.
Ajout | Modification | Nouveaux tests |
|---|---|---|
Plusieurs étudiants | Tableau d’enregistrements | 1 étudiant, capacité maximale |
Validation | Contrôle des notes et numéros | Valeurs négatives, 20, doublon |
Décision | Fonction fondée sur le seuil | Sous, égal et au-dessus du seuil |
Statistiques | Somme, comptage et maximum | Classe minimale, égalités |
Tri | Déplacement des enregistrements complets | Déjà trié, ordre inverse, doublons |
19.3.4 Tester chaque partie
Les tests unitaires vérifient les modules isolés. Les tests d’intégration vérifient ensuite leur coopération.
Module | Entrée | Résultat attendu |
|---|---|---|
CalculerMoyenne | [10,12,14], n=3 | 12 |
DeterminerDecision | moyenne=10, seuil=10 | Admis |
NumeroExiste | [E01,E02], recherche E02 | Vrai |
TrouverMeilleur | [11,16,13] | indice 1 |
CompterAdmis | [Admis,Ajourné,Admis] | 2 |
Lorsqu’un module n’est pas encore développé, un bouchon de test peut retourner temporairement une valeur simple afin de tester les modules qui en dépendent.
19.3.5 Améliorer la solution
Aspect | Question | Amélioration |
|---|---|---|
Lisibilité | Les noms expriment-ils le rôle ? | Renommer et raccourcir les modules |
Duplication | Un calcul est-il répété ? | Créer une fonction commune |
Robustesse | Les entrées invalides sont-elles gérées ? | Ajouter validations et messages |
Efficacité | Y a-t-il des parcours inutiles ? | Regrouper certains calculs |
Évolutivité | Une règle modifie-t-elle tout le programme ? | Isoler les règles |
Attention : Optimiser après avoir obtenu une solution correcte. Une optimisation prématurée complique souvent inutilement le code. |
19.3.6 Raffinement progressif
Niveau 1 : description globale
Algorithme GestionResultatsClasse |
Niveau 2 : modules identifiés
Algorithme GestionResultatsClasse |
Le niveau suivant détaille chaque module. Le raffinement conserve une vue d’ensemble tout en ajoutant progressivement la précision nécessaire.
19.4 Vérification
19.4.1 Vérifier la terminaison
Un algorithme termine lorsque toute exécution valide atteint la fin après un nombre fini d’étapes. Les boucles et les appels récursifs nécessitent une attention particulière.
Structure | Question de terminaison |
|---|---|
Boucle Pour | Les bornes sont-elles finies et le pas correct ? |
Boucle TantQue | Une variable évolue-t-elle vers la sortie ? |
Validation de saisie | Une valeur valide permet-elle de sortir ? |
Récursivité | Chaque appel se rapproche-t-il du cas de base ? |
Parcours | L’indice ou le pointeur progresse-t-il ? |
Boucle terminante
i ← 0 |
Boucle probablement infinie
i ← 0 |
Dans la première boucle, n - i est un variant : cette quantité entière non négative diminue jusqu’à 0.
19.4.2 Vérifier les résultats
La vérification consiste à contrôler que les sorties satisfont les règles définies pendant l’analyse. Elle utilise les calculs manuels, les tables de trace, les propriétés et les assertions.
Propriété | Exemple |
|---|---|
Bornes | Une moyenne de notes valides reste dans [0,20]. |
Conservation | Un tri ne change ni le nombre ni le contenu des étudiants. |
Cohérence | Le nombre d’admis est compris entre 0 et n. |
Relation | Admis + ajournés = effectif total. |
Maximum | Aucune moyenne ne dépasse celle du meilleur déclaré. |
19.4.3 Préconditions, postconditions et invariants
Une précondition doit être vraie avant l’exécution. Une postcondition décrit ce qui est garanti après. Un invariant de boucle reste vrai avant et après chaque itération.
Spécification d’un module
Fonction SommeTableau(T : Tableau d’Entier, n : Entier) : Entier |
19.4.4 Étudier les cas limites
Élément | Cas limites |
|---|---|
Effectif | 1 et 200 étudiants |
Note | 0, 20, juste sous 0, juste au-dessus de 20 |
Seuil | 0, 10 et 20 |
Décision | Moyenne exactement égale au seuil |
Maximum | Toutes les valeurs égales ; maximum en première ou dernière position |
Tri | Déjà trié ; ordre inverse ; valeurs identiques |
19.4.5 Comparer aux résultats attendus
Le résultat attendu doit être défini avant l’exécution du test. Il peut être calculé manuellement ou déduit d’une propriété connue.
Jeu d’essai | Résultat attendu | But |
|---|---|---|
[10,12,14] | Moyenne = 12 | Cas normal |
[0,0,0] | Moyenne = 0 | Borne minimale |
[20,20,20] | Moyenne = 20 | Borne maximale |
Moyenne=10, seuil=10 | Admis | Frontière |
Numéro déjà présent | Nouvelle saisie | Unicité |
19.4.6 Table de trace
Pour les moyennes [12, 15, 11, 16], on calcule la somme et l’indice du meilleur étudiant.
i | Moyenne | Somme avant | Somme après | Maximum | Indice |
|---|---|---|---|---|---|
0 | 12 | 0 | 12 | 12 | 0 |
1 | 15 | 12 | 27 | 15 | 1 |
2 | 11 | 27 | 38 | 15 | 1 |
3 | 16 | 38 | 54 | 16 | 3 |
La moyenne de classe vaut 54 / 4 = 13,5 et l’indice du meilleur est 3.
19.4.7 Correction partielle et totale
Un algorithme est partiellement correct si son résultat est correct lorsqu’il termine. Il est totalement correct si sa terminaison est également garantie.
Démarche pratique : Une vérification pédagogique peut justifier la terminaison, le respect des contrats et la couverture des cas essentiels par les tests. |
Projet d’application — Gestion des résultats d’une classe
1. Cahier des charges simplifié
Concevoir un algorithme permettant d’enregistrer les étudiants d’une classe, de saisir trois notes par étudiant, de calculer les moyennes, de déterminer les décisions, de produire des statistiques et d’afficher un classement décroissant.
Règle | Description |
|---|---|
Effectif | Entre 1 et 200 étudiants |
Identité | Nom non vide et numéro unique |
Notes | Trois notes dans [0,20] |
Moyenne | Moyenne arithmétique |
Décision | Admis si moyenne ≥ 10 |
Classement | Ordre décroissant des moyennes |
Statistiques | Moyenne de classe, admis et meilleur étudiant |
2. Modèle de données
Type structuré
Type Etudiant = Enregistrement |
3. Modules retenus
Module | Rôle |
|---|---|
LireEntierValide(min,max) | Lire un entier dans un intervalle |
LireNoteValide() | Lire une note dans [0,20] |
NumeroExiste(classe,taille,numero) | Vérifier l’unicité |
SaisirEtudiant(classe,taille) | Construire un étudiant valide |
CalculerMoyenne(notes,n) | Calculer la moyenne |
DeterminerDecision(moyenne) | Retourner Admis ou Ajourné |
CalculerStatistiques(classe,n) | Moyenne, admis et meilleur |
TrierParMoyenne(classe,n) | Classer par ordre décroissant |
AfficherRapport(...) | Présenter les résultats |
4. Fonctions principales
Fonction LireNoteValide() : Réel |
Fonction NumeroExiste(classe : Tableau d’Etudiant, |
Fonction SaisirEtudiant(classe : Tableau d’Etudiant, |
5. Statistiques et tri
Procédure CalculerStatistiques(classe, n, |
Procédure TrierParMoyenneDecroissante(classe, n) |
6. Programme principal
Algorithme GestionResultatsClasse |
7. Jeux d’essai
Cas | Données | Résultats attendus |
|---|---|---|
Normal | Moyennes 12, 15 et 9 | 2 admis, moyenne 12, meilleur 15 |
Minimal | 1 étudiant, notes 10,10,10 | Moyenne 10 et admis |
Limites | Notes 0 et 20 | Valeurs acceptées |
Doublon | Même numéro deux fois | Deuxième refusé |
Erreur | Note -1, puis 21, puis 14 | Saisie répétée jusqu’à 14 |
Égalité | Deux meilleures moyennes égales | Appliquer la règle choisie |
8. Améliorations possibles
- utiliser des coefficients ;
- ajouter des mentions ;
- modifier ou supprimer un étudiant ;
- rechercher par numéro ;
- gérer les égalités de classement ;
- enregistrer les données dans un fichier ;
- produire des statistiques par matière ;
- traduire la solution dans un langage.
Erreurs fréquentes à éviter
Erreur | Conséquence | Correction |
|---|---|---|
Coder sans analyser | Oublis et réécriture | Préparer une fiche d’analyse |
Mélanger les responsabilités | Modules difficiles à tester | Séparer saisie, calcul et affichage |
Multiplier les variables globales | Dépendances cachées | Utiliser des paramètres |
Tester seulement le cas normal | Échec aux frontières | Ajouter cas limites et incorrects |
Oublier le résultat attendu | Test non concluant | Définir l’oracle avant le test |
Optimiser trop tôt | Complexité inutile | Corriger et mesurer avant |
Modifier plusieurs parties ensemble | Erreur difficile à localiser | Procéder par petites étapes |
Travaux dirigés
Exercice 1 — Analyse d’un distributeur de billets
Un distributeur remet une somme entière positive avec des billets de 200, 100, 50 et 20. Reformuler le besoin et identifier données, résultats, contraintes et cas impossibles.
Exercice 2 — Décomposition d’une bibliothèque
Proposer les modules pour ajouter, rechercher, emprunter, retourner et afficher les livres disponibles. Préciser la responsabilité de chacun.
Exercice 3 — Contrat d’une fonction
Écrire le contrat d’une fonction qui retourne le maximum d’un tableau non vide de réels.
Exercice 4 — Conception progressive
Décrire quatre versions successives d’une gestion de stock, depuis un produit jusqu’à l’affichage des ruptures.
Exercice 5 — Terminaison
Étudier la boucle et proposer une correction :
i ← n |
Exercice 6 — Cas limites
Proposer des jeux d’essai pour un tarif selon l’âge : gratuit avant 4 ans, réduit de 4 à 17, plein tarif de 18 à 64, senior à partir de 65.
Exercice 7 — Résultats attendus
Pour [7,2,9,9,1], déterminer Somme, Minimum, Maximum, NombreOccurrences(9) et IndicePremierMaximum.
Exercice 8 — Mauvaise décomposition
Une procédure LitCalculeTrieEtAfficheClasse réalise tout. Expliquer les problèmes et proposer une meilleure décomposition.
Exercice 9 — Mini-problème complet
Concevoir une gestion de file d’attente avec ajout, service, affichage et estimation du temps d’attente.
Exercice 10 — Revue de conception
Construire une grille de dix questions pour évaluer un algorithme complet avant sa programmation.
Corrigés indicatifs des travaux dirigés
Correction 1 — Distributeur
Rubrique | Proposition |
|---|---|
Besoin | Décomposer une somme en billets disponibles en minimisant leur nombre. |
Entrée | Somme entière positive. |
Résultats | Nombre de billets ou message d’impossibilité. |
Contraintes | Billets de 200, 100, 50 et 20. |
Cas impossible | Par exemple 30. |
Une stratégie gloutonne doit vérifier le reste final. Elle n’est pas toujours suffisante avec n’importe quel ensemble de valeurs.
Correction 2 — Bibliothèque
Module | Responsabilité |
|---|---|
AjouterLivre | Valider l’identifiant puis insérer |
RechercherLivre | Retourner l’indice correspondant |
EmprunterLivre | Vérifier la disponibilité et changer l’état |
RetournerLivre | Rendre le livre disponible |
AfficherDisponibles | Afficher les livres disponibles |
Correction 3 — MaximumTableau
Élément | Contenu |
|---|---|
Précondition | n > 0 et n ≤ Taille(T) |
Paramètres | T : tableau de Réel ; n : Entier |
Résultat | Un réel |
Postcondition | Le résultat appartient à T et aucune valeur ne lui est supérieure. |
Effet de bord | Aucun |
Correction 4 — Gestion de stock
Version | Contenu |
|---|---|
V1 | Un produit et valeur = prix × quantité |
V2 | Plusieurs produits et valeur totale |
V3 | Recherche et modification |
V4 | Produits sous le seuil de rupture |
Correction 5 — Terminaison
La boucle ne termine pas pour n > 0 car i augmente. Remplacer i ← i + 1 par i ← i - 1. Le variant i diminue alors jusqu’à 0.
Correction 6 — Tarif selon l’âge
Âge | Résultat attendu |
|---|---|
-1 | Invalide |
0 | Gratuit |
3 | Gratuit |
4 | Réduit |
17 | Réduit |
18 | Plein tarif |
64 | Plein tarif |
65 | Senior |
Correction 7 — Tableau [7,2,9,9,1]
Fonction | Résultat |
|---|---|
Somme | 28 |
Minimum | 1 |
Maximum | 9 |
NombreOccurrences(9) | 2 |
IndicePremierMaximum | 2 avec indices à partir de 0 |
Correction 8 — Décomposition
Séparer SaisirClasse, CalculerMoyennes, DeterminerDecisions, TrierClasse et AfficherClasse. Chaque module devient plus simple et testable.
Correction 9 — File d’attente
Modules : EnfilerClient, DefilerClient, FileVide, AfficherFile et CalculerAttenteEstimee. La structure doit préserver l’ordre FIFO.
Algorithme GestionFile |
Correction 10 — Grille de revue
- Le besoin est-il reformulé ?
- Les entrées, sorties et contraintes sont-elles complètes ?
- Les cas particuliers sont-ils identifiés ?
- Chaque module a-t-il une responsabilité claire ?
- Les paramètres et résultats sont-ils définis ?
- Les boucles terminent-elles ?
- Les variables sont-elles initialisées ?
- Les tests couvrent-ils les frontières ?
- Les résultats attendus sont-ils connus ?
- Le pseudo-code est-il lisible et prêt à être programmé ?
Synthèse du chapitre
Étape | Actions essentielles |
|---|---|
Analyse | Reformuler, identifier données, résultats, contraintes et cas particuliers |
Décomposition | Créer des sous-problèmes et définir leurs contrats |
Conception progressive | Construire, ajouter, tester et améliorer |
Vérification | Justifier la terminaison et tester les frontières |
Documentation | Conserver fiche d’analyse, contrats et jeux d’essai |
Conclusion : Un algorithme complet est une solution documentée, modulaire, terminante et validée sur des situations représentatives. |
Glossaire
Terme | Définition |
|---|---|
Besoin | Résultat ou service attendu. |
Contrainte | Règle limitant les données ou le comportement. |
Décomposition | Division en sous-problèmes. |
Module | Partie autonome à responsabilité précise. |
Contrat | Préconditions, résultat, postconditions et effets. |
Raffinement | Passage progressif du général au détail. |
Précondition | Propriété requise avant exécution. |
Postcondition | Propriété garantie après exécution. |
Invariant | Propriété conservée pendant une boucle. |
Variant | Quantité évoluant vers la terminaison. |
Oracle de test | Moyen de connaître le résultat attendu. |
Régression | Erreur introduite dans une fonction auparavant correcte. |
Auto-évaluation
Pour chaque affirmation, indiquer : Acquis, En cours d’acquisition ou À revoir.
Compétence | Auto-évaluation |
|---|---|
Je sais reformuler un besoin ambigu. | □ Acquis □ En cours □ À revoir |
Je distingue données, résultats et contraintes. | □ Acquis □ En cours □ À revoir |
Je décompose un problème en modules. | □ Acquis □ En cours □ À revoir |
Je définis les contrats des fonctions. | □ Acquis □ En cours □ À revoir |
Je construis des versions progressives. | □ Acquis □ En cours □ À revoir |
Je teste séparément les modules. | □ Acquis □ En cours □ À revoir |
Je justifie la terminaison. | □ Acquis □ En cours □ À revoir |
Je prépare des cas limites. | □ Acquis □ En cours □ À revoir |
Je définis les résultats attendus. | □ Acquis □ En cours □ À revoir |
Je présente un algorithme complet. | □ Acquis □ En cours □ À revoir |