Calculabilité et complexité : DM PDF

Afin de concevoir un nouveau produit et satisfaire la fonction d'usage nous principales qui répondent aux besoins de l'utilisateur

DM-3200 Prise en main

Pour des détails complets sur les fonctions décrites ici et sur toutes les autres fonctions consultez le Mode d'emploi. Avec les touches curseur

Sur lerreur dinterpolation des fonctions de plusieurs variables par

Sur l'erreur d'interpolation des fonctions de plusieurs variables par les Dm-splines. RAIRO. Analyse numérique tome 12

Approximation spline de surfaces de type explicite comportant des

données de Lagrange ou d'Hermite du 1er ordre d'une fonction non régulière f fonctions non régulières On étudie enfin la convergence des Dm splines ...

DM corrigé

b) Fonction mesurable. c) L'intégrale de Lebesgue d'une fonction positive. d) Fonction Lebesgue intégrable. Quelles sont les pré-

DM?770

DM?770. • Poids plume 40% plus léger que les smartphones La fonction Guide Vocale perfectionnée

DM : STATISTIQUE – CALCUL LITTERAL – FONCTIONS

DM : STATISTIQUE – CALCUL LITTERAL – FONCTIONS. EXERCICES STATISTIQUE ET CALCUL LITTERAL OBLIGATOIRES. Statistique – Brevet (6 points).

Calculabilité et complexité : DM

La composition n'est définie que sur les tuples o`u tous les ?i sont définies. • est close par récursion primitive. Pour toutes fonctions semi-récursives ? ?

SHARP TWAIN AR/DM - Guide de lutilisateur

AR/DM. Chapitre 3: Utilisation de SHARP TWAIN AR/DM. Explique les fonctions et utilisations des différentes boîtes de dialogue du logiciel SHARP.

DM/1/I (F)

1 févr. 2022 créateur indiqué à la rubrique 11 du formulaire DM/1. ... Le signataire dont les fonctions sont indiquées ci-dessus

Calculabilite et complexite : DM

Maximilien Colange

1 Fonctions recursives

On considere des fonctions (possiblement partielles), d'arite nie, deNdansN. Plus formellement, on se place dans[k2N(Nk)N. Pour une fonctionf, on note f(~n) =?sifn'est pas denie sur le tuple~n. Ledomaine de denitionfest

D(f) =f~njf(~n)6=?g.

