Tri par insertion

 Publié le November 24, 2023  |  4 minutes  |  827 mots  |  David Latreyte

Tri du joueur de cartes Le tri par insertion est un tri « naturel » souvent qualifié de « tri du joueur de carte ». Comment un joueur de carte trie-t-il ses cartes ? Au début, la main gauche du joueur est vide et ses cartes sont posées sur la table. Le joueur prend alors sur la table les cartes, une par une avec sa main droite, pour les placer dans sa main gauche. [Lire]
Tri  Invariant de boucle  Variant de boucle  Complexité 

Tri par sélection

 Publié le November 24, 2023  |  8 minutes  |  1610 mots  |  David Latreyte

La recherche d’un élément dans un tableau est beaucoup plus efficace si ce tableau est ordonné. À vrai dire, ce n’est pas en cours d’informatique que vous avez découvert ceci : dans toutes les bibliothèques les livres sont classés de façon à rendre leur recherche plus rapide ! Le tri des tableaux/listes permet de trouver rapidement les objets recherchés et facilite la recherche des valeurs extrêmes. La question que se propose d’aborder ce document est donc : « comment classer les éléments d’un tableau selon une relation d’ordre donnée ? [Lire]
Tri  Invariant de boucle  Variant de boucle  Complexité 

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 

Rappels d'algorithmique

 Publié le September 12, 2020  |  19 minutes  |  3957 mots  |  David Latreyte

Algorithmique Un algorithme est une suite finie et non ambiguë d’opérations ou d’instructions à réaliser afin de résoudre un problème. En informatique, pour qu’un algorithme puisse être implémenté, il est nécessaire de s’assurer que la « suite finie et non ambiguë d’opérations ou d’instructions à réaliser » s’effectue en une durée finie . Lorsqu’on élabore ou étudie un algorithme, il est donc nécessaire de vérifier : Sa finitude : Il doit se terminer en un temps fini. [Lire]
Algorithmique  Complexité  Terminaison  Invariant  Variant  Correction 

Recherche d'un élément dans un tableau : algorithmes itératifs et récursifs

 Publié le September 9, 2020  |  4 minutes  |  829 mots  |  David Latreyte

Recherche d’un élément dans un tableau La recherche d’éléments dans un tableau a déjà été évoquée en classe de première. Les deux algorithmes mis en œuvre à cette occasion, la recherche linéaire et la recherche dichotomique, utilisaient des boucles. L’objectif de cette séance est de rapidement revoir ces algorithmes et de mettre en œuvres des algorithmes récursifs de même complexité. Quatre algorithmes de recherche vont donc être implémentés : La recherche linéaire itérative ; La recherche linéaire récursive ; La recherche dichotomique itérative ; La recherche dichotomique récursive. [Lire]
Récursivité  Recherche linéaire  Recherche dichotomique  Complexité  Terminaison  Correction