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) :
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}.
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 :
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)
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 :
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))))
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.
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.
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.
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.
Combien de fois l’algorithme de tri par sélection fait-il appel à
l’algorithme MinR ?
Réponse :
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)
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
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).