TD 1 – Fonctions récursives primitives
Solution de l'exercice 1. On va montrer que les singletons sont récursifs primitifs car leur fonction caractéristique est récursive primitive.
Fonctions récursives primitives et récursives partielles
Le prédicat de disibilité x
Solution :
Corrigé de l'interrogation. Exercice 1 : Montrez que les fonctions suivantes sont primitives récursives : 1. plus=?xy.x+y. 2. sigma=?x. Solution :.
Contrôle continu 2 éléments de corrigé par P. Brunet et L. Gonnord
Préliminaire : rappels sur les fonctions primitives récursives. Une fonction f : Nn ? N est récursive primitive si elle est : — Une des fonctions renvoyant
TD 3 – Théorème s-m-n théorèmes de Rice et de point fixe
Exercice 1. Montrer qu'il existe une fonction récursive primitive f telle que pour tout n ? N
TD 2 – Fonctions récursives
Exercice 4. Est-il vrai qu'une fonction totale est récursive primitive si et seulement si son graphe est récursif primitif ? Université Paris Diderot.
Corrigé du TD de Logique 9 (Machines à registres)
Dec 1 2014 Corrigé du TD de Logique 9 (Machines à registres) ... Exercice 3 (Fonctions universelle primitive récursive) :.
Calculabilité
1.1.1 Définition de fonctions récursives primitives . 2.7 Exercices – analyse de décidabilité de probl`emes . ... Je viens de corriger.
TD 2 – Fonctions récursives
Exercice 4. Est-il vrai qu'une fonction totale est récursive primitive si et seulement si son graphe est récursif primitif ? Solution de l'exercice 4.
Séance 5 : Fonctions récursives et machine de Turing
et ensuite définir la sous-famille des fonctions primitives récursives qui sont des fonctions totales. Pour la somme ? c'est un exercice.
[PDF] TD 1 – Fonctions récursives primitives
Solution de l'exercice 1 On va montrer que les singletons sont récursifs primitifs car leur fonction caractéristique est récursive primitive
[PDF] Fonctions récursives primitives et récursives partielles
Exercice 3 Montrer que les constructeurs suivants sont récursifs primitifs (c'est `a dire que s'ils sont utilisés sur des fonctions récursives primitives
[PDF] rappels sur les fonctions primitives réc - CNRS
éléments de corrigé par P Brunet et L Gonnord Durée 1H Une fonction f : Nn ? N est récursive primitive si elle est : résolution de l'exercice
[PDF] Séance 5 : Fonctions récursives et machine de Turing
Fonctions primitives récursives - Fonctions récursives partielles et récursives - Machines de Turing - Equivalence de deux modèles de calcul
[PDF] Corrigés des exercices sur les fonctions récursives
Corrigés des exercices sur les fonctions récursives Exercice 7 1 1 sous-programmes récursifs Pour chacun des sous-programmes nous donnerons les
Master informatique semestre 1 Modèles de calcul devoir 2005
Exercice 1 : fonctions primitives récursives Un corrigé est disponible ci-dessous Les fonctions primitives récursives sont des fonctions de plusieurs
[PDF] Corrigé du TD de Logique 8 (Fonctions primitives récursives)
19 nov 2012 · Exercice 4 (Fonction d'Ackermann) : 1 Si t ? Im(?z?(yz)) alors si t = ?(nx0) > x0 et donc le schéma µ borné rend bien ce x0
[PDF] TD de Logique 9 (Fonctions récursives) - mathenspsleu
26 nov 2012 · être corrigé au début du TD Les exercices qui ne sont pas abordés en cours Exercice 4 (Fonction universelle primitive récursive) :
[PDF] Fonctions récursives
FONCTIONS R´ECURSIVES Exercice 175 Montrer que les fonctions suivantes sont récursives primitives (les prédicats sont vus comme des fonctions `a valeur
TD 1 Fonctions récursives primitives - PDF Free Download
Donc la fonction sup p est récursive primitive pour tout p N Exercice 4 Exercices - Fonctions de plusieurs variables : corrigé Pour commencer
Comment faire une fonction récursive ?
?rire une fonction python récursive reste(a,b) prenant en arguments deux entiers naturels non nuls a et b et retournant le reste de la division euclidienne de a par b. A l'aide des deux propriétés suivantes : – pour tous entiers a et b, on a pgcd(a;b) = pgcd(a ?b;b). – pour tout entier a, on a pgcd(a;0) = a.- La fonction récursive ne change pas de signature. Elle prend toujours en paramètres les variables base et times . Elle retourne toujours un nombre.
Corrigés des exercices sur les fonctions
récursivesExercice 7.1.1sous-programmes récursifs
Pour chacun des sous-programmes, nous donnerons les paramètres en précisant le paramètre sur
lequel porte la récurrence, le cas de base (valeur de ce paramètre pour lequel le calcul s"arrête) et la
variation qui affecte le paramètre à chaque appel récursif.1. Ecrire un sous-programme récursif qui calcule la somme des n premiers carrés. Par exemple, si
n vaut 3, ce sous-programme calculera12+ 22+ 32. Ce sous programme n"est défini que pour un n supérieur à 0. - Un seul paramètre n, qui doit être positif. - cas de base : n=1. - variation de n à chaque appel : -12. Ecrire un sous-programme récursif qui calcule la somme des éléments positifs d"un tableau.
- Deux paramètres : un tableau d"entiers tab et un indice ind. Le but de la fonction est de renvoyer la somme des entiers positifs du tableau compris entre ind et la fin du tableau. Pour avoir le résultat pour tout le tableau, il faut appeler la fonction avec pour indice 0. - cas de base : ind=tab.length. - variation de ind à chaque appel : +13. Ecrireunsous-programmerécursifquivérifiesiunechaînedecaractèreestunpalindrôme.Pour
cela vous utiliserez les méthodescharAtetlengthde la classeString.s.charAt(i) renvoie le ième caractère de la chaînesets.length()renvoie la longueur des. - Deux paramètres : une chaîne s et un indice ind - cas de base : ind=s.length()/2. En effet, à chaque appel, on va vérifier la correspondance de 2 caractères. Il est inutile de parcourir le tableau en entier. - variation de ind à chaque appel : +14. Ecrire un sous-programme récursif qui réarrange les éléments d"un tableau en ordre inverse.
- Deux paramètres : une tableau d"entiers tab et un indice ind - cas de base : ind=tab.length/2. En effet, à chaque appel, on va inverser 2 caractères. Il ne faut surtout pas faire un parcours complet du tableau, sinon chaque élément est changé de place deux fois et revient à sa position d"origine. - variation de ind à chaque appel : +15. Ecrire un sous-programme récursif qui calcule la valeur numérique d"une chaîne de caractères
composée de chiffres.Ici encore, deux paramètres : la chaîne et un indice. Cette fois, nous parcourons la chaîne de droite à gauche, ce qui simplifie la tâche. Cas de base : 0. Pas de calcul : -1. 1 Si cela vous aide, vous pouvez commencer par chercher une formule qui exprime le calcul récursifà effectuer.
de la section 13.3.1 du cours. Remarquez comment est fait le traitement d"exception dans cet exemple; c"est un peu diffé- rent de ce que nous avons vu jusqu"ici.classExo20_1{ static intsommePremiersCarres(intn)throwsHorsDomaine{ if(n==1){ return1; }else if(n>0){ return(n*n)+sommePremiersCarres(n-1); throwHorsDomaine.typique; static intsommePositifs(int[] tab,intindice)throwsHorsDomaine{ if(indice >= tab.length){ return0; }else if(indice>=0){ if(tab[indice]>0){ returntab[indice]+sommePositifs(tab, indice+1); }else{ returnsommePositifs(tab, indice+1); throwHorsDomaine.typique; static booleanpalindrome(String s,intnieme)throwsHorsDomaine{ if(nieme > s.length() /2){ return true; if((nieme<0) || (nieme > s.length() /2)){ throwHorsDomaine.typique; return(s.charAt(nieme) == s.charAt(s.length()-nieme-1)) && palindrome(s, nieme+1); static voidordreInverse(int[] tab,intindice)throwsHorsDomaine{ if(indice<0){ throwHorsDomaine.typique; }else if(indice < tab.length /2){ inttampon; tampon = tab[indice]; tab[indice] = tab[tab.length-indice-1]; tab[tab.length-indice-1]=tampon; ordreInverse(tab,indice+1); static intvaleurDeChar(charc)throwsHorsDomaine{ if(c == "0"){ return0; }else if(c == "1"){2 NFA031
cCNAM 2012
return1; }else if(c == "2"){ return2; }else if(c == "3"){ return3; }else if(c == "4"){ return4; }else if(c == "5"){ return5; }else if(c == "6"){ return6; }else if(c == "7"){ return7; }else if(c == "8"){ return8; }else if(c == "9"){ return9; throwHorsDomaine.typique; static intvaleurNumerique(String s,intindice)throwsHorsDomaine{ charc = s.charAt(indice); if(indice == 0){ returnvaleurDeChar(c); }else{ return(valeurNumerique(s, indice-1) *10 + valeurDeChar(c)); public static voidmain(String[] args)throwsHorsDomaine{ int[] test = {1, 5, -5, 10, -10, 3}; for(inti=0; iTerminal.ecrireChar("");
Terminal.sautDeLigne();
ordreInverse(test,0); for(inti=0; iTerminal.ecrireChar("");
Terminal.sautDeLigne();
classHorsDomaineextendsException{ staticHorsDomaine typique =newHorsDomaine();NFA031
cCNAM 2012 3
Exercice 7.1.2Fibonacci
Ecrire une fonction qui calcule les valeurs de la série de Fibonacci, définie par : -u0= 0 -u1= 1 -un=un1+un2Ecrivez cette fonction sous forme itérative et sous forme récursive. Laquelle des deux variantes
est préférable ici?classExo20_2{ static intfiboIteratif(intn){ if((n == 0) || (n == 1)){ returnn; }else{ intmoinsDeux = 0; intmoinsUn = 1; intnouveau; for(inti=2; ielle est moins efficace que la version itérative. Dans la version itérative, une valeur de la suiteunest
conservée pendant deux tours de boucles successifs (d"abord dans moinsUn, puis dans moinsDeux),alors que dans la version récursive, comme il n"y a pas de possibilité de conserver une valeur dans une
variable entre deux appels récursifs, la valeur est recalculée. Il y a un effet cumulatif. Voici par exemple les appels effectués pour le calcul de fiboRecursif(5).4 NFA031
cCNAM 2012
fibo(5)fibo(3) fibo(4) fibo(1) fibo(2) fibo(2) fibo(3) fibo(0) fibo(1) fibo(0) fibo(1) fibo(1) fibo(2) fibo(0)fibo(1)On voit que fiboRecursif(2) est appelé trois fois, fiboRecursif(1) quatre fois, etc. La version itéra-
tive ne calcule qu"une fois chaque terme de la suite. Elle est donc préférable.NFA031
cCNAM 2012 5
quotesdbs_dbs16.pdfusesText_22[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
[PDF] prime prof principal contractuel
[PDF] evaluation anglais 6ème description physique