---

 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)

1. Ecrire une fonction Scheme qui implémente cet algorithme.
2. Combien de fois le test de la ligne 6 sera-t-il exécuté ?
3. 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 ?
4. 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 :

1. Fonction Scheme :

   (define (minr A) (let ((imin 0)) (do ((i 1 (+ i 1))) ((>= i (vector-length A)) imin) (if (> (vector-ref A imin) (vector-ref A i)) (set! imin i)))))

2. Soit L la longueur du tableau A. Le test de la ligne 6 sera effectué L-1 fois.
3. 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.

4. 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 :

(define (minr A i) (let ((imin i)) (do ((j (+ i 1) (+ j 1))) ((>= j (vector-length A)) imin) (if (> (vector-ref A imin) (vector-ref A j)) (set! imin j)))))

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:

(define (tri-select! A) (do ((i 0 (+ i 1))) ((>= i (vector-length A)) A) (let ((j (minr A i))) (let ((tmp (vector-ref A j))) (vector-set! A j (vector-ref A i)) (vector-set! A i tmp)))))

Écrire maintenant le pseudocode de l’algorithme de tri par sélection.

 

Combien de fois l'algorithme de tri par sélection fait-il appel à l'algorithme MinR ?

Réponse :

1. Pseudo-code de la fonction qui détermine le plus petit élément du tableau A de longeur L entre les indices i et L-1 :

   1 Nom de l'algorithme : MinR 2 Entrée : A; un tableau indicé de 0 à L-1 3 i; un indice compris entre 0 et L-1 4 Sortie : l'indice de la plus petite valeur de A 5 entre i et L-1 6 imin <- i; 7 pour j allant de i+1 à L-1 faire 8 si A[imin] > A[j] alors 9 imin <- j 10 finsi 11 fait 12 retourner(imin)

2. Pseudo-code du tri par sélection :

   1 Nom de l'algorithme : Tri-select 2 Entrée : A; un tableau indicé de 0 à L-1 3 pour i allant de 0à L-1 4 j <- MinR(A, i) 5 tmp <- A[j] 6 A[j] <- A[i] 7 A[i] <- tmp 8 fait 9 retourner A

3. L'algorithme de tri par sélection fait appel L fois à la fonction MinR. L'algorithme de MinR traite à chaque appel un sous-tableau de longueur K variant entre L-1 et 1, soit en moyenne L−2/2, et, comme nous l'avons vu, effectue K−1/2 comparaison, soit L−3/4. L'algorithme de tri effectue donc en moyenne L × L−3/4 opérations élémentaires, il est en O(n²).

---

 3.

Une chaîne d'ADN peut être représentée comme une chaîne de caractères contenant uniquement les caractères A,T,G,C.

 

On peut aussi représenter une chaîne d'ADN par un nombre en considérant que chaque lettre représente un chiffre et que le nombre représentant la chaîne d'ADN est écrit en base 4. Par exemple en admettant que A représente le chiffre 0, T, le chiffre 1, G, le chiffre 2 et C le chiffre 3, la chaîne d'ADN ATG serait représentée par le nombre 6 = 0 * 16 + 1 * 4 + 2 * 1. Par quel nombre serait représentée la chaîne GTG? la chaîne TAA ?

Réponse :

GTG → 2 × 16 + 1 × 4 + 2 × 1 = 38

TAA → 1 × 16 + 0 × 4 + 0 × 1 = 16

 

Si une chaîne d'ADN a une longueur de 2 nucléotides (deux lettres), quelle est la chaîne représentée par le nombre 15 ? par le nombre 0 ?

Réponse :

15 = 3 × 4 + 3 × 1 = CC

00 = 0 × 4 + 0 × 1 = AA

 

Quelle est le plus grand nombre qui représente une chaîne d'ADN de longueur 10 ? Quelle chaîne représente-t-il ? Le nombre représentant une chaîne d'ADN dépend de l'association que nous définissons entre les lettres A,T,G et C et les chiffre 0, 1, 2, 3. Si nous décidons d'associer T à 0, G à 1, C à 2 et A à 3, par quel nombre serait représentée la chaîne ATG ? la chaîne GTG ? Quelle serait la chaîne d'ADN représentée par le nombre 15 ?

Réponse :

Dans notre système à base 4, le « chiffre » qui a la plus grande valeur est C, qui vaut 4−1=3. Le plus grand nombre représenté par dix chiffres en base 4 sera constitué de dix « chiffres » C, et vaudra :

