Mines Informatique MP 2001

Thème de l'épreuve Algorithme émondant un automate; étude d'algorithmes de calcul de xn; construction d'un comparateur 8-bits
Principaux outils utilisés automates finis, implémentation en Caml et en Pascal, portes logiques, logique propositionnelle

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                       

Rapport du jury

(télécharger le PDF)
     

Énoncé obtenu par reconnaissance optique des caractères


A 2001 -- INF -- MP

ÉCOLE NATIONALE DES PONTS ET CHAUSSÉES,
ÉCOLES NATIONALES SUPÉRIEURES DE L' AERONAUTIQUE ET DE L'ESPACE,
DES TECHNIQUES AVANCÉES, DES TÉLÉCOMMUNICATIONS,
DES MINES DE PARIS, DES MINES DE SAINT--ÊTOENNE, DES MINES DE NANCY,
DES TELECOMMUNICATIONS DE BRETAGNE,
ÉCOLE POLYTECHNIQUE
(Filière T.S.I.)

CONCOURS D'ADMISSION 2001

ÉPREUVE D'INFORMATIQUE
Filière MP
(Durée de l'épreuve: 3 heures)

Sujet mis àla disposition des concours Cycle International, ENSTIM et TPE-EIVP.

Les candidats et les candidates sont priés de mentionner de façon
apparente sur la première page de la copie :

_ « INFORMATIQUE - Filière MP >>

RECOMMANDATIONS AUX CANDIDATS ET CANDIDATES

. L'énoncé de cette épreuve, y compris cette page de garde, comporte 8 pages.

0 Si, au cours de l'épreuve, un candidat ou une candidate repère ce qui lui 
semble être une erreur
d'énoncê, il ou elle le signale sur sa copie et poursuit sa composition en 
expliquant les raisons
des initiatives qu'il ou elle a décidé de prendre.

. Tout résultat fourni dans l'énoncé peut être utilisé pour les questions 
ultérieures même s'il n'a
pas été démontré.

. Il ne faut pas hésiter à fOrmuler les commentaires qui semblent pertinents 
même lorsque
l'énoncé ne les demande pas explicitement. '

0 L'utilisation d'une calculatrice ou d'un ordinateur est interdite.

COMPOSITION DE L'ÉPREUVE

L'épreuve comprend trois problèmes indépendants :

o le problème de théorie des automates, n° 1 page 2, à résoudre en 1h15 min 
environ;
. le problème de complexité algorithmique, n° 2 page 5, à résoudre en 60 min 
environ;
0 le problème de logique des propositions n0 3 page 7, à résoudre en 45 min 
environ.
Attention ! Dans chacun des deux premiers problèmes, les candidats et les 
candidates sont invités à donner

le nom du langage de programmation, Pascal ou Caml, dans lequel les algorithmes 
seront écrits lorsque des
questions le demanderont. Seuls les programmes écrits dans le langage choisi 
seront corrigés.

page 1/8
Tournez la page S.V.P.

Épreuve d'Informatique

1 Problème sur les automates finis ---- 1 h 15 min environ

Rappels pour fixer les notations et la terminologie

Un alphabet A est un ensemble fini d'éléments appelés lettres. A* est 
l'ensemble des suites finies de
lettres de A, appelées mots. Un langage est une partie de A*.

Un automate A est un graphe orienté et étiqueté, décrit par une structure < 
Q,A,E,I,T > :

-- A est un alphabet;

-- Q est un ensemble fini, non vide et appelé ensemble des états ; ce sont les 
sommets du graphe;
-- E Ç_ Q >< A >< Q est appelé l'ensemble des transitions, ce sont les arcs du 
graphe;

--- I g Q est appelé ensemble des états initiaux de l'automate;

--- T <_; Q est appelé ensemble des états terminaux de l'automate.

Une transition (p,a,q) E E est un arc du graphe, d'étiquette a et allant de 
l'état p vers l'état q que l'on
pourra noter p --a--> q.

La représentation graphique d'un automate obéit aux conventions suivantes :

-- un état 6, est figuré par un cercle marqué en son centre par e ; si e E I, 
cela est figuré par une flèche
entrante sans origine; si 6 EUR T, cela est figuré par une flèche sortante sans 
but;

-- une transition (p,a,q) E E est figurée par une flèche allant de l'état p 
vers l'état q; cette flèche est
étiquetée parla lettre a.

Exemple: une telle représentation graphique est illustrée dans la question 3 
page ci--contre.

Un calcul de A est un chemin pg -----> p1 -----2-> pg & p,, dans le graphe: 
pour z' 6 [1,n] on
a p,--..1 -------> p,-- E E. On dit que pg est l'origine du calcul, p,, est son 
extrémité, et que le calcul traverse

les états pg,p1, . . . ,pn.

L'étiquette du calcul est le mot formé par la suite des étiquettes des arcs 
successifs du chemin. Un
calcul d'origine p, d'extrémité q etd'étiquette u-peut être noté p --Ï+ q. Il 
est dit réussi lorsque p est un
état initial et q est un état terminal. Un mot de U E A* est reconnu par A s'il 
existe un calcul réussi de A
qd'étiquette u. L(A), le langage reconnu par A, est l'ensemble des étiquettes 
des calculs réussis.

L' automate A est dit émondê si pour chaque état p de A, il existe un état 
initial i, un état terminal t et
deux mots u et 1) tels que i ------> p et p ------> t sont des calculs, 
c'est-à-dire que tout état est réellement utile

