Algorithmique & complexité

Deuxième partie

Hafidi Imad [Link]@[Link]

1 Hafidi Imad-ENSA de Khouribga-Cours Algo GE
 Complexité & algorithme de trie

2 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Complexité d’un problème, d’un
algorithme
On fixe une mesure élémentaire:
nombre de comparaisons,
nombre d’affectations,
mémoire utilisée,
temps utilisé,
...
Cette mesure associe à un algorithme A et une entrée d une valeur
Complexite(A, d).
On cherche souvent à évaluer cette complexité en fonction d’un paramètre
naturel n = taille(d), représentatif des entrées.
Exemple:
A: l’algorithme itératif pour MAX précédent.
d: une liste donnée en entrée.
n = taille(d), le nombre d’éléments dans la liste.
Complexite(A, d), le nombre de comparaisons de A sur d.

3 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 On peut alors parler de la complexité (au pire cas)
d’un algorithme (on fait varier seulement les entrées)

d’un problème (on fait varier l’algorithme, et les entrées)

On arrive parfois à parler de la complexité exacte.

On doit souvent se limiter à une étude asymptotique, ou à
des bornes asymptotiques.

4 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Exemple d’étude exacte
Etude du problème MAX en nombre de comparaisons:
Le problème MAX admet une solution avec n − 1
comparaisons.

Cet algorithme est optimal en nombre de comparaisons.

5 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Notion de landau(pire de cas)
Notation de Landau:
f (n) = O(g(n)) si et seulement si il existe deux constantes
positives n ≥0 et B telles que

Ce qui signifie que f ne croît pas plus vite que g.

Exemple:
Le problème MAX admet une solution itérative en O(n)
affectations.

6 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Notion Landau
Notation de Landau (suite)
f (n) = Ω(g(n)) si et seulement si il existe deux constantes
positives n≥0 et B telles que

f (n)= (g(n)) si et seulement si il existe trois constantes

positives n ≥ 0,B et C telles que

Exemple:
Le problème MAX nécessite ( (n) comparaisons.
(à venir) Trier nécessite Ω(n log n) comparaisons.

7 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Trie
Trier est une opération naturelle.
Travailler sur des données triées est parfois plus efficace.
Exemple:
Rechercher un élément dans un tableau à n éléments : O(n)
(utiliser le principe de la fonction Dans précédente sur les
listes).
Rechercher un élément dans un tableau trié à n éléments:
O(log n) (par dichotomie).
Trier devient intéressant dès que le nombre de recherches est
en Ω(Complexite(tri)/n).

8 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Recherche dichotomie

Nombre de comparaisons
C(1) = 2,
C(n) 2 + C(n/2), pour n pair,
C(n) = 2 log n + 2, pour n puissance de 2.
C(n) = O(log n)
dans le cas général.

9 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Tri par insertion
Méthode souvent utilisée pour trier un jeu de cartes.
Etape préliminaire: savoir insérer un élément x dans une liste triée
e1.e2. · · · .en, avec ei ≤ ei+1.
Equations récursives:

Correction: par induction, si on suppose (a, L) triée, le résultat

est bien trié.

10 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Trie par insertion

Complexité I (n) de Insere en comparaisons : I (n) = O(n).

Complexité C(n) de Trie en comparaisons:
C(n) nI (n) = O(n2).
Le pire cas est atteint lorsqu’on trie une liste déjà triée, et mène à
(n2) comparaisons. La complexité du tri par insertion est donc
bien en (n2).

11 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Tri par fusion
Fusion:
Construire une liste triée qui contienne l’union des éléments de
deux listes triées.
Exemple: Fusion([Link], 2.4.9) = [Link].5.7.9
Equations récursives de Fusion(X,Y ):

Correction: par induction, si on suppose (a, L) et (b,M)

triées, le résultat est correct.

12 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Fusion

Complexité en nombre de comparaisons: O(longueur (a) +

longueur (b)).

13 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Tri Fusion
Une liste de 0 ou 1 élément est triée.
Toute autre liste L peut se découper en deux sous-listes L1 et
L2 de même taille (à 1 près).
Les sous-listes L1 et L2 sont triées récursivement,
puis fusionnées.

TriFusion(L) = Fusion(TriFusion(L1),TriFusion(L2)).

14 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Paradigme « diviser pour régner »
Complexité C(n) en nombre de comparaisons en O(Fusion)
+ 2C(n/2)), soit
C(n) = O(n + 2C(n/2)),
ce qui mène à
C(n) = O(n log n).
Note:
comment résoudre une telle récurrence: poser n = 2p et faire
le changement de variable C0(p) = C(2p).
C0(p) = O(2p + 2C0(p − 1)),
donc C0(p) = O(2pp).

