IFT436 – Algorithmes et struct.
de données Devoir 5 Automne 2024
IFT436 – Algorithmes et structures de données
Université de Sherbrooke
Devoir 5
Enseignant: Michael Blondin
Date de remise: lundi 2 décembre 2024 à 23h59
À réaliser: en équipe de trois ou moins
Modalités: remettre en ligne sur Turnin dans un fichier PDF
Bonus: les questions bonus sont indiquées par ⋆
Pointage: max. 15 points + 1,5 points bonus
Le pivot idéal pour le tri rapide est la médiane. En théorie, on peut calculer la médiane d’une séquence en
temps linéaire, mais cela s’avère peu efficace en pratique. Une autre approche consiste à choisir un élément à
une distance raisonnable de la médiane, comme un élément compris entre le premier et troisième quartile.
Soit s une séquence de n éléments comparables distincts. Le rang d’un élément x ∈ s, dénoté rang(x), cor-
respond à la position de x dans s ordonnée en ordre croissant (en comptant à partir de 1). Nous disons qu’un
élément x ∈ s est raisonnable si
⌈n/4⌉ < rang(x) ≤ ⌊3n/4⌋.
Par exemple, considérons la séquence s = [50, 13, 20, 67, 41, 89, 70, 30]. Nous avons rang(13) = 1, rang(67) = 6
et rang(89) = 8. Les pivots raisonnables de s sont 30, 41, 50 et 67.
Afin d’identifier un pivot raisonnable, une approche probabiliste consiste à choisir k éléments aléatoirement
(de façon uniforme), puis de retourner la médiane de ces k éléments, où k ∈ N est un paramètre impair:
Entrées : séquence s de n ∈ N≥3 éléments comparables distincts
Résultat : un élément raisonnable x ∈ s
pseudomedk(s):
t ← []
faire k fois
choisir i ∈ [1..n] aléatoirement de façon uniforme
ajouter s[i] à t
trier t
retourner t[⌈k/2⌉]
Remarques:
— la constante k ne fait pas partie de l’entrée, il s’agit d’un paramètre fixe et toujours impair. Autrement dit, pseudomed1 ,
pseudomed3 , pseudomed5 , pseudomed7 , . . . sont tous des algorithmes différents;
— le choix d’un nombre aléatoire est ici une opération élémentaire qui s’effectue toujours en temps constant.
1
IFT436 – Algorithmes et struct. de données Devoir 5 Automne 2024
Question 1.
(a) L’algorithme pseudomedk est-il de Las Vegas ou de Monte Carlo? Justifiez. 2 pts
(b) Quelle est la probabilité que pseudomed3 retourne la médiane de s = [42, 9000, 0]? Justifiez. 4 pts
Indice: combien y a-t-il de séquences avec 2 éléments identiques, 3…
Pour les sous-questions suivantes, supposez que n est divisible par 4 (cela simplifie les calculs).
(c) Donnez la probabilité d’erreur de pseudomed1 et de pseudomed3 , puis généralisez en donnant une expres- 6 pts
sion symbolique qui décrit la probabilité d’erreur de pseudomedk . Justifiez.
Indice: considérez trois types d’éléments: raisonnables, déraisonnables de gauche et déraisonnables de droite;
oubliez les nombres, pensez à des chaînes formées avec les caractères {r, g, d}, puis au coefficient binomial.
(d) La procédure ci-dessous exécute pseudomed3 jusqu’à ce qu’un élément raisonnable soit identifié. Ainsi, sa 3 pts
valeur de retour est toujours correcte. Quel est son temps espéré sous notation O? Justifiez.
Entrées : séquence s de n ∈ N≥3 éléments comparables distincts
Résultat : un élément raisonnable x ∈ s
faire
x ← pseudomed3 (s)
tant que x n’est pas raisonnable // déterminé avec algo. déterministe en temps O(n)
retourner x
⋆ Montrez qu’il existe une valeur de k pour laquelle la probabilité d’erreur de pseudomedk est ≤ 1/2275 . ⋆ 1,5 pts
