Cours algorithme : Algorithme de Tri - Algorithmes GLOUTONS - Algorithmes Arbres

Objectifs du cours : 

- Comment concevoir des algorithmes efficaces ?
- Comment savoir que les algorithmes conçus sont corrects et efficaces ?
- Comprendre qu’il est peu probable qu’un algorithme efficace existe.

1)    Principe d’algorithmes efficaces

1.1    Diviser pour régner

Le principe consiste à résoudre un problème en résolvant deux ou plusieurs problèmes du même type, en simplifiant le problème premier par des sous-problèmes identiques, mais simplifiés.
Attention, ce n’est pas la même chose que la programmation structurée. Ici, c’est le programme qui divise le problème et non le programmeur.

Cette méthode donne souvent des algorithmes efficaces et élégants, mais il peut parfois y avoir des conflits.

1.2    Quelques exemples

1.2.1    Algorithme de Tri rapide

Dans un tableau, on choisit un élément pivot (dans la méthode de base, cela consiste à prendre la premier élément du tableau).

On divise le tableau en trois parties :

• Les éléments plus petits que le pivot,
• Les éléments égaux au pivot,
• Les éléments plus grands que le pivot.

On recommence cette méthode, récursivement pour les premières (inférieur au pivot) et troisièmes (supérieur au pivot) parties.

1.2.2    Algorithme de Tri par fusion

Méthode récursive consistant à diviser les éléments en deux parties (équilibrées), trier chaque partie, puis fusionner les parties élémentaires.

1.2.3    Algorithme Min-Max

L’algorithme Min-Max consiste à trouver le minimum et le maximum d’un tableau.
S’il n’y a que deux éléments dans le tableau, il suffit de les comparer.
Sinon, on divise le tableau en deux parties (identiques et paires… ce qui implique que le tableau est de longueur n avec n pair. Voir TD 1 pour n impair) et on recommence l’algorithme (récursif). Lorsqu’on a le maximum et le minimum de deux parties, on les compare.
Cette méthode fait approximativement 3n/2 comparaisons.

2)    Algorithmes gloutons

2.1    Principe

Les algorithmes gloutons sont ceux qui trouvent une solution parmi plusieurs possibles, comparables selon un critère global. A chaque fin d’étape de l’algorithme, on choisit l’étape suivante en fonction des informations locales. La méthode gloutonne ne trouve pas forcément la meilleure solution.

2.2    Exemples

2.2.1    Arbre recouvrant de poids minimum

Cet algorithme permet, dans un graphe ou les arêtes ont un poids, de trouver l’arbre qui relie tous les sommets avec une somme des poids minimale.

On peut considérer deux méthodes :

Algorithme très glouton non optimal : on commence avec un arbre d’un seul sommet et on choisit toujours l’arête de poids minimum pour rejoindre le sommet suivant.
Algorithme glouton et optimal : on commence avec n arbres (n correspondant au nombre de sommet du graphe) d’un seul sommet et on choisit toujours l’arête de poids minimum qui relie deux arbres.

2.2.2    Sac à dos continu

Le problème consiste à remplir un containeur avec une charge la plus grande possible étant donné plusieurs matériaux, chacun avec une valeur/kilo et une quantité disponible.
Il s’agit d’un algorithme glouton : il faut toujours chercher et choisir le matériau avec le meilleur rapport valeur/poids.

2.3    Cas où la méthode gloutonne n’est pas optimale

2.3.1    Exemples

On peut retenir trois exemples :

• Sac à dos discret : avec des objets que l’on ne peut découper.

• Coloration de graphe : on veut colorier les sommets d’un graphe avec le plus petit nombre couleurs possible sachant que deux sommets voisins (reliés par une arrête) doivent avoir des couleurs différentes.

• Commis voyageur : étant donnée une carte des distances entre des paires de villes, trouver le chemin le moins coûteux qui passe par chaque ville une seule fois (et retourne au point de départ).

2.3.2    Commentaires sur la non existence d’algorithmes efficaces (connus) pour ces trois exemples
Ces trois problèmes sont des variantes des problèmes NP-complets. Personne ne connaît des algorithmes garantis de trouver une solution optimale en temps raisonnable (borné par un polynôme), mais il n’est pas dit que ce soit impossible.