àla reconnaissance des mots de L(A).

Problème

Dans ce problème, on se donne un automate A = < Q,A,E,I,T >. Nous allons écrire 
un algorithme
permettant de l'émonder, c'est-à--dire de déterminer ses états inutiles.

1 --- Il faudra rédiger des algorithmes. Choisir le langage, Pascal ou Caml, 
dans lequel seront rédigés ces
algorithmes. Attention! Tous les algorithmes demandés dans ce problème devront 
être écrits dans le
langage choisi.

page 2/8

Épreuve commune 2001

Représentation informatique d'un automate. Soit NE et NL des constantes 
entières strictement positives. On
suppose que l'automate a NE états numérotés de 1 à NE. Pour i EUR [1,NE], on 
notera ei l'état numéro i. On
suppose que l'alphabet contient NL lettres numérotées de 1 à NL. Pour j EUR 
[1,NL], on notera 13-- la lettre
numéro j . On choisit de représenter l'automate ainsi: '

---- à un état e i et une lettre 1j , on associe un vecteur de NE booléens, 
noté TL_î, tel que pour tout
k EUR [1,NE], TLâ[k] est vrai si et seulement si (EURi,lj,EURk) E E; le vecteur 
TLî est une description
des transitions issues de e i et étiquetées par lj ; '

-- l'ensemble des transitions issues d'un état e i est représenté par le 
vecteur noté TRi des NL vecteurs
TLî pour 1 < j < NL ; c'est-à--dire TRi [j] = TLä pour tout j EUR [1,NL];

