[PDF] Introduction `a la calculabilit´e

View - Download Introduction `a la calculabilit´e

Previous PDF

Next PDF

Introduction a la calculabilite

Pierre Wolper

Email: pw@monteore.ulg.ac.be

URL: http: //www.monteore.ulg.ac.be/~pw/

http: //www.monteore.ulg.ac.be/ ~pw/cours/calc.html

Reference

Pierre Wolper,Introduction a la calculabilite - 2ieme edition, Dunod, 2001. 1

Chapitre 1

Introduction

2

1.1 Motivation

Comprendre les limites de l'informatique.

Distinguer problemes solubles et insolubles par des algorithmes. Obtenir des resultats independants de la technologie employee pour construire les ordinateurs. 3

1.2 Problemes et Langages

Quels problemes sont solubles par un programme execute sur un ordinateur ?

Il faut preciser :

{la notion de probleme, {la notion de programme execute sur un ordinateur. 4

La notion de probleme

Probleme : questiongenerique.

Exemples :

trier un tableau de nombres ; determiner si un programme ecrit en C s'arr^ete quelles que soient les valeurs des donnees qui lui sont fournies (probleme de l'arr^et) ; determiner si une equation a coecients entiers a des solutions entieres (10ieme probleme de Hilbert). 5

La notion de programme

Procedure eective : programme pouvant ^etre execute sur un ordinateur.

Exemples :

Procedure eective : programme ecrit en JAVA ;

Procedure non eective : \pour resoudre le probleme de l'arr^et, il faut determiner si le programme n'a pas de boucles ou de sequences d'appels recursifs innies." 6

Probleme de l'arr^et

recursive functionthreen(n:integer):integer; begin if(n= 1)then1 elseifeven(n)thenthreen(n2) elsethreen(3n+ 1); end; 7

1.3 La formalisation des problemes

Comment represente-t-on les instances de problemes ? 8

Alphabets et mots

Alphabet : ensemble ni de symboles.

Exemples

f a;b;cg f ;; g f 1;2;3g f| ;};~g 9 Mot sur un alphabet : sequencenied'elements de cet alphabet.

Exemples

a, abs, zt, bbbssnbnzzyyyyddtrra, grosseguindaillesont des mots sur l'alphabetfa;:::;zg.

4|3}5~2;12765;|~sont des mots sur l'alphabet

f0;:::;8;|;};~;g.

Mot vide : designe pare,"ou encore.

Longueur du motw:jwj

w=aaabbaaaabb w(1) =a,w(2) =a,. . . ,w(11) =b 10

Representation des problemes

Encodage d'un probleme

Considerons un probleme binaire dont les instances sont encodees par des mots denis sur un alphabet . L'ensemble de tous les mots denis sur peut ^etre partitionne en 3 sous-ensembles : instances positives : reponseoui (positive instances) ; instances negatives : reponsenon (negative instances) ; mots ne representant pas des instances du probleme. 11

Ou encore :

les mots representant des instances du probleme pour lesquelles la reponse estoui,instances positives; les mots ne representant pas des instances du probleme ou representant des instances du probleme pour lesquelles la reponse est non,instances negatives. 12

Langages

Langage (language) : ensemble de mots denis sur le m^eme alphabet.

Exemples