On denit la classe des fonction semi-recursivesSReccomme la plus petite classe qui : contientZ:N7!Nla fonction constante de valeur 0 :8n2N:Z(n) = 0 ; contientS:N7!Nla fonction successeur :8n2N:S(n) =n+ 1 ; contient toutes les projections. Pour 1ik2N, on notePki:Nk7!N la projection selon la composantei:Pki(x1;:::;xk) =xi. est close par composition. Pour toutes fonctions semi-recursives1;:::;p (de m^eme aritek), et toute fonction semi-recursive d'aritep, la fonction ~n7! (1(~n);:::;p(~n)) est semi-recursive. La composition n'est denie que sur les tuples ou tous lesisont denies. est close par recursion primitive. Pour toutes fonctions semi-recursives ; , la fonctiondenie comme suit (m;~n) =( (~n) sim= 0 (m1;(m1;~n);~n) sim >0 est semi-recursive. est close par minimisation. Pour toute fonction semi-recursive, la fonc- tion~n7!minfm2Nj(~n;m) = 0gest recursive, avec la convention que min;=?. Notez que seule l'operation de minimisation peut introduire des fonctions par- tielles (la composition et la recursion ne font que propager les defauts de denition). Si on remplace, dans la denition ci-dessus, la minimisation par la minimisa- tiontotale, en ne considerant que des fonctionstelles que8~n9m:(~n;m) = 0, on obtient la classe des fonctionsrecursives, noteeRec. Notez que les fonctions recursives sont toutes totales (car la composition de fonctions totales est totale, et que la recursion primitive denie a partir de fonctions totales est totale).

SoitAN. La fonction caracteristique deAestA:x7!(

1 six2A

0 six =2A. La

fonction caracteristique partielle deAestA:x7!(

1 six2A

?six =2A. On dit que 1 Aest recursif si sa fonction caracteristique est recursive, etAest semi-recursif si sa fonction caracteristique partielle est semi-recursive. On rappelle qu'une fonction partiellef: 7!est semi-calculable si il existe une machine de TuringMsur l'alphabet telle que, pour tout input u2, sif(u)6=?alorsMs'arr^ete sur l'inputuavec l'outputf(u). De m^eme, une fonction totalef: 7!est calculable si il existe une machine de TuringMsur l'alphabet telle que, pour tout inputu2,Ms'arr^ete sur l'inputuavec l'outputf(u).

1. Montrez que les fonctions semi-recursives sont semi-calculables. On xera

un alphabet et on pourra alors ecrire les entiers en basejj.

2. Montrez que toute fonction semi-calculable est semi-recursive. On pourra

considerer une conguration d'une machine de Turing comme un entier (ecrit dans une base appropriee) et decrire une fonction qui fait passer d'une conguration a la suivante.

3. Montrez (a partir des reponses precedentes) qu'une fonction est recursive

si et seulement si elle est calculable.

4. Montrez qu'un ensemble est semi-recursif si et seulement si il est recursive-

ment enumerable.

5. Montrez qu'un ensemble est recursif (au sens des fonctions recursives) si

et seulement si il est recursif (au sens des machines de Turing).

6. Montrez que le domaine de denition d'une fonction semi-recursive est

semi-recursif.

7. Montrez que le domaine de denition d'une fonction recursive est recursif.

Historiquement, les fonctions recursives et semi-recursives forment le premier modele de calcul connu. L'origine de la notion de fonctions recursives se perd dans les mathematiques du XIXe siecle, mais il semble que la premiere formali- sation soit due a Dedekind en 1888. Leur utilisation comme modele de calcul est proposee en 1933 par Godel. Church introduit le-calcul en 1936, et demontre que ce modele de calcul est equivalent (en termes de fonctions denissables) a celui des fonctions recursives. La m^eme annee, Turing accomplit un travail sim- ilaire avec son modele de machines abstraites qui portent aujourd'hui son nom. Cette concordance inattendue conduira a la formulation de la these dite de Church-Turing, qui postule que la notion (jusque-la informelle) de calculabilite est caracterisee par ces trois modeles equivalents. Cette these sera renforcee par les dierentes tentatives de caracteriser la notion de calculabilite qui ont jusqu'a present toutes abouti a la denition de modeles equivalents. On parle parfois de Turing-completude pour caracteriser l'expressivite de ces modeles (expression qui temoigne de la preeminence actuelle du modele de Turing pour comprendre et denir la calculabilite).

2 Fonctions primitives recursives

La classe des fonctions primitives recursives, noteePrim, est l'ensemble des fonctions recursives qu'on peut denir sans utiliser la minimisation. 2

1. Montrez que les operations arithmetiques usuelles (addition, soustrac-

tion, multiplication, division, modulo, exponentiation, factorielle) sont recursives primitives.

2. Montrez que la fonction qui anassocie le plus petit nombre premier plus

grand quenest recursive primitive.

2.1 Hierarchie de Grzegorczyk

On denit la suite de fonctions (n)n2N:

0(m) =m+ 1

n+1(0) =n(1) n+1(m+ 1) =n(n+1(m)) On appelle cette suite de fonctions la hierarchie de Grzegorczyk (en fait, il y en a plusieurs denitions possibles, notamment en termes de classes imbriquees de fonctions, mais l'idee sous-jacente est la m^eme).

1. Montrez que1(m) =m+ 2 pour toutm.

2. Montrez que2(m) = 2m+ 3 pour toutm.

3. Montrez que3(m) = 2m+33 pour toutm.

4. Montrez que4(m) = 222

|{z} m+33 pour toutm.

5. Montrez que toutes lesnsont recursives primitives.

6. Montrez que toutes lesnsont strictement croissantes.

7. Montrez quen(m) +kn+k(m) pour tousn;m;k.

8. Montrez quek(m(n))2+max(k;m)(n) pour tousm;n;k.

9. Montrez que pour toute fonction recursive primitivefd'aritek, il existe

unmtel que8~n2Nk:f(~n)m(max~n).

10. Utilisez la hierarchie de Grzegorczyk pour denir une fonctionAcka un

argument qui n'est pas primitive recursive.

11. Montrez que l'ensemble (n;Ack(n)) est recursif.

Rappelons que la formalisation des fonctions recursives peut ^etre attribuee a Dedeking en 1888. La notion de fonction primitive recursive est proposee par le suedois Skolem (au passage l'un des peres de la logique formelle) en 1923. La fonctionAckattendue ci-dessus est une fonction denie par Peter et Robin- son en 1948. C'est une variante de la fonction d'Ackermann, denie en 1928 par le mathematicien allemand eponyme. C'est un des premiers exemples de fonction recursive mais non recursive primitive (la premiere est exhibee en 1927 par le mathematicien roumain Sudan). La fonction d'Ackermann, decouverte 3 independamment des travaux de Sudan, est restee la plus connue de par sa sim- plicite. Les travaux de Sudan et d'Ackermann, montrant l'expressivite limitee de la recursion primitive, marquent l'emergence de la notion de complexite. Avec le recul que l'on a aujourd'hui, ils demontrent l'existence de fonctions parfaitement calculables qui semble pourtant hors d'atteinte en pratique. Sachez que la valeur de cette fonction en 5 n'est pas connue precisement, et semble largement hors de portee de la technologie actuelle. Il est facile de denir des fonctions qui croissent encore plus vite, en generalisant sa construction. L'inverse de cette fonction appara^t dans l'analyse de complexite de certains algorithmes (par exemple dans les structures d'union-nd). Cette fonction in- verse est croissante et tend vers l'inni, mais si lentement qu'on la considere en pratique comme constante, de valeur au plus 5. 4quotesdbs_dbs46.pdfusesText_46

[PDF] Calculabilité et complexité : DM

Calculabilite et complexite : DM

Maximilien Colange

1 Fonctions recursives

D(f) =f~njf(~n)6=?g.

SoitAN. La fonction caracteristique deAestA:x7!(

1 six2A

0 six =2A. La

1 six2A

1. Montrez que les fonctions semi-recursives sont semi-calculables. On xera

2. Montrez que toute fonction semi-calculable est semi-recursive. On pourra

3. Montrez (a partir des reponses precedentes) qu'une fonction est recursive

4. Montrez qu'un ensemble est semi-recursif si et seulement si il est recursive-

5. Montrez qu'un ensemble est recursif (au sens des fonctions recursives) si

6. Montrez que le domaine de denition d'une fonction semi-recursive est

7. Montrez que le domaine de denition d'une fonction recursive est recursif.

2 Fonctions primitives recursives

1. Montrez que les operations arithmetiques usuelles (addition, soustrac-

2. Montrez que la fonction qui anassocie le plus petit nombre premier plus

2.1 Hierarchie de Grzegorczyk

On denit la suite de fonctions (n)n2N:

0(m) =m+ 1

1. Montrez que1(m) =m+ 2 pour toutm.

2. Montrez que2(m) = 2m+ 3 pour toutm.

3. Montrez que3(m) = 2m+33 pour toutm.

4. Montrez que4(m) = 222

5. Montrez que toutes lesnsont recursives primitives.

6. Montrez que toutes lesnsont strictement croissantes.

7. Montrez quen(m) +kn+k(m) pour tousn;m;k.

8. Montrez quek(m(n))2+max(k;m)(n) pour tousm;n;k.

9. Montrez que pour toute fonction recursive primitivefd'aritek, il existe

10. Utilisez la hierarchie de Grzegorczyk pour denir une fonctionAcka un

11. Montrez que l'ensemble (n;Ack(n)) est recursif.