--- le graphe orienté et étiqueté de l'automate est représenté par le vecteur G 
des NE vecteurs TRi pour
1 { i < NE; c'est--à-dire G[i] : TRi pour tout i E [1,NE].

On remarque que l'on ne représente que les transitions et que l'on ne 
représente pas encore le caractère
initial ou terminal des états. Cela sera pris en compte plus tard dans le 
problème.

Important! Dans les calculs de complexité qui seront demandés, on admettra que 
les opérations
élémentaires du langage de programmation (opérations arithmétiques, 
comparaisons arithmétiques, accès
et modifications de la valeur d'une variable ou d'un élément de tableau, etc.) 
ont une complexité en O(l).

2 --- Dans le langage choisi, décrire comment représenter, en accord avec les 
éléments qui viennent d'être
donnés, le graphe orienté et étiqueté d'un automate.

3 -- Toujours dans le langage choisi et en supposant NE : 5 et NL : 2, utiliser 
la réponse à la question
précédente pour représenter l'automate suivant:

Émonder l'automate revient à déterminer ses états inutiles. Un état e est 
inutile s'il n'existe pas de
calcul dont l'origine est un état initial et dont l'extrémité est e ou bien 
s'il n'existe pas de calcul dont-
l'origine est e et dont l'extrémité est un état terminal.

Matrice d'accesibilité d'un automate. Pour déterminer les états inutiles, il 
faudra calculer la matrice
d'accessibilité de l'automate. Cette matrice est une matrice de booléens C, 
carrée de dimension NE, telle
que pour (i,j) EUR [1,NE] >< [LNB], C[i,j] vaut vrai si et seulement s'il 
existe un calcul d'origine ei et
d'extrémité e j.

4 -- Dans le langage choisi, décrire comment représenter la matrice 
d'accessibilité d'un automate.

page 3/8
Tournez la page S.V.P.

Épreuve d'Informatique

L'algorithme de Roy--Washaü. L'algorithme qui va être utilisé s'appelle 
algorithme de Roy--Warshall. Cet
algorithme commence par initialiser la matrice C : pour (i,j) EUR [1,NE] >< 
[LNB], C[i,j] est initialisé à vrai
si et seulement si i = 3° ou bien s'il existe une transition de e 1 vers ej 
dans l'automate. L'algorithme
transforme la matrice C initialisée, que l'on nommera C0, en NE étapes. Pour k 
6 [1,NE ], on note Ck la
matrice à l'issue de k-ième étape de transformation. L'idée de cet algorithme 
est que pour tous k 6 [O,NE ]
et (i,j) EUR [1,NE ] x [1,NE ], Ck[i,j] est vrai si et seulement si i = j ou 
bien s'il existe un calcul d'origine
ei, d'extrémité ej et tel qu'aucun état traversé par ce calcul à l'exception de 
l'origine et de l'extrémité n'a
un numéro strictement supérieur à k. On dit alors que la matrice Ck vérifie la 
propriété au rank k.

5 -- Dans le langage choisi, écrire un algorithme permettant d'initialiser la 
matrice d'accessibilité C à partir
de la représentation G de l'automate. '

6 -- Quelle est la complexité en temps de l'algorithme de la question 5 en 
fonction de NE et NL ?

7 -- Vérifier trivialement que Co vérifie la propriété au rang 0.

8 -- Vérifier trivialement que si CNE vérifie la propriété au rang NE alors CNE 
est la matrice d'accessibilité
du graphe.

9 -- Soit k EUR [O,NE -- 1], on suppose Ck vérifie la propriété au rang k et 
Ck+1 vérifie la propriété au rang k+1.
Soit (i,j) EUR [1,NE] >< [1,NE], démontrer que Ck+1[i,j] est vrai si et 
seulement si Ck[i,j] est vrai ou
bien si Ck[i,k+l] et Ck[k+l,j] sont vrais.

10 ---- Soit k EUR [O,NE -- 1], on suppose Ck vérifie la propriété au rang k et 
Ck+1 vérifie la propriété au rang k+1.
Soit (i,j ) EUR [1,NE] x [LNB], démontrer que:
a ---- Ck]i,k+l] est vrai si et seulement si Ck+1[i,k+l] est vrai ;
b -- Ck[k+l,j] est vrai si et seulement si Ck+l[k+l, j] est vrai.

11 -- Déduire et justifier à l'aide des questions 9 et 10 un algorithme 
permettant de transformer la matrice
Ck en Ck+1 pour tout k EUR [O,NE ---- 1].

12 -- Quelle est la complexité en temps de l'algorithme de la question 11 en 
fonction de NE et NL ?

13 -- Dans le langage de programmation choisi, écrire un algorithme prenant en 
argument la représentation G
de l'automate et produisant sa matrice C d'accessibilité.

14 ---- Quel est la complexité en temps de l'algorithme de la question 13 en 
fonction de NE et NL ?

On suppose que les états initiaux sont décrits par un vecteur I de NE booléens 
tel que pour tout
k EUR [1,NE], I[k] est vrai si et seulement si ek est un état initial. On 
suppose également que les états
terminaux sont décrits par un vecteur F de NE booléens tel que pour tout k EUR 
[LNB], F[k] est vrai si
et seulement si ek est un état terminal. On désire obtenir le vecteur U de NE 
booléens tel que pour tout
k 6 [1,NE], U[k] est vrai si et seulement si ek est un état inutile.