(4−1) × 4⁹ + (4−1) × 4⁸ + ... + (4−1) × 4² + (4−1) × 4¹ + (4−1) × 4⁰

soit en développant :

4¹⁰ − 4⁹ + 4⁹ − 4⁸ + 4⁸ − ... + 4³ − 4² + 4² − 4¹ + 4¹ −1

et grâce à ces combinaisons d'additions et de soustractions :

CCCCCCCCCC → 4¹⁰−1 = 1048575

 

Combien y a-t-il de façons d'associer les lettres A, T, G et C chacune avec un chiffre différent pris entre 0 et 3 ?

Réponse :

S'il y a 4 choix possibles pour A, il en reste 3 pour T, 2 pour G et 1 pour C : donc 4!=24 solutions possibles, qui sont appelées les permutations de l'ensemble { A,T,G,C } (cf. http://fr.wikipedia.org/wiki/Permutation).

 

Une chaîne de protéine est une chaîne d'acides aminés, elle peut être représentée comme une chaîne de caractères ne contenant que les caractères suivants:

A,C,D,E,F,G,H,I,K,L,M,N,P,Q,R,S,T,V,W,Y.

En effet il y a 20 acides aminés. On peut représenter une chaîne de protéine par un nombre en considérant que chacun des caractères pouvant apparaître dans une chaîne de protéine est associé à un nombre pris entre 0 et 19. Le calcul pour une protéine se fera donc en base 20.

On peut prendre comme correspondance entre acide aminé et chiffre la correspondance suivante par exemple:

A: 0; C: 1; D: 2; E: 3; F: 4; G: 5; H: 6; I: 7; K: 8; L: 9; M:10; N:11; P:12; Q:13; R:14; S:15; T:16; V:17; W:18; Y:19;

Dans ce cas quelle est la valeur du nombre représentant le tripeptide CAY ?

Réponse :

CAY → 1 × 20² + 0 × 20¹ + 19 × 20⁰

soit : 1 × 400 + 0 × 20 + 19 × 1 = 419

 

Quel est le plus grand nombre représentant un tripeptide (une protéine formée de trois acides aminés) ? Quel est le plus grand nombre représentant une protéine de 300 acides aminés ?

Réponse :

Le raisonnement est le même qu'à la question :

YYY → 20³−1 = 7999

YYYYYYYYYYYYYYYYYYYY → 20³⁰⁰−1

 

Soit la fonction Scheme:

(define (adn->number DNA-CHAINE) (let ((valeur 0)) (do ((i 0 (+ i 1))) ((>= i (string-length DNA-CHAINE))valeur) (set! valeur (+ (* valeur 4) (if (char=? (string-ref DNA-CHAINE i) #\T) 0 (if (char=? (string-ref DNA-CHAINE i) #\G) 1 (if (char=? (string-ref DNA-CHAINE i) #\C) 2 3))))))))

Cette fonction rend la valeur d’un nombre associé à une chaîne d’ADN.
Quelle correspondance a-t-on choisi entre les nucléotides (lettres) de
la chaîne d’ADN et les chiffres 0,1,2,3 ?

 Réponse :

T → 0

G → 1

C → 2

A → 3

 

Donner le pseudocode de l'algorithme décrit par la fonction adn->number.

Réponse :

1 Nom de l'algorithme : ADN->number 2 Entrée : A ; une séquence d'ADN représentée par une 3 chaîne de caractères 4 Résultat : la valeur numérique qui représente la séquence 5 valeur <- 0 6 L <- longueur de A 7 pour i allant de 0 à L-1 faire 8 si A[i] = T alors valeur <- 4*valeur + 0 9 sinon si A[i] = G alors valeur <- 4*valeur + 1 10 sinon si A[i] = C alors valeur <- 4*valeur + 2 11 sinon si A[i] = A alors valeur <- 4*valeur + 3 12 finsi 13 fait 14 retourner valeur

 

On peut se demander si deux chaînes sont identiques de la façon suivante: ont-elle la même longueur et dans ce cas sont-elles représentées par le même nombre ? Ecrire la fonction.

Réponse :

(define (adn=? seq1 seq2) (and (= (string-length seq1) (string-length seq1)) (= (adn->number seq1) (adn->number seq2))))

---

Ce document a été traduit de L^AT_EX par H^EV^EA