1 Introduction à la Calculabilité Cours LFI2 (Master Académique) 2007/2008

1

Introduction à la Calculabilité

Cours LFI2 (Master Académique)

2007/2008

2

Plan

1- Introduction

2- Intérêt d’étudier la calculabilité

3- Notion de Problème

4- Notion de Programme (procédure de calcul)

5- Notion de Décidabilité

6- Notion de Calculabilité

7- Notion de dénombrabilité

8- Notion de codage

9- Formalisation des problèmes

10- Formalisation du calcul

3

Introduction

4

Chaque science a ses limites théoriques& pratiques

Mathématiques

Mécanique

Physique

….

Qu’en est-il pour l’Informatique?

L’informatique, est-elle limitée ?

Introduction

5

A la recherche des limites de l’informatique

Deux Questions principales se posent:

Introduction

Limites théoriques ? Limites pratiques ?

6

• Est-ce qu’il y a des problèmes qu’on ne peut pas résoudre par ordinateur ?

par ordinateur = par moyen algorithmique

indépendamment des ressources disponibles

limites absolues

Théorie de la calculabilité

Limites théoriques ?

Introduction

7

Limites pratiques ?

• Est-ce qu’il y a des problèmes qu’on ne peut pas

résoudre de façon efficace ?

en présence de ressources (temps, espace)

limites relatives

Théorie de la complexité

Introduction

8

En effet:

Il existe des problèmes qui n’ont pas une solution algorithmique

Il existe des problèmes qui n’ont pas de solution satisfaisante en terme d’efficacité

Introduction

9

Introduction

Limites théoriques ? Limites pratiques ?

Calculabilité Complexité

Limites

Dans ce cours on s’intéresse seulement à la théorie de la Calculabilité

10

Intérêt d’étudier la calculabilité

11

Intérêt d’étudier la calculabilité

Quand un informaticien tente de résoudre un problème et qu’il n’arrive pas à avoir un algorithme.

Que fait-il ?

Il corrige quelques détails

de l’algorithme,

Il ajoute de nouveaux cas

…..etc.

Il se dit:

« je vais y arriver ,

j’essaye encore»

Il cherche une autre méthode de résolution

Il se dit :

« j’ai mal démarré,

je recommence à zéro »

12

Intérêt d’étudier la calculabilité

Après avoir suivi ce cours:

Il se rendra peut être compte que le problème qu’il est censé résoudre n’a pas de solution algorithmique.

Il économise ses efforts dés le départ.

13

L’intérêt d’étudier la théorie de calculabilité

Comprendre les limites de l’informatique:

Ne pas essayer de résoudre un problème qu’on ne peut pas résoudre

Disposer des méthodes qui permettent de montrer que certains problèmes ne peuvent pas être résolus

Intérêt d’étudier la calculabilité

Obtenir des résultats indépendants de la technologie employée pour construire les ordinateurs.

14

Quels problèmes sont solubles par un programme exécuté sur un ordinateur ?

Il faut préciser :

– La notion de problème,

– La notion de programme exécuté sur un ordinateur.

Intérêt d’étudier la calculabilité

15

Notion de problème

16

• Problème est une question générique.

Notion de problème

Définition

(i.e. un problème contient des paramètres ou variables libres. Lorsqu’on attribue des valeurs à ces variables on obtient une instance du problème)

• Un problème existe indépendamment de toute solution ou de notion de programme pour le résoudre.

• Un problème peut avoir plusieurs solutions: Plusieurs algorithmes différents peuvent résoudre le même problème.

17

Des Exemples de Problèmes…

Notion de problème

18

Problème: Trier un tableau de nombres

- Méthodes de tri basé sur la recherche du min

(ou max) et des opérations de permutation

– C’est donc un problème « décidable »

Notion de problème

19

– Crible d’Eratosthène:• Construire la liste des nombres premiers jusqu’à N:

• Écrire tous les entiers jusqu’à N, éliminer tous les multiples de 2, puis parmi les nombres qui restent, tous les multiples de 3 etc.

– C’est donc un problème « décidable »

Problème: Déterminer si un nombre est premier

Notion de problème

20

• La réponse négative à cette question constitue le désormais célèbre « dernier théorème de Fermat »

• La question est restée ouverte jusqu’en 1996 (Andrew Wiles)

Problème: Déterminer si pour tout entier n>2,

il existe des entiers positifs a, b, c tels que:

an + bn = cn

Notion de problème

21

Problème: Conjecture de Goldbach

• Tout nombre pair supérieur à 0 peut s’écrire comme la somme de deux nombres premiersExemple: 4 = 2+2, 6=3+3, 8=5+3, 10=5+5, 12=5+7 100=97+3 … etc.

Notion de problème

