TD d’algorithmique numéro 1 Natacha Portier et Daniel Hirschkoff semaine du 25 au 29 septembre 2000

On s’intéresse à des ensembles d’entiers tous distincts rangés dans un tableau : L[1]...L[n]. Les algorithmes considérés dans ce TD effectuent des affectations et leur seul critère de décision (ou de bifurcation) est la comparaison de deux éléments (= et <). En aucun cas ils ne peuvent effectuer des opérations arithmétiques, comme l’addition et la multiplication.

Question 1.1 ⋆ maximum de n entiers ⋆

Écrire un algorithme (naïf!) qui calcule le maximum de n entiers. Quelle en est la complexité (en nombre de comparaisons effectuées, en nombre d’affectations effectuées, dans le pire des cas, le meilleur, en moyenne) ?

Indications pour le calcul des affectations en moyenne : Soit P_{n,k} le nombre de permutations σ de {1, ..., n} telles que sur la donnée L[1] = σ(1)...L[n] = σ(n) l’algorithme effectue k affectations. Donner une relation de récurrence pour P_{n,k}. Soit G_{n}(z) = ∑ P_{n,k}z^{k}. Montrer que G_{n}(z) = z(z + 1)...(z + n − 1). En déduire le résultat.

Question 1.2

L’algorithme ci-dessus est-il optimal pour la complexité en comparaisons dans le pire des cas ?

A partir de maintenant, on ne s’intéresse plus qu’à la complexité dans le pire des cas et en nombre de comparaisons des algorithmes considérés.

Question 2.1 ⋆ plus petit et plus grand ⋆

On s’intéresse maintenant au calcul (simultané) du maximum et du minimum de n entiers. Donner l’algorithme naïf et sa complexité.

Question 2.2

L’idée pour améliorer l’algorithme est de regrouper les éléments à comparer par paires, de manière à diminuer le nombre de comparaisons à effectuer. Décrire l’algorithme, en évaluer la complexité.

Question 2.3

Montrons l’optimalité de cet algorithme. Soit A un algorithme qui trouve le maximum et le minimum. Pour une donnée fixée, au cours du déroulement de l’algorithme, on appelle novice (N) un élément qui n’a jamais subi de comparaison, gagnant (G) un élément qui a été comparé au moins une fois et a toujours été supérieur aux éléments auquels il a été comparé, perdant (P) un élément qui a été comparé au moins une fois et a toujours été inférieur aux éléments auquels il a été comparé, et moyens (M) les autres. Le nombre de ces éléments est représenté par un quadruplet d’entiers (i, j, k, l) et on a bien sûr i + j + k + l = n. Donner la valeur de ce quadruplet au début et à la fin de l’algorithme, et en déduire un nombre minimal de tests à effectuer. On choisira bien sûr la donnée de manière à maximiser ce nombre. Conclure.