Lernzettel: Introduction aux Types de Données Abstraits

📋 Plan du Cours

1. Plan du chapitre et notions TDA TD SD
2. Démarche de résolution d’un problème
3. Algorithme et programme
4. Types de données abstraits : définition et descriptions
5. Exemples de TDA et description axiomatique
6. Types de données : TD simples et composés
7. Création et implémentation d’un type de données
8. Implémentation d’un TDA en C : interface et opérations
9. Utilisation d’un TDA indépendamment de l’implémentation
10. Structures de données et allocation dynamique

📖 1. Plan du chapitre et notions TDA TD SD

🔑 Notions clés & Définitions

• TDA : Un TDA est une spécification d’un type de données abstrait, décrivant ce qu’on peut faire sans imposer comment c’est stocké.
• TD : Un TD est un type de données concret, dont les variables prennent des valeurs issues d’un domaine défini.
• SD : Une SD est une structure de données qui implémente des TD/collections, en organisant le stockage en mémoire.
• Pointeurs : Un pointeur est une cellule dont la valeur contient l’adresse d’une autre cellule.
• Références : Une référence est un mécanisme de langage orienté objet permettant d’accéder à un objet sans manipuler directement son adresse.

📝 Points essentiels

• Le chapitre annonce explicitement TDA, TD et SD comme notions centrales.
• Un TDA est décrit par un nom, des opérations, et des descriptions fonctionnelle et axiomatique.
• Un TD peut être simple (primitif) ou composé (structuré ou de référence en Java).
• Une SD peut être implémentée via des tableaux (statique) ou via des mécanismes dynamiques (pointeurs).
• Les pointeurs sont gérés par deux procédures : Allouer et Libérer.

💡 Astuce mémo

TDA = “quoi”, TD = “valeurs”, SD = “où en mémoire”.

📖 2. Démarche de résolution d’un problème

🔑 Notions clés & Définitions

• Formalisation du problème : La formalisation du problème consiste à transformer l’énoncé en une spécification exploitable pour construire une solution.
• Spécification : Une spécification décrit précisément ce que le système doit faire, avant d’en écrire l’algorithme.
• Traduction en langage de programmation : La traduction en langage de programmation consiste à exprimer la solution sous forme de code dans un langage donné.

📝 Points essentiels

• La démarche comporte : compréhension du problème, formalisation en spécification, mise en œuvre de l’algorithme, puis traduction en langage.
• La mise en œuvre de l’algorithme correspond à l’étape où l’on construit la suite d’instructions réalisant le traitement.
• La traduction en langage de programmation produit un programme exécutable dans un langage (exemples cités : ADA, C++, Java, Cobol).
• La spécification sert de pont entre l’énoncé et l’algorithme.
• L’ordre des étapes est : comprendre → spécifier → algorithme → programmer.

💡 Astuce mémo

Comprendre → Spécifier → Algorithme → Programmer (CSAP).

📖 3. Algorithme et programme

🔑 Notions clés & Définitions

• Algorithme : Un algorithme est une suite d’instructions exécutées dans un ordre séquentiel pour réaliser un traitement.
• Programme : Un programme est un algorithme traduit dans un langage de programmation pour être exécuté.

📝 Points essentiels

• Un algorithme réalise un traitement via une suite d’instructions séquentielles.
• Un programme correspond à la traduction de l’algorithme dans un langage donné.
• Les langages cités incluent ADA, C++, Java et Cobol.
• La différence clé : l’algorithme est indépendant du langage, le programme dépend du langage.
• Le chapitre relie explicitement algorithme et programme dans la démarche de résolution.

💡 Astuce mémo

Algorithme = recette, Programme = recette écrite dans un langage.

📖 4. Types de données abstraits : définition et descriptions

🔑 Notions clés & Définitions

• Type de données abstrait : Un type de données abstrait est une spécification d’un type de données concret, centrée sur les opérations et leur sens.
• Description fonctionnelle : La description fonctionnelle précise les opérations d’un TDA via leurs signatures, avec noms et ensembles de départ/arrivée.
• Description axiomatique : La description axiomatique donne la sémantique d’un TDA sous forme d’axiomes sur les opérations.
• Signature d’une opération : Une signature d’opération indique le nom de l’opération et les types/ensembles d’entrée et de sortie.

📝 Points essentiels

• Chaque TDA est caractérisé par un nom et des opérations prévues.
• La description fonctionnelle décrit les signatures en indiquant noms et ensembles de départ et d’arrivée.
• La description axiomatique correspond à la sémantique du TDA.
• Le chapitre donne un exemple de TDA : entier avec opérations arithmétiques (+, -, /, …).
• Le chapitre donne un exemple de TDA : liste avec opérations comme vider et insérer.