• Non Décidable

22

Problème: Équations diophantiennes (10ème problème de Hilbert 1900)

• Déterminer si une équation de la forme P=0, où P est un polynôme à coefficients entiers, possède des solutions entièresExemples : x2 + y2 – 1 = 0,

x2 – 991y2 – 1 = 0etc…

Notion de problème

• Ce problème n’est pas « décidable »

Démontré en 1970 par Yuri Matijasevic

Il n’existe aucun algorithme qui indique, pour chaque équation diophantienne, si elle a ou non des solutions

23

Notion de problème

Problème: Les mots correspondants (1)

Etant donnés deux suites de mots, est-il possible de former un nouveau mot en concaténant une série de la première suite de façon telle que l’on retrouve le même mot en concaténant la même série de mots de la deuxième suite

Une instance du problème

1 2 3 4 5

abb a bab baba aba

bbab aa ab aa a

Groupe-1

Groupe-2

Oui il y a la série: 2 1 1 4 1 5

a abb abb baba abb aba = aabbabbbabaabbabaaa bbab bbab aa bbab a = aabbabbbabaabbaba

24

Notion de problème

Une autre instance du problème

1 2 3 4 5

bb a bab baba aba

bab aa ab aa a

Groupe-1

Groupe-2

Pas de Solution

En général le problème n’est pas soluble.

Problème: Les mots correspondants (2)

25

Problème: Déterminer si un programme P, pris au hasard, calcule une fonction donnée non nulle f(n) (n entier)

• C’est un problème « indécidable »

Il n’existe pas d’algorithme général tel qu’étant donné un programme P et une fonction f de N dans N, il soit capable de dire si P calcule effectivement f

Notion de problème

26

Problème: Déterminer si deux programmes calculent la même chose (sont équivalents)

• C’est un problème « indécidable »

Il n’existe pas d’algorithme général permettant de dire, étant donnés deux programmes P et P’ qu’ils font la même chose.

Notion de problème

27

Problème: Déterminer si un programme quelconque, sur une donnée représentée par un entier n, ne va pas boucler indéfiniment (Problème de terminaison)

• C’est un problème « indécidable »

Il n’existe pas d’algorithme général qui, étant donné un programme P et un entier n, permette de dire que P ne va pas boucler indéfiniment sur l’entrée n

Notion de problème

28

Notion de programme

29

Notion de programme

Définition

• Un programme (ou encore algorithme) est une procédure effective pour résoudre un problème (toutes les instances du problème)

• Une caractéristique importante d’une procédure effective est qu’elle contient exactement la marche à suivre pour résoudre le problème, et qu’aucune décision supplémentaire ne doit être prise lors de l’exécution de la procédure.

• Une procédure effective doit se terminer pour toutes les instances du problème

30

Exemple de Procédure non effective (1)

• Cette procédure n’est pas une procédure effective car on ne sait pas comment détecter les boucle infinie , ni les appels récursif infinis

Notion de programme

• Pour résoudre le problème de terminaison (l’arrêt) d’un programme

• Soit la procédure qui consiste à « déterminer si le programme n’a pas de boucles ou de séquences d’appels récursifs infinies.”

31

Fonction Calcul (n: integer ):integer ;begin if n = 1 then 1 else if pair(n) then Calcul (n ÷ 2) else Calcul(3 × n+1);end.

Calcul(1) =1,

Calcul (2)=1,

Calcul(3)=Calcul(10)=Calcul(5)=Calcul(16)=Calcul(8)=Calcul(4)

= Calcul(2)=Calcul(1)=1

Calcul(7)=Calcul(22)=Calcul(11)=Calcul(34)=Calcul(17)

= Calcul(3*17+1) ……

Notion de programme

Exemple de Procédure non effective (1)

32

Notion de Décidabilité

33

Soit un prédicat P (une propriété), applicable à un entier n

P est décidable si et seulement si il existe une méthode (un algorithme) permettant de dire au bout d’un temps fini (i.e.: un nombre fini de pas de calcul) si P(n) est vrai ou si P(n) est faux

Définition:

Décidabilité

Notion de Décidabilité

34

Notion de Décidabilité

Exemples:

Propriété P1(n) = « L’entier n est pair »

P1 est décidable

Propriété P2(n) = « L’entier n a au moins un nombre premier qui lui est strictement supérieur »

P2 non décidable

35

Notion de Calculabilité

36

Soit f une fonction de N dans N,

f est calculable si et seulement si il existe une méthode de calcul (un algorithme) permettant pour tout entier n d’obtenir f(n) si nDom(f) et si nDom(f)

Calculabilité

Définition:

Notion de Calculabilité

37

• Les opérations simples (addition, produit…) sont des fonctions « calculables »:

