292 rue Saint-Martin – 75141 PARIS Cedex 03
–0–
Chaire de Bioinformatique
lundi 26 juin 2006 Heure : 18h15 – 20h15
TITRE DE L'ENSEIGNEMENT : Algorithmique de la Bioinformatique
(BNF103)
1.
Programme min
L'algorithme suivant permet de calculer l'indice de la valeur minimale d'un tableau.
1 Nom de l'algorithme : Min 2 Entrée : A; un tableau indice de 0 à longueur(A)-1 3 Sortie : l'indice de la plus petite valeur de A 4 imin <- 0; 5 pour i allant de 1 à longueur(A) -1 faire 6 si A[imin] > A[i] alors 7 imin <- i 8 finsi 9 fait 10 retourner(imin) |
- Ecrire une fonction Scheme qui implémente cet algorithme.
- Combien de fois le test de la ligne 6 sera-t-il exécuté ?
- Combien de fois l'affectation de la ligne 7 sera-t-elle exécutée dans le pire des cas, dans le meilleur des cas, en moyenne ?
- Quand la ligne 7 est exécutée que peut-on dire de la relation entre A[i] et les valeurs des cases précédentes du tableau ?
Réponse :
-
Fonction Scheme :
- Soit L la longueur du tableau A. Le test de la ligne 6 sera effectué L-1 fois.
- Si le tableau est trié en ordre décroissant, le nombre contenu
dans chaque case sera inférieur au nombre contenu dans la case
précédente, et ainsi l’affectation de la ligne 7 sera effectuée
L-1 fois (le pire des cas).
Si le tableau est trié en ordre croissant, l’élément de la case 0
sera le plus petit, et l’affectation de la ligne 7 ne sera
jamais effectuée (le meilleur des cas).En moyenne, l’affectation de la ligne 7 sera effectuée
integer(L−1/2) fois. - La ligne 7 est exécutée si A[i] est inférieur à A[imin], ce qui signifie que A[i] est inférieur aux valeurs de toutes les cases précédentes du tableau.
2.
Tri par sélection
Nous voulons définir un algorithme qui permette de trier un tableau A dont les indices vont de 0 à longueur(A)-1. Pour cela nous allons procéder par étapes. La première sera numérotée 0, la seconde 1, etc...
Au cours d'une étape donnée i nous considérerons que les éléments du tableau jusqu'à l'élément numéro i−1 sont triés et nous chercherons dans les éléments de numéro i, i+1, ... longueur(A)−1 le plus petit, nous échangerons alors cet élément avec l'élément de numéro i puis nous recommencerons.
On considère maintenant la fonction Scheme minr telle qu'un appel à (minr A i) permet de trouver l'indice du plus petit élément de A entre i et longueur(A)-1.
Cette fonction s'écrit :
Cette fonction implémente un algorithme que nous appelons
MinR. C’est une variante de l’algorithme Min de
la question 1. Ecrire le pseudocode de l’algorithme MinR.
La fonction Scheme suivante réalise l'algorithme du tri par sélection:
Écrire maintenant le pseudocode de l’algorithme de tri par sélection.