15 --- Dans le langage de programmation choisi, décrire comment représenter les 
vecteurs I, F et U.

16 -- Toujours dans le langage de programmation choisi, écrire un algorithme 
prenant en arguments la
représentation G de l'automate, les représentations des vecteurs I et F 
décrivant ses états initiaux et
terminaux et produisant la représentation du vecteur U de ses états inutiles.

17 -- Quel est la complexité en temps de l'algorithme de la question 16 en 
fonction de NE et NL ?

18 --- L'hypothèse a été faite en début de problème que les opérations 
élémentaires du langage de

programmation ont une complexité en O(l). Expliquer pourquoi cette hypothèse 
est réaliste pour le
langage de programmation choisi.

FIN DU PROBLÈME SUR LES AU TOMATES

page 4/8

Épreuve commune 2001

2 Problème de complexité a]gorithmique -- 60 min environ

Calcul efficace de a:"

Le problème du calcul efficace de a:" pour n entier positif devient crucial 
lorsque n est particulièrement
grand ou bien lorsque (1: est un type de données où le produit est 
algofithmiquement coûteux. C'est le cas si
a: est une matrice carrée de grande dimension ou bien si $ est un polynôme de 
degré élevé. Dans ces cas, le
temps d'exécution d'une multiplication n 'est plus négligeable et il peut être 
raisonnable de rechercher des
algorithmes où l'on cherche à minimiser le nombre de multiplications effectuées.

, Ce qui intéresse l'informaticien dans le calcul de ac" est le nombre de 
multiplications par 3: où par des
puissances déjà calculées de a:. Pour essayer de compter et de minimiser ce 
nombre de multiplications, on
peut se contenter d'étudier le cas où cr est un entier et n un entier 
strictement positif. C'est ainsi que la
question est abordée dans ce problème. '

Terminologie et notation. Sin > 0 est un entier:

-- on appelle représentation binaire minimale (en abrégé r.b.m.) de n, la 
représentation binaire de 71.
où l'on ne considère que les chiffres significatifs, c'est-à--dire que l'on 
élimine tous les éventuels
chiffres 0 figurant en tête (à gauche) de la représentation ;

---- on note À(n) le nombre de chiffres de la représentation binaire minimale 
de n ;
-- on note u(n) le nombre de chiffres égaux à 1 dans la représentation binaire 
minimale de n.

1 -- Il faudra rédiger des algorithmes. Choisir le langage, Pascal ou Caml, 
dans lequel seront rédigés ces
algorithmes. Attention! Tous les algorithmes demandés dans ce problème devront 
être écrits dans le

langage choisi.

La méthode élémentaire

2 --- L' al orithme le lus sim le our calculer a:" est basé sur les é uations 
suivantes:
g P P P q

931 a:
oek+1 æoe'° si k > 0

a --- Dans le langage choisi, écrire un algorithme récursif, nommé es, prenant 
en arguments un entier a:
et un entier n > 0 et calculant a:" en utilisant les équations ci-dessus.

b ---- Combien de multiplications sont--elles effectuées par l'algorithme es en 
fonction de son deuxième
argument n ?

La méthode de Legendre

3 -- L'algorithme de Legendre considère la représentation binaire minimale de 
l'exposant entier n > O.
L'algorithme pour calculer x" s'énonce ainsi:
-- on part de la valeur 1 ;

-- on parcourt la r.b.m. de n de gauche à droite ; pour chaque chiffre 
rencontré, on élève la valeur au
carré, puis si le chiffre est 1, on multiplie la valeur par x.

page 5/8
Tournez la page S.V.P.

Épreuve d'Informatique

a --- Démontrer que cet algorithme est correct. Attention ! Il est inutile de 
le programmer.

b -- Exprimer le nombre de multiplications qui sont effectuées par cet 
algorithme en fonction de À(n)
et u(n) où n est l'exposant?

La méthode dichotomique

4 '-- L' algorithme dichotomique pour calculer a:" est basé sur les équations 
suivantes:

131 :$

:D" = (æ2)k si [<: > 0
æ2k+1 = ææ2k si k > 0

On suppose que le langage de programmation choisi dispose d'une fonction pair 
dont l'argument est-
un entier et le résultat est un booléen qui est vrai si et seulement si 
l'argument est pair.

a -- Dans le langage choisi, écrire un algorithme récursif, nommé ed, prenant 
en arguments un entier w
et un entier n > 0 et calculant a:" en utilisant les équations ci-dessus.

b -- En examinant l'algorithme ed, écrire un algorithme récursif, nommé cd, 
prenant en argument un
entier n > 0 et calculant le nombre de multiplications effectuées pendant le 
calcul déed(oe,n) pour
un a: entier quelconque.

c --- Soit k > 0 un entier, exprimer À(2k) en fonction de À(k) et exprimer À(2k 
+ 1) en fonction de
À(2k). En'déduire et écrire un algorithme récursif, nommé lambda, prenant en 
argument un entier
n > 0 et calculant À(n).

d --- Soit le > 0 un entier, exprimer u(2k)' en fonction de 1/(k) et exprimer 
1/(2k + 1) en fonction de
u(2k). En déduire et écrire un algorithme récursif, nommé nu, prenant en 
argument un entier n > 0
et calculant u(n).

e -- Pour n > 0 entier, on pose 7r(n) = À(n) + u(n) ---- 2. En utilisant les 
résultats des deux questions
précédentes, déduire et écrire-,un algorithme récursif, nommé pz', prenant en 
argument un entier
n > 0 et calculant 7r(n). ' '

f -- Quel est le nombre de multiplications effectuées par l'algorithme ed en 
fonction de À(n) et u(n)
où n, entier strictement positif, est le deuxième argument?

g --- Quel est le nombre de multiplications effectuées par l'algorithme ed en 
fonction de son deuxième
argument n lorsque celui-ci est de la forme 2'° où k 2 0 est un entier naturel.

La méthode des facteurs

L'algorithme dichotomique réduit sensiblement le nombre de multiplications par 
rapport à l'algofitMe
le plus simple de la question 2 page précédente. Mais il n'est pas optimal. On 
a 7r(15) = 6 mais en

remarquant que 15 = 3 >< 5 et donc 51:15 = (æ3)5, on peut calculer 51:15 en 5 
multiplications : on calcule :c3

en 2 multiplications à l'aide de la méthode dichotomique puis on l'élève àla 
puissance 5 en 3 multiplications
toujours à l'aide de la méthode dichotomique. Cela donne:

OE2=OE£C OE3=£L'OE2 OE6=OE3OE3 OE12=OE6OE6 OE15=OE12OE3

Cette méthode, appelée méthode des facteurs, utilise le fait que sin = p q 
alors on a a:" = (:c")?

