Discussion :

[Cladouros]

Bonjour à tous,

En révisant pour un examen, je suis tombé sur un exercice trouvé dans les annales qui me laisse vraiment perplexe. La première partie ne m'a pas posée de problème. En revanche, la seconde partie propose un algorithme alternatif que je n'arrive vraiment pas à comprendre. Voici l'énoncé et les réponses aux questions que j'ai déjà, en espérant que vous puissiez m'aider à le terminer.

La recherche de la kième plus petite valeur d'un tableau T est un problème classique en algorithmique. On dit que l'on cherche la valeur de rang k. Dans cette partie nous vous proposons d'étudier deux algorithmes qui permettent de résoudre le problème. Nous considérons un tableau T de n nombres. Les indices du tableau T vont de 0 à n-1 comme en langage C. Nous disposons de l'algorithme echange(a,b) qui échange le contenu des variables a et b.

Soit l'algorithme suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
entier partition(T : tableau, debut : entier, fin : entier) 
 
pivot, i, pivotNouveauIndice : entier
pivotNouveauIndice := fin 
 
si (debut=fin) 
<div style="margin-left:40px">retourner debut</div>
sinon
<div style="margin-left:40px">pivot := T[debut] i := debut+1 
 
// point d'observation 1 
 
tant_que (i ≠ pivotNouveauIndice) faire
<div style="margin-left:40px">si (T[i]>=pivot) alors
echange(T[pivotNouveauIndice], T[i])
pivotNouveauIndice := pivotNouveauIndice - 1 
 
sinon i := i+1 
fin_si 
 
// point d'observation 2</div>fin_tant_que 
 
si (T[pivotNouveauIndice]>pivot) alors
<div style="margin-left:40px">pivotNouveauIndice := pivotNouveauIndice - 1
echange(T[debut], T[pivotNouveauIndice]) 
sinon echange(T[debut],T[pivotNouveauIndice])</div>fin_si
 
// point d'observation 3
 
retourner pivotNouveauIndice</div>fin_si

Cet algorithme comporte en commentaire trois points d'observation, où l'on désire observer l'état des variables i, pivotNouveauIndice et du tableau T en entier.

Attention on suppose que cet algorithme est invoqué avec debut <= fin. Le cas debut > fin est donc impossible.

Question 1 (2 points) : faire fonctionner l'algorithme sur le tableau T = {707, 703, 706, 709, 710, 703, 710, 710, 711, 704} avec debut = 0 et fin = 9. Aux points d'observation que valent les variables i, pivotNouveauIndice et que contient le tableau T ?

Je ne vais pas détailler toute la démarche comme c'est demandé (car c'est assez long) mais plutôt vous donner le résultat au point d'observation 3 :

T = { 703, 703, 706, 704, 707, 710, 710, 711, 710, 709 }
i = 4
pivotNouveauIndice = 4

Question 2 (2 points) : prouver la terminaison de cet algorithme sachant que debut <= fin quand on l'invoque.

Soit i s'incrémente, soit pivotNouveauIndice se décremente à chaque passage dans la boucle, les deux valeurs finiront donc forcément par être égales sachant que début <= fin et que fin est pivotNouveauIndice.

Question 3 (1 point) : donner sa complexité en argumentant simplement.

O(n/2) = O(n)

Nous introduisons maintenant l'algorithme récursif

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
entier selection(T : tableau, debut : entier, fin : entier, ind_rang : entier)
 
entier pivotNouveauIndice, pivotIndice : entier
 
pivotNouveauIndice = partition(T, debut, fin)
 
// point d'observation 1
 
si (ind_rang = pivotNouveauIndice) retourner T[ind_rang]
sinon 
<div style="margin-left:40px">si (ind_rang < pivotNouveauIndice)
retourner selection(T, debut , pivotNouveauIndice-1, ind_rang) 
sinon
retourner selection(T, pivotNouveauIndice+1, fin , ind_rang)</div>

En revanche, nous introduisons le point d'observation 1 au sein de l'algorithme selection. Nous voulons y observer les contenus des variables debut, fin, rang, pivotNouveauIndice et le contenu du tableau T.

Attention : les tableaux sont indicés à partir de l'indice 0. Le paramètre ind_rang est l'indice du tableau dans lequel nous aurons la valeur telle que :

• Toutes les valeurs du tableau T comprises dans les indices {debut, debut+1, ... , ind_rang-1} seront strictement inférieures à la valeur T[ind_rang]
  
• Toutes les valeurs du tableau comprises dans les indices {ind_rang+1, ind_rang+1, ... , fin} seront supérieures ou égales à la valeur rangée dans T[ind_rang]

C'est à cet endroit que je bloque. Je ne comprends pas l'intérêt de cet algorithme puisqu'il fait appel à la fonction décrite précédemment avant de se rappeler lui même. Pouvez-vous m'aider à répondre à ces deux dernières questions ?

Question 4 (1,5 points) : Soit T = {7, 4, 11, 9, 10, 3, 3, 10, 12, 6}, debut = 0, fin = 9, ind_rang = 3, donner les valeurs des variables observées et le contenu du tableau au point d'observation 1 ainsi que la valeur retournée quand on invoque selection(T , 0, 9, 3).

Question 5 (1,5 points) : Considérons que la taille d'un tableau T est un nombre pair n. Donner la complexité de l'algorithme selection si on l'applique avec ind_rang = n/2 ET si le tableau T est déjà trié par ordre croissant mais qu'on ne le sait pas. Expliquer.

Si vous avez pris la peine de me lire jusqu'ici, sachez que je vous en remercie énormément !

[pseudocode]

C'est à cet endroit que je bloque. Je ne comprends pas l'intérêt de cet algorithme puisqu'il fait appel à la fonction décrite précédemment avant de se rappeler lui même.

L'intérêt c'est qu'on applique la fonction "partition()" sur une partie seulement des données, et pas sur toute l tableau. En fait, l'algorithme proposé ici est une variante du célèbre "quicksort".

L'idée c'est de dire que si on trie d'abord le tableau des données, alors on aura "k-1" valeurs avant la valeur de rang "k" (par définition ). Et comme le tableau sera trié, toutes ces valeur seront celles qui son inférieures a T[k].

En inversant le point de vue : si on peut séparer le tableau en 2 parties, à gauche celle qui sont inférieures à T[k] (et donc à droite celles qui sont supérieures), alors T[k] est la valeur de rang "k"