[PDF] Notes dinformatique fondamentale (cours pour lÉcole dIngénieurs

View - Download Notes dinformatique fondamentale (cours pour lÉcole dIngénieurs

Previous PDF

Next PDF

Notes d'informatique fondamentale

Roberto M. Amadio

Universite de Paris

3 janvier 2022

2

Table des matieres

1 Langages rationnels5

1.1 Notation pour les langages formels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Automates nis deterministes (AFD) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3 Expressions rationnelles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4 Automates nis non-deterministes (AFN) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.5 Lemme d'iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Calculabilite19

2.1 Machines de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2Enumerations et MdT universelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.3 These de Church-Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.4 Langages indecidables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3 Calcul propositionnel33

3.1 Algebre initiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.2 Syntaxe et semantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.3Equivalence logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.4 Denissabilite et formes normales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.5 Compacite et consequence logique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4 Logique du premier ordre45

4.1 Syntaxe et semantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.2 Simplication de la structure d'une formule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4.3 Interpretations d'Herbrand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.4 Calculabilite et validite . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

5 Classes de complexite :PetNP65

5.1 Temps de calcul polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.2 Reductions polynomiales etNP-completude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.3 Classication de quelques problemes remarquables . . . . . . . . . . . . . . . . . . . . . . . . . 71

Bibliographie76

Index79

A Travaux pratiques81

A.1 Analyse lexicale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

A.2 Diagrammes de decision binaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

A.3 Specication et verication de programmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

A.4 Reduction aSAT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

3 4

Chapitre 1

Langages rationnels

La theorie des langages formels s'interesse notamment aux problemes suivants : | denir des outils (automates, grammaires,:::) qui permettent de decrire de facon synthetique et precise un langage formel, | classier les langages formels d'apres lastructuredes outils qui les denissent. | a partir d'une specication d'un langageL, construire de facon plus ou moins automa- tique un programme (un automate) quidecidesi un motwappartient aL, | developper des methodes pour montrer qu'un certain langage n'est pas dans une cer- taine classe. Dans ce chapitre, on se focalise en particulier sur une classe de langages formels dits ra- tionnels (ou reguliers ou reconnaissables) et on se limite a presenter des resultats elementaires qui remontent essentiellement aux annees 1960 [RS59]. Le lecteur interesse au developpement ulterieur du sujet peut consulter, par exemple, [Per90].

1.1 Notation pour les langages formels

Unalphabet est un ensemble ni et non-vide. On appellecaractereun element de . Si Xest un ensemble alorsXest l'ensemble des sequences nies d'elements deX: X =fx1:::xnjn0;xi2Xg:(1.1) En particulier, si est un alphabet alors on appellemotsles elements de et on denote avec la sequence vide. On associe avec chaque motw2salongueurjwj 2Nen denissant jj= 0 etjawj= 1 +jwjsia2 etw2. Siw1;w22alors on denote parw1w22 laconcatenationde mots. Souvent, on omet le symboleet on ecritw1w2. On remarque que l'operation de concatenation est associative et que le mot videest une identite gauche et droite. Unlangage formelLsur un alphabet est simplement un sous-ensemble de . L'operation de concatenation est etendue aux langages de la facon suivante : siL1;L2alors L

1L2=fw1w2jwi2Li;i= 1;2g:

La concatenation de langages est aussi une operation associative ayant le langagefgcomme identite gauche et droite. Comme pour les mots, souvent on omet le symboleet on ecrit L 1L2. 5

6Langages rationnels

L'iterationd'un langageLest denotee parLet denie par : L

0=fg; Ln+1=LLn; L=S

n2NLn: En particulier, on remarque que;=fg 6=;. On denit aussiL+commeL+=LL. La proposition suivante, connue comme lemme d'Arden [Ard61], montre que dans l'espace des langages on peut toujours trouver un point xe d'une transformation ane (droite). Proposition 1.1.1SoientAetBdeux langages sur un alphabet. L'equationX=AX[B a une plus petite solution (par rapport a l'inclusion de langages) qui s'exprime parX=AB. Id ee de la preuve. On verie aisement queABest une solution car :

A(AB)[B=A+B[A0B=AB :

SoitYune autre solution. On prouve par recurrence surn0 queAnBY. Pourn= 0, on a : A

0B=BAY[BY :

SupposonsAnBY. Alors :

A n+1B=A(AnB)AYAY[BY :

CommeAB=S

n0AnB, on peut conclure queABY.2

1.2 Automates nis deterministes (AFD)

On introduit une classe de programmes tres simples qu'on appelle automates nis deterministes.

Langages reconnaissables

Denition 1.2.1 (AFD)Un automate ni deterministe (AFD)Mest un vecteur(;Q;q0 F;)ouest un alphabet,Qest un ensemble ni qui represente l'ensemble des etats de l'automate,q02Qest l'etat initial,FQest l'ensemble des etats naux (ou accepteurs), et : Q!Qest la fonction de transition. Un AFD se represente graphiquement comme un graphe dirige tel que : (i) les noeuds correspondent aux etats, (ii) il y a une ar^ete etiquetee paradeqaq0si et seulement si (a;q) =q0, (iii) le noeud qui correspond a l'etat initial est marque par>et (iv) les noeuds qui correspondent aux etats naux ont un double contour.

Dans la suite, on procede en trois etapes :

1. On denit la notion decongurationd'un automate.

2. On decrit comment un automate peut se deplacer d'une conguration a une autre.

3. On specie quels mots sont acceptes par l'automate.

Une methodologie similaire est utilisee dans le chapitre 2 pour un type d'automate plus general qu'on appellemachine de Turing.

Langages rationnels7

Denition 1.2.2 (langage reconnu)SoitM= (;Q;q0;F;)un AFD. Une conguration est un couple(w;q)2Q. On denit une relation de reduction`Mpar(aw;q)`M (w;(a;q))et on suppose que`Mest la cl^oture re exive et transitive de`M. Le langage

L(M)reconnu (ou accepte) parMest deni par :

L(M) =fw2j(w;q0)`M(;q)etq2Fg:

On dit aussi que un langageLestreconnaissables'il y a un AFDMtel queL=L(M). Exemple 1.2.3 (de l'AFD au langage)SoitM= (fa;bg;f1;2g;1;f2g;)avec fonction de transitionspeciee par : a b 11 2 21 2
Il n'est pas dicile de montrer queL(M)est l'ensemble des mots qui terminent parb. Remarque 1.2.4Dans la denition de AFD, on insiste pour que pour chaque etatqet pour chaque caractereade l'alphabet il y ait exactementune ar^etesortante deqavec etiquettea. En pratique, on peut rel^acher cette condition et demander juste qu'il y aitau plus une ar^ete sortante deqavec etiquettea. Un tel automate peut ^etre transforme facilement en un AFD en introduisant un etat `puits'qset en etendant la fonction de transitionde facon telle que (a;qs) =qspour touta2et(a;q) =qschaque fois que(a;q)n'est pas deni.

Indice d'un langage et minimisation d'AFD

Tout langage induit une relation d'equivalence sur les mots. On va montrer que cette relation a un nombre ni de classes d'equivalence ssi le langage est reconnaissable et que dans ce cas il y a un AFD qui reconna^t le langage et qui a un nombre minimum d'etats. L'ensemble de ces resultats et connu comme theoreme de Myhill-Nerode [Ner58]. Denition 1.2.5 (equivalence de mots)SiLalors on denote parLla relation d'equivalence sur les mots dansdenie par : wLw0si8z2(wz2Lssiw0z2L):

On denote par

=Ll'ensemble quotient des classes d'equivalences induites parLet on dit queLest d'indice nisi l'ensemble quotient est ni. Proposition 1.2.6SiLest reconnu par un AFD avecnetats alors](=L)n. Id ee de la preuve.Par contradiction, supposonsw1;:::;wn+1mots tels quewi6Lwjsi i6=j. Comme on a moins d'etats que de mots il doit y avoir un etatqet deux motswi;wj (i6=j) tels que (q0;wi)`(q;) et (q0;wj)`(q;). Mais dans ce cas, pour tout motz,M acceptewizssiMacceptewjz, ce qui revient a dire quewiLwj. Contradiction.2 Proposition 1.2.7SiLest d'indice ninalors il y a un AFD avecnetats qui reconna^tL. Id ee de la preuve.On construit un AFD qui reconna^tL:

8Langages rationnels

| les etats sont les classes d'equivalenceL=L, | l'etat initial est []L, | les etats accepteurs sont les classes d'equivalence qui contiennent un mot dansL, | la fonction de transition est(a;[w]L) = [wa]L.2 Corollaire 1.2.8Pour tout langage reconnaissable il existe un AFD qui reconna^t le langage et qui a un nombre minimum d'etats. Id ee de la preuve.SoitLun langage reconnu par un AFD avecmetats. Par la proposi- tion 1.2.6,Ldoit ^etre d'indice ninetnmet par la proposition 1.2.7 il y a un AFD avec exactementnetats qui reconna^tL.2 En pratique, on dispose d'une description du langage par un AFD (ou par un autre formalisme qu'on peut traduire en AFD) et on construit un AFD minimum en calculant un quotient des etats. Proposition 1.2.9 (minimisation AFD)SoitM= (;Q;q0;F;)un AFD. Alors on peut construire un AFDM0= (;Q0;q00;F0;)qui reconna^t le m^eme langage et qui a un nombre minimum d'etats. Id ee de la preuve.On va supposer que tous les etats dansQsont accessibles depuis l'etat initialq0. A defaut, on peut les supprimer sans changer le langage reconnu par l'automate. Ensuite on denit une suite de relationsn,n0, sur les etats :

0=QQ ;

n+1=f(q;q0)j(q2Fssiq02F) et8a2 ((a;q)n(a;q0))g: Il est immediat de verier que : (i)nest un relation d'equivalence, (ii)nn+1et (iii)n converge en un nombre ni de pas a une relation. On peut maintenant construire l'automate minimumM0. Siq2Qest un etat on denote par [q]sa classe d'equivalence par rapport a la relationet on denit : Q

0=f[q]jq2Qg; q00= [q0]; 0(a;[q]) = [(a;q)]; F0=f[q]jq2Fg:

2 Exemple 1.2.10 (minimisation)SoitM= (fq0;q1;q2;q3;q4;q5g;f0;1g;q0;;fq2;q3;q4g) un AFD avec transitions :q

0q1q2q3q4q50q

1q0q4q4q4q5

1q

2q3q5q5q5q5

En calculant, on trouveq0q1etq2q3q4et on obtient ainsi un AFD avec3etats.

1.3 Expressions rationnelles

On introduit une classe de langages formels.

Langages rationnels9

Denition 1.3.1 (langages rationnels)L'ensemble des langages rationnels sur un alpha- betest le plus petit ensemble de langages qui contient les sous-ensembles nis de(les langages nis) et qui est stable par rapport aux operations d'union, concatenation et iteration. Les expressions rationnelles sont une notation pratique pour denoter les langages ration- nels. Denition 1.3.2 (expressions rationnelles)L'ensembleEdes expressions rationnels sur un alphabetest deni commeS n0Enou : E

0= [ f;g [ fg

E n+1=En[ f(+;;)j;2Eng [ f(;;)j;2Eng [ f(;)j2Eng: Il est entendu que;etsont deux symboles dierents qui ne font pas partie de l'alphabet . Siest une expression rationnelle on denit par [[]] le langage rationnel associe. Ce langage est deni de facon unique une fois qu'on a xe les interpretations (attendues!) pour les symboles [ f;;;+;;g. A savoir :

SymboleInterpretation

a2fag(ensemble singleton) ;;(ensemble vide) fg(ensemble contenant le mot vide) +union langages concatenation langages iteration langage Ce qu'on vient de decrire est lasyntaxe abstraitedes expressions rationnelles. En pratique, on utilise unesyntaxe concretedans laquelle le symbole + est inxe, le symboleest omis et le symboleest postxe :

Syntaxe abstraiteSyntaxe concrete

Par ailleurs, on supprime des parentheses en supposant quea priorite surqui a priorite sur + et queet + associent a gauche (par exemple). Avec ces conventions, on ecrira (a+b)cd pour (;(;(+;a;b);c);(;d)). Le resultat suivant est connu comme theoreme de Kleene et sa preuve est basee sur un certain nombre de constructions interessantes decrites dans cette section et la prochaine.quotesdbs_dbs1.pdfusesText_1

[PDF] informatique generale et internet

[PDF] informatique s1 smia pdf

[PDF] informe de auditoria de gestion ejemplo

[PDF] informe de auditoria de gestion ejemplos

[PDF] informe de investigacion ejemplo pdf

[PDF] informe de practica laboral

[PDF] informe final practica profesional

[PDF] informer d'un fait d'histoire 3as

[PDF] infos de rentrée automne 2017

[PDF] infoterre cadastre

[PDF] infoterre carrières

[PDF] infoterre carte géologique

[PDF] infraction brulage plastique

[PDF] infraction code de la route algerien pdf

[PDF] infraction debit de boisson