💡 Astuce mémo

Fonctionnelle = signatures, Axiomatique = sémantique.

📖 5. Exemples de TDA et description axiomatique

🔑 Notions clés & Définitions

• Ensemble : L’ensemble est un domaine d’éléments utilisé dans les signatures des opérations d’un TDA.
• Booléen : Le booléen est un type de résultat logique utilisé pour des opérations qui testent une propriété.
• Axiomes de PEANO : Les axiomes de PEANO sont un ensemble d’axiomes qui définissent la structure des entiers naturels et leurs opérations.
• Sémantique : La sémantique d’un TDA est l’interprétation formelle des opérations donnée par les axiomes.

📝 Points essentiels

• Le chapitre illustre des signatures d’opérations avec des formes du type {} → Booléen.
• Exemple d’opérations : estVide : {} → Booléen et appartient : Elément x {} → Booléen.
• Exemple d’opérations : ajouter : Elément x {} → {} et enlever : Elément x {} → {}.
• Le chapitre donne aussi union : {} x {} → {} pour combiner deux ensembles.
• Pour la description axiomatique ℕ, le cours liste des axiomes de PEANO portant sur succ, égalités et opérations + et x.

💡 Astuce mémo

PEANO = succ + axiomes sur + et x (structure de ℕ).

📖 6. Types de données : TD simples et composés

🔑 Notions clés & Définitions

• TD simple : Un TD simple (primitif) est un type dont chaque variable prend une seule valeur appartenant à un domaine à un instant donné.
• TD composé : Un TD composé (structuré) permet de stocker sous un même nom de variable plusieurs valeurs, éventuellement de types différents.
• Enregistrement : Un enregistrement est un exemple de TD composé structuré, regroupant plusieurs champs sous un même type.
• Tableau : Un tableau est un exemple de TD composé permettant de stocker plusieurs valeurs du même type.

📝 Points essentiels

• Un TD simple inclut des exemples comme entier et booléen.
• Pour un TD simple, une variable ne peut prendre qu’une valeur du domaine à la fois.
• Un TD composé peut stocker plusieurs valeurs sous un même nom de variable.
• Le cours cite tableau d’entiers comme exemple de stockage de plusieurs valeurs du même type.
• Le cours cite aussi un type enregistrement comme exemple de TD composé avec plusieurs valeurs de types non nécessairement identiques.

💡 Astuce mémo

Simple = une valeur, Composé = plusieurs valeurs sous un même nom.

📖 7. Création et implémentation d’un type de données

🔑 Notions clés & Définitions

• Interface abstraite : L’interface abstraite est la partie logique exposée à l’utilisateur, indépendante du stockage réel.
• Implémentation : Une implémentation est la façon concrète de réaliser un type de données à partir de son interface logique.
• Niveau logique : Le niveau logique correspond à la spécification/vision abstraite du type, avant le détail d’exécution.
• Utilisateur : L’utilisateur interagit avec le type via l’interface abstraite, sans connaître l’implémentation.

📝 Points essentiels

• Le schéma distingue un niveau logique et des implémentations concrètes.
• La création d’un type passe par une interface abstraite reliée à des TD/implémentations.
• Le cours montre plusieurs implémentations possibles pour un même type logique.
• L’utilisateur manipule le type via l’interface abstraite.
• La séparation logique/implémentation prépare l’indépendance d’utilisation.

💡 Astuce mémo

Interface abstraite = porte d’entrée, Implémentations = coulisses.

📖 8. Implémentation d’un TDA en C : interface et opérations

🔑 Notions clés & Définitions

• Interface en C : L’interface en C correspond aux déclarations (fichier d’en-tête) des types et des opérations offertes par le TDA.
• Opérations d’un TDA : Les opérations d’un TDA sont les fonctions/macro proposées qui définissent comment on manipule le type.
• PILE : PILE est le type de données abstrait/structure de base utilisée dans l’exemple de pile.
• Interface utilisateur : L’interface utilisateur est l’ensemble des en-têtes de fonctions qui permettent d’utiliser le TDA sans voir le code interne.

📝 Points essentiels

• Le cours donne un exemple de TDA PILE avec une déclaration dans pile.h.
• Le modèle de structure inclut size, base et top dans le typedef struct.
• Les opérations déclarées incluent init_pile, push, pop et del_pile.
• Le fichier pile.c définit les corps des fonctions correspondant à l’interface.
• L’interface sert de séparation entre l’utilisateur et l’implémentation.