5 -- En remarquant que 33 = 3 >< 11, appliquer la méthode des facteurs 
esquissée ci--dessus et vérifier
qu'elle n'est pas optimale.

FIN DU PROBLÈME DE COMPLEXITÉ ALGORITHM1Q UE

page 6/8

Épreuve commune 2001

3 Problème de logique des propositions ---- 45 min environ

Afin de construire des circuits logiques, on se donne les trois portes logiques 
élémentaires correspondant
aux trois connecteurs suivants:

-- le connecteur unaire et préfixé de la négation noté --1 ;
-- le connecteur binaire et infixé de la conjonction noté A;
---- le connecteur binaire et infixé de la disjonction noté V.

On se donne également le noeud duplicateur produisant sur ses deux sorties la 
valeur fournie sur son unique
entrée. Ces éléments de circuits logiques sont représentés graphiquement ainsi:

a: m a:
a: --voe :::/\ oeV _oe_.<
----'< >"-- $
" y 31

Porte NON Porte ET Porte OU N oeud duplicateur

NB. Les circuits logiques construits en réponse à une question quelconque de ce 
problème devront être
construits en n'utilisant que les élements de circuits logiques donnés 
ci-dessus et ceux "construits en réponses
aux questions qui précédent cette question.

Si à: et y sont deux valeurs numériques, on note max(oe,y) la plus grande de 
ces deux valeurs et
min(æ,y) la plus petite de ces deux valeurs.

