UA 4 : Utilisation des structures de données et des sous-algorithmes

# UA 4 : Utilisation des structures de données et des sous-algorithmes ## Objectifs et prérequis Ce chapitre vise à permettre à l’élève de Première de maîtriser l’utilisation des structures de données fondamentales (tableaux, enregistrements) et des sous-algorithmes (fonctions et procédures), y compris la récursivité, dans la conception d’algorithmes structurés et lisibles. Il s’agit de développer la capacité à décomposer un problème en sous-tâches réutilisables, à manipuler des collections de données homogènes ou hétérogènes, et à appliquer la récursivité lorsqu’elle est pertinente. Les prérequis comprennent la maîtrise des notions de base de l’algorithmique (variables, affectations, entrées/sorties, structures de contrôle séquentielles, conditionnelles et itératives) vues en Seconde, ainsi que la capacité à écrire et lire un algorithme en pseudocode conforme aux normes du système éducatif camerounais (francophone). ## Introduction Dans la résolution de problèmes informatiques, il est rare qu’un algorithme traite une seule donnée isolée. Souvent, il faut gérer des listes de notes d’élèves, des fiches d’identité de citoyens, ou encore des séquences de calculs répétitifs comme la factorielle ou la suite de Fibonacci. Les structures de données permettent d’organiser ces informations de manière cohérente, tandis que les sous-algorithmes (fonctions et procédures) évitent la redondance du code et facilitent la maintenance. La récursivité, quant à elle, offre une approche élégante pour résoudre des problèmes définis par récurrence, particulièrement adaptée à certains contextes africains comme la modélisation de la croissance démographique ou le calcul des impôts progressifs par tranches. Ce chapitre présente ces concepts de façon progressive, en s’appuyant sur des exemples concrets tirés du quotidien camerounais et africain, afin de renforcer l’ancrage culturel et pédagogique. ## I. Fonctions récursives ### Contexte La récursivité est une technique où une fonction s’appelle elle-même pour résoudre un problème en le décomposant en sous-problèmes plus simples du même type. Elle est particulièrement utile lorsque la définition d’un problème est naturellement récursive, comme dans les suites mathématiques, les parcours d’arbres ou la résolution de puzzles. En contexte camerounais, on peut penser au calcul des cotisations tontinières où chaque versement dépend du précédent, ou à la répartition hiérarchique des responsabilités dans un village traditionnel. ### Définitions > Une fonction récursive est une fonction qui s’appelle elle-même dans son propre corps, avec un cas de base permettant d’arrêter la récursion et éviter un appel infini. > Le cas de base est la condition qui interrompt la récursion et retourne une valeur connue sans appel récursif. > Le cas récursif est la partie où la fonction s’appelle elle-même avec un argument modifié, se rapprochant du cas de base. ### Faits et concepts clés La récursivité repose sur deux piliers : un cas de base bien défini et un pas de récursion qui réduit la taille du problème. Sans cas de base, la fonction s’appellerait indéfiniment, provoquant un débordement de pile (stack overflow). Chaque appel récursif crée une nouvelle instance de la fonction sur la pile d’appels, avec ses propres variables locales. La résolution se fait en deux phases : la descente (appels successifs) et la remontée (retour des résultats). En Afrique, la récursivité trouve des parallèles dans les traditions orales : un conte peut être raconté en faisant référence à une version antérieure du même conte, jusqu’à atteindre une histoire originelle (cas de base). De même, dans certaines sociétés, la lignée familiale est définie récursivement : une personne appartient à un clan si son père appartient à ce clan, avec le fondateur du clan comme cas de base. ### Exemples concrets **Exemple 1 : Factorielle d’un entier** La factorielle de n (notée n!) est le produit de tous les entiers de 1 à n. Elle se définit récursivement comme : - 0! = 1 (cas de base) - n! = n × (n-1)! pour n > 0 (cas récursif) Algorithme : ``` Fonction factorielle(n : entier) : entier Début Si n = 0 Alors Retourner 1 Sinon Retourner n * factorielle(n-1) FinSi Fin ``` **Exemple 2 : Suite de Fibonacci** Cette suite, où chaque terme est la somme des deux précédents, modélise des phénomènes de croissance observée en biologie (reproduction de lapins, croissance de certaines plantes). En contexte africain, elle peut servir à estimer l’évolution d’une population de poissons dans un lac sous hypothèses simplifiées. - F(0) = 0, F(1) = 1 (cas de base) - F(n) = F(n-1) + F(n-2) pour n ≥ 2 (cas récursif) Algorithme : ``` Fonction fibonacci(n : entier) : entier Début Si n = 0 Alors Retourner 0 Sinon Si n = 1 Alors Retourner 1 Sinon Retourner fibonacci(n-1) + fibonacci(n-2) FinSi Fin ``` > La fonction de Fibonacci naïve présentée ci-dessus effectue un nombre exponentiel d’appels. Pour n=30, elle effectue plus d’un million d’appels. Une version itérative ou avec mémoïsation serait plus efficace, mais la forme récursive reste utile pour l’enseignement de la concept. ### Vocabulaire à retenir - Récursivité - Cas de base - Cas récursif - Pile d’appels - Débordement de pile - Récurrence ### Exemple de sujet type examen avec plan **Sujet :** On définit la fonction suivante : ``` Fonction mystère(n : entier) : entier Début Si n ≤ 1 Alors Retourner 1 Sinon Retourner n * mystère(n-1) FinSi Fin ``` 1. Que retourne mystère(4) ? Justifiez par le tracé des appels. 2. Quel est le cas de base de cette fonction ? 3. Cette fonction calcule-t-elle la factorielle de n ? Expliquez. 4. Pourquoi cette fonction ne convient-elle pas pour calculer mystère(1000) en pratique ? 5. Proposez une version itérative équivalente. **Plan de correction :** 1. mystère(4) = 4 × mystère(3) = 4 × (3 × mystère(2)) = 4 × 3 × (2 × mystère(1)) = 4 × 3 × 2 × 1 = 24 2. Le cas de base est quand n ≤ 1, retourne 1. 3. Oui, car elle multiplie tous les entiers de 1 à n, avec 0! = 1 par convention (ici, n≤1 retourne 1, donc 0 et 1 donnent 1). 4. Parce que la profondeur de récursion dépasserait les limites de la pile d’appels, provoquant un débordement. 5. Version itérative : initialiser résultat à 1, boucler de 1 à n, multiplier résultat par i à chaque étape. ## II. Tableaux ### Contexte Les tableaux permettent de stocker une collection d’éléments du même type, accessibles par un indice. Ils sont essentiels lorsque l’on doit traiter des listes de données homogènes : notes d’une classe, températures journalières, prix de marchandises sur un marché. Au Cameroun, un professeur peut utiliser un tableau pour enregistrer les notes de 40 élèves en mathématiques, un agronome pour suivre le rendement de 10 parcelles de maïs, ou un commerçant pour lister les prix de 20 articles en vente. ### Définitions > Un tableau est une structure de données linéaire qui regroupe un nombre fixé d’éléments du même type, accessibles par des indices entiers commençant généralement à 0 ou 1 selon la convention adoptée. > L’indice d’un élément dans un tableau est la valeur entière qui permet de localiser sa position dans la structure. > La taille (ou longueur) d’un tableau est le nombre total d’éléments qu’il peut contenir. ### Faits et concepts clés Dans le système éducatif camerounais, les tableaux sont généralement indexés à partir de 0 (comme en pseudocode officiel), bien que certains manuels utilisent l’indexation à partir de 1 pour se rapprocher de la pensée naturelle. Il est crucial de préciser la convention utilisée. L’accès à un élément se fait en temps constant O(1), mais l’insertion ou la suppression au milieu nécessite un décalage des éléments, en O(n). Les tableaux sont statiques : leur taille est fixée à la déclaration et ne peut pas changer pendant l’exécution (dans ce cadre pédagogique). Ils permettent des parcours séquentiels (pour lire ou modifier tous les éléments) et des recherches (linéaires ou dichotomiques si triés). Un exemple camerounais : un tableau de 12 cases pour stocker les précipitations mensuelles à Yaoundé, permettant de calculer la moyenne annuelle ou d’identifier le mois le plus pluvieux. ### Exemples concrets **Exemple 1 : Saisie et affichage des notes** Un professeur veut saisir les notes de 15 élèves en physique et afficher celles supérieures à 10. Algorithme : ``` Algorithme GestionNotes Début Déclarer notes[14] : réel // indices 0 à 14 pour 15 éléments Déclarer i : entier Pour i allant de 0 à 14 Faire Ecrire "Entrez la note de l'élève ", i+1, " : " Lire notes[i] FinPour Ecrire "Notes supérieures à 10 :" Pour i allant de 0 à 14 Faire Si notes[i] > 10 Alors Ecrire notes[i] FinSi FinPour Fin ``` **Exemple 2 : Recherche du maximum dans un tableau** Trouver la température maximale enregistrée sur une semaine à Douala. Algorithme : ``` Algorithme MaxTableau Début Déclarer temp[6] : réel // 7 jours, indices 0 à 6 Déclarer i, indiceMax : entier temp[0] ← 28,5 temp[1] ← 29,0 temp[2] ← 30,2 temp[3] ← 29,8 temp[4] ← 31,0 temp[5] ← 30,5 temp[6] ← 29,9 indiceMax ← 0 Pour i allant de 1 à 6 Faire Si temp[i] > temp[indiceMax] Alors indiceMax ← i FinSi FinPour Ecrire "La température maximale est ", temp[indiceMax], "°C enregistrée le jour ", indiceMax+1 Fin ``` > Dans un tableau déclaré avec n éléments, les indices valides vont de 0 à n-1 si l’indexation commence à 0. Accéder à un indice en dehors de cet intervalle provoque une erreur d’accès hors limites (out-of-bounds), pouvant conduire à un comportement imprévisible ou à un arrêt du programme. ### Vocabulaire à retenir - Tableau - Indice - Taille - Indexation - Parcours - Recherche linéaire ### Exemple de sujet type examen avec plan **Sujet :** On veut stocker les âges de 10 enfants d’un quartier de Yaoundé et déterminer combien sont en âge d’aller à l’école primaire (6 ans et plus). 1. Déclarez un tableau adapté pour stocker ces âges. 2. Écrivez l’algorithme pour saisir les 10 âges. 3. Écrivez l’algorithme pour compter combien d’enfants ont 6 ans ou plus. 4. Que se passe-t-il si on essaie d’accéder à âge[10] dans un tableau de taille 10 indexé de 0 à 9 ? 5. Proposez une modification pour permettre de stocker aussi le sexe de chaque enfant. **Plan de correction :** 1. Déclarer âges[9] : entier // 10 éléments, indices 0 à 9 2. Boucle de i=0 à 9 : lire âges[i] 3. Initialiser compteur à 0 ; pour i=0 à 9 : si âges[i] ≥ 6 alors compteur ← compteur+1 ; afficher compteur 4. Cela provoque une erreur d’accès hors limites, car l’indice 10 est en dehors de l’intervalle valide [0,9]. 5. Utiliser deux tableaux parallèles (âges et sexes) ou un tableau d’enregistrements (voir prochaine leçon). ## III. Enregistrements ### Contexte Les enregistrements permettent de regrouper des informations de types différents appartenant à une même entité. Alors qu’un tableau ne peut contenir que des éléments d’un seul type, un enregistrement (ou structure) peut associer, par exemple, un nom (chaîne), un âge (entier) et une note (réel) pour représenter un élève. Cela reflète mieux la réalité : une fiche d’identité citoyenne au Cameroun comporte nom, prénom, date de naissance, lieu de naissance, numéro d’identité — des données hétérogènes. ### Définitions > Un enregistrement est une structure de données composée de plusieurs champs, chacun pouvant être d’un type différent, représentant les attributs d’une entité du monde réel. > Un champ est une donnée individuelle appartenant à un enregistrement, ayant un nom et un type spécifique. > L’instanciation d’un enregistrement consiste à créer une variable de ce type et à lui affecter des valeurs à chacun de ses champs. ### Faits et concepts clés Les enregistrements permettent une meilleure organisation des données que l’usage de plusieurs tableaux parallèles (qui risque de perdre la synchronisation). Ils facilitent la passage d’informations complexes à des sous-algorithmes. Dans le pseudocode camerounais, on déclare un type d’enregistrement avec la structure `Type` ou `Enregistrement`, puis on déclare des variables de ce type. L’accès à un champ se fait par la notation `variable.nomChamp`. Un exemple typique : un enregistrement `Etudiant` avec champs `nom` (chaîne), `matricule` (entier), `moyenne` (réel). On peut alors créer un tableau d’enregistrements pour gérer une classe entière. En contexte africain, les enregistrements modélisent bien les fiches de suivi agricole : une parcelle peut être décrite par sa localisation (chaîne), sa superficie (réel), le type de culture (chaîne), le rendement attendu (entier), et l’accès à l’irrigation (booléen). ### Exemples concrets **Exemple 1 : Déclaration et utilisation d’un enregistrement** Représenter un élève avec son nom, son âge et sa moyenne. Algorithme : ``` Type Etudiant nom : chaîne âge : entier moyenne : réel FinType Algorithme UtilisationEnregistrement Début Déclarer e1 : Etudiant e1.nom ← "Amina" e1.âge ← 16 e1.moyenne ← 12,5 Ecrire "L'élève ", e1.nom, " aged ", e1.âge, " ans a une moyenne de ", e1.moyenne Fin ``` **Exemple 2 : Tableau d’enregistrements pour une classe** Gérer les notes de 5 élèves en mathématiques et physique. Algorithme : ``` Type Eleve nom : chaîne maths : réel physique : réel FinType Algorithme MoyenneClasse Début Déclarer classe[4] : Eleve // 5 élèves, indices 0 à 4 Déclarer i : entier Déclarer sommeMaths, sommePhys : réel // Saisie Pour i allant de 0 à 4 Faire Ecrire "Nom de l'élève ", i+1, " : " Lire classe[i].nom Ecrire "Note en maths : " Lire classe[i].maths Ecrire "Note en physique : " Lire classe[i].physique FinPour // Calcul des moyennes sommeMaths ← 0 sommePhys ← 0 Pour i allant de 0 à 4 Faire sommeMaths ← sommeMaths + classe[i].maths sommePhys ← sommePhys + classe[i].physique FinPour Ecrire "Moyenne en maths : ", sommeMaths/5 Ecrire "Moyenne en physique : ", sommePhys/5 Fin ``` > L’avantage principal des enregistrements est qu’ils permettent de traiter une entité complexe comme une unité logique, réduisant le risque d’erreurs liées à la gestion de variables séparées et améliorant la lisibilité du code. ### Vocabulaire à retenir - Enregistrement - Champ - Type structuré - Instanciation - Accès au champ - Tableau d’enregistrements ### Exemple de sujet type examen avec plan **Sujet :** On veut gérer une bibliothèque scolaire. Chaque livre est caractérisé par son titre (chaîne), son auteur (chaîne), son année de publication (entier) et son disponibilité (booléen : vrai si disponible, faux sinon). 1. Déclarez un type d’enregistrement adapté pour représenter un livre. 2. Écrivez l’algorithme pour saisir les informations de 3 livres et les stocker dans un tableau. 3. Écrivez l’algorithme pour afficher uniquement les livres disponibles publiés après 2010. 4. Quel avantage y a-t-il à utiliser un enregistrement plutôt que trois tableaux parallèles (titre, auteur, année) ? 5. Comment modifieriez-vous l’enregistrement pour ajouter le nombre de pages ? **Plan de correction :** 1. Type Livre titre : chaîne auteur : chaîne année : entier disponible : booléen FinType 2. Tableau livres[2] : Livre ; boucle de i=0 à 2 : lire chaque champ de livres[i] 3. Pour i=0 à 2 : si livres[i].disponible ET livres[i].année > 2010 alors afficher livres[i].titre, livres[i].auteur 4. Cela évite le risque de désynchronisation (ex : échanger deux titres sans échanger les années correspondantes) et regroupe logiquement les données d’une même entité. 5. Ajouter un champ `pages : entier` dans le type Livre. ## IV. Fonctions et procédures ### Contexte Les fonctions et procédures sont des sous-algorithmes qui permettent de décomposer un problème complexe en tâches plus simples, réutilisables et lisibles. Une fonction retourne une valeur et peut être utilisée dans une expression, tandis qu’une procédure effectue une action mais ne retourne pas de valeur. Cette modularité est fondamentale en programmation : elle évite la duplication de code, facilite le débogage et permet le travail en équipe. Au Cameroun, un programme de gestion de caisse au marché pourrait utiliser une procédure pour afficher le menu, une fonction pour calculer la taxe sur une vente, et une autre pour rendre la monnaie. ### Définitions > Une fonction est un sous-algorithme qui prend zéro ou plusieurs paramètres, effectue un traitement, et retourne une valeur pouvant être utilisée dans une expression. > Une procédure est un sous-algorithme qui prend zéro ou plusieurs paramètres, effectue un traitement (comme afficher ou modifier des données), mais ne retourne pas de valeur. > Un paramètre est une variable déclarée dans l’en-tête d’un sous-algorithme pour recevoir une valeur passée lors de l’appel. > Le passage de paramètres par valeur signifie que une copie de la valeur est transmise au sous-algorithme ; les modifications du paramètre n’affectent pas l’argument original. > Le passage de paramètres par référence signifie que l’adresse de la variable est transmise ; les modifications du paramètre affectent l’argument original. (Note : dans ce cadre pédagogique camerounais, on se limite généralement au passage par valeur pour la simplicité, sauf indication contraire.) ### Faits et concepts clés La décomposition en sous-algorithmes respecte le principe de séparation des préoccupations : chaque fonction ou procédure devrait avoir une seule responsabilité bien définie. Cela améliore la maintenabilité et la lisibilité. La réutilisabilité permet d’appeler le même sous-algorithme depuis plusieurs endroits du programme sans réécrire le code. La portabilité du code est accrue : un sous-algorithme bien conçu peut être réutilisé dans d’autres projets. Un exemple camerounais : une procédure `AfficherEntete` qui imprime l’en-tête d’un bulletin scolaire (nom de l’école, logo, période), réutilisée pour chaque trimestre. Une fonction `CalculerMoyenne` qui prend trois notes et retourne leur moyenne, utilisée pour les mathématiques, les sciences, etc. > En l’absence de retour explicite, une fonction retourne une valeur indéfinie ou nulle selon le langage ; en pseudocode camerounais, il est attendu que toute fonction spécifiant un type de retour effectue effectivement un `Retourner`. ### Vocabulaire à retenir - Fonction - Procédure - Paramètre - Passage par valeur - Retour - Modularité ### Exemples concrets **Exemple 1 : Fonction qui retourne une valeur** Calculer le prix TTC d’un article sachant le prix HT et le taux de TVA. Algorithme : ``` Fonction PrixTTC(prixHT : réel, tauxTVA : réel) : réel Début Retourner prixHT * (1 + tauxTVA/100) Fin Algorithme UtilisationPrixTTC Début Déclarer ht, tva, ttc : réel Ecrire "Prix HT : " Lire ht Ecrire "Taux de TVA (%) : " Lire tva ttc ← PrixTTC(ht, tva) Ecrire "Prix TTC : ", ttc Fin ``` **Exemple 2 : Procédure qui effectue une action** Afficher le bulletin d’un élève avec son nom et sa moyenne. Algorithme : ``` Procedure AfficherBulletin(nom : chaîne, moyenne : réel) Début Ecrire "Bulletin de ", nom Ecrire "Moyenne : ", moyenne Si moyenne >= 12 Alors Ecrire "Mention : Assez bien" Sinon Si moyenne >= 10 Alors Ecrire "Mention : Passable" Sinon Ecrire "Mention : Insuffisant" FinSi Fin Algorithme UtilisationProcedure Début Déclarer nomEleve : chaîne Déclarer moy : réel Ecrire "Nom de l'élève : " Lire nomEleve Ecrire "Moyenne obtenue : " Lire moy AfficherBulletin(nomEleve, moy) Fin ``` > Une procédure ne doit pas contenir de `Retourner` avec une valeur, car elle n’est pas destinée à être utilisée dans une expression. Son appel se fait en tant qu’instruction autonome. ### Vocabulaire à retenir - Fonction - Procédure - Paramètre - Retour - Modularité - Encapsulation ### Exemple de sujet type examen avec plan **Sujet :** On veut calculer l’indice de masse corporelle (IMC) d’une personne sachant son poids (en kg) et sa taille (en mètres). L’IMC se calcule comme poids / (taille²). On veut ensuite afficher une interprétation selon les catégories suivantes : IMC < 18,5 : maigreur ; 18,5 ≤ IMC < 25 : normal ; 25 ≤ IMC < 30 : surpoids ; IMC ≥ 30 : obésité. 1. Écrivez une fonction `CalculerIMC` qui prend le poids et la taille en paramètres et retourne l’IMC. 2. Écrivez une procédure `InterpreterIMC` qui prend l’IMC en paramètre et affiche l’interprétation. 3. Écrivez l’algorithme principal qui saisit le poids et la taille, utilise les deux sous-algorithmes, et affiche le résultat. 4. Pourquoi est-il préférable de séparer le calcul et l’interprétation en deux sous-algorithmes plutôt que de tout faire dans l’algorithme principal ? 5. Que se passe-t-il si on oublie le `Retourner` dans la fonction `CalculerIMC` ? **Plan de correction :** 1. Fonction CalculerIMC(poids : réel, taille : réel) : réel Début Retourner poids / (taille * taille) Fin 2. Procedure InterpreterIMC(imc : réel) Début Si imc < 18,5 Alors Ecrire "Maigreur" Sinon Si imc < 25 Alors Ecrire "Normal" Sinon Si imc < 30 Alors Ecrire "Surpoids" Sinon Ecrire "Obésité" FinSi Fin 3. Algorithme Principal Début Déclarer p, t, imc : réel Ecrire "Poids (kg) : " Lire p Ecrire "Taille (m) : " Lire t imc ← CalculerIMC(p, t) Ecrire "Votre IMC est : ", imc Inter