• parce que nous connaissons des algorithmes pour les effectuer, cela signifie que nous sommes capables de réduire ces tâches à des opérations encore plus simples, que nous combinons entre elles.

Exemples:

Notion de Calculabilité

38

5 6 9 8

+ 3 9 6 4

-------------

9 6 6 2 décomposé en :

faire 8 + 4 (table d’addition)

2, retenue de 1

faire 9 + 6 + 1 (la retenue)

etc.

Notion de Calculabilité

Exemple: addition entière

39

2- Noter aussi que nos algorithmes de calcul (addition, produit…) reposent sur certaines conventions (choix d’un mode de représentation des nombres, choix d’une base…) et sur une définition implicite des opérations

Notion de Calculabilité

Remarques:

1- De telles actions font appel à des opérations encore plus simples

40

– Par exemple: prendre deux mots d’inégale longueur

et chercher à savoir si le plus petit figure à l’intérieur du plus grand (pattern-matching)

– Vérifier si une expression contenant des parenthèses est correctement parenthésée

Notion de Calculabilité

Remarques:

3- Tout ne se ramène pas à des calculs sur les entiers…

41

- Les couples d’entiers

– Les suites d’entiers– Les entiers relatifs– Les fractions– Les nombres réels– Les chaînes de caractères– Les arbres– ….

4- Dans la définition de calculabilité et de décidabilité la fonction f et le prédicat P sont définis sur N , Qu’en est-il pour les autres types de données ?

Notion de Calculabilité

Remarques:

42

Les définitions s’étendent aux prédicats et fonctions qui s’appliquent à des ensembles dénombrables

Notion de Calculabilité

43

Notion de dénombrabilité

44

Dénombrabilité

• Un ensemble dénombrable est un ensemble dont les éléments peuvent être énumérés, ou numérotés : on peut les arranger de telle sorte qu’il y ait un premier, un deuxième, un troisième, etc.

Définition:

Notion de Dénombrabilité

• L’ensemble est considéré comme étant un ensemble dénombrable

45

Exemples

Notion de Dénombrabilité

• {0, 1, 2, 3, 4} est dénombrable

• {Ali, Sara, Mohamed, Brahim} est dénombrable (il suffit de choisir un classement arbitraire, par exemple par ordre d’âge)

• {xN; x<100} est dénombrable

• {0,1, 2, 3}{0, 1, 2, 3} est dénombrable

(classer les couples dans l’ordre lexicographique, avec 0<1<2<3)

• {0, 1, 2, 3}n est dénombrable pour tout n (même raison)

46

• L’ensemble des mots utilisant les lettres de l’alphabet Français et de longueur inférieure ou égale à 26 est dénombrable

Notion de Dénombrabilité

Exemples

• N est dénombrable

• P = {xN, x est pair} est infini dénombrable:

Il existe une bijection de P vers N (donc une numérotation possible des entiers pairs)

47

• Z (l’ensemble des entiers relatifs) est infini dénombrable…

Exemples Notion de Dénombrabilité

on peut classer les relatifs comme suit:

0; -1; +1; -2; +2; -3; +3; -4; +4; -5 etc.

La fonction qui donne la numérotation est:

f(0) = 1

f(-n) = 2n (n0)

f(+n) = 2n+1

48

• NN est infini dénombrable

On peut classer les couples (m, n) comme suit:

(0,0);(1,0);(0,1);(0,2);(1,1);(2,0);(3,0);(2,1);

(1,2);(0,3);(0,4);(1,3);(2,2);(3,1);(4,0) etc.

• Q+ est infini dénombrable,

• Q- est infini dénombrable,

• Q aussi

Exemples

Notion de Dénombrabilité

49

Les réels contiennent les rationnels et les irrationnels, ces derniers se caractérisent par le fait qu’ils n’ont aucune représentation sous forme d’un objet fini,

Donc… comment espérer avoir une réponse en un temps fini lorsqu’on part d’un objet qui n’a aucune représentation finie?

• R non dénombrable

Notion de Dénombrabilité

Exemples

50

• Tout ensemble fini est dénombrable. Un ensemble fini est dénombrable parce qu’il est

toujours possible de définir une bijection de cet ensemble vers une partie finie de N (c’est-à-dire un ensemble de la forme {0,1,...n})

Remarques

• L’union de deux ensembles dénombrables est dénombrable.

• Le produit d’ensembles dénombrables est dénombrable. (ex: Nk pour tout entier k)

Notion de Dénombrabilité

51

Notion de Codage

52

E N

Si f est bijective alors les éléments de E peuvent être codés par des entiers et vice versa

Soit E: un ensemble dénombrable

N: l’ensemble des entiers naturels

f: une fonction de numérotation de EN

codage

Notion de Codage

