IFT436 – Algorithmes et struct.

de données Devoir 5 Automne 2023

Annabelle 20
Fortin FORA
IFT436 – Algorithmes et structures de données AnthonyLopezGagnon Lora
210
Université de Sherbrooke

Devoir 5
Enseignant: Michael Blondin
Date de remise: mardi 5 décembre 2023 à 23h59
À réaliser: en équipe de deux ou individuellement
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.
13,2030,4150167170.89
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. 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 2023

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

2
C'estunalgorithmdeMonteCarlocar l'operation est faite un nombre fini
defois ar lieud'etre répétéjusqu'davoirle bon résultat

Il 13 résultats sur 27 possibilities done 1327 chances de returner

a
y
le bon résultat
 Pow une sequence de n values il y a Ya des valens

déraisonnable degauche et 44 des valens déraisonnable de

droite Il
y a done V2 Valens raisonnables

Ainsi puisque pseudomed prendonesale

variable et la retourne il y
a 501de chances d'errew 14yd'erreur
Poor pseudo
meds il a 64
piges possibles avec44 qui vetownent me
y
valour raisonnable comme nous powersvoiravec exemple suivant en considérant
one sequence de 4 valeurs Siune
pigemax Ivariable
déraisonnable de droiteet max 1

variablederaisonnabledegauchealors i'algorithme retournera une variable

raisonnable
14 4cierreur

s givraid

ggg [Link] rigg egg

[Link] regr dgr
[Link] [Link]
rigd dga
grig ring ring drag
grin river river drr
[Link] river river dr.r
grid rind rind and
gray ring ring drag
grer river river drer
gree river river drer

gigiigiigig
rdr rdr
gdr ddr
gdr rdr rdr ddr
geld reld redd dad
equivalent
degaucheusdroite
variable
d
chance avoirune
déraisonnablegauche
autre
les
guy 0déraisonnablemeter
1,11 de gauche

É Ya in 2
te
itai y
d
nombre optiondeivaleurs
d la
chance avoirune dans souspigedek
diraisonnablede
gauche