TD d’algorithmique avancée

Ce document présente des exercices corrigés d’algorithmique avancée, destinés aux étudiants en informatique ou mathématiques. Il traite principalement des algorithmes de recherche du maximum, du deuxième plus grand élément, ainsi que de la recherche simultanée du maximum et du minimum dans un ensemble d’éléments, en analysant leur complexité et optimalité.

Recherche du maximum

On considère un ensemble A de n éléments, et on souhaite déterminer l’élément maximal en utilisant uniquement une fonction de comparaison.

Algorithme :

Maximum(A)
max ← A[1]
pour i ← 2 à n faire
  si max < A[i] alors max ← A[i]
renvoyer max

Complexité : Le nombre de comparaisons est n − 1.

Optimalité : Chaque élément sauf le maximum doit perdre au moins une comparaison pour garantir que ce n’est pas le maximum. Il y a donc au minimum n − 1 comparaisons nécessaires.

Recherche du deuxième plus grand élément

On suppose que l’ensemble ne contient pas de valeurs dupliquées.

Algorithme simple

Deuxieme-Plus-Grand(A)
rang_max ← 1
pour i ← 2 à n faire
  si A[rang_max] < A[i] alors rang_max ← i

si rang_max = 1 alors rang_second ← 2
sinon rang_second ← 1

pour i ← 2 à n faire
  si i ≠ rang_max et A[rang_second] < A[i] alors rang_second ← i

renvoyer A[rang_second]

Complexité : La recherche du maximum coûte n − 1 comparaisons, puis la recherche du deuxième plus grand coûte n − 2 comparaisons, soit un total de 2n − 3 comparaisons.

Algorithme sous forme de tournoi

Le processus est organisé comme un tournoi :

• Phase 1 : les éléments sont comparés par paires, chaque paire produit un vainqueur (plus grand) et un vaincu (plus petit).
• Phase 2 : les vainqueurs sont comparés entre eux par paires.
• On répète jusqu’à obtenir un seul vainqueur, le maximum.

Illustration :

Fig. 1 – Méthode du tournoi pour la détermination du maximum :

• A : comparaison par paires des éléments.
• B : comparaison des vainqueurs de la phase A.
• C : comparaison des vainqueurs de la phase B.
• D : un seul élément reste, le maximum.

Recherche du deuxième plus grand élément dans le tournoi

Le deuxième plus grand élément est nécessairement un des éléments battus par le maximum, et uniquement par lui.

Fig. 2 – Le deuxième plus grand élément a forcément été battu par le maximum. Ces éléments sont ceux comparés au maximum lors du tournoi.

Nouvel algorithme :

1. Rechercher le maximum via le tournoi.
2. Parmi les éléments battus par le maximum, rechercher le maximum (qui sera le deuxième plus grand élément).

Complexité :

La recherche du maximum coûte n − 1 comparaisons. Le nombre d’éléments battus par le maximum est m, au plus égal à la hauteur de l’arbre binaire presque parfait, soit log2 n. La recherche du deuxième plus grand coûte donc m − 1 comparaisons.

La complexité totale est :

T(n) = n + log2 n − 2

Ce nouvel algorithme est optimal.

Recherche simultanée du maximum et du minimum

On suppose toujours que l’ensemble ne contient pas de valeurs dupliquées.

Algorithme naïf

Maximum-et-Minimum(A)
max ← A[1]
pour i ← 2 à n faire
  si max < A[i] alors max ← A[i]

min ← A[1]
pour i ← 2 à n faire
  si min > A[i] alors min ← A[i]

renvoyer max et min

Complexité : 2n − 2 comparaisons.

Algorithme plus efficace

L’idée est de comparer les éléments par paires, puis de rechercher le minimum parmi les plus petits et le maximum parmi les plus grands.

Maximum-et-Minimum(A)
pour i ← 1 à n − 1 par pas de 2 faire
  si A[i] > A[i + 1] alors échanger A[i] et A[i + 1]

min ← A[1]
pour i ← 3 à n par pas de 2 faire
  si A[i] < min alors min ← A[i]

max ← A[2]
pour i ← 4 à n par pas de 2 faire
  si A[i] > max alors max ← A[i]

si n est impair alors
  si A[n] > max alors max ← A[n]

renvoyer max et min

Complexité :

• Phase de comparaison par paires : environ n/2 comparaisons.
• Recherche du minimum parmi n/2 éléments : n/2 − 1 comparaisons.
• Recherche du maximum parmi n/2 éléments : n/2 − 1 comparaisons.

Soit un total de :

T(n) = (n/2) + (n/2 − 1) + (n/2 − 1) = 3n/2 − 2 comparaisons

Optimalité de l’algorithme

On définit une unité d’information comme :

• « L’élément x ne peut pas être le maximum »
• « L’élément x ne peut pas être le minimum »

Pour garantir la validité du résultat, il faut produire au moins 2n − 2 unités d’information (n − 1 pour le maximum et n − 1 pour le minimum).

Analyse des unités d’information produites par une comparaison :

1. Si aucun des deux éléments comparés n’a d’information préalable, la comparaison produit 2 unités d’information (le plus petit ne peut pas être maximum, le plus grand ne peut pas être minimum).
2. Si les deux éléments ont la même unité d’information, la comparaison produit 1 unité d’information.
3. Si les deux éléments ont des unités d’information différentes, la comparaison peut produire 2 unités d’information ou 0 selon le cas.
4. Si un élément a une unité d’information et l’autre aucune, la comparaison produit 1 ou 2 unités d’information.
5. Si un élément a deux unités d’information et l’autre aucune, la comparaison produit 1 unité d’information.

Conclusion :

On a au plus n/2 comparaisons produisant 2 unités d’information, les autres comparaisons en produisent au pire 1. Pour atteindre 2n − 2 unités d’information, il faut au minimum :

T(n) ≥ n + ⌈n/2⌉ − 2 = 3n/2 − 2 comparaisons

L’algorithme présenté est donc optimal.

Glossaire des termes clés

• Algorithme de recherche du maximum : procédure pour trouver l’élément le plus grand dans un ensemble.
• Complexité : nombre de comparaisons effectuées par un algorithme.
• Algorithme de tournoi : méthode d’organisation des comparaisons en phases successives, comme dans un tournoi sportif.
• Deuxième plus grand élément : élément immédiatement inférieur au maximum dans un ensemble sans doublons.
• Unité d’information : information obtenue par une comparaison indiquant qu’un élément ne peut pas être maximum ou minimum.
• Optimalité : propriété d’un algorithme d’effectuer le nombre minimal de comparaisons nécessaire.
• Arbre binaire presque parfait : structure arborescente utilisée pour modéliser le tournoi, avec une hauteur proche de log2 n.

Points clés à retenir

• La recherche du maximum nécessite au minimum n − 1 comparaisons.
• Le deuxième plus grand élément peut être trouvé en n + log2 n − 2 comparaisons grâce à la méthode du tournoi.
• La recherche simultanée du maximum et du minimum peut être optimisée à 3n/2 − 2 comparaisons en comparant les éléments par paires.
• L’analyse des unités d’information permet de démontrer l’optimalité des algorithmes de recherche du maximum et minimum.
• Les algorithmes naïfs sont souvent moins efficaces que ceux exploitant des structures comme les tournois ou les comparaisons par paires.