f aab;aaaa;";a;b;abababababbbbbbbbbbbbg,f";aaaaaaa;a;bbbbbbget; (l'ensemble vide) : langages sur l'alphabetfa;bg. pour l'alphabetf0;1g, f0;1;00;01;10;11;000;001;010;011;100;

101;110;111;:::g: langage contenant tous les mots.

langage; 6= langagef"g. ensemble des mots representant les programmes C qui s'arr^etent toujours. 13

1.4 La description des langages

Operations sur les langages

Soit deux langagesL1etL2.

L1[L2=fwjw2L1ouw2L2g;

L1L2=fwjw=xy;x2L1ety2L2g;

L1=fwj9k0 etw1;:::;wk2L1tels quew=w1w2:::wkg;

L1=fwjw62L1g.

14

Langages reguliers

R(ensemble des langages reguliers sur un alphabet ) est le plus petit ensemble de langages tel que :

1.; 2 Retf"g 2 R,

2.fag 2 Rpour touta2 et

3. si A;B2 R, alorsA[B,ABetA2 R. 15

Les expressions regulieres

Notation pour representer les langages reguliers.

1.;,"et les elements de sont des expressions regulieres.

2. Si etsont des expressions regulieres, alors (), ([), ()sont des expressions regulieres. Les expressions regulieres constituent un langage sur l'alphabet

0= [ f);(;;;[;;"g.

16

Langage denote par une

expression reguliere

1.L(;) =;,L(") =f"g,

2.L(a) =fagpour touta2,

3.L(([)) =L()[L(),

4.L(()) =L()L(),

5.L(()) =L().

17

Theoreme

Un langage est regulier

si et seulement si il est denote par une expression reguliere. 18

Langages reguliers : exemples

L'ensemble de tous les mots sur =fa1;:::;angest denote par (a1[:::[an)(ou encore ). L'ensemble de tous les mots non vides sur =fa1;:::;angest denote par (a1[:::[an)(a1[:::[an)(ou encore , ou +). l'expression (a[b)a(a[b)denote le langage des mots composes de \a" et \b" qui contiennent au moins un \a". 19

Langages reguliers : exemples (suite)

(ab)[(ba)= (a[b)

Demonstration

(ab)[(ba)(a[b)car (a[b)denote l'ensemble de tous les mots composes des caracteres \a" et \b". considerons un mot arbitraire w=w1w2:::wn2(a[b):

On peut distinguer les 4 cas suivants...

20

1.w=anet doncw("a)(ba);

2.w=bnet doncw("b)(ab);

3.wcontient desaet desbet se termine parb

w=a:::ab|{z} ab:::b |{z} (ab)a:::ab|{z} ab:::b |{z} (ab) )w2(ab)[(ba);

4.wcontient desaet desbet se termine para)decomposition

similaire a celle du cas 3. 21

1.5 Les langages non reguliers

Fait Il n'y a pas assez d'expressions regulieres pour representer tous les langages !

Denition

Cardinalite d'un ensemble...

Exemple

Les ensemblesf0;1;2;3g,fa;b;c;dg,f|;};~;gont tous la m^eme taille. Ils peuvent ^etre mis en bijection, par exemplef(0;|);(1;});(2;~);(3;)g. 22

Les ensembles denombrables

Denition

Un ensemble inni estdenombrable(denumerable) si il existe une bijection entre cet ensemble et l'ensemble des nombres naturels.

Remarque

Au sens courant de \denombrable", tout ensemble ni est aussi denombrable. 23

Ensembles denombrables : exemples

1.

L'ensemble des nomb respairs est d enombrable:

f(0;0);(2;1);(4;2);(6;3);:::g: 2. L'ensemble des mots sur l'alphab etfa;bgest denombrable : f(";0);(a;1);(b;2);(aa;3);(ab;4);(ba;5); (bb;6);(aaa;7):::g. 3.

Les nomb resrationnels sont d enombrables:

(3=1;5);:::g. 4.

Les exp ressionsr egulieressont d enombrables.

24

La technique de la diagonale

Theoreme

L'ensemble des sous-ensembles d'un ensemble denombrable n'est pas denombrable.

Demonstrationa

0a1a2a3a4s

0 s 12 s 2 s 3 2 s

4 2...D=faijai62sig

25

Conclusion

L'ensemble des langages n'est pas denombrable.

L'ensemble des langages reguliers est denombrable. Il y a donc (beaucoup) plus de langages que de langages reguliers. 26

1.6 Un apercu de la suite...

Notion de procedure eective (automates).

Problemes non solubles algorithmiquement.

Problemes non solubles ecacement.

27

Chapitre 2

Les automates nis

28

2.1 Introduction

Automates nis : premiere modelisation de la notion de procedure eective.(Ont aussi d'autres applications). Derivation de la notion d'automate ni de celle de programme execute sur un ordinateur : etat, etat initial, fonction de transition. Hypothese du nombre d'etats ni. Consequence : sequences d'etats nies ou cycliques. Probleme de la representation des donnees : nombre de donnees dierentes limitees car nombre d'etats initiaux possibles ni. 29

Representation des donnees.

Probleme : reconna^tre un langage.

Donnees : mot.

On supposera le mot fourni caractere par caractere, la machine traitant un caractere a chaque cycle et s'arr^etant a la n du mot. 30

2.2 Description

Ruban d'entree.

Ensemble d'etats :

{etat initial, {etats accepteurs.

Mecanisme d'execution.

ruban : t^ete :ba a ab AAA 31

2.3 Formalisation

Un automate ni deterministe est deni par un quintuplet

M= (Q;;;s;F), ou

Qest un ensemble ni d'etats,

est un alphabet, :Q!Qest la fonction de transition, s2Qest l'etat initial,

FQest l'ensemble des etats accepteurs.

32

Denition du langage accepte

Conguration : (q;w)2Q.

quotesdbs_dbs45.pdfusesText_45

[PDF] épaisseur atmosphère saturne

[PDF] fonction primitive récursive exercice corrigé

[PDF] théorème de godel démonstration

[PDF] codage de godel

[PDF] théorème de gödel pdf

[PDF] arithmétique de robinson

[PDF] nombre de godel

[PDF] godel dieu

[PDF] théorème d'incomplétude pour les nuls

[PDF] incomplétude définition

[PDF] introduction ? la calculabilité pdf

[PDF] indemnité prof principal 2017

[PDF] isoe prof principal

[PDF] hsa prof

[PDF] indemnite tuteur stagiaire education nationale