Donc, il est utile de considérer des algorithmes qui ont une garantie de trouver une solution proche de l’optimale. Un premier essai à un tel algorithme pourrait être un algorithme glouton simple. Un deuxième essai serait d’améliorer le résultat du premier par des modifications locales gloutonnes.

3)    Arbres

3.1    Arbres binaires de recherche

Les arbres binaires sont des structures utiles. Exemples :

• La structure représente la structure logique des données (arbre syntaxique, arbre généalogique)

• La structure est utilisée pour permettre les opérations nécessaires sur une structure abstraite (arbre binaire de recherche, additions, suppressions d’éléments plus efficacement qu’avec un tableau ou liste avec pointeurs).

3.1.1    Insertion, recherche, annulation dans un arbre binaire de recherche

3.1.1.1    La recherche dans un arbre binaire

On commence la recherche à la racine, on parcours à gauche ou à droite selon la comparaison avec la valeur à chaque nœud (échec si sous arbre vide).

3.1.1.2    Insertion d’une valeur dans un arbre binaire

Idem que pour la recherche, en remplaçant le sous-arbre vide par un nouveau sous arbre contenant la valeur à insérer.

3.1.1.3    Suppression dans un arbre binaire

La suppression est facile au niveau d’une feuille ou si le nœud n’a qu’un seul fils. S’il y a deux fils, on remplace par exemple le nœud supprimé par le sous arbre.

3.1.1.4    Remarque

Les traitements dans la hauteur de l’arbre ont toujours un nombre d’opération linéaire. Il s’agit de quelques manipulations de pointeurs

3.1.2    Les ordres de parcours

Il existe trois ordres de parcours (souvent utiles)  permettant de visiter tous les nœuds d’un arbre (binaire) :

• Ordre infixe : (par exemple, afficher les éléments d’un arbre binaire de recherche en ordre). On parcourt tous le sous arbre gauche (en parcourant les sous arbre du sous arbre dans le même ordre… récursivement), ensuite la racine, puis tout le sous arbre droit.

• Ordre préfixe : (utile pour calculer la profondeur de chaque nœud) on traite d’abord la racine, puis le sous arbre gauche et enfin le sous arbre droit.

• Ordre post-fixe : (pour calculer par exemple la valeur d’une expression à partir de son arbre syntaxique, ou pour calculer une hauteur) d’abord les deux sous-arbre (gauche et droit), et la racine pour finir.

3.2    Arbres équilibrés

Un arbre binaire de recherche peut avoir une hauteur près de son nombre de nœud (n), en revanche, la moyenne est O(log n). C’est cette hauteur qui détermine le temps des opérations de base.

Il existe un grand nombre possible d’arbres avec n nœuds, on en obtient un selon l’ordre des insertions.
L’idée, pour obtenir un arbre équilibré, consiste à faire un peu plus de travail (à chaque insertion) afin de garder une hauteur plus raisonnable (de préférence O(log n)).

3.2.1    Arbre AVL

Un arbre AVL est un arbre dont la différence entre les hauteurs des deux sous arbres est au maximum 1. Ce type d’arbre nécessite le stockage d’une petite information cachée à chaque nœud : la différence entre les deux hauteurs des sous-arbres (-1, 0, 1).
Dans ce type d’arbre, la suppression d’un élément devient donc un peu plus compliquée.

3.2.2    Arbres 2-3

Un arbre 2-3 est un arbre pour lequel chaque nœud a soit une valeur et un fils, soit deux valeurs et trois fils. L’ordre est : sous-arbre, valeur, sous-arbre [, valeur, sous-arbre].
Dans un tel arbre, toutes les feuilles sont à la même profondeur.

• Pour ajouter une valeur dans un nœud qui n’en contient qu’un : trivial.
• S’il y en a déjà deux : insérer le deuxième dans le nœud père et diviser ce nœud en deux (avec peut-être une réaction en chaîne vers la racine).

-------------------------------------------------------------------------------------------------------
Suivant :     Structures récursives et Programmation Dynamique