Structures de données, types abstraits et complexité (Big O).
« Algorithms + Data Structures = Programs » (Niklaus Wirth). L'algorithmie est la partie du génie logiciel qui se concentre sur les étapes logiques pour atteindre le but. Deux regards : le mathématicien cherche un optimal absolu ; l'ingénieur cherche un optimal pratique — efficace, puis efficient.
| Structure de données | organisation de types primitifs par des relations et des opérations (concrète). |
| Enregistrement (record) | simple regroupement de types (ex. le tuple). Si la structure encapsule aussi les opérations → c'est un objet. |
| Type de données abstrait (TDA) | type défini par son comportement (sa sémantique), composé à partir de types primitifs (ou d'autres TDA), offrant une abstraction du matériel. (Inventé par Barbara Liskov, 1974.) |
| Liste | TDA qui restitue ses données dans l'ordre où elles ont été fournies (parcourable dans cet ordre, accès par indice). |
| Collection | TDA qui rend l'ensemble des données fournies — sans rien garantir (ni ordre, ni unicité). |
| Ensemble (set) | TDA qui rend les données uniques (sans doublons) ; aucun ordre garanti. |
| Ensemble ordonné | un set qui respecte en plus une relation d'ordre imposée. |
| Pile (stack) | TDA LIFO : dernier-arrivé, premier-sorti. |
| File (queue) | TDA FIFO : premier-arrivé, premier-sorti. |
| Tableau dynamique (vecteur) | structure qui implémente une liste via un tableau (ex. ArrayList). |
| Liste chaînée | structure qui implémente une liste par une valeur + un pointeur vers le suivant. |
| Dictionnaire | TDA qui accède à une valeur à partir d'une clé en O(1) (= table d'association). |
| Arbre binaire | TDA qui associe à toute valeur au plus deux fils directs. |
| Arbre binaire de recherche | arbre binaire ordonné : fils gauche < parent < fils droit. |
| Complexité algorithmique | estimation du degré de composition d'un algorithme (« complexe » = composé), en ordre de grandeur. |
| Complexité temporelle | nombre d'opérations CPU nécessaires. |
| Complexité spatiale | quantité de mémoire RAM nécessaire (totale, et auxiliaire). |
| Notation Big O | ordre de grandeur quand N → ∞. Ω = meilleur cas, θ = cas moyen, O = pire cas. |
| Fonction de hachage | f(valeur) → entier, qui maximise l'entropie, est prédictible, peu coûteuse et en O(1). |
| Entropie | grandeur qui caractérise le degré de désorganisation d'un système. |
Un TDA est défini par ce qu'il fait (son contrat), pas par comment il est réalisé. On peut donc raisonner sur les lois de l'abstraction sans considérer la machine — c'est l'émergence d'une pensée architecturale. Une même abstraction peut avoir plusieurs implémentations.
| Structure | Règle / sémantique | Implémentation typique |
|---|---|---|
| Liste | ordre d'insertion, accès par indice | tableau dynamique / liste chaînée |
| Ensemble (set) | données uniques, sans ordre | table de hachage |
| Ensemble ordonné | uniques + relation d'ordre | arbre binaire de recherche |
| Pile (LIFO) | dernier entré, premier sorti — ex. CTRL-Z, retour navigateur | tableau / liste chaînée |
| File (FIFO) | premier entré, premier sorti — ex. requêtes d'un serveur | liste chaînée |
| Dictionnaire | valeur via clé en O(1) | table de hachage |
| Arbre bin. de recherche | gauche < parent < droite | nœuds + pointeurs / tableau |
Dériver les tests d'un TDA (méthode du cours) : le cas nominal (insérer puis récupérer, vérifier l'ordre), les cas limites (structure vide, au-delà du dernier, indice négatif, doublons) et les cas dégénérés (indice invalide). Penser aussi à la mutabilité et à la taille.
On estime le coût quand le nombre d'éléments N devient grand, indépendamment du matériel (c'est une abstraction). Pour un même algorithme, on distingue le meilleur cas Ω, le cas moyen θ (qui dépend des données d'entrée) et le pire cas O.
| Classe | Nom | Exemple |
|---|---|---|
| O(1) | constante | accès par indice ; accès à un dictionnaire / set |
| O(log N) | logarithmique | recherche dichotomique ; arbre binaire de recherche équilibré |
| O(N) | linéaire | parcours / recherche dans une liste (une boucle for) |
| O(N²) | quadratique | deux boucles for imbriquées (recherche de doublons) |
| O(2ᴺ) | exponentielle | à éviter (mais négligeable si N reste petit) |
Spatiale : mêmes notations. On distingue la complexité totale et la complexité auxiliaire (l'espace supplémentaire utilisé). Ex. : sommer un tableau → spatiale O(N), auxiliaire O(1) ; créer une matrice N×M → O(N×M) pour les deux.
Le contrat d'un set est simple : savoir si une valeur existe, récupérer les données (ordre arbitraire), les retirer. Comme l'ordre n'est pas demandé, on en tire une garantie : on peut viser un accès en O(1).
On range chaque valeur à un indice prédictible via une fonction de hachage :
indice(valeur) = hachage(valeur) % taille(table)Comme les valeurs possibles sont infinies et les indices finis, des collisions sont inévitables et doivent être gérées. Un set ainsi implémenté est un HashSet ; dès lors, un dictionnaire (clé → valeur en O(1)) devient trivial à construire.
Vocabulaire : la première valeur est la racine, les nœuds sont reliés par des branches, les feuilles sont les nœuds sans fils ; deux arbres forment une forêt. Un arbre est un graphe orienté acyclique.
Implémentation : par des nœuds à deux pointeurs (gauche, droit), ou par un tableau (fils gauche à l'indice 2i+1, fils droit à 2i+2).
Très sensible à l'ordre d'insertion : des données déjà triées donnent un arbre dégénéré (filiforme), équivalent à une liste chaînée → recherche en O(N). On préfère donc insérer des données randomisées. Un arbre équilibré / complet est optimal (O(log N)). Les arbres AVL et rouge-noir rééquilibrent automatiquement (vu en algorithmie avancée).
| Nom | Pourquoi il est cité |
|---|---|
| Barbara Liskov | invente les types de données abstraits (1974) ; le principe de substitution de Liskov (le « L » de SOLID). |
| Donald Knuth | invente l'analyse de la complexité et la notation Big O dans The Art of Computer Programming (par « pollinisation » des maths). |
| Niklaus Wirth | « Algorithms + Data Structures = Programs » ; la pensée architecturale : raisonner sur les abstractions sans considérer la machine. |
À retenir : on décrit d'abord ce que fait une structure (le TDA, son contrat), puis on choisit comment l'implémenter — et la complexité Big O sert à comparer ces choix quand N grandit.
D'après le cours d'algorithmie (A. Roger, ENSICAEN). Fiche de révision personnelle.