Corrigé de l'examen BNF103 - Algorithmes pour la biologie - juin 2021

Corrigé de l’examen BNF103 - Algorithmes pour la biologie - juin 2021

Article mis en ligne le 26 juin 2021

dernière modification le 17 juin 2022

par Laurent Bloch

Les problèmes 1 et 3 sont notés sur 8 points, le problème 2 sur 4 points. Il est recommandé de lire entièrement les énoncés des trois problèmes avant de commencer à répondre.

Problème N° 1

On s’intéresse à l’écriture des nombres conformes à la syntaxe de la calculette standard des systèmes Unix, bc, et on veut créer des expressions régulières qui vérifient la syntaxe de tels nombres. Par exemple, si j’écris -1.23^-5 cela dénote le nombre − 1, 23^− 5 (l’accent circonflexe est l’opérateur d’élévation à la puissance, et conformément à l’usage anglo-saxon c’est un point qui sépare la partie entière de la partie décimale du nombre).

On rappelle quelques points de la syntaxe des expressions régulières (x, y et z étant des symboles du texte ou des expressions régulières élémentaires) :

z? signifie que z doit exister en zéro ou un exemplaire à cet endroit du texte examiné ; (xyz)? signifie que xyz doit exister en zéro ou un exemplaire à cet endroit du texte examiné (cette règle des parenthèses s’applique de la même façon aux cas ci-dessous) ;
z* signifie que z doit exister en un nombre quelconque d’exemplaires à cet endroit du texte examiné, éventuellement zéro ;
z+ signifie que z doit exister en au moins un exemplaire à cet endroit du texte examiné ;
z|w signifie qu’à cet endroit du texte examiné il doit y avoir z ou bien w ;
l’accent circonflexe^, lorsqu’il apparaît en début d’expression régulière, dénote le début de ligne (ou de chaîne de caractères), $, lorsqu’il apparaît en fin d’expression régulière, la fin de ligne (ou de chaîne de caractères) ;
le point . dénote n’importe quel caractère ; l’expression régulière qui dénote le point est \.

Soit le fichier texte.txt, dont voici le contenu (attention, dans le texte et dans les expressions régulières entre guillemets, les espaces sont matérialisés par le caractère ) :

123
123.12
123,12
-123.12
1.23^4
-1.23^-5
.23^-6
4.^-7
4^-7
.^-7

Question 1

Quelles seront les lignes du fichier texte.txt imprimées par les commandes ci-dessous ?

egrep "^[0-9]+$" texte.txt
egrep "^[0-9]*(\.[0-9]*)?$" texte.txt
egrep "^([0-9]*)?(\.[0-9]*)?\^[0-9]+$" texte.txt
egrep "^([0-9]*)?(\.[0-9]*)?\^(+|-)?[0-9]+$" texte.txt

Réponse :

123

123
123.12

1.23^4

1.23^4
.23^-6
4.^-7
4^-7
.^-7

Question 2

Examinez les deux commandes ci-dessous :

egrep "^([0-9]*)?(.[0-9]*)?$" texte.txt
egrep "^([0-9]*)?(\.[0-9]*)?$" texte.txt

Quelle différence entre les résultats obtenus par chacune d’entre elles ?

Réponse :

Dans la première commande on a omis la barre oblique inverse devant le point, de ce fait tout caractère est accepté en cette position, en l’occurrence la virgule.

Question 3

Écrivez une expression régulière qui accepte toutes les ligne du fichier texte.txt sauf la ligne 3.

Réponse :

egrep "^(+|-)?([0-9]*)?(\.[0-9]*)?(\^(+|-)?[0-9]+)?$" texte.txt

Question 4

Comment pourrait-on éviter de valider la ligne 10 du fichier texte.txt, qui est acceptée par bc avec la valeur 0, mais qui peut ne pas correspondre à notre vision des nombres ?

Réponse :

Il faut soit des chiffres avant le point décimal, soit des chiffres après :

egrep \
"^(+|-)?((([0-9]+)(\.[0-9]*)?)|(([0-9]*)?(\.[0-9]+)))(\^(+|-)?[0-9]+)?$" \
texte.txt

Problème N° 2

L’expression régulière, réponse de l’exercice 1.3, est équivalente à l’automate fini dont voici le graphe (la notation "+,-,0-9" signifie que cette transition est choisie si le symbole lu dans le texte est soit "+", soit "-", soit un chiffre de 0 à 9) :

Question 1

Cet automate est-il déterministe (DFA) ou non-déterministe (NFA) ?

Réponse :

DFA

Question 2

Donnez la table de transitions de cet automate.

Réponse :

		+,-	0-9	.	ˆ
→	q₀	q₁	q₁	q₂
*	q₁		q₁	q₂
*	q₂		q₂		q₃
	q₃	q₄	q₄
*	q₄		q₄

Problème N° 3

Voici un algorithme qui permet de trier un vecteur. Les entités à trier seront des nombres entiers, contenus dans les cases d’un vecteur.

Le principe de ce tri est le suivant : on met en bonne position l’élément numéro 1, c’est-à-dire le plus petit. Puis en met en bonne position l’élément suivant. Et ainsi de suite jusqu’au dernier. Par exemple, si l’on part de :

On commence par rechercher, parmi les 12 valeurs, quel est le plus petit élément, et où il se trouve. On l’identifie en quatrième position (c’est le nombre 3), et on l’échange alors avec le premier élément (le nombre 45). Le tableau devient ainsi :

On recommence à chercher le plus petit élément, mais cette fois, seulement à partir du deuxième (puisque le premier est maintenant correct, on n’y touche plus). On le trouve en troisième position (c’est le nombre 12). On échange donc le deuxième avec le troisième :

On recommence à chercher le plus petit élément à partir du troisième (puisque les deux premiers sont maintenant bien placés), et on le place correctement, en l’échangeant, ce qui donnera in fine :

...

Question 1

On considère la fonction Scheme MinR telle qu’un appel à permet de trouver l’indice du plus petit élément de A entre i et longueur(A)-1.

Cette fonction, qui nous sera utile pour trier A, 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)))))

Elle implémente un algorithme que nous appelons MinR.

Ecrire le pseudocode de l’algorithme MinR.

Réponse :

Algo	: MinR
Données :  V un tableau indicé de 0 à L-1
           i un indice compris entre 0 et L-1
Résultat : l'indice de la plus petite valeur de V
           entre i et L-1
imin <- i
pour j allant de i+1 à L-1 faire
   si V[imin] > V[j] alors
      imin <- j
    finsi
 fait
retourner(imin)

Question 2

Nous allons pour écrire cet algorithme utiliser celui de la question précédente, minr, qui nous donne le plus petit élément du tableau A entre i et longueur(A)-1, ainsi que la procédure permute.scm qui effectue la permutation de deux éléments d’un tableau :

(define (permute v i j)
   (let ((temp (vector-ref v i)))
      (vector-set! v i (vector-ref v j))
      (vector-set! v j temp)))

Voici, en pseudo-code, l’algorithme de tri par sélection :

Algo : tri-select
Donnée :   vecteur V
Résultat : V trié
Soient 	   i <- 0
	   L <- longueur(V)
	   posmini <- 0
tant que i < longueur(V)
      ;; on calcule avec MinR l'indice posmini du plus
      ;; petit élément de V entre V[i] et V [L-1]
   posmini <- MinR(V, i)   
      ;; Il ne reste plus qu'à effectuer la permutation.
   permute(V, i, posmini)
      ;; On a placé correctement l'élément numéro i,
      ;; on passe à présent au suivant.
   i <- i+1
fait
retourner V
fin

Écrire, en Scheme, le programme de tri par sélection. On pourra utiliser la procédure donnée ci-dessus et la procédure vue au problème précédent.

Réponse :

(define (tri-select-vecteur V)
   (let ((i 0)
	 (L (vector-length V))
	 (posmini 0))
      (let loop ()
	 (if (<= i (- L 1))
	     (begin
		(set! posmini (MinR V i))
		(permute V i posmini)
		(set! i (+ i 1))
		(loop))))
      V))

Votre inscription a été enregistrée avec succès !

Sommaire

Problème N° 1

Question 1

Réponse :

Réponse :

Question 2

Réponse :

Réponse :

Question 3

Réponse :

Réponse :

Question 4

Réponse :

Réponse :

Problème N° 2

Question 1

Réponse :

Réponse :

Question 2

Réponse :

Réponse :

Problème N° 3

Question 1

Réponse :

Réponse :

Question 2

Réponse :

Réponse :

Au menu

Dans la même rubrique