Le codage d'Huffman

 Publié le November 16, 2020  |  10 minutes  |  1977 mots  |  David Latreyte

Cette séance a pour objet l’étude d’une méthode de compression de données inventée par David Albert Huffman en 1952. Cette méthode permet de réduire la longueur du codage d’un alphabet et repose sur la création d’un arbre binaire. Différents types de codages On appelle alphabet l’ensemble des symboles (caractères) composant la donnée de départ à compresser. Dans la suite, nous utiliserons un alphabet composé seulement des 8 lettres A, B, C, D, E, F, G et H. [Lire]
Arbre binaire  Compression 

Arbres Binaires Recherche

 Publié le November 10, 2020  |  7 minutes  |  1436 mots  |  David Latreyte

Introduction Quelle structure de données permet : d’organiser les données selon un ordre donné (numérique, lexicographique, etc.) ; d’effectuer des recherches le plus efficacement possible ; d’accéder à, d’insérer ou de supprimer les données le plus efficacement possible. Tableaux Propriétés On peut ordonner des données dans un tableau mais l’algorithme de tri le plus rapide, pour un jeu de données aléatoires, est en $O(n \; \log n)$ ; On peut accéder à une donnée en $O(1)$ ; On peut rechercher une valeur efficacement en utilisant la dichotomie (si le tableau est trié ! [Lire]
Arbres  Arbres binaires  Arbres binaires de recherche 

Les arbres binaires

 Publié le November 5, 2020  |  21 minutes  |  4426 mots  |  David Latreyte

Arbres binaires Définition Un arbre binaire est une structure de données abstraite formée d’un ensemble de nœuds organisés hiérarchiquement selon la définition par récurrence suivante : Un arbre binaire est : soit un arbre vide, noté $E$, ne contenant aucun nœud ; soit un nœud, appelé racine, relié à exactement deux arbres binaires $g$ et $d$, respectivement appelés sous-arbres gauche et sous-arbre droit. On note $T(r,g,d)$ l’arbre non vide dont la racine $r$ (on peut aussi indiquer l’étiquette de cette racine). [Lire]
Arbres  Arbres binaires 

Structures de données abstraites arborescentes : les arbres

 Publié le November 5, 2020  |  5 minutes  |  876 mots  |  David Latreyte

La notion de listes chaînées est parfaite pour structurer un ensemble d’élements destinés à être énumérés séquentiellement. Elle permet aussi d’implémenter les structures de piles et de files. Elle n’est cependant pas adaptée aux accès spécifiques à des positions données dans la séquence, puisqu’il faut alors parcourir toutes les cellules depuis le début de la liste jusqu’à la position souhaitée (complexité en $O(N)$). Document de référence pour ce cours Structures arborescentes Lorsqu’on manipule une information présentant une certaine hiérarchie, il est commun de la représenter graphiquement : [Lire]
Arbres  Listes 

Les Files

 Publié le October 31, 2020  |  6 minutes  |  1164 mots  |  David Latreyte

Rappel : Type de Données Abstrait (TDA) Une structure de données ou type de données abstrait est un moyen d’organiser et de manipuler les données en mémoire. Un TDA est donc définit par : Son nom ; Sa spécification, c’est à dire la liste des manipulations/opérations que l’on peut ou pas effectuer. La spécification indique généralement la complexité de chacune des opérations prévues par le TDA. Un type de données abstrait ne dépend pas de la manière dont la structure de données est implémentée dans le langage de programmation utilisé. [Lire]
File  Pile  Liste chaînée  Liste  Tableau dynamique  Complexité 

Les Piles

 Publié le October 27, 2020  |  6 minutes  |  1260 mots  |  David Latreyte

Rappel : Type de Données Abstrait (TDA) Une structure de données ou type de données abstrait est un moyen d’organiser et de manipuler les données en mémoire. Un TDA est donc définit par : Son nom ; Sa spécification, c’est à dire la liste des manipulations/opérations que l’on peut ou pas effectuer. La spécification indique généralement la complexité de chacune des opérations prévues par le TDA. Un type de données abstrait ne dépend pas de la manière dont la structure de données est implémentée dans le langage de programmation utilisé. [Lire]
Pile  Liste  Liste chaînée  Complexité  Classe 

Listes Chaînées, présentation

... et implémentation à l'aide d'une classe

 Publié le October 14, 2020  |  13 minutes  |  2710 mots  |  David Latreyte

Tableaux Un tableau est une structure de données dans laquelle les éléments, tous de même type, occupent des positions contiguës en mémoire. Le nombre d’éléments qu’un tableau peut contenir est déterminé à la création d’un tableau. Type Python Type Opération Exemple Complexité N’existe pas Tableau Accès à un élément tab[i] $O(1)$ Modification d’un élément tab[i] = x $O(1)$ Effacement d’un élément retire(tab, i) $O(n)$ Insertion d’un élément insere(tab, x, i) $O(n)$ Recherche d’un élément est_dans(tab, x) $O(n)$ La structure de données appelée « liste » dans le langage Python est implémentée à l’aide de tableaux dynamiques. [Lire]
Tableau  Tableau dynamique  Liste  Liste chaînée  Complexité 

Structures de données fournies avec le langage Python

 Publié le October 13, 2020  |  8 minutes  |  1670 mots  |  David Latreyte

Python possède dans la bibliothèque standard un grand nombre de structures de données, programmées de manière efficace. Rappels : modules, fonctions Pour chaque module, on distingue : sa réalisation (ou implémentation) : c’est le code lui-même. son interface (API) : c’est l’énumération des fonctions définies dans le module qui sont utilisées depuis d’autres modules/programmes, les clients. L’interface doit présenter une documentation dans laquelle tout ce que doit savoir le client doit être indiqué. [Lire]
Dictionnaire  Liste  Tableau dynamique  Structures de données  Ensemble  Complexité  Tableau associatif 

Itérer sur les éléments d'un dictionnaire

 Publié le October 13, 2020  |  3 minutes  |  600 mots  |  David Latreyte

Au zoo de Beauval, il y a 5 éléphants d’Asie, 17 écureuils d’Asie, 2 pandas d’Asie, etc. On représente cet inventaire à l’aide d’un dictionnaire, de façon suivante : 1 2 3 4 5 6 7 zoo_Beauval={ 'éléphant': ('Asie', 5), 'écureuil': ('Asie', 17), 'panda': ('Asie', 2), 'hippopotame': ('Afrique', 7), 'girafe': ('Afrique', 4) } On représente de la même façon le zoo de La Flèche : 1 2 3 4 5 6 zoo_LaFleche = { 'ours': ('Europe', 4), 'tigre': ('Asie', 7), 'girafe': ('Afrique', 11), 'hippopotame': ('Afrique', 3) } On souhaite se doter d’une fonction plus_grand_nombre() qui prend un zoo en paramètre et qui renvoie le nom de l’animal le plus représenté dans ce zoo. [Lire]
Dictionnaire  Liste 

Tri par insertion

Chapitre 5,2

 Publié le October 7, 2020  |  10 minutes  |  2026 mots  |  David Latreyte

Objectifs Le tri par insertion a été étudié en classe de 1ère. Dans ce document, après un rappel du cours de 1ère, nous allons implémenter une version récursive de cet algorithme et ensuite utiliser la possibilité que les fonctions en Python ont d’accepter des fonctions comme paramètres, afin de rendre plus générale et utile cette fonction de tri. Tri du joueur de cartes Le tri par insertion est un tri « naturel » souvent qualifié de « tri du joueur de carte ». [Lire]
Tri  Récursivité  Fonction