structures.md

% Quelle structure de données choisir
pour faire ses courses ? % Jill-Jênn Vie % 29 mars 2016

Un problème classique…

\

Un problème classique…

\

Un problème classique…

\

… et sa résolution

\

… et sa résolution

\

… et sa résolution

\

Complexité

J'ai $n$ éléments dans mon sac.

• \textcolor{green!50!black}{$O(1)$} : constant.
  Le meilleur des mondes.
• \textcolor{green!50!black}{$O(\log n)$} : de l'ordre du nombre de chiffres de $n$.
  La belle vie.
• $O(n)$ : heureux.
• $O(n \log n)$ : convenable.
• \alert{$O(n^2)$} : parfois proscrit.
• \alert{$O(2^n)$} : interdit. Par la loi.

Structures de données

Pile

File

Tas

Extraire le minimum en $O(\log n)$
Ajouter un élément en $O(\log n)$

Union-Find

Unir deux classes $\simeq O(1)$
Trouver le représentant d'une classe en $\simeq O(1)$

Graphes

Un problème d'optimisation

Une machine qui rend la monnaie :

• Rendre le moins de pièces possible ?
• Dans la limite du stock ?
• Rendre le plus de pièces rouges possible ?

D'autres types de problèmes algorithmiques

Problèmes exacts

• Comment sortir de ce labyrinthe ?

. . .

Recherche opérationnelle

• Comment parcourir un maximum de Paris en 15 heures ?

. . .

La vraie vie

• Comment résoudre le chômage ?