Developing Software — Data Types and Structures

# Developing Software — Data Types and Structures ## Objectifs et prérequis Ce chapitre vise à permettre aux élèves de Lower Sixth (anglophone) de comprendre les concepts fondamentaux des types de données et des structures de données en programmation, de les appliquer à des problèmes concrets, et de maîtriser les opérations de base sur ces structures. Les prérequis incluent une connaissance de base de la programmation (variables, boucles, conditions) acquise en Form 5 ou équivalent, ainsi qu’une familiarité avec un langage de programmation de haut niveau tel que Python ou Java, couramment utilisé dans le système éducatif camerounais anglophone. ## Introduction Dans le domaine des Technologies de l’Information et de la Communication (TIC), le développement logiciel repose sur la capacité à représenter, manipuler et organiser l’information de manière efficace. Les types de données définissent la nature des valeurs qu’un programme peut traiter (entiers, chaînes de caractères, booléens, etc.), tandis que les structures de données permettent d’organiser ces valeurs de façon structurée pour faciliter l’accès, la recherche, la modification et la suppression. Ce chapitre explore ces deux piliers du développement logiciel, en insistant sur leur application pratique dans des contextes africains et camerounais, tels que la gestion des données étudiantes, le suivi des récoltes agricoles, ou la gestion des stocks dans les petites entreprises locales. L’accent est mis sur la compréhension théorique renforcée par des exemples concrets et des exercices types examen. ## I. Data Types and Data Structures ### Contexte La notion de type de donnée est fondamentale en programmation : elle indique au compilateur ou à l’interpréteur comment interpréter une séquence de bits en mémoire. Sans types de données définis, un programme ne pourrait pas distinguer entre un nombre représentant une note d’élève et une chaîne de caractères représentant un nom. Les structures de données, quant à elles, émergent du besoin de gérer des collections d’éléments liés — comme une liste de notes, un tableau de températures mensuelles, ou un répertoire de contacts — de manière efficace. Dans le système éducatif camerounais anglophone, ces concepts sont introduits progressivement, en s’appuyant sur des exemples tirés de la vie quotidienne africaine pour renforcer la pertinence pédagogique. ### Définitions > **Data Type** : Une classification qui spécifie le type de valeur qu’une variable peut contenir, les opérations autorisées sur cette valeur, et la manière dont elle est stockée en mémoire. > **Primitive Data Type** : Un type de donnée de base fourni par le langage de programmation, non décomposable en autres types (ex. : entier, flottant, booléen, caractère). > **Data Structure** : Un format organisé pour stocker, gérer et accéder efficacement à des données, permettant des opérations définies (insertion, suppression, recherche, parcours). > **Abstract Data Type (ADT)** : Un modèle mathématique pour un type de donnée qui définit son comportement (opérations) sans spécifier son implémentation concrète. > **Static Data Structure** : Une structure de données dont la taille est fixée au moment de la compilation et ne peut pas changer pendant l’exécution (ex. : tableau). > **Dynamic Data Structure** : Une structure de données dont la taille peut varier pendant l’exécution en fonction des besoins (ex. : liste chaînée, pile, file). ### Faits, dates et noms exacts - Les types de données primitifs sont hérités des premiers langages de programmation comme Fortran (années 1950) et C (début des années 1970), qui ont influencé la conception de pratiquement tous les langages modernes. - Le concept de structure de données abstraite (ADT) a été formalisé dans les années 1970 par des informaticiens tels que Barbara Liskov, pionnière en programmation orientée objet et en théorie des types. - En programmation structurée, les tableaux (arrays) ont été parmi les premières structures de données utilisées pour représenter des collections homogènes de données, notamment dans les applications scientifiques et de gestion. - Aucune date ou nom spécifique n’est associé à l’introduction de ces concepts dans le programme camerounais anglophone de Lower Sixth, mais ils sont alignés sur les standards internationaux tels que ceux du Cambridge International AS & A Level ICT syllabus (9626), utilisé dans de nombreux établissements privés et bilingues du Cameroun. ### Causes et conséquences La nécessité de distinguer les types de données provient des limites matérielles des premières ordinateurs : manipuler des bits sans interprétation conduisait à des erreurs logiques. Par exemple, ajouter deux chaînes de caractères représentant des nombres (« 5 » + « 3 » = « 53 ») sans conversion explicite donne un résultat inattendu. L’utilisation de types de données évite ces ambiguités et permet au compilateur de détecter les erreurs de type à la compilation (dans les langages statiquement typés) ou à l’exécution (dans les langages dynamiquement typés). Les structures de données répondent au besoin d’efficacité algorithmique. Stocker 1000 notes d’élèves dans 1000 variables séparées serait ingérable ; un tableau permet de les gérer avec une seule variable et d’accéder à toute note via son indice. Une mauvaise choix de structure (par exemple, utiliser un tableau pour des insertions fréquentes au début) peut conduire à une complexité en O(n) au lieu de O(1) ou O(log n), ralentissant considérablement les applications réelles comme les systèmes de gestion scolaire ou les applications de suivi des prix des marchés locaux. ### Exemples concrets (camerounais et africains) - **Types de données** : Dans une application de gestion des notes pour un lycée de Yaoundé, la note d’un élève est stockée comme un flottant (ex. : 12.5), le nom comme une chaîne de caractères (« Emmanuel »), le sexe comme un caractère (« M » ou « F »), et le statut d’admission comme un booléen (vrai/faux). - **Structures de données** : - Un tableau unidimensionnel peut stocker les notes de tous les élèves d’une classe pour un examen donné. - Une liste chaînée pourrait représenter une file d’attente au guichet d’inscription d’une université de Buea, où chaque nouvel étudiant est ajouté à la fin et le premier servi est retiré du début. - Une pile (stack) peut modéliser l’historique de navigation dans une application éducative hors ligne utilisée dans les zones rurales sans connexion constante. - Une table de hachage (hash table) pourrait associer les numéros d’identification nationaux (NIN) des élèves à leurs dossiers académiques pour une recherche rapide dans un système national de suivi éducatif. ### Vocabulaire à retenir - Data Type, Primitive Data Type, Abstract Data Type (ADT), Static Data Structure, Dynamic Data Structure, Array, Linked List, Stack, Queue, Hash Table, Time Complexity, Space Complexity, Homogeneous, Heterogeneous, Indexing, Traversal. ### Exemple de sujet type examen avec plan **Sujet** : Une école secondaire de Bamenda souhaite développer une application pour gérer les prêts de livres dans sa bibliothèque. Chaque livre possède un titre (chaîne de caractères), un auteur (chaîne de caractères), un numéro d’identifiant unique (entier), et un statut indiquant s’il est disponible ou emprunté (booléen). Les élèves peuvent emprunter un livre s’il est disponible, et le retourner plus tard. 1. Expliquez pourquoi il est approprié d’utiliser différents types de données pour représenter les attributs d’un livre. (4 points) 2. Proposez une structure de données adaptée pour stocker la collection de tous les livres de la bibliothèque. Justifiez votre choix en termes d’efficacité pour les opérations de recherche par numéro d’identifiant et d’ajout de nouveaux livres. (6 points) 3. Décrivez comment vous implémenteriez l’opération de retour d’un livre en utilisant la structure de données choisie. Incluez les étapes logiques et l’impact sur le statut du livre. (5 points) **Plan attendu** : 1. **Types de données** : - Titre et auteur : chaînes de caractères (texte variable). - Numéro d’identifiant : entier (valeur discrète, utilisée pour l’indexation ou la recherche). - Statut : booléen (deux états seulement : disponible/emprunté). - Chaque type correspond à la nature réelle de l’attribut et permet des opérations adaptées (comparaison de chaînes, calcul sur entiers, test booléen). 2. **Structure de données proposée** : Table de hachage (hash table) avec le numéro d’identifiant comme clé. - Recherche par numéro d’identifiant : O(1) en moyenne, idéale pour un accès rapide. - Ajout d’un nouveau livre : O(1) en moyenne, efficace même avec des milliers de livres. - Alternative acceptable : tableau trié + recherche dichotomique (O(log n) pour recherche, mais O(n) pour insertion si maintien du tri), moins adapté aux ajouts fréquents. 3. **Opération de retour** : - L’élève fournit le numéro d’identifiant du livre. - Le système utilise ce numéro comme clé pour localiser le livre dans la table de hachage. - Le statut du livre est mis à jour de « emprunté » à « disponible ». - Aucun autre changement n’est nécessaire si la structure stocke directement le statut. ## II. Operations on Data Structures ### Contexte Une fois que les données sont organisées dans une structure adaptée, il devient essentiel de pouvoir les manipuler efficacement : les ajouter, les retirer, les rechercher, les modifier, ou les parcourir dans un ordre spécifique. Ces opérations définissent l’utilité pratique d’une structure de données. Leur efficacité est mesurée en termes de complexité temporelle (temps d’exécution) et spatiale (mémoire utilisée), souvent exprimée en notation Big O. Dans le contexte camerounais, comprendre ces opérations permet de concevoir des applications locales performantes, même sur des matériels limités — par exemple, une application de suivi des prix du manioc sur les marchés de Maroua qui doit répondre rapidement malgré une connexion intermittente ou un appareil de faible puissance. ### Définitions > **Traversal** : Le processus de visite de chaque élément d’une structure de données exactement once, généralement dans un ordre prédéfini (ex. : séquentiel pour un tableau, en profondeur ou en largeur pour un arbre). > **Search (Recherche)** : L’opération de localisation d’un élément spécifique dans une structure de données basée sur sa valeur ou sa clé. > **Insertion** : L’ajout d’un nouvel élément dans une structure de données à une position spécifiée. > **Deletion (Suppression)** : Le retrait d’un élément existant d’une structure de données. > **Update (Mise à jour)** : La modification de la valeur d’un élément déjà présent dans la structure. > **Sorting (Tri)** : Le réarrangement des éléments d’une structure de données dans un ordre spécifique (croissant ou décroissant) basé sur une clé. > **Time Complexity** : Une mesure de la quantité de temps qu’un algorithme prend pour s’exécuter en fonction de la taille de l’entrée, exprimée en notation Big O (ex. : O(1), O(n), O(log n), O(n²)). > **Space Complexity** : Une mesure de la quantité de mémoire qu’un algorithme utilise pendant son exécution en fonction de la taille de l’entrée. ### Faits, dates et noms exacts - Les notions de complexité algorithmique ont été popularisées dans les années 1960-1970 par des informaticiens tels que Donald Knuth, dont l’ouvrage *The Art of Computer Programming* reste une référence fondamentale. - Le tri à bulles (bubble sort) est l’un des plus anciens algorithmes de tri, connu depuis les années 1950, bien qu’inefficace (O(n²)) pour de grands ensembles de données. - Le tri rapide (quicksort), développé par Tony Hoare en 1960, atteint une complexité moyenne de O(n log n) et est largement utilisé dans les bibliothèques standards de langages comme Python et Java. - La recherche dichotomique (binary search) nécessite un tableau trié et atteint une complexité de O(log n), mais ne peut être appliquée directement sur des structures non triées ou non indexables comme les listes chaînées. - Aucune date ou nom spécifique n’est associé à l’enseignement de ces opérations dans le programme camerounais anglophone de Lower Sixth, mais elles sont conformes aux attentes du syllabus Cambridge International AS & A Level ICT (9626), notamment dans la section sur la résolution de problèmes et la conception d’algorithmes. ### Causes et conséquences Le choix de l’opération et de la structure de données a un impact direct sur les performances d’une application. Par exemple, rechercher un élève par nom dans un tableau non trié nécessite un parcours séquentiel (O(n)), tandis qu’une table de hachage permet une recherche en O(1) en moyenne. Cependant, les tables de hachage consomment plus de mémoire et nécessitent une bonne fonction de hachage pour éviter les collisions. À l’inverse, une liste chaînée permet des insertions et suppressions efficaces en O(1) si la position est connue, mais la recherche y est lente (O(n)) car elle nécessite un parcours séquentiel. Dans des environnements à ressources limitées — courants dans les écoles rurales du Cameroun — une mauvaise complexité peut rendre une application inutilisable : un algorithme de tri en O(n²) sur 10 000 notes pourrait prendre plusieurs secondes ou minutes, tandis qu’un O(n log n) terminerait en moins d’une seconde. Cela influence directement l’expérience utilisateur et la viabilité des solutions locales. ### Exemples concrets (camerounais et africains) - **Recherche** : Dans une application de suivi des vaccinations dans un district sanitaire de l’Extrême-Nord, rechercher un enfant par son numéro de carte de vaccination dans un tableau trié permet d’utiliser la recherche dichotomique (O(log n)), accélérant considérablement le processus lors des campagnes de masse. - **Insertion/Suppression** : Dans une file d’attente numérique pour l’accès à un laboratoire informatique limité à Yaoundé, une file (queue) permet d’ajouter les étudiants à la fin (enqueue, O(1)) et de servir celui qui attend le plus longtemps en premier (dequeue, O(1)), modélisant équitablement l’accès. - **Parcours** : Pour afficher la liste des résultats d’un examen dans l’ordre alphabétique des noms, un parcours séquentiel d’un tableau de chaînes de caractères (après tri) est utilisé pour générer le bulletin affiché dans le hall de l’établissement. - **Mise à jour** : Dans une application de gestion des stocks d’une coopérative agricole de l’Ouest, mettre à jour la quantité de maïs disponible après une vente implique de localiser l’article (par nom ou code) et de modifier sa valeur — une opération en O(1) avec une table de hachage, O(n) avec un tableau non trié. - **Tri** : Avant d’afficher les meilleurs élèves d’une classe, les notes sont triées par ordre décroissant (du plus haut au plus bas) pour identifier les lauréats — un tri efficace (O(n log n)) est essentiel pour éviter les retards lors des cérémonies de remise de prix. ### Vocabulaire à retenir - Traversal, Search, Insertion, Deletion, Update, Sorting, Time Complexity, Space Complexity, Big O Notation, Linear Search, Binary Search, Bubble Sort, Quick Sort, Merge Sort, Hashing, Collision, Enqueue, Dequeue, Push, Pop, FIFO, LIFO. ### Exemple de sujet type examen avec plan **Sujet** : Un groupe d’étudiants de l’Université de Douala a développé une application mobile pour permettre aux vendeurs du marché de Mvog-Beti de suivre leurs ventes quotidiennes de légumes (tomates, oignons, piments). Chaque vente enregistre le nom du légume (chaîne de caractères), la quantité vendue (entier en kg), et le prix unitaire (flottant en FCFA). L’application doit permettre d’ajouter une nouvelle vente, de rechercher toutes les ventes d’un légume spécifique, de calculer le revenu total du jour, et d’afficher les ventes dans l’ordre décroissant de la quantité vendue. 1. Justifiez le choix d’utiliser une liste de tuples ou d’enregistrements (records) pour stocker les ventes quotidiennes. (4 points) 2. Comparez l’efficacité de deux méthodes pour rechercher toutes les ventes d’un légume spécifique : (a) parcours séquentiel d’une liste non triée, et (b) utilisation d’un dictionnaire (table de hachage) où la clé est le nom du légume et la valeur est une liste de ses ventes. Incluez les complexités temporelles pour l’insertion et la recherche. (6 points) 3. Décrivez comment vous implémenteriez l’affichage des ventes triées par quantité vendue (du plus élevé au plus bas). Précisez l’algorithme de tri que vous utiliseriez et justifiez votre choix en termes d’efficacité pour un ensemble de données pouvant atteindre 500 entrées. (5 points) **Plan attendu** : 1. **Justification du stockage** : - Chaque vente est un groupe d’attributs liés (nom, quantité, prix) → naturellement représenté comme un enregistrement (record) ou un tuple. - Une liste de tels enregistrements permet de stocker un historique dynamique des ventes, facile à parcourir et à modifier. - Alternative : utiliser trois listes parallèles (noms, quantités, prix) est moins sûr (risque de désynchronisation) et moins lisible. 2. **Comparaison des méthodes de recherche** : - (a) Parcours séquentiel d’une liste non triée : - Recherche d’un légume : O(n) dans le pire cas (il faut vérifier chaque vente). - Insertion d’une nouvelle vente : O(1) (ajout à la fin de la liste). - (b) Dictionnaire (table de hachage) avec clé = nom du légume : - Recherche : O(1) en moyenne pour accéder à la liste des ventes de ce légume. - Insertion : O(1) en moyenne (calcul du hachage, ajout dans la liste associée à la clé). - Avantages : Recherche extrêmement rapide, surtout utile si plusieurs recherches sont effectuées par jour. - Inconvénients : Légère surcharge mémoire due à la structure de hachage et à la gestion des collisions. - Conclusion : Pour un marché où l’on recherche fréquemment les ventes d’un légume (ex. : pour réapprovisionner), la table de hachage est préférable malgré un coût mémoire légèrement supérieur. 3. **Implémentation du tri par quantité vendue** : - Utiliser l’algorithme de tri rapide (quicksort) ou de tri par fusion (merge sort) pour trier la liste des ventes par le champ quantité vendue en ordre décroissant. - Justification : - Pour 500 entrées, O(n²) (comme le tri à bulles) serait trop lent en pratique (potentiellement plusieurs secondes). - O(n log n) de quicksort ou merge sort est largement suffisant (exécution en quelques millisecondes même sur un appareil modeste). - Merge sort offre une complexité garantie O(n log n) et est stable, utile si l’on veut préserver l’ordre relatif des ventes égales en quantité. - Quicksort est souvent plus rapide en moyenne et utilise moins de mémoire auxiliaire, mais risque O(n²) dans le pire cas (peu probable avec une bonne stratégie de pivot). - Étapes : - Extraire ou accéder au champ quantité vendue de chaque enregistrement. - Appliquer l’algorithme de tri sur cette clé. - Parcourir la liste triée et afficher chaque vente (nom, quantité, prix) dans l’ordre résultant. ## Synthèse du chapitre - Les types de données définissent la nature et les opérations autorisées sur les valeurs manipulées par un programme (ex. : entier, flottant, chaîne, booléen). - Les structures de données permettent d’organiser efficacement des collections de données liées pour faciliter l’accès, la modification et la gestion. - Les types de données primitifs sont fournis par le langage ; les types abstraits (ADT) définissent le comportement sans spécifier l’implémentation. - Les structures statiques (comme les tableaux) ont une taille fixe ; les dynamiques (comme les listes chaînées, piles, files) peuvent varier pendant l’exécution. - Les opérations fondamentales sur les structures de données incluent le parcours, la recherche, l’insertion, la suppression, la mise à jour et le tri. - L’efficacité de ces opérations est évaluée en complexité temporelle et spatiale, souvent exprimée en notation Big O. - Le choix d’une structure de données et d’un algorithme doit tenir compte du contexte d’utilisation : fréquence des opérations, volume des données, contraintes matérielles. - Dans des contextes africains et camerounais (gestion scolaire, agricole, commerciale), des structures comme les tables de hachage, les files ou les piles offrent des solutions adaptées aux problèmes locaux de suivi, d’attente ou de recherche. - Des algorithmes efficaces (comme le tri rapide ou la recherche dichotomique) sont essentiels pour garantir la réactivité des applications, même sur des appareils modestes. - Une mauvaise conception peut conduire à des lenteurs inacceptables ; une conception réfléchie améliore l’expérience utilisateur et la viabilité des solutions technologiques locales. ## Glossaire - **Data Type** : Classification qui définit le type de valeur qu’une variable peut contenir et les opérations autorisées. - **Primitive Data Type** : Type de donnée de base fourni par le langage (ex. : entier, flottant, booléen, caractère). - **Abstract Data Type (ADT)** : Modèle qui définit le comportement d’un type de donnée (opérations) sans spécifier son implémentation. - **Static Data Structure** : Structure de données dont la taille est fixée à la compilation et ne change pas pendant l’exécution. - **Dynamic Data Structure** : Structure de données dont la taille peut varier pendant l’exécution en fonction des besoins. - **Array (Tableau)** : Structure de données statique qui stocke des éléments du même type dans des emplacements mémoire contigus, accessibles par indice. - **Linked List (Liste Chaînée)** : Structure de données dynamique où chaque élément (noeud) contient une valeur et une référence vers le suivant (ou précédent). - **Stack (Pile)** : Structure de données suivant le principe LIFO (Last In, First Out), avec opérations push (empiler) et pop (dépiler). - **Queue (File)** : Structure de données suivant le principe FIFO (First In, First Out), avec opérations enqueue (ajouter à la fin) et dequeue (retirer du début). - **Hash Table (Table de Hachage)** : Structure de données qui associe des clés à des valeurs via une fonction de hachage, permettant une recherche, insertion et suppression moyennes en O(1). - **Time Complexity** : Mesure de la croissance du temps d’exécution d’un algorithme en fonction de la taille de l’entrée, exprimée en notation Big O. - **Space Complexity** : Mesure de la croissance de la mémoire utilisée par un algorithme en fonction de la taille de l’entrée.