Algorithmique pour débutants : Travaux pratiques et projets
TP 1 à TP 8 avec corrections détaillées
De l’initiation aux algorithmes au mini-projet
Présentation générale des travaux pratiques
Les huit travaux pratiques consolident progressivement les notions étudiées dans le cours. Chaque séance associe analyse du problème, écriture algorithmique, test manuel et correction argumentée.
TP | Thème | Compétences principales |
|---|---|---|
TP 1 | Premiers algorithmes | Entrées-sorties, calculs, conversions, affectation |
TP 2 | Conditions | Tests, alternatives, choix multiples, équations |
TP 3 | Boucles | Compteurs, accumulateurs, répétitions, suites |
TP 4 | Tableaux | Parcours, statistiques, recherche, inversion |
TP 5 | Chaînes | Parcours, analyse, validation |
TP 6 | Fonctions et procédures | Modularité, paramètres, validation |
TP 7 | Recherche et tri | Recherche séquentielle/dichotomique, tris simples |
TP 8 | Mini-projet | Analyse, conception, modularité, tests, présentation |
Convention de pseudo-code
Élément | Notation utilisée |
|---|---|
Affectation | variable ← expression |
Entrée | Lire(variable) |
Sortie | Écrire(expression) |
Condition | Si … Alors … Sinon … FinSi |
Boucle | Pour, TantQue ou Répéter…Jusqu’à |
Tableau | T[0..n−1] |
Fonction | Fonction Nom(paramètres) : Type |
Important : Les corrections représentent une solution de référence. D’autres algorithmes sont acceptables s’ils sont corrects, terminants, lisibles et correctement testés. |
TP 1 — Premiers algorithmes
Élément | Description |
|---|---|
Durée indicative | 2 à 3 heures |
Prérequis | Structure générale, variables, types et opérateurs |
Organisation | Travail individuel ou en binôme |
Livrable | Pseudo-code, jeux d’essai et réponses aux questions |
Objectifs pédagogiques
- Utiliser les instructions Lire, Écrire et l’affectation.
- Construire des expressions arithmétiques.
- Réaliser des conversions d’unités.
- Comprendre l’échange de deux variables.
Méthode de travail : Lire chaque énoncé, identifier les entrées et sorties, écrire le pseudo-code, effectuer au moins un test manuel, puis comparer avec la correction. |
Exercice 1 — Présentation d’un utilisateur
Écrire un algorithme qui demande le prénom et l’âge d’une personne, puis affiche une phrase de bienvenue.
Travail demandé
- Identifier les types adaptés.
- Afficher : « Bonjour prénom, vous avez âge ans. »
Jeux d’essai proposés
Entrées | Résultat attendu |
|---|---|
prénom = Lina, âge = 19 | Bonjour Lina, vous avez 19 ans. |
Exercice 2 — Calculs sur deux nombres
Lire deux nombres réels a et b, puis afficher leur somme, leur différence, leur produit et leur moyenne.
Travail demandé
- Prévoir des variables distinctes pour les résultats.
- Tester avec des nombres positifs, négatifs et décimaux.
Jeux d’essai proposés
Entrées | Résultat attendu |
|---|---|
a = 8, b = 4 | somme = 12 ; différence = 4 ; produit = 32 ; moyenne = 6 |
a = −3, b = 5 | somme = 2 ; différence = −8 ; produit = −15 ; moyenne = 1 |
Exercice 3 — Rectangle
Lire la longueur et la largeur d’un rectangle, puis calculer son périmètre et sa surface.
Travail demandé
- Écrire les formules utilisées.
- Vérifier que les valeurs sont exprimées dans la même unité.
Jeux d’essai proposés
Entrées | Résultat attendu |
|---|---|
L = 7, l = 3 | périmètre = 20 ; surface = 21 |
Exercice 4 — Conversion de température
Convertir une température exprimée en degrés Celsius en degrés Fahrenheit à l’aide de la formule F = 1,8 × C + 32.
Travail demandé
- Lire une valeur réelle.
- Afficher le résultat avec son unité.
Jeux d’essai proposés
Entrées | Résultat attendu |
|---|---|
C = 0 | F = 32 |
C = 25 | F = 77 |
C = −10 | F = 14 |
Exercice 5 — Conversion d’une durée
Une durée est donnée en secondes. La convertir en heures, minutes et secondes.
Travail demandé
- Utiliser la division entière et le modulo.
- Vérifier la reconstruction de la durée initiale.
Jeux d’essai proposés
Entrées | Résultat attendu |
|---|---|
durée = 3672 | 1 h 1 min 12 s |
durée = 59 | 0 h 0 min 59 s |
Exercice 6 — Échange de deux variables
Lire deux valeurs A et B, puis échanger leurs contenus en utilisant une variable temporaire.
Travail demandé
- Afficher les valeurs avant et après l’échange.
- Expliquer le rôle de la variable temporaire.
Jeux d’essai proposés
Entrées | Résultat attendu |
|---|---|
A = 5, B = 9 | Après échange : A = 9, B = 5 |
Corrections du TP 1
Correction 1 — Présentation
Les deux données sont lues puis utilisées directement dans l’affichage.
Pseudo-code corrigé
Algorithme Presentation |
Correction 2 — Calculs sur deux nombres
La moyenne est obtenue en divisant la somme par 2.
Pseudo-code corrigé
Algorithme CalculsDeuxNombres |
Correction 3 — Rectangle
Le périmètre correspond à deux longueurs et deux largeurs ; la surface est le produit des dimensions.
Pseudo-code corrigé
Algorithme Rectangle |
Correction 4 — Température
La formule est appliquée après la lecture de la température Celsius.
Pseudo-code corrigé
Algorithme CelsiusVersFahrenheit |
Correction 5 — Durée
La division entière extrait les unités complètes ; le modulo conserve le reste.
Pseudo-code corrigé
Algorithme ConvertirDuree |
À retenir : On doit avoir total = heures × 3600 + minutes × 60 + secondes. |
Correction 6 — Échange
Sans variable temporaire, la première valeur serait perdue après la première affectation.
Pseudo-code corrigé
Algorithme Echanger |
TP 2 — Conditions
Élément | Description |
|---|---|
Durée indicative | 3 heures |
Prérequis | Opérateurs relationnels et logiques, structures conditionnelles |
Organisation | Travail individuel ou en binôme |
Livrable | Pseudo-code, jeux d’essai et réponses aux questions |
Objectifs pédagogiques
- Choisir entre condition simple, alternative et conditions imbriquées.
- Ordonner correctement plusieurs tests.
- Traiter les cas particuliers.
- Résoudre des problèmes à plusieurs branches.
Méthode de travail : Lire chaque énoncé, identifier les entrées et sorties, écrire le pseudo-code, effectuer au moins un test manuel, puis comparer avec la correction. |
Exercice 1 — Maximum de deux puis de trois valeurs
Écrire un algorithme qui détermine d’abord le maximum de deux nombres, puis une seconde version pour trois nombres.
Travail demandé
- Prévoir le cas de valeurs égales.
- Éviter les comparaisons inutiles.
Jeux d’essai proposés
Entrées | Résultat attendu |
|---|---|
4, 9 | maximum = 9 |
7, 7, 2 | maximum = 7 |
Exercice 2 — Mention
Lire une note comprise entre 0 et 20 et afficher : Ajourné si note < 10, Passable de 10 à moins de 12, Assez bien de 12 à moins de 14, Bien de 14 à moins de 16, Très bien à partir de 16.
Travail demandé
- Contrôler d’abord que la note est valide.
- Tester les frontières 10, 12, 14 et 16.
Exercice 3 — Tarif selon des critères
Une salle de sport applique le tarif mensuel suivant : 100 DH pour les moins de 18 ans, 150 DH de 18 à 59 ans et 90 DH à partir de 60 ans. Une réduction supplémentaire de 10 % est accordée aux étudiants.
Travail demandé
- Lire l’âge et le statut étudiant.
- Calculer puis afficher le tarif final.
Jeux d’essai proposés
Entrées | Résultat attendu |
|---|---|
âge = 16, étudiant = non | 100 DH |
âge = 22, étudiant = oui | 135 DH |
âge = 65, étudiant = oui | 81 DH |
Exercice 4 — Équation du premier degré
Résoudre l’équation ax + b = 0 en traitant les cas a ≠ 0, a = 0 et b = 0.
Travail demandé
- Distinguer solution unique, aucune solution et infinité de solutions.
Exercice 5 — Équation du second degré
Résoudre ax² + bx + c = 0 dans l’ensemble des réels. Si a = 0, ramener le problème à une équation du premier degré.
Travail demandé
- Calculer le discriminant Δ = b² − 4ac.
- Traiter Δ < 0, Δ = 0 et Δ > 0.
Corrections du TP 2
Correction 1 — Maximum
Une variable max est initialisée avec la première valeur, puis mise à jour lorsque nécessaire.
Pseudo-code corrigé
Algorithme MaximumTrois |
Correction 2 — Mention
Les intervalles doivent être testés dans un ordre cohérent et sans chevauchement.
Pseudo-code corrigé
Algorithme Mention |
À retenir : Lorsque les tests sont effectués par ordre croissant, chaque condition profite des conditions précédemment éliminées. |
Correction 3 — Tarif
On détermine d’abord le tarif de base selon l’âge, puis on applique éventuellement la réduction.
Pseudo-code corrigé
Algorithme TarifSalle |
Correction 4 — Premier degré
Lorsque a est nul, le terme contenant x disparaît.
Pseudo-code corrigé
Algorithme EquationPremierDegre |
Correction 5 — Second degré
Le discriminant détermine le nombre de solutions réelles.
Pseudo-code corrigé
Algorithme EquationSecondDegre |
TP 3 — Boucles
Élément | Description |
|---|---|
Durée indicative | 3 à 4 heures |
Prérequis | Structures Pour, TantQue et Répéter…Jusqu’à |
Organisation | Travail individuel ou en binôme |
Livrable | Pseudo-code, jeux d’essai et réponses aux questions |
Objectifs pédagogiques
- Utiliser compteurs et accumulateurs.
- Choisir une boucle adaptée.
- Contrôler une condition d’arrêt.
- Construire des suites numériques.
Méthode de travail : Lire chaque énoncé, identifier les entrées et sorties, écrire le pseudo-code, effectuer au moins un test manuel, puis comparer avec la correction. |
Exercice 1 — Sommes et produits
Lire un entier positif N, calculer la somme 1 + 2 + … + N et le produit 1 × 2 × … × N.
Travail demandé
- Utiliser deux accumulateurs correctement initialisés.
- Comparer le produit obtenu avec la factorielle de N.
Exercice 2 — Factorielle
Calculer N! pour un entier N ≥ 0. Rappeler que 0! = 1.
Travail demandé
- Valider la saisie.
- Tester N = 0, 1 et 5.
Exercice 3 — Table de multiplication
Afficher la table de multiplication d’un entier N de N × 0 à N × 10.
Travail demandé
- Présenter chaque ligne sous une forme lisible.
Exercice 4 — Nombres premiers
Déterminer si un entier N ≥ 2 est premier.
Travail demandé
- Chercher un diviseur entre 2 et la racine carrée de N.
- Arrêter la recherche dès qu’un diviseur est trouvé.
Jeux d’essai proposés
Entrées | Résultat attendu |
|---|---|
N = 2 | premier |
N = 21 | non premier, divisible par 3 |
N = 29 | premier |
Exercice 5 — Suite de Fibonacci
Afficher les N premiers termes de la suite définie par F0 = 0, F1 = 1 et Fn = Fn−1 + Fn−2.
Travail demandé
- Traiter N = 1 et N = 2.
- Utiliser trois variables pour faire évoluer les termes.
Corrections du TP 3
Correction 1 — Somme et produit
La somme commence à 0 ; le produit commence à 1, élément neutre de la multiplication.
Pseudo-code corrigé
Algorithme SommeProduit |
i | somme | produit |
|---|---|---|
initial | 0 | 1 |
1 | 1 | 1 |
2 | 3 | 2 |
3 | 6 | 6 |
4 | 10 | 24 |
Correction 2 — Factorielle
La validation garantit que le calcul n’est lancé qu’avec un entier non négatif.
Pseudo-code corrigé
Algorithme Factorielle |
Correction 3 — Table
Le compteur représente le multiplicateur courant.
Pseudo-code corrigé
Algorithme TableMultiplication |
Correction 4 — Nombre premier
Il suffit de tester les diviseurs jusqu’à √N. Si N possède un diviseur plus grand, il possède aussi un diviseur associé plus petit.
Pseudo-code corrigé
Algorithme EstPremier |
À retenir : L’arrêt anticipé évite les tests inutiles après la découverte d’un diviseur. |
Correction 5 — Fibonacci
À chaque tour, le nouveau terme est calculé puis les deux termes précédents sont décalés.
Pseudo-code corrigé
Algorithme Fibonacci |
TP 4 — Tableaux
Élément | Description |
|---|---|
Durée indicative | 3 à 4 heures |
Prérequis | Tableaux à une dimension et boucles |
Organisation | Travail individuel ou en binôme |
Livrable | Pseudo-code, jeux d’essai et réponses aux questions |
Objectifs pédagogiques
- Saisir et afficher un tableau.
- Calculer minimum, maximum et moyenne.
- Rechercher une valeur.
- Inverser les éléments d’un tableau.
Méthode de travail : Lire chaque énoncé, identifier les entrées et sorties, écrire le pseudo-code, effectuer au moins un test manuel, puis comparer avec la correction. |
Exercice 1 — Saisie et affichage
Saisir N valeurs réelles dans un tableau T, puis les afficher avec leurs indices.
Travail demandé
- Vérifier que 1 ≤ N ≤ capacité du tableau.
Exercice 2 — Minimum et maximum
Trouver la plus petite et la plus grande valeur d’un tableau non vide, ainsi que leurs premiers indices.
Travail demandé
- Initialiser avec le premier élément et non avec une valeur arbitraire.
Exercice 3 — Moyenne
Calculer la moyenne des éléments et compter combien d’éléments sont strictement supérieurs à cette moyenne.
Travail demandé
- Effectuer deux parcours : calcul de la moyenne, puis comptage.
Exercice 4 — Recherche
Rechercher une valeur x dans le tableau. Afficher le premier indice trouvé ou −1 si elle est absente. Proposer ensuite une version comptant toutes les occurrences.
Travail demandé
- Utiliser un arrêt anticipé pour la première version.
Exercice 5 — Inversion
Inverser le tableau sur place : le premier élément échange sa place avec le dernier, le deuxième avec l’avant-dernier, etc.
Travail demandé
- Effectuer uniquement N div 2 échanges.
Corrections du TP 4
Correction 1 — Saisie et affichage
La même boucle peut être utilisée avec une instruction de lecture puis avec une instruction d’affichage.
Pseudo-code corrigé
Algorithme SaisirAfficherTableau |
Correction 2 — Minimum et maximum
L’initialisation avec T[0] rend l’algorithme correct même si toutes les valeurs sont négatives.
Pseudo-code corrigé
Algorithme MinMax |
Correction 3 — Moyenne et comptage
Le seuil « moyenne » n’est connu qu’après le calcul de la somme ; un second parcours est donc nécessaire.
Pseudo-code corrigé
Algorithme MoyenneEtSuperieurs |
Correction 4 — Recherche
La première version mémorise −1 tant qu’aucune occurrence n’a été trouvée.
Pseudo-code corrigé
Algorithme Rechercher |
Correction 5 — Inversion
Chaque échange place simultanément deux éléments à leur position finale.
Pseudo-code corrigé
Algorithme InverserTableau |
TP 5 — Chaînes de caractères
Élément | Description |
|---|---|
Durée indicative | 3 heures |
Prérequis | Chaînes, indices, boucles et conditions |
Organisation | Travail individuel ou en binôme |
Livrable | Pseudo-code, jeux d’essai et réponses aux questions |
Objectifs pédagogiques
- Parcourir une chaîne caractère par caractère.
- Compter et rechercher des motifs simples.
- Normaliser une chaîne pour effectuer des comparaisons.
- Valider un mot de passe selon plusieurs règles.
Méthode de travail : Lire chaque énoncé, identifier les entrées et sorties, écrire le pseudo-code, effectuer au moins un test manuel, puis comparer avec la correction. |
Exercice 1 — Comptage des voyelles
Lire une chaîne et compter ses voyelles, sans distinguer majuscules et minuscules.
Travail demandé
- Considérer a, e, i, o, u et y.
- Afficher également la longueur de la chaîne.
Exercice 2 — Palindrome
Déterminer si un mot est un palindrome. Une seconde version doit ignorer la casse et les espaces d’une phrase.
Travail demandé
- Comparer les caractères symétriques.
- Arrêter dès qu’une différence est trouvée.
Jeux d’essai proposés
Entrées | Résultat attendu |
|---|---|
radar | vrai |
Kayak | vrai après conversion en minuscules |
bonjour | faux |
Exercice 3 — Nombre de mots
Compter le nombre de mots d’une phrase, en considérant qu’un mot est une suite de caractères non espaces.
Travail demandé
- Gérer plusieurs espaces consécutifs et les espaces au début ou à la fin.
Exercice 4 — Mot de passe
Un mot de passe est valide s’il contient au moins 8 caractères, une majuscule, une minuscule, un chiffre et aucun espace.
Travail demandé
- Produire un message indiquant les règles non respectées.
Corrections du TP 5
Correction 1 — Voyelles
Chaque caractère est converti en minuscule avant le test.
Pseudo-code corrigé
Algorithme CompterVoyelles |
Correction 2 — Palindrome
Deux indices se déplacent depuis les extrémités vers le centre.
Pseudo-code corrigé
Fonction EstPalindrome(mot : Chaîne) : Booléen |
Correction 3 — Nombre de mots
On compte une entrée dans un mot : caractère courant non espace et caractère précédent espace, ou début de chaîne.
Pseudo-code corrigé
Fonction NombreMots(phrase : Chaîne) : Entier |
Correction 4 — Mot de passe
Quatre indicateurs mémorisent la présence des catégories requises.
Pseudo-code corrigé
Fonction MotDePasseValide(mdp : Chaîne) : Booléen |
À retenir : Pour expliquer les erreurs, tester séparément chaque règle et afficher le message correspondant. |
TP 6 — Fonctions et procédures
Élément | Description |
|---|---|
Durée indicative | 4 heures |
Prérequis | Modularité, paramètres, tableaux et validation |
Organisation | Travail individuel ou en binôme |
Livrable | Pseudo-code, jeux d’essai et réponses aux questions |
Objectifs pédagogiques
- Écrire des fonctions courtes et réutilisables.
- Distinguer fonction et procédure.
- Utiliser paramètres d’entrée et de sortie.
- Construire une petite bibliothèque algorithmique.
Méthode de travail : Lire chaque énoncé, identifier les entrées et sorties, écrire le pseudo-code, effectuer au moins un test manuel, puis comparer avec la correction. |
Exercice 1 — Bibliothèque mathématique
Créer les fonctions Carre(x), Maximum(a,b), ValeurAbsolue(x), EstPair(n) et PuissanceEntiere(x,n).
Travail demandé
- Indiquer les types des paramètres et des résultats.
- Tester chaque fonction indépendamment.
Exercice 2 — Calculs mathématiques
Créer une fonction PGCD(a,b) utilisant l’algorithme d’Euclide et une fonction PPCM(a,b) utilisant le PGCD.
Travail demandé
- Traiter les valeurs positives.
- Rappeler : PPCM(a,b) = |a×b| / PGCD(a,b).
Exercice 3 — Manipulation de tableaux
Écrire les modules SaisirTableau, AfficherTableau, SommeTableau, MoyenneTableau, IndiceMaximum et InverserTableau.
Travail demandé
- Préciser quels modules modifient le tableau.
- Réutiliser les fonctions dans un programme principal.
Exercice 4 — Validation des entrées
Créer LireEntierIntervalle(min,max) qui répète la saisie jusqu’à obtenir un entier compris dans l’intervalle.
Travail demandé
- Utiliser cette fonction pour lire une note entre 0 et 20 et un nombre d’étudiants entre 1 et 40.
Exercice 5 — Programme intégré
Construire un programme modulaire qui saisit les notes d’une classe, calcule la moyenne, affiche la meilleure note et compte les admis.
Travail demandé
- Un étudiant est admis si sa note est supérieure ou égale à 10.
- Le programme principal doit rester court et lisible.
Corrections du TP 6
Correction 1 — Bibliothèque mathématique
Chaque fonction réalise une seule opération et renvoie explicitement son résultat.
Pseudo-code corrigé
Fonction Carre(x : Réel) : Réel |
Correction 2 — PGCD et PPCM
Le PGCD est calculé par divisions successives. Le PPCM réutilise directement cette fonction.
Pseudo-code corrigé
Fonction PGCD(a, b : Entier) : Entier |
Correction 3 — Modules de tableau
Les procédures de saisie et d’inversion modifient le tableau ; les fonctions statistiques ne le modifient pas.
Pseudo-code corrigé
Procédure SaisirTableau(Sortie T : Tableau, Entrée N : Entier) |
Correction 4 — Validation
La fonction encapsule la répétition de saisie et peut être réutilisée partout.
Pseudo-code corrigé
Fonction LireEntierIntervalle(min, max : Entier) : Entier |
Correction 5 — Programme intégré
Le programme principal orchestre les fonctions sans contenir les détails de calcul.
Pseudo-code corrigé
Algorithme GestionNotesModulaire |
TP 7 — Recherche et tri
Élément | Description |
|---|---|
Durée indicative | 4 heures |
Prérequis | Tableaux, fonctions, complexité élémentaire |
Organisation | Travail individuel ou en binôme |
Livrable | Pseudo-code, jeux d’essai et réponses aux questions |
Objectifs pédagogiques
- Implémenter deux méthodes de recherche.
- Comprendre la condition de tri préalable.
- Implémenter trois tris simples.
- Comparer les résultats et le nombre d’opérations.
Méthode de travail : Lire chaque énoncé, identifier les entrées et sorties, écrire le pseudo-code, effectuer au moins un test manuel, puis comparer avec la correction. |
Exercice 1 — Recherche séquentielle
Écrire une fonction qui renvoie le premier indice de x dans T, ou −1. Ajouter une version qui renvoie le nombre d’occurrences.
Travail demandé
- Tester un élément présent au début, au milieu, à la fin et absent.
Exercice 2 — Recherche dichotomique
Dans un tableau trié croissant, rechercher x par division successive de l’intervalle.
Travail demandé
- Écrire une version itérative.
- Vérifier que les bornes gauche et droite évoluent à chaque tour.
Exercice 3 — Tri par sélection
Trier un tableau dans l’ordre croissant en sélectionnant le minimum de la partie non triée.
Travail demandé
- Afficher le tableau après chaque passe.
Exercice 4 — Tri à bulles
Trier un tableau en comparant les éléments voisins. Arrêter lorsque aucune permutation n’a eu lieu.
Travail demandé
- Compter le nombre de comparaisons et d’échanges.
Exercice 5 — Tri par insertion
Insérer chaque élément dans la partie déjà triée du tableau.
Travail demandé
- Tester avec un tableau presque trié et un tableau inversé.
Corrections du TP 7
Correction 1 — Recherche séquentielle
La recherche de la première occurrence s’arrête dès que la valeur est trouvée.
Pseudo-code corrigé
Fonction RechercheSequentielle(T : Tableau, N : Entier, x : Réel) : Entier |
Correction 2 — Recherche dichotomique
La méthode suppose le tableau trié et élimine la moitié de l’intervalle à chaque comparaison.
Pseudo-code corrigé
Fonction RechercheDichotomique(T : Tableau, N : Entier, x : Réel) : Entier |
gauche | droite | milieu | T[milieu] | décision |
|---|---|---|---|---|
0 | 7 | 3 | 16 | x > 16 |
4 | 7 | 5 | 27 | x < 27 |
4 | 4 | 4 | 21 | trouvé |
Correction 3 — Tri par sélection
À la passe i, la plus petite valeur de T[i..N−1] est placée en position i.
Pseudo-code corrigé
Procédure TriSelection(EntréeSortie T : Tableau, Entrée N : Entier) |
Correction 4 — Tri à bulles optimisé
Si une passe complète ne produit aucun échange, le tableau est déjà trié.
Pseudo-code corrigé
Procédure TriBulles(EntréeSortie T : Tableau, Entrée N : Entier) |
Correction 5 — Tri par insertion
La clé est mémorisée, les valeurs plus grandes sont décalées vers la droite, puis la clé est insérée.
Pseudo-code corrigé
Procédure TriInsertion(EntréeSortie T : Tableau, Entrée N : Entier) |
À retenir : Le tri par insertion est souvent efficace sur un tableau de petite taille ou presque trié. |
Comparaison expérimentale
Méthode | Précondition | Meilleur cas | Pire cas | Observation |
|---|---|---|---|---|
Recherche séquentielle | Aucune | O(1) | O(n) | Convient aux données non triées |
Recherche dichotomique | Tableau trié | O(1) | O(log n) | Très rapide pour de grandes tailles |
Sélection | Aucune | O(n²) | O(n²) | Peu d’échanges |
Bulles optimisé | Aucune | O(n) | O(n²) | Détecte un tableau déjà trié |
Insertion | Aucune | O(n) | O(n²) | Bon sur presque trié |
TP 8 — Mini-projet
Élément | Description |
|---|---|
Durée indicative | 6 à 12 heures |
Prérequis | Ensemble du cours |
Organisation | Travail individuel ou en binôme |
Livrable | Pseudo-code, jeux d’essai et réponses aux questions |
Objectifs pédagogiques
- Analyser un besoin et définir les données.
- Décomposer l’application en modules.
- Implémenter un menu et des traitements cohérents.
- Préparer des jeux d’essai et présenter les résultats.
Méthode de travail : Lire chaque énoncé, identifier les entrées et sorties, écrire le pseudo-code, effectuer au moins un test manuel, puis comparer avec la correction. |
Organisation générale du mini-projet
L’étudiant choisit un sujet parmi les huit propositions. Le projet peut être réalisé uniquement en pseudo-code ou traduit ensuite en Python, C ou Java selon les objectifs de la formation.
Livrables attendus
- Fiche d’analyse : besoin, utilisateurs, entrées, sorties et contraintes.
- Structure des données utilisées.
- Découpage en fonctions et procédures.
- Pseudo-code complet et commenté.
- Au moins six jeux d’essai, dont des cas limites et incorrects.
- Brève présentation des choix réalisés et des améliorations possibles.
Fonctions communes recommandées
AfficherMenu() |
Sujet A — Gestion des notes d’une classe
Gérer les étudiants, leurs notes, moyennes, décisions et classement.
- Données : numéro, nom, prénom, tableau de notes, moyenne et décision.
- Fonctions : ajouter, saisir notes, calculer moyenne, classer, rechercher et afficher statistiques.
Sujet B — Gestion d’une bibliothèque
Gérer livres, disponibilités, emprunts et recherches.
- Données : code, titre, auteur, catégorie et disponibilité.
- Interdire l’emprunt d’un livre déjà emprunté.
Sujet C — Gestion d’un stock
Gérer produits, quantités, mouvements et alertes de seuil.
- Données : référence, désignation, quantité, prix et seuil minimum.
- Alerter lorsque la quantité devient inférieure ou égale au seuil.
Sujet D — Gestion des réservations
Gérer ressources, créneaux, clients et conflits de réservation.
- Données : identifiant, client, date, heure de début, durée et ressource.
- Refuser deux réservations incompatibles sur la même ressource.
Sujet E — Gestion d’une file d’attente
Ajouter, servir et afficher les clients selon le principe FIFO.
- Données : numéro, nom, heure d’arrivée et priorité éventuelle.
- Version de base : file FIFO simple.
Sujet F — Analyse de mesures de capteurs
Saisir des mesures, calculer statistiques, détecter seuils et anomalies.
- Données : date/heure, température, humidité ou autre mesure.
- Calculer moyenne, minimum, maximum et nombre de dépassements.
Sujet G — Jeu de devinette
Faire deviner un nombre avec indications, compteur d’essais et niveaux.
- L’ordinateur choisit un nombre dans un intervalle.
- Afficher « trop petit » ou « trop grand » et compter les tentatives.
Sujet H — Morpion simplifié
Gérer un plateau 3×3, deux joueurs, validation des coups et détection de victoire.
- Plateau : matrice 3×3 contenant vide, X ou O.
- Détecter lignes, colonnes, diagonales, égalité et saisies invalides.
Correction complète de référence — Gestion des notes
1. Analyse et structures
Élément | Choix proposé |
|---|---|
Capacité | 40 étudiants maximum |
Étudiant | numéro, nom, prénom, notes[0..4], moyenne, décision |
Règle de moyenne | moyenne arithmétique des notes saisies |
Décision | Admis si moyenne ≥ 10, sinon Ajourné |
Classement | Moyenne décroissante |
Contrôles | note entre 0 et 20, numéro unique, effectif valide |
2. Type et fonctions principales
Type Etudiant = Enregistrement |
3. Modules corrigés
Fonction CalculerMoyenne(e : Etudiant) : Réel |
Fonction RechercherNumero(classe : Tableau, n, numero : Entier) : Entier |
Procédure TrierParMoyenne(EntréeSortie classe : Tableau, n : Entier) |
4. Programme principal
Algorithme GestionClasse |
5. Jeux d’essai de validation
Test | Données | Résultat attendu |
|---|---|---|
Ajout valide | numéro 101, notes 12, 14, 9, 15, 10 | moyenne 12 ; Admis |
Numéro dupliqué | ajouter à nouveau 101 | nouvelle saisie demandée |
Note invalide | note 23 puis 18 | 23 refusée ; 18 acceptée |
Classe vide | statistiques avec n = 0 | message Aucune donnée |
Classement | moyennes 11, 16, 8 | ordre 16, 11, 8 |
Recherche absente | numéro 999 | Introuvable |
Corrections de référence pour les autres sujets
Bibliothèque — Architecture corrigée
Type Livre = Enregistrement |
Règles essentielles : La correction doit empêcher les codes dupliqués, l’emprunt d’un livre indisponible et le retour d’un livre déjà disponible. |
Stock — Architecture corrigée
Type Produit = Enregistrement |
Réservations — Détection de conflit
Deux réservations de la même ressource sont incompatibles lorsque leurs intervalles temporels se chevauchent.
Fonction Conflit(debut1, fin1, debut2, fin2 : Entier) : Booléen |
File d’attente — Correction
Enfiler(file, fin, client) : fin ← fin+1 ; file[fin] ← client |
Mesures de capteurs — Correction
Saisir N mesures valides |
Jeu de devinette — Correction
secret ← NombreAleatoire(min,max) |
Morpion — Correction
Initialiser plateau 3×3 avec espaces |
La fonction Gagne vérifie les trois lignes, les trois colonnes et les deux diagonales.
Grille d’évaluation du mini-projet
Critère | Indicateurs | Points |
|---|---|---|
Analyse du besoin | Entrées, sorties, contraintes et cas particuliers correctement identifiés | 3 |
Structures de données | Choix cohérents, champs et tailles justifiés | 3 |
Modularité | Fonctions courtes, paramètres clairs, responsabilités séparées | 4 |
Correction algorithmique | Résultats corrects et traitements complets | 4 |
Validation | Contrôles de saisie et gestion des erreurs | 2 |
Jeux d’essai | Cas normal, limites, incorrects et résultats attendus | 2 |
Lisibilité et présentation | Noms explicites, indentation, commentaires utiles | 2 |
Synthèse des compétences pratiques
Compétence | TP concernés |
|---|---|
Lire, afficher et calculer | TP 1 |
Décider selon des conditions | TP 2 |
Répéter et contrôler la terminaison | TP 3 |
Traiter des collections de valeurs | TP 4 |
Analyser des textes | TP 5 |
Décomposer en modules | TP 6 |
Rechercher, trier et comparer | TP 7 |
Concevoir une application complète | TP 8 |
Auto-évaluation finale
Pour chaque affirmation, cocher le niveau correspondant.
Compétence | Acquis | En cours | À revoir |
|---|---|---|---|
J’identifie les entrées, traitements et sorties. | □ | □ | □ |
J’écris des conditions sans oubli de cas. | □ | □ | □ |
Je choisis une boucle adaptée. | □ | □ | □ |
Je parcours et modifie un tableau. | □ | □ | □ |
Je traite une chaîne caractère par caractère. | □ | □ | □ |
Je crée des fonctions réutilisables. | □ | □ | □ |
Je réalise une recherche et un tri. | □ | □ | □ |
Je construis et teste un mini-projet modulaire. | □ | □ | □ |
Conclusion : La réussite des travaux pratiques repose autant sur la méthode et les tests que sur l’écriture du pseudo-code. Une solution simple, claire et vérifiée est préférable à une solution complexe non maîtrisée. |