Please enable JavaScript.
Coggle requires JavaScript to display documents.
Structures de données, Algorithmique - Coggle Diagram
Structures de données
Listes, piles, files: structures linéaires.Dictionnaires, index et clé.
-
-
-
-
-
Structures de données, interface et implémentation.
-
-
-
L’abstraction des structures de données est introduite après plusieurs implémentations d’une structure simple comme la file (avec un tableau ou avec deux piles).
Graphes: structures relationnelles.Sommets, arcs, arêtes, graphes orientés ou non orientés.
-
-
On s’appuie sur des exemples comme le réseau routier, le réseau électrique, internet, les réseaux sociaux.
Le choix de la représentation dépend du traitement qu’on veut mettre en place: on fait le lien avec la rubrique « algorithmique ».
Arbres: structures hiérarchiques.Arbres binaires: nœuds, racines, feuilles, sous-arbres gauches, sous-arbres droits.
-
Évaluer quelques mesures des arbres binaires (taille, encadrement de la hauteur, etc.).
-
Introduction
L’écriture sur des exemples simples de plusieurs implémentations d’une même structure de données permet de faire émerger les notions d’interface et d’implémentation, ou encore de structure de données abstraite. Le paradigme de la programmation objet peut être utilisé pour réaliser des implémentations effectives des structures de données, même si ce n’est pas la seule façon de procéder.
Le lien est établi avec la notion de modularité qui figure dans la rubrique « langages et programmation » en mettant en évidence l’intérêt d’utiliser des bibliothèques ou des API (Application Programming Interface).
Vocabulaire de la programmation objet: classes, attributs, méthodes, objets.
-
On n’aborde pas ici tous les aspects de la programmation objet comme le polymorphisme et l’héritage.
Algorithmique
-
Introduction
On continue l’étude de la notion de coût d’exécution, en temps ou en mémoireet on montre l’intérêt du passage d’un coût quadratique en 𝑛2 à 𝑛log2𝑛 ou de 𝑛 à log2𝑛. Le logarithme en base 2 est ici manipulé comme simple outil de comptage (taille en bits d’un nombre entier).
Le travail de compréhension et de conception d’algorithmes se poursuit en terminale notamment via l’introduction des structures d’arbres et de graphes montrant tout l’intérêt d’une approche récursive dans la résolution algorithmique de problèmes
-
-
-
-