Type abstrait

hiérarchique parmi ces nœuds. Un nœud, comme tout élément d'une liste, peut être de n'importe quel type. Structures de données (2012-2013) 8 4 ah-fsr-v2.0 Terminologie (1) (suite) D'une manière plus formelle, une structure d'arbre de type de base T est : soit la structure vide ; soit un noeud de type T, appelé racine, associé à un nombre fini de structures d'arbre disjointes du type de base T appelées sous arbres C'est une définition récursive ; la récursivité est une propriété

réponse ; branche gauche étiquetée par FAUX, branche droite par VRAI. Recherche : par arbres binaires de recherche. Files de priorité : par arbres-tournoi : gestion des tampons avec priorité. 12 de 1 Spécification formelle Définition (Type abstrait ABin) Opérations : Vide : {} → ABin Noeud : ABin × ABin → ABin EstVide : ABin → Booleen SAG, SAD : ABin → ABin Préconditions : SAD(t), SAG(t) défini seulement si non EstVide(t) Axiomes : EstVide(Vide()) = VRAI EstVide(Noeud(g, d)) =

par tas Tri par tas Codes préfixes Codage de Huffman Codage de Huffman adaptatif Amphi 7 1 Files de priorité Une file de priorité est un type abstrait de données opérant sur un ensemble ordonné, et muni des opérations suivantes : • trouver le maximum, • insérer un élément, • retirer le maximum. En inversant l'ordre, on obtient un type abstrait permettant de trouver le minimum et de le retirer. Amphi 7 2 Files de priorité Exemples d'utilisation : • Ordonnancement des tâches d'un système

données.) Le but de ce chapitre est de décrire des représentations des structures de données telles : les piles et les files. L’autre but recherché est de voir l’importance de ces structures à travers quelques exemples d’applications. En python, le type liste permet de représenter chacune de ces structures de données. 1. Pile Une pile est une structure de données qui suit le principe dernier entré - premier sorti (Ou LIFO pour Last In - First Out ). Elle correspond exactement à l’image traditionnelle

Définition 2.1. Un type abstrait est un triplet composé : d'un nom, d'un ensemble de valeurs, d'un ensemble d'opérations définies sur ces valeurs. Les types abstrait de bases de l'algorithmique sont : entier,caractères,booléen,réél que l'on écrit respectivement en EXALGO entier,car,booléen,réél Définition 2.2. Une variable est un triplet composé d'un type (déjà défini), d'un nom (a priori toute chaîne alphanumérique), d'une valeur. On écrit en EXALGO var NomDeVariable: Type; Type est à prendre

3 Structures de données (2010-2011) 4 ah-fsr-v2.0 ah-fsr-v2.0 Exemples de tables Table d'identificateurs dans un compilateur : Annuaire téléphonique : té Ensemble de couples (clé : nom ; informations : type, adresse mémoire, etc.) clé mé Type Abstrait Table Type Table Utilise Clé, Infos, Booléen Clé Boolé Opérations Opé table_vide est_vide insérer insé supprimer rechercher appartient Taille : : : : : : : Table Table Booléen Boolé Clé × Infos × Table Table Clé Clé × Table Table

peinture abstraite (1910), on peut citer d'autres précurseurs, d'origine russe, bien moins connus en France : le lithuanien Tchurlianis (Ciurlionis), qui a initié le mouvement abstrait vers 1906-19073, ou Nathalie Gontcharova, dont Guillaume Apollinaire montrait en 1914 les œuvres peintes de 1909 à 1911, les qualifiant de « rayonnisme4 ». Michel Seuphor donne une définition de l'art abstrait assez prudente5, citée dans l'introduction du chapitre « Origines du développement de l'art abstrait » de Michel

Approche Objet Notions manipulées dans le monde des objets Objets Encapsulation Classe Héritage Polymorphisme II-6 JMF Approche Objet Objet objet = données + opérations sur ces données (méthodes) = variables de "type abstrait" = entité du domaine du problème Un objet est composé de 2 parties : - partie interface: opérations qu'on peut faire dessus (partie publique) - partie interne (intime): données sensibles de l'objet (partie privée) Les utilisateurs (i.e. les éléments

en Java

Méthode et variables, constructeurs, contrôle d’accès

Extension de classe, méthode et héritage, variables et héritage, constructeurs et héritage

Classe Object, clonage, classes abstraites et interface, Classes internes et emboîtées

Classe Object, clonage, classes abstraites et interface, classes internes et emboîtées

Exceptions, assertions

Enumeration, tableaux, conversions, noms

Généralités, types génériques imbriqués, types paramètres bornés, méthodes génériques

statique d'un système. 2 Les classes  La classe est une description abstraite d’un ensemble d’objets  La classe peut être vue comme la factorisation des éléments communs à un ensemble d’objets  La classe décrit le domaine de définition d’un ensemble d’objets  Description conceptuellement séparée en deux parties  La spécification d’une classe qui décrit le domaine de définition et les propriétés des instances de cette classe (type de donnée)  La réalisation qui décrit comment la spécification est