UA 3 : ORGANISATION DES DONNÉES EN INFORMATIQUE

## Objectifs et prérequis **Objectifs** : À la fin de ce chapitre, l’élève pourra - expliquer ce qu’est une organisation structurée des données et citer les principales structures linéaires et non linéaires ; - décrire comment les différents types de données (entiers, réels, caractères) sont représentés en binaire dans la mémoire d’un ordinateur ; - mettre en œuvre des codages simples de détection et de correction d’erreurs (parité, code de Hamming) et comprendre les notions de redondance et de compression ; - résoudre des exercices de conversion, de codage et de décodage en montrant chaque étape de raisonnement. **Prérequis** : maîtriser la numérotation binaire de base, connaître les opérations logiques (ET, OU, NON) et savoir manipuler des tableaux à une dimension en algorithme ou en pseudo‑code. ## Introduction contextualisée Dans la vie quotidienne, nous manipulons des informations sous diverses formes : listes de contacts, emplois du temps, photos, sons. En informatique, ces informations doivent être organisées de façon à permettre un traitement efficace par le processeur et un stockage optimal en mémoire. Ce chapitre montre comment passer d’une donnée brute à une représentation interne exploitable, puis comment la protéger contre les altérations lors de sa transmission ou de son stockage. ## I. Leçon 5 : Organisation structurée des données ### A. Définition et propriétés > **Une donnée structurée est un ensemble d’éléments liés entre eux selon un schéma prédéfini, permettant des opérations d’accès, d’insertion, de suppression et de parcours définies.** Les propriétés essentielles sont : - **Homogénéité** (ou hétérogénéité contrôlée) : tous les éléments d’un même type ou bien typés selon un enregistrement ; - **Accès déterministe** : la position d’un élément peut être calculée à partir d’indices ; - **Complexité bornée** : les opérations fondamentales ont une complexité en O(1), O(log n) ou O(n) selon la structure. ### B. Principales structures étudiées en 3ᵉ | Structure | Type | Accès | Exemple d’utilisation | |-----------|------|-------|-----------------------| | Tableau (vecteur) | Linéaire, homogène | Index direct O(1) | Stockage de notes d’une classe | | Liste simplement chaînée | Linéaire, homogène | Parcours séquentiel O(n) | Gestion d’une file d’attente | | Enregistrement (struct) | Heterogène | Champs nommés O(1) | Fiche élève (nom, âge, moyenne) | | Arbre binaire de recherche | Non linéaire | Recherche O(log n) en moyenne | Dictionnaire de mots | ### C. Opérations fondamentales - **Insertion** : placer un nouvel élément tout en préservant l’ordre ou la propriété de la structure. - **Suppression** : retirer un élément et ré‑ajuster les liens ou les indices. - **Recherche** : localiser un élément selon sa clé. - **Parcours** : visiter chaque élément exactement suivant un ordre prédéfini (pré‑ordre, in‑ordre, post‑ordre pour les arbres). ### D. Exemples résolus **Exemple 1 – Tableau** Donné le tableau `T = [12, 7, 9, 15, 3]`. 1. Rechercher la valeur 9. - On parcourt les indices : T[0]=12≠9, T[1]=7≠9, T[2]=9 → trouvé à l’indice 2. 2. Insérer la valeur 4 à la fin. - Nouveau tableau : `[12, 7, 9, 15, 3, 4]`. 3. Supprimer l’élément d’indice 1. - On décale les éléments à gauche : `[12, 9, 15, 3, 4]`. **Exemple 2 – Liste simplement chaînée** Liste L : 5 → 8 → 3 → NULL. 1. Insérer la valeur 6 après le nœud contenant 8. - Créer nœud N(6). - Faire `N.succ = 8.succ` (qui pointe vers 3). - Faire `8.succ = N`. - Résultat : 5 → 8 → 6 → 3 → NULL. 2. Supprimer le nœud contenant 3. - Trouver le prédécesseur de 3 (c’est 6). - Faire `6.succ = 3.succ` (qui est NULL). - Résultat : 5 → 8 → 6 → NULL. ## II. Leçon 6 : Représentation des données dans l’ordinateur ### A. Représentation binaire de base > **Tout donnée numérique est stockée sous forme de bits (0 ou 1) ; un groupe de 8 bits forme un octet (byte).** La valeur d’un entier non signé sur *n* bits est : $$N = \sum_{i=0}^{n-1} b_i \cdot 2^{i}$$ où $b_i$ est le i‑ème bit (poids faible à droite). ### B. Codage des entiers #### 1. Entiers non signés (unsigned) Plage : $[0, 2^{n}-1]$. Exemple sur 8 bits : 200 → $11001000_2$. #### 2. Entiers signés – complément à deux > **Dans le complément à deux, le bit de poids fort représente le signe (0 = positif, 1 = négatif) et la valeur négative se obtient en inversant tous les bits puis en ajoutant 1.** Formule pour un nombre sur *n* bits : $$V = -b_{n-1}\cdot 2^{n-1} + \sum_{i=0}^{n-2} b_i \cdot 2^{i}$$ Exemple sur 8 bits : -42 - +42 en binaire : $00101010$ - Inversion : $11010101$ - +1 : $11010110$ → représentation de -42. Plage : $[-2^{n-1}, 2^{n-1}-1]$ → $[-128,127]$ sur 8 bits. ### C. Codage des réels (virgule flottante simplifiée) > **Le format IEEE 754 simple précision utilise 1 bit de signe, 8 bits d’exposant (biais = 127) et 23 bits de mantisse.** Valeur : $$(-1)^{s}\times 1.m \times 2^{E-127}$$ où $s$ est le bit de signe, $E$ l’exposant stocké, $m$ la fraction mantisse. Exemple : représenter 5,75. - 5,75 en binaire : $101,11$ → $1,0111 \times 2^{2}$ - $s=0$, $E = 2+127 = 129 = 10000001_2$ - Mantisse (23 bits) : $01110000000000000000000$ - Résultat : `0 10000001 01110000000000000000000`. ### D. Codage des caractères > **ASCII utilise 7 bits (0‑127) ; UTF‑8 est un encodage variable compatible ASCII, utilisant 1 à 4 octets selon le point de code Unicode.** Tableau partiel ASCII : | Déc | Hex | Caractère | |-----|-----|-----------| | 65 | 0x41| ‘A’ | | 97 | 0x61| ‘a’ | | 48 | 0x30| ‘0’ | Exemple UTF‑8 : le caractère « é » (U+00E9) → octets `11000011 10101001` (C3 A9 en hex). ### E. Exemples résolus **Exemple 3 – Conversion entier signé** Représenter -13 sur 8 bits en complément à deux. - +13 = $00001101$ - Inversion = $11110010$ - +1 = $11110011$ → -13 = `11110011$. **Exemple 4 – Conversion réel IEEE 754** Encoder -0,625 en simple précision. - 0,625 en binaire = $0,101$ → $1,01 \times 2^{-1}$ - $s=1$ (négatif) - Exposant réel = -1 → $E = -1+127 = 126 = 01111110_2$ - Mantisse = $01000000000000000000000$ (on prend la partie après la virgule) - Résultat : `1 01111110 01000000000000000000000$. ## III. Leçon 7 : Codification des données ### A. Notions de base > **Un code est une transformation qui ajoute de la redondance afin de détecter ou corriger des altérations ; le taux de redondance est le rapport entre les bits ajoutés et les bits d’information.** Objectifs : détection d’erreur (parité), correction d’erreur (code de Hamming), compression (codage de source). ### B. Bit de parité > **Le bit de parité est ajouté de façon à ce que le nombre total de bits à 1 soit pair (parité paire) ou impair (parité impaire).** - Détection : toute inversion d’un seul bit change la parité → erreur détectée. - Limitation : ne détecte pas les erreurs paires de bits. Exemple : octet `10110010` (4 bits à 1 → pair). - Parité paire → bit ajouté = 0 → `101100100`. - Si un bit se flippe (ex. 3ᵉ bit passe de 1 à 0) → `100100100` (3 bits à 1 → impair) → erreur détectée. ### C. Code de Hamming (7,4) > **Le code de Hamming (7,4) encode 4 bits de donnée en 7 bits en ajoutant 3 bits de contrôle permettant de corriger toute erreur simple et de détecter une erreur double.** Positions des bits de contrôle : 1, 2, 4 (puissances de 2). Les bits de donnée occupent les positions 3, 5, 6, 7. Règles de parité : - $C_1$ couvre les positions où le bit de poids faible de l’index est 1 : 1,3,5,7. - $C_2$ couvre les positions où le deuxième bit de l’index est 1 : 2,3,6,7. - $C_4$ couvre les positions où le troisième bit de l’index est 1 : 4,5,6,7. Chaque bit de contrôle est choisi pour rendre la parité de son groupe paire. **Exemple de codage** Données : $d_3 d_5 d_6 d_7 = 1\,0\,1\,1$. - Position 3 = 1, 5 = 0, 6 = 1, 7 = 1. Calcul : - Groupe C1 (1,3,5,7) : bits = $?,1,0,1$ → somme des 1 = 2 (pair) → $C_1=0$. - Groupe C2 (2,3,6,7) : bits = $?,1,1,1$ → somme = 3 (impair) → $C_2=1$ pour rendre pair. - Groupe C4 (4,5,6,7) : bits = $?,0,1,1$ → somme = 2 (pair) → $C_4=0$. Code final (positions 1→7) : $0\,1\,1\,0\,0\,1\,1$ → `0110011$. **Décodage et correction** Si le mot reçu est `0110111` (erreur sur la position 5) : - Calcul des syndromes : - $s_1 =$ parité de (1,3,5,7) = $0\oplus1\oplus1\oplus1 = 1$ (impair) → 1 - $s_2 =$ parité de (2,3,6,7) = $1\oplus1\oplus1\oplus1 = 0$ (pair) → 0 - $s_4 =$ parité de (4,5,6,7) = $0\oplus1\oplus1\oplus1 = 1$ (impair) → 1 - Syndrome binaire $s_4 s_2 s_1 = 101_2 = 5$ → indique l’erreur à la position 5. - Inverser le bit 5 : `0110111` → `0110011`. - Extraire les données (positions 3,5,6,7) : $1\,0\,1\,1$ → `1011$. ### D. Codage de source (compression) – aperçu > **Le codage de source supprime la redondance intrinsèque des données sans perte d’information.** - **RLE (Run Length Encoding)** : remplace une suite de symboles identiques par un couple (symbole, nombre de répétitions). Exemple : `AAAABBBCCDAA` → `4A3B2C1D2A`. - **Codage de Huffman** : construit un arbre binaire où les symboles les plus fréquents ont les codes les plus courts. Exemple rapide : symboles {A:45, B:13, C:12, D:16, E:9, F:5}. Après construction, on obtient par exemple : A=0, C=100, D=101, B=1100, F=11010, E=11011. ### E. Exemples résolus **Exemple 5 – Bit de parité** Donnée : `1101001` (4 bits à 1 → pair). - Parité paire → ajouter 0 → `11010010`. - Si un bit se flippe (ex. 2ᵉ bit passe de 1 à 0) → `10010010` (3 bits à 1 → impair) → erreur détectée. **Exemple 6 – Code de Hamming (7,4)** Encoder le nibble `1010`. - Placer les données : positions 3=1,5=0,6=1,7=0. - Calcul des bits de contrôle : - C1 (1,3,5,7) : ?,1,0,0 → somme=1 → C1=1 (pour rendre pair). - C2 (2,3,6,7) : ?,1,1,0 → somme=2 → C2=0. - C4 (4,5,6,7) : ?,0,1,0 → somme=1 → C4=1. - Code : positions 1→7 : `1 0 1 1 0 1 0` → `1011010$. **Exemple 7 – RLE** Compresser `XXXXYYYZZXXXXX`. - Suite X (4) → `4X` - Suite Y (3) → `3Y` - Suite Z (2) → `2Z` - Suite X (5) → `5X` Résultat : `4X3Y2Z5X$. ## Synthèse du chapitre - Les données structurées (tableaux, listes, enregistrements, arbres) permettent des opérations définies avec des complexités connues. - En mémoire, tout se représente en binaire : entiers non signés, signés (complément à deux), réels (IEEE 754), caractères (ASCII/UTF‑8). - La codification ajoute de la redondance : bit de parité pour détection simple, code de Hamming (7,4) pour correction d’erreur simple, et des techniques de compression (RLE, Huffman) pour réduire la taille. - Chaque notion s’appuie sur des formules précises et des procédures algorithmiques que l’élève doit savoir appliquer étape par étape. ## Glossaire | Terme | Définition | |-------|------------| | **Structure de données** | Organisation logique permettant d’accéder, d’insérer, de supprimer et de parcourir des éléments selon des règles précises. | | **Tableau** | Collection contiguë d’éléments homogènes accessible par indice en O(1). | | **Liste simplement chaînée** | Suite de nœuds contenant une donnée et un pointeur vers le suivant ; accès séquentiel O(n). | | **Complément à deux** | Méthode de représentation des entiers négatifs où la valeur se obtient par inversion des bits puis ajout de 1. | | **IEEE 754** | Norme de représentation des nombres à virgule flottante (signe, exposant biaisé, mantisse). | | **Bit de parité** | Bit ajouté pour rendre le nombre de 1 pair ou impair, permettant de détecter une erreur simple. | | **Code de Hamming (7,4)** | Code correcteur d’erreurs qui ajoute 3 bits de contrôle à 4 bits de donnée pour corriger toute erreur simple. | | **RLE (Run Length Encoding)** | Méthode de compression qui remplace une séquence répétée par le symbole et son nombre d’occurrences. | | **Codage de Huffman** | Algorithme de compression sans perte qui attribue des codes binaires de longueur variable selon la fréquence des symboles. | | **Syndrome** | Résultat du contrôle de parité dans un code de correction d’erreur ; indique la position de l’erreur éventuelle. | ## Exercices d'application corrigés ### Exercice 1 – Tableau (niveau facile) Donné le tableau `T = [2, 5, 8, 11, 14]$. 1. Trouver l’indice de la valeur 11. 2. Insérer la valeur 20 à la position 2 (indice 2, en décalant les éléments à droite). 3. Supprimer l’élément d’indice 4. **Corrigé** 1. Parcours : T[0]=2≠11, T[1]=5≠11, T[2]=8≠11, T[3]=11 → indice 3. 2. Avant insertion : `[2,5,8,11,14]$. Décaler à partir de l’indice 2 : `[2,5,_,8,11,14]$. Placer 20 → `[2,5,20,8,11,14]$. 3. Après suppression de l’indice 4 (valeur 11) : on décale les éléments à gauche à partir de l’indice 5 → `[2,5,20,8,14]$. ### Exercice 2 – Complément à deux (niveau moyen) Représenter -57 sur 8 bits en complément à deux. **Corrigé** +57 en binaire sur 8 bits : `00111001$. Inversion des bits : `11000110$. Ajout de 1 : `11000110 + 1 = 11000111$. Donc -57 = `11000111$. ### Exercice 3 – IEEE 754 simple précision (niveau moyen) Encoder le nombre 12,25 en format IEEE 754 simple précision. **Corrigé** 12,25 en binaire : 12 = `1100$, 0,25 = `0,01$ → `1100,01$ = `1,10001 × 2³$. - Signe $s = 0$ (positif). - Exposant réel = 3 → $E = 3 + 127 = 130 = 10000010_2$. - Mantisse (23 bits) : on prend la partie après la virgule de `1,10001$ → `10001$ puis on complète avec des 0 jusqu’à 23 bits → `10001000000000000000000$. Résultat : `0 10000010 10001000000000000000000$. ### Exercice 4 – Bit de parité (niveau facile) On veut transmettre l’octet `10101100$ en utilisant une parité impaire. Quel bit de parité ajouter ? **Corrigé** Nombre de 1 dans l’octet : bits = 1,0,1,0,1,1,0,0 → quatre 1 (pair). Pour obtenir une parité impaire, il faut ajouter un bit qui rende le nombre total de 1 impair → ajouter 1. Octet transmis : `101011001$. ### Exercice 5 – Code de Hamming (7,4) (niveau difficile) Détecter et corriger l’erreur dans le mot reçu `1101110$ sachant qu’il s’agit d’un code de Hamming (7,4). **Corrigé** Positions : 1 2 3 4 5 6 7 → bits reçus : 1 1 0 1 1 1 0. Calcul des syndromes : - $s_1$ (positions 1,3,5,7) : $1 \oplus 0 \oplus 1 \oplus 0 = 0$. - $s_2$ (positions 2,3,6,7) : $1 \oplus 0 \oplus 1 \oplus 0 = 0$. - $s_4$ (positions 4,5,6,7) : $1 \oplus 1 \oplus 1 \oplus 0 = 1$ (car 1⊕1=0, 0⊕1=1, 1⊕0=1). Syndrome $s_4 s_2 s_1 = 100_2 = 4$ → erreur à la position 4. Inverser le bit 4 : `1101110$ → `1100110$. Extraire les données (positions 3,5,6,7) : bits = 0,1,1,0 → `0110$. Donc le nibble transmis était `0110$. ### Exercice 6 – RLE (niveau moyen) Compresser la chaîne `AAABBBCCCDDDDEEEEE$. **Corrigé** - A répété 3 fois → `3A$ - B répété 3 fois → `3B$ - C répété 3 fois → `3C$ - D répété 4 fois → `4D$ - E répété 5 fois → `5E$ Résultat : `3A3B3C4D5E$. ## Erreurs fréquentes | Erreur fréquente | Pourquoi elle se produit | Comment l’éviter | |------------------|--------------------------|------------------| | Confondre complément à deux et valeur absolue | L’élève oublie d’ajouter 1 après l’inversion des bits. | Toujours rappeler la procédure : inverser → ajouter 1. | | Placer les bits de contrôle aux mauvaises positions dans le code de Hamming | On pense que les bits de contrôle sont aux extrémités. | Mémoriser la règle : positions 1, 2, 4, 8,… (puissances de 2). | | Oublier de biaiser l’exposant en IEEE 754 | On utilise l’exposant réel directement. | Appliquer systématiquement $E = e + 127$ (simple précision). | | Compter mal les 1 pour la parité | On oublie un bit ou on compte deux fois. | Faire le comptage à voix haute ou utiliser une règle de groupe de 4 bits. | | Décaler dans le mauvais sens lors d’une insertion/suppression dans un tableau | Confondre gauche/droite. | Visualiser le tableau et se rappeler que l’insertion décale les éléments vers la droite, la suppression vers la gauche. | | Utiliser le mauvais arbre de Huffman (inversion des 0/1) | On attribue 0 à la branche droite au lieu de gauche. | Lors de la construction, choisir systématiquement 0 pour la branche gauche et 1 pour la droite (ou inverser, mais rester cohérent). | --- Fin du cours.