Soit n un entier strictement positif et a; un entier tel que 0 < a: < 2", on 
note M2 la
représentation en base 2 sur n bits de a: qui est définie comme suit: on prend 
la représentation en base 2
de a: qui est de longueur au plus n et on. la complète éventuellement avec des 
zéros à gauche pour que sa
longueur soit exactement n.

Un comparateur logique

1 ---- Construire un circuit logique Co prenant en entrées deux bits 
d'information a: et y et fournissant en
sorties les valeurs maæ(æ,y) et min(æ,y) :

2 -- Construire un circuit logique 01 prenant en entrées deux bits 
d'information a: et y et fournissant en
sorties les valeurs T1, T0, 31 et so telles que:

_ (T1,T'o) : (3,3!) et (31730) = (170) Si 27 > y;
" (T17T0) : (OE,y) et (31330) = (1,1) SÎ.OE : y;
- (mm) = (y'a?) et (81,80) = (0,1) Si 33 < y. '

page 7/8
Tournez la page S.V.P.

Épreuve d'Informatique

3 -- Construire un circuit logique Cg prenant en entrées quatre bits 
d'information 81 , eo, a: et y et fournissant
en sorties les valeurs n, m, 31 et 30 telles que:

On appelle C3 le circuit logique 02 dans lequel on a supprimé les sorties 31 et 
30-

On appelle comparateur 8--bits un circuit logique prenant en arguments deux 
entiers positifs ou

nuls et = (1,7 - - - a02 et b = b»; -- - - bo str1ctemegt mfer1eurs a 28 = 256 
et foum1ssant en sorties les deux
entiers positifs c : C7 - - - co? et d : d7 - - -- do tels que c : maæ(a,b) et 
d = min(a,b). Un tel circuit
logique peut être représenté graphiquement ainsi:

c : maæ(a,b)

a 1 Comparateur c 1
"° 8--bits °°
.b7 d7
bô d6
b5 d5
b d
b 4 4 d = min(a,b)

b3 d3
b2 d2
b1 dl
bo do

4 -- À l'aide des circuits logiques Cl, Cg et 03, construire un comparateur 
8-bits.

FIN DU PROBLÈME DE LOGIQUE DES PROPOSITIONS

FIN DE L'ÉPREUVE

page 8/8

Extrait du corrigé obtenu par reconnaissance optique des caractères



Mines Informatique MP 2001 -- Corrigé
Ce corrigé est proposé par Olivier Bertrand (ENS Lyon) ; il a été relu par 
Xavier
Goaoc (ENS Cachan) et Codrin Nichitiu (Maître de conférence).

L'épreuve se compose de trois problèmes indépendants.
Dans le premier problème, consacré aux automates finis, on écrit un algorithme
permettant d'émonder un automate, c'est-à-dire de déterminer ses états inutiles.
On utilise dans ce but l'algorithme de Roy-Warshall qui construit la matrice 
d'accessibilité d'un automate.
Dans le deuxième problème, consacré à l'algorithmique, on étudie différents 
algorithmes essayant de minimiser le nombre de multiplications dans le calcul 
de xn .
Dans le troisième problème, consacré à la logique propositionnelle, on construit
différents circuits logiques aboutissant à la conception d'un comparateur 
8-bits.

Indications
Partie I
I.2 Penser aux types array et boolean.
I.5 Parcourir entièrement le tableau G.
I.9 Supposer Ck+1 [i, j] vrai et Ck [i, j] faux. . .
I.11 Modifier le tableau Ck grâce à la propriété de la question I.9.
I.13 Utiliser la question I.11 pour k de 0 à NE - 1, ou de 1 à NE .
I.16 Utiliser la matrice d'accessibilité.
I.17 Ne pas oublier le temps pris par l'algorithme de Roy-Warshall.

Partie II
II.3.a Faire une récurrence forte sur n.
II.4.a Séparer les cas n pair et n impair.
II.4.f Trouver une formule de récurrence pour  à partir des deux récurrences 
précédentes, et remarquer que les fonctions cd et pi calculent les mêmes 
valeurs.

Partie III
III.1 Penser à  et .
III.2 Utiliser le circuit de la question III.1.
III.3 Faire un tableau de Karnaugh pour chacune des sorties.
III.4 Comparer deux nombres se fait de la façon suivante : on compare leurs 
premiers bits, s'ils diffèrent on sait quel est le plus grand des deux nombres.
Sinon on recommence sur leurs deuxièmes bits, et ainsi de suite.

I.

Problème sur les automates finis

I.1 Dans ce corrigé nous vous proposons systématiquement une version Caml et
une version Pascal de chaque programme. Le jour du concours, vous devez bien sûr
choisir un seul langage (et vous y tenir).
I.2 L'énoncé propose une structure de vecteurs emboîtés pour décrire le graphe
orienté et étiqueté d'un automate. Une telle structure s'implémente facilement 
sous
forme de tableau, que ce soit en Pascal ou en Caml. Dans ces deux langages, on 
utilise
une structure de tableau de NE tableaux de NL tableaux de NE booléens.
Version Caml
val G : bool array array array
Version Pascal
var G : array of array of array of boolean

Il ne serait pas judicieux d'utiliser des tableaux d'entiers avec 1 pour vrai
et 0 pour faux. En effet, ceci supprimerait quelques vérifications de types du
compilateur : un tel tableau pourrait contenir d'autres valeurs que 0 et 1, ce
qui n'a pas de sens. De plus, cela conduirait à un code plus lourd.

I.3 Dans les deux langages, on commence par initialiser un tableau à trois 
dimensions où toutes les cases possèdent la valeur faux. Il suffit alors 
d'instancier à vrai
chacune des cases G[i, j, k] telles que (ei , ek ) soit dans E et étiquetée par 
lj .
Version Caml
let g = init_vect 5
(fun _ -> init_vect 2 (fun _ -> make_vect 5 false));;
g.(0).(0).(1) <- true;
g.(1).(1).(2) <- true;
g.(2).(0).(0) <- true;
g.(2).(1).(4) <- true;
g.(2).(0).(3) <- true;
g.(4).(0).(3) <- true;;
init_vect a pour type int -> (int -> 'a) -> 'a vect.
init_vect n f renvoie le vecteur (de longueur n)
[|f 0 ; f 1 ; f 2 ; ... ; f (n-1)|]

Version Pascal
const ne = 5;
const nl = 2;
var g = array[1..ne, 1..nl, 1..ne] of boolean;
begin
for i := 1 to
for j := 1
for k =
g[i,
g[1, 1, 2] :=
g[2, 2, 3] :=
g[3, 1, 1] :=
g[3, 2, 5] :=
g[3, 1, 4] :=
g[5, 1, 4] :=
end;

ne do
to nl do
1 to ne do
j, k] := false;
true;
true;
true;
true;
true;
true;

Il ne faut pas oublier qu'en Caml la première case d'un tableau porte le
numéro 0. Croire que ce numéro est 1 (confusion fréquente) conduit à des
erreurs qui sont difficiles à déceler, donc à corriger.
I.4 La matrice d'accessibilité C d'un automate peut être implémentée, en Caml
comme en Pascal, par un tableau de NE tableaux de NE booléens. C[i, j] a la 
valeur
vrai si, et seulement si, il existe un calcul d'origine ei et d'extrémité ej .
I.5 L'idée est de construire une matrice carrée C de taille NE où tous les 
éléments
ont la valeur faux, et d'examiner ensuite chaque couple (i, j)  [[ 1 ; NE ]]2 
en fixant
C[i, j] à vrai si
i=j

ou

(k  [[ 1 ; NL ]] G[i, k, j] = vrai)

Version Caml
let init g =
let ne = vect_length g in
let nl = vect_length g.(0) in
let result =
init_vect ne (fun _ ->
init_vect ne (fun _ -> false)) in
for i=0 to ne-1 do
for j=0 to ne-1 do
if i=j
then result.(i).(j) <- true
else
for k=0 to nl-1 do
if g.(i).(k).(j) then result.(i).(j) <- true
done
done
done;
result;;