15 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Tri fusion

Note: L1 et L2 sont en fait ici dans l’ordre inverse des éléments pairs et
impairs, par commodité.
Note: le tri fusion fait toujours de l’ordre de n log n comparaisons, et pas
seulement au pire cas.

16 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Insertions vs fusion

17 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Complexité du problème de tri
Tout algorithme de tri
qui fonctionne par comparaisons,
qui n’a pas d’autres informations sur les données,

effectue (n log n) comparaisons dans le pire des cas.

Autrement dit, la complexité du problème du tri (avec ces

hypothèses) est en (n log n).
Le tri par fusion est donc parmi les tris optimaux en O(n log
n).

18 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Piles & Files

19 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Structure données abstraite
On souhaite considérer une structure de données, que l’on
va appeler sac, permettant de stocker des Objets.
On veut pouvoir:
tester si un sac est vide?
ajouter un élément dans un sac.
retirer un élément d’un sac non vide.

20 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 de décrire un objet uniquement par ses fonctions de base.
de faire abstraction de la réalisation.
Un sac peut être implémenté par une liste, par un tableau, . . .
Modifier son implémentation ne modifie pas le reste du
programme.

21 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Piles & Files
Les piles et les files sont des sacs.
Une pile est un sac LIFO (Last-In First-Out)
lorsqu’on retire un élément, on récupère toujours le dernier
ajouté.
ajouter se dit empiler (push), retirer se dit dépiler (pop).
Une file est un sac FIFO (First-in First-Out)
on retire les éléments dans l’ordre de leur insertion.
ajouter se dit enfiler, retirer se dit d´efiler.

22 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Files
Elles sont présentes dès qu’on a besoin d’utiliser ou de
modéliser une file d’attente.
par exemple:
les impressions dans un système d’exploitation sont grées par
une file;
dans une simulation d’un guichet, on modélisera généralement
l’arrivée des clients par une file.

23 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Les piles
Les piles sont des objets informatiques omniprésents:
par exemple:
les annulations d’édition dans un traitement de texte sont
gérées par une pile;
reconnaître une expression bien parenthésée nécessite une pile;
les appels récursifs sont gérés par une pile de récursion;
évaluer une expression arithmétique nécessite une pile.

24 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Utiliser bibliothèques JAVA
Piles et files sont tellement utilisées qu’elles sont proposées
dans les classes JAVA standards.
Exemple: la classe Stack du package [Link] (qui correspond
à l’implémentation par tableaux dynamiques précédente)
pour les piles.
Des piles de quoi?

25 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Classes génériques
Les classes de la bibliothèque JAVA sont en fait génériques.
Stack est une classe générique qui prend une classe en
argument.
Exemple: Stack<String> désigne une pile de chaînes de
caractères.
Plus généralement, Stack<E> est une pile d’objets de la
classe E.

26 Hafidi Imad-ENSA de Khouribga-Cours Algo GE

 Bibliothèques JAVA Files
La classe LinkedList<C> (package [Link]) fait l’affaire.
Il s’agit en fait d’une double-ended queue.
On peut utiliser
les méthodes addFirst et addLast (put) pour ajouter un élément
au debut ou à la fin.
les méthodes removeFirst (get) et removeLast pour récupérer le
premier ou dernier élément.
Le tout en temps constant, par des listes doublement chaînées
Il existe d’autres classes de la bibliothèque standard avec des
noms plus séduisants (comme Queue), mais LinkedList<C> est
peut-être la plus pratique.

27 Hafidi Imad-ENSA de Khouribga-Cours Algo GE