💡 Astuce mémo

pile.h = “ce que je peux faire”, pile.c = “comment c’est fait”.

📖 9. Utilisation d’un TDA indépendamment de l’implémentation

🔑 Notions clés & Définitions

• Indépendance d’implantation : L’indépendance d’implantation signifie que l’on utilise un TDA uniquement via ses opérations, sans dépendre de la représentation interne.
• En-têtes de fonctions : Les en-têtes de fonctions sont les déclarations qui constituent le contrat entre l’utilisateur et le TDA.
• Manipulation par opérations : Manipuler un TDA consiste à appeler uniquement les opérations associées, plutôt que d’accéder directement aux champs internes.

📝 Points essentiels

• L’utilisation d’un TDA se fait exclusivement via les opérations associées.
• Les en-têtes des fonctions/procédures constituent l’interface entre l’utilisateur et le TDA.
• On peut manipuler le TDA sans connaître son implémentation interne.
• Le code utilisateur reste valable même si l’implantation change.
• Le cours illustre l’idée avec un programme d’essai utilisant init_pile, push, pop et del_pile.

💡 Astuce mémo

Tu appelles push/pop : tu ne touches pas aux champs internes.

📖 10. Structures de données et allocation dynamique

🔑 Notions clés & Définitions

• Structure de données : Une structure de données est une organisation mémoire permettant de stocker et manipuler des données efficacement.
• Allocation dynamique : L’allocation dynamique consiste à obtenir et libérer de la mémoire au moment de l’exécution via des pointeurs.
• Allocation statique : L’allocation statique fixe la taille maximale dès le départ et réserve un espace contigu en mémoire.
• Fragmentation : La fragmentation correspond au fait que l’espace libre peut être non contigu, ce qui gêne l’allocation contiguë.
• MC : MC désigne la mémoire centrale où l’on réserve et libère des blocs de mémoire.

📝 Points essentiels

• Les SD basées sur des tableaux contigus sont statiques et imposent une taille maximale dès le départ.
• L’allocation statique empêche d’utiliser un espace libre non contigu même s’il existe.
• Le cours mentionne une perte d’espace mémoire quand l’espace réservé est plus grand que nécessaire.
• La solution proposée pour éviter ces limites utilise des pointeurs et l’allocation dynamique.
• Les pointeurs permettent de ne pas dépendre de la position des cases libres en mémoire centrale.

💡 Astuce mémo

Statique = taille figée, Dynamique = mémoire au besoin (via pointeurs).

📊 Tableaux de synthèse

Algorithme vs programme

TD simple vs TD composé

⚠️ Pièges & confusions fréquents

1. Confondre TDA et TD : un TDA est une spécification d’opérations, tandis qu’un TD décrit des valeurs concrètes d’un domaine.
2. Croire que l’on manipule un TDA en accédant directement aux champs internes : le cours impose l’usage exclusif des opérations.
3. Penser que plusieurs implémentations sont impossibles : le cours indique qu’un même TDA peut avoir plusieurs implémentations.
4. Oublier que l’allocation statique impose une taille maximale et peut gaspiller de la mémoire.
5. Mélanger description fonctionnelle et axiomatique : la première donne les signatures, la seconde donne la sémantique via axiomes.

✅ Checklist Examen

1. Savoir définir un algorithme et un programme, et relier programme = traduction d’un algorithme.
2. Maîtriser la démarche de résolution : compréhension, formalisation en spécification, mise en œuvre de l’algorithme, traduction en langage.
3. Savoir caractériser un TDA : nom, opérations, description fonctionnelle (signatures), description axiomatique (sémantique).
4. Savoir interpréter des signatures d’opérations du type {} → Booléen et Elément x {} → {} (exemples estVide, appartient, ajouter, enlever, union).
5. Connaître la différence entre TD simple et TD composé, avec exemples (entier/booléen vs tableau/enregistrement).
6. Comprendre le schéma logique : interface abstraite côté utilisateur et plusieurs implémentations possibles côté réalisation.
7. Savoir décrire l’implémentation en C d’un TDA via une interface (pile.h) et des opérations (init_pile, push, pop, del_pile).
8. Savoir expliquer l’utilisation indépendante de l’implémentation : manipulation uniquement par opérations via en-têtes, sans dépendre des détails internes.
9. Savoir comparer SD statiques (tableaux contigus) et SD dynamiques (pointeurs) : taille maximale, fragmentation, gaspillage, et allocation/libération.