Remarque

53

Des chaînes aux nombres entiers

• Les chaînes de caractères (les mots sur un alphabet donné A) constituent un ensemble infini dénombrable:

• on peut donc associer à chaque chaîne un entier• Cet entier peut être: - le numéro d’ordre dans un classement quelconque des chaînes - Le numéro calculé selon un code attribuant un chiffre à chaque caractère (cf. code ASCII),….

Notion de Codage

54

Chaînes de caractères

codage

N

Notion de Codage

• Tout calcul sur les chaînes peut donc se ramener à un calcul sur des entiers

Des chaînes aux nombres entiers

55

Des nombres entiers aux chaînes

• Pour procéder à des calculs sur les nombres entiers, il faut leur donner une représentation sous forme de chaîne (ou mot).

• Une représentation possible est une représentation dans le système binaire : sous forme de suite de 0 et 1

Donc les calculs sur des entiers se ramènent à des calculs sur des chaînes.

Notion de Codage

56

Remarque

• Finalement, tout algorithme et tout calcul se ramène à manipuler des suites de symboles ( donc des chaînes).

Notion de Codage

• Les instances d’un problème sont des symboles (des chaînes)

57

• Si par exemple on a représenté les nombres entiers en binaire

• Le problème « est-ce que n est pair? » se ramène au problème « est-ce que la représentation de n appartient à

l’ensemble des représentations des entiers pairs? »

Exemple-1

Notion de Codage

58

• Le problème « est-ce qu’il existe des solutions entières de l’équation xn+yn=zn? »

se ramène au problème

« savoir si un certain ensemble de chaînes est non vide. »

Exemple-2

Notion de Codage

59

Formalisation des problèmes

60

Formalisation des problèmes

•Les instances d’un problème sont représentées par des chaînes de symboles (mots)

• Il est nécessaire de rappeler certaines définitions:

alphabet, mot, langage,…etc.

61

Alphabet

Un alphabet est un ensemble fini de symboles.

Définition:

Exemples

• = {a, b, c}

• = {,, }

• = {0,1, 2, 3,4,5,6,7,8,9}

• = {♠,♣,♥,●}

Formalisation des problèmes

62

• Un Mot sur un alphabet est une séquence finie d’éléments de cet alphabet.

MotDéfinition:

Exemples• a, abs, zt, bbbssnbnzzyyyyddtrra, grosseguindaille

sont des mots sur l’alphabet = {a, . . . , z}.

• 4♠3●5 2 , 12765 ♠

sont des mots sur l’alphabet ={0, . . . , 8, ♠, ●, }.

• Mot vide est désigné par ou

• Longueur du mot w est notée |w|

Formalisation des problèmes

63

LangagesDéfinition:

Exemples

Un langage est ensemble (fini ou non) de mots définis sur le même alphabet.

• {aab, aaaa, , a, b, abababababbbbbbbbbbbb}, { , aaa, a, bbb} et

sont des langages sur l’alphabet {a, b}.

•{0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100,101,111,…}

est le langage contenant tous les mots de l’alphabet {0, 1}.

• L’ensemble des mots représentant les programmes C qui s’arrêtent

toujours.

Remarque: {}

Formalisation des problèmes

64

Opérations sur les langages

Soit deux langages L1 et L2.

• L1 L2 = {w /w L1 ou w L2}

• L1 · L2 = {w/ w = xy , x L1 et y L2}

• L1 = {w * / w L1}= * \ L1

• L1* = {w/ k 0 et w1, . . . ,wk L1 et w = w1w2 . . .wk}

Union

Concaténation

Complément

Fermeture itérative (fermeture de Kleene)

Formalisation des problèmes

65

Formalisation du Calcul

66

• Les problèmes se ramènent à des problèmes de reconnaissance de l’appartenance à un certain langage:

Formalisation du calcul

• Tout ensemble de chaînes est défini comme un langage

• Etant donné un langage L et un mot w

Est-ce que wL ?

67

Formalisation du calcul

Exemple

Problème P(n) : L’entier n est-il pair

Se ramène au problème

wL

Où w: est la chaîne de caractères qui représente

l’entier n

L: langage dont les éléments sont les chaînes

représentant tous les entiers pairs

68

• Il faut donc déterminer le plus petit ensemble possible d’opérations élémentaires, suffisamment générales pour que le maximum de calculs (sur des entiers, des chaînes quelconques etc.) puissent se ramener à des combinaisons de ces opérations.

Formalisation du calcul

Comment procéder à la reconnaissance de mot d’un langage?

69

Plusieurs solutions

• Machines de Turing• Automates• Machines RAM• fonctions récursives (Church)• Lambda – calcul • …

Formalisation du calcul

Modèles de Calcul

70

FIN