Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Corrigé de l’examen BNF103 de juin 2007
Article mis en ligne le 8 juillet 2007
dernière modification le 8 juillet 2013

par Laurent Bloch

Examen BNF103 2007 Exercices de tri et d'expressions régulières -- Éléments de corrigé

Examen BNF103 2007
Exercices de tri et d’expressions régulières – Éléments de corrigé

Laurent Bloch



Exercice 1

Soit le fichier exemple.txt, dont voici le contenu (attention, dans le texte, les espaces sont matérialisés par le caractère _) :

1 -_voici_les_paragraphes_du_texte_: 2 321ABM75_numéro_parisien 3 voici_un_numéro_:_321_ABM_75 4 321_abm_75_c'est_un_numéro_en_minuscules 5 321abm75 6 567_QWT_972 7 567qwt971 8 9 weekknights 10 weeknights 11 weenights 12 13 .TK_blabla 14 .AM_commentaire 15 .CD_et_là_? 16 .MA_ici

1.1  

Quel est le résultat imprimé par les commandes ci-dessous ?

1 egrep "(wee|week)(knights|night)" exemple.txt 2 egrep "[0-9]{2,4}[A-Z]{2,3}[0-9]{2,3}" exemple.txt 3 egrep "^\.[A-Z][A-Z] " exemple.txt

Réponse :

1 weekknights 2 weeknights 3 weenights
1 321ABM75 numéro parisien
1 .TK blabla 2 .AM commentaire 3 .CD et là ? 4 .MA ici

1.2  

Quelle commande faudrait-il taper pour que soient imprimées les lignes n° 2, 3 et 6 du texte, et uniquement elles ?

Réponse :

1 egrep "[0-9]{2,4} ?[A-Z]{2,3} ?[0-9]{2,3}" exemple.txt

Même question pour les lignes n° 5, 6 et 7 ?

1 egrep "^[0-9]{2,4} ?[a-zA-Z]{2,3} ?[0-9]{2,3}$" exemple.txt

Pour les lignes n° 13, 14 et 15 ?

1 egrep "^\.([A-K]|[T-Z])[A-Z] " exemple.txt


Exercice 2

2.3  

Dessiner le diagramme de transition de l’automate à états fini dont voici la table de transition (le symbole → indique l’état initial, le caractère * les états acceptants) :

   0  1 
    q0        {q0,q1}        {q0}    
 q1{q2}
*q2


Réponse


NFA simple
Figure 1: Un automate à états fini

2.4  

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

Réponse

Cet automate est non-déterministe (NFA) parce que sa fonction de transition δ, lorsqu’elle reçoit comme arguments l’état q0 et le symbole 0, rend comme résultat une partie de l’ensemble des états, {q0,q1}.

2.5  

Quelle est la définition du langage reconnu par cet automate ?

Réponse

Cet automate fini non déterministe accepte tous les mots terminés par la chaîne 01.



Exercice 3

3.6  

Dressez la table de transition de l’automate à états fini dont voici le diagramme de transition :


DFA simple
Figure 2: Un automate à états fini

Réponse

   0  1 
{q0} {q0,q1}{q0}
 {q0,q1}{q0,q1}{q0,q2}
*{q0,q2}{q0,q1}{q0}


Pour une meilleure compréhension, nous pouvons renommer ces ensembles, qui sont les états du DFA, de noms plus simples, en l’occurrence les lettres B, E, F. Il est de cette façon plus facile à voir que l’automate décrit par cette table de transitions est un DFA :

   0  1 
BEB
 EEF
*FEB


3.7  

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

Réponse

Il est déterministe (DFA) parce que pour chaque couple d’arguments {état, symbole} la fonction de transition donne comme résultat un seul état.

3.8  

Quelle est la définition du langage reconnu par cet automate ?

Réponse

Le langage reconnu par cet automate est le même que celui de la question précédente : l’ensemble des mots terminés par la chaîne 01.



Exercice 4

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 :
    1 (define (minR A) 2 (let ((LA (vector-length A))) 3 (do ((i 1 (+ i 1)) 4 (imin 0 5 (if (> (vector-ref A imin) 6 (vector-ref A i)) 7 i 8 imin))) 9 ((>= i LA) imin))))
  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.


Exercice 5

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.

5.9  

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 :

1 (define (minr A i) 2 (let ((imin i)) 3 (do ((j (+ i 1) (+ j 1))) 4 ((>= j (vector-length A)) imin) 5 (if (> (vector-ref A imin) 6 (vector-ref A j)) 7 (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.

5.10  

La fonction Scheme suivante réalise l’algorithme du tri par sélection:

1 (define (tri-select! A) 2 (do ((i 0 (+ i 1))) 3 ((>= i (vector-length A)) A) 4 (let ((j (minr A i))) 5 (let ((tmp (vector-ref A j))) 6 (vector-set! A j (vector-ref A i)) 7 (vector-set! A i tmp)))))

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

5.11  

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(n2).

Ce document a été traduit de LATEX par HEVEA