CH.8 Décidabilité
Propriétés des langages récursivement énumérables : Fermés par union mais pas par intersection. Page 2. Automates ch8 3. Théorème : Le langage L est récursif si
05/06 - 2.2.3 Récursivité gauche
Un symbole non terminal A d'une grammaire est dit récursif si A algébrique non récursive gauche qui reconna?t le même langage.
Introduction `a la Programmation des Algorithmes 3.2. Langage C
Langage C – Fonctions récursives. François Fleuret https://fleuret.org/11x001/. On peut définir des fonctions mathématiques de mani`ere récursive.
Calculabilité
décidé par une certaine machine de Turing. Un langage ou un problème décidable est aussi dit récursif. Un langage qui n'est.
INDÉCIDABILITÉ MT ET GRAMMAIRES
Un langage L est récursif ssi L et ¬L sont récursivement énumérables. 10. Preuve. Page 11. Propriétés des langages récursifs.
Thème 1 : la récursivité 1 Rappels sur les fonctions
Pour définir nos fonctions nous utiliserons du pseudo-code ou la syntaxe du langage Python rappelée ci-dessous. Définition de la fonction : def maFonction(x1..
Programmation récursive 1. Quest-ce que la programmation récursive
Définition : la programmation récursive est une technique de programmation qui remplace les question de goût de style et de langage de programmation.
Calculabilité Cours 3 : réductions
L'ensemble des langages décidables avec oracle B est {A
Introduction `a la calculabilit´e
Langages récursifs et récursivement énumérables. Un langage est récursif s'il est décidé par une machine de Turing. Un langage est récursivement énumérable
L3 Informatique Calculabilité 18 septembre 2014 Exercice 1
18 sept. 2014 Exercice 1 (Clôture des langages récursifs) ... Montrer que L est un langage récursivement énumérable si et seulement s'il.
[PDF] Algorithmique Récursivité
Moyen simple et élégant de résoudre certain problème Définition On appelle récursive toute fonction ou procédure qui s'appelle elle même Algorithme Fact
[PDF] LIFAP2 : ALGORITHMIQUE ET PROGRAMMATION RECURSIVE
Algorithme itératif / récursif Programmation impérative / fonctionnelle Langage commun entre la machine et nous : Scheme N Guin – M Lefevre
[PDF] Séance 5 : Fonctions récursives et machine de Turing
Or le langage RP est équivalent à une partie du langage Pascal seulement avec la boucle for et sans appels récursifs V 1 2 3- Quelques exemples de fermeture
[PDF] Programmation récursive 1 Quest-ce que la programmation - LIPN
Définition : la programmation récursive est une technique de programmation qui remplace les instructions de boucle (while for etc ) par des appels de fonction
[PDF] La récursivité - Zeste de Savoir
12 août 2019 · La récursivité est un concept général qui peut être illustré dans (quasiment) tous les langages de programmation et qui peut être utile
[PDF] Récursivité
C'est ce qui garantit que le programme s'achèvera Exercice 5 Un programme en langage python : Jean-Manuel Mény – Ludovic Fasquelle – Irem de Lyon
[PDF] Récursivité - LACL
langages de programmation tel que le langage C Bien entendu cela complique l'implémentation d'un tel langage mais facilite la tâche du programmeur
[PDF] Récursivité
On peut citer à ce sujet Guido van Rossum le créateur du langage Python : I don't believe in recursion as the basis of all programming This is a fundamental
[PDF] Thème 1 : la récursivité 1 Rappels sur les fonctions
Pour définir nos fonctions nous utiliserons du pseudo-code ou la syntaxe du langage Python rappelée ci-dessous Définition de la fonction : def maFonction(x1
Inconnu
1 Rappels sur les fonctions
1.1 Qu"est-ce qu"une fonction?Définition.Une fonction est une séquence d"instructions que l"on regroupe sous un même nom; en général une
fonction comporte des variables ouparamètres d"entrée.L"appel de la fonction consiste en l"exécution de la séquence d"instruction pour des valeurs des paramètres d"entrée
(arguments); cet appel retourne une valeur de sortie.Pour définir nos fonctions nous utiliserons du pseudo-code ou la syntaxe du langage Python rappelée ci-dessous.
Définition de la fonction :
defmaFonction(x1,...,xN): """commentaires""" instruction 1 instruction n returnsortieAppel de la fonction :
Entrées ou arguments-→instruction 1
instruction 2 instruction n-→sortieExercice1.On définit une fonctionpuissance2(n)dont le paramètre est un entiernet qui retourne2n.
Pseudo-codeFonction :puissance2(n).Entrée :un entiernSortie :l"entier2nk= 0p= 1Tant quek < n:p= 2pk=k+ 1RetournerpPython
Justifier la terminaison de la fonction ci-dessus. Justifier qu"elle est correcte. 1 PC 2014-2015InformatiqueLycée Bertran de Born1.2 Variables locales et variables globalesDéfinition.Les variables utilisées dans le corps d"une fonction sont desvariables locales. Elles sont affectées au
moment de l"appel de la fonction et sont détruites à la sortie. Les paramètres d"entrés subissent le même traitement.On peut définir des fonctions et utiliser des variables locales dans ces fonctions sans se préoccuper de savoir si elles existent
ailleurs dans le script. Les affectations temporaires à l"appel de la fonction ne risquent pas d"interférer avec les autres
variables.Les variables utilisées à l"extérieur d"une fonction sont desvariables globales. Une fonction peut modifier une variable
globale à condition de la déclarer comme telle dans le corps de la fonction : on utilise l"instrutionglobal.
1.3 Fonctions et procédures en Python
Fonctions et procédures ont la même syntaxe; on les distinguent de la manière suivante : •Une fonction prend des arguments et retourne une valeur;•Une procédure réalise une action : affichage, écriture d"un fichier, ouverture d"une fenêtre graphique, modification
d"un objet... Ces changements perdurent après l"appel de la procédure. Elle retourne la valeurNone.
Exercice2.
Écrire une procédure Pythonechange(L,i,j)dont les pa- ramètres sont :Lde type list,ietjde typeint. La pro-cédure échangeL[i]etL[j].On peut naturellement envisager des objets de type mixte. D"un point de vue théorique nous travaillerons essentiellement
avec desfonctions pures.1.4 Exercice : la factorielle itérative
1.Écrire une fonction fact(n)dont l"argument d"entrée est un entiern. La fonction retourne la valeurn!calculée à
l"aide d"une bouclefor. 2. Étudier la terminaison et la correction de v otrefonction. 2 PC 2014-2015InformatiqueLycée Bertran de Born2 Fonctions récursives2.1 GénéralitésDéfinition.Unefonction récursiveest une fonction qui contient au moins un appel à elle-même.Un langage récursif est un langage dans lequel on peut programmer des fonctions récursives. Python est un langage
récursif.Exemple.Voici une définition récursive pour fonctionpuissance2(n)dont le paramètre est un entiernet qui retourne
2 n. On part du constat que : puissance2(n) = 2n= 2×2n-1= 2×puissance2(n-1)Pseudo-codeFonction :puissance2(n).Entrée :un entiernSortie :l"entier2nSin== 0:Retourner1Sinon:Retourner2×puissance2(n-1)Python
Que se passe-t"il lors de l"appel depuissance2(n)?Pour s"assurer de la terminaison d"une fonction récursive, on doit respecter les règles suivantes :Règles.
•La fonction doit contenir un ou plusieurscas de basene comportant pas d"appel récursif.Dans la fonctionpuissance2: c"est le casn= 0.
•Les appels de la fonction se font des arguments plus simple pour conduire aux cas de base.Dans l"appel depuissance2(n): les arguments successifs sontn-1> n-2>···>0.Voici deux mauvaises versions de la fonctionpuissance2(n).Pourquoi?
Mauvaise version 1.defpuissance2(n) :return2*puissance2(n-1)Mauvaise version 2. defpuissance2(n) :ifn==0 :return1else:return4*puissance2(n-2)3 PC 2014-2015InformatiqueLycée Bertran de Born2.2 Exemples simples de fonctions récursives2.2.1 La factorielle récursive
Exercice3.Écrire une fonction récursivefactRec(n)pour le calcul den!. Donner le nombre d"appel et le nombre de
multiplication pour le calcul den!.2.2.2 L"exponentiation rapide
L"exponentiation rapide s"appuie sur un algorithme que nous présentons dans le cas particulier du calcul deq25.
•Pour calculerq25, on calculeq12×q12×q. •Pour calculerq12,on calculeq6×q6. •Pour calculerq6, on calculeq3×q3. •Pour calculerq3, on calculeq2×q •Pour calculerq2, on calculeq×q. •Pour calculerq, on calculeq×1.Nombre de multiplication nécessaires :
Écrire une fonction Python récursiveexpo(q,n)qui calculeqnen s"appuyant sur le principe : q n=? qn2 ?2si n est pair q.? qn-122sinon.Exercice4. Analyse de l"algorithme.
1.Justifier qu"un app elde expo(q,n)se termine.
2. Justifier qu"un app elde expo(q,n)retourne toujoursqn.3.Complexité de l"algorithme.NotonsC(n)le nombre de multiplications lors d"un appel deexpo(q,n)pour
n≥1. (a)Justifier que C(n) =C??n2
??+rnavecrnà expliciter en fonction den. (b) (c) Comparer sou sPython a vecla fonction timele temps d"exécution depuissance(2,n)etexpo(2,n)pour de grandes valeurs den. 4PC 2014-2015InformatiqueLycée Bertran de Born2.3 La suite de Fibonacci : limite de la récursivité
La multiplication des lapins.Vous allez faire l"acquisition d"un couple de bébés lapins. Au bout d"un mois ce couple
est adulte. Le mois suivant il donne naissance à un couple de bébés lapins : vous avez maintenant 4 lapins. Puis chaque
couple engendre tous les mois un nouveau couple deux mois après sa naissance.Nous avons le schéma ci-contre :
Légende :m :bébé lapin; M :lapin adulte.•Mois 0.m m •Mois 1.M M •Mois 2.M M m m •Mois 3.M M M M m m •Mois 4.M M M M M M m m m mNotonsFNle nombre de lapins que l"on a au bout duN-ième mois. On convient que :F0= 2. Nous avons doncF1= 2
puisF2= 4etF3= 6. Plaçons nous au moisN+ 2, nous aurons tous les couples de lapins du mois précédent (le mois
N+ 1) et toutes les progénitures des couples de lapins du moisN. Nous avons donc la relation : FN+2=FN+1+FN
Écrire deux fonctions PythonFiboIt(N)etFiboRec(N)pour le calcul deFN. La première est rédigée de manière itérative,
la seconce récursive.FiboIt(N)FiboRec(N)
Exercice5.
1.Analyse de l"algorithme itératif.Estimer la complexité de l"algorithme itératif.
2.Analyse de l"algorithme récursif.
(a) Dénom brerles app elsde la fonction FiboRec(N)pour l"argumentN= 5. (b) On note A(N)le nombre d"appels récursifs deFiboRec(N). Justifier que pourN≥3,A(N)≥?32 NComment qualifier cette complexité?
5PC 2014-2015InformatiqueLycée Bertran de Born3 Récursivité et tableaux : une première approche
" divide ut regnes. »Jules César, Napoléon...
Dans cette partie on reprend quelques éléments d"algorithmique sur les listes (ou tableaux). On met en évidence la
stratégie dudiviser pour régnerqui cherche à résoudre un problème en appliquant les trois principes suivants :
•Diviser :c"est découper le problème en sous-problèmes identiques mais sur des entrées de tailles inférieures.
•Régner :c"est pouvoir résoudre tous les sous-problèmes soit directement (cas de base), soit de manière récursive.
•Combiner :c"est résoudre le problème initial à partir des solutions des sous-problèmes.
On applique cette méthode sur deux problèmes simples ayant trait aux tableaux (ou listes).3.1 Problème 1 : le maximum récursif
On cherche à résoudre le problème de recherche du maximum d"une listeL. La stratégie dudiviser pour régnersuggère
l"approche suivante :•Diviser :on découpe la liste en deux sous-listes de taille égale (ou presque) pour lesquelles on se pose le problème
du maximum;•Régner :si une sous-liste ne contient qu"un seul élément son maximum est cet élément, sinon on le trouve de
manière récursive;•Combiner :ayant trouvé le maximum des deux sous-listes, on cherche la plus grande des deux valeurs.
L=????
maxi(L1)???? maxi(L2) maxi(L)=max(maxi(L1),maxi(L2))Fonction récursivemaxi(L,i,j)qui cherche le maximum de la listeLentre les indicesietj.Analyse de la complexité de l"algorihtme (Nombre d"appels récursifs, nombre de comparaisons) : vérifier que la complexité
est enO(n). 6PC 2014-2015InformatiqueLycée Bertran de Born3.2 Problème 2 : recherche dichotomique récursive
On cherche à résoudre le problème de recherche d"un élémentxdans une listeLd"objets triés par ordre croissant (par
exemple : une liste de nombres, une liste de mot pour l"ordre alphabétique). On applique encore la stratégie dudiviser
pour régner•Diviser :on se place au milieu (ou presque) de la liste (position d"indicem); on découpe alors la liste en deux
sous-listes.•Régner :si une sous-liste ne contient qu"un seul élément la réponse est obtenue en testant l"égalité avecx, sinon
la réponse pour une sous-liste est obtenue de manière récursive.•Combiner :on compareL[m]etx: s"ils sont égaux on a trouvé, siL[m]>xon cherche dans la sous-liste à gauche,
sinon on cherche dans la sous-liste à gauche.L=•????
L[m] = x?Fonction récursiverechDicho(L,x,i,j)qui cherche l"élémentxdans liste triéeLentre les indicesietj. La fonction
retourne l"indice dexs"il est dans la liste etFalsesinon.Analyse de la complexité de l"algorihtme (Nombre d"appels récursifs, nombre de tests d"égalité) : vérifier que la complexité
est enO(log2(n)). 7 PC 2014-2015InformatiqueLycée Bertran de Born4 Transformée de FourierLa transformée de Fourier discrète est un outil majeur en traitement du signal et intervient dans des domaines très variés.
4.1 Un contexte : spectre d"un signal périodique
Un signalf, de périodeT, se développe en série de Fourier sous la forme : f(t) =+∞? n=-∞c ne2iπ ntT oùcndésignent les coefficients de Fourier qui se calculent sous la forme intégrale : c n=1T T 0 f(t)e-2iπ ntT dtLe spectre defest l"ensemble des couples?nT
,cn? n?Z. La détermination du spectre est un élément important de l"étude d"un signal périodique.On suppose connue la périodeTdu signal ainsi qu"un nombre finiNde valeurs du signal régulièrement espacés sur une
période : y k=f? kTN aveck= 0,1,2···N-1La méthode des rectangle nous permet d"approcher les coefficients de Fourier par la somme ci-dessous :
1N N-1? k=0y ke-2iπ nkN ?cn On vérifie que l"approximation est essentiellement valable pour-N2 -1(ou un intervalle centré siNest impair). C"est sur le calcul de ces coefficients que se concentre notre étude.4.2 Transformée de Fourier discrèteDéfinition.Nous fixons un entierN >0et nous posonsωN=e2iπN
Y n=N-1? k=0y kω-nk Ns"appelle latransformée de Fourier discrète.Dans le calcul des coefficients de Fourier (casNpair) nous avons donc :
Nc n?? ?Y Y n+Nsi-N2 8 PC 2014-2015InformatiqueLycée Bertran de BornCalcul direct. 1.Écrire u nefonction Python TFD(y)qui prend une listeyen entrée et retourne la listeYobtenue par transformée
de Fourier discrète des coefficients dey. La somme est calculée de manière itérative. 2.Estimer le nom bred"additions et de m ultiplicationsn écessairesp ource calcu l.Nombre d"opérations?
Comment qualifier la complexité?
4.3 Transformée de Fourier rapide
Nous présentons dans cette dernière partie un algorithme connu sous le nom detransformée de Fourier rapide(TFR) ou
fast Fourier transform(FFT) qui va nettement faire baisser le coût de calcul de la tranformée de Fourier discrète.
La méthode : principe général.C"est une autre illustration du paradigmediviser pour régner.On suppose queNest
un nombre pair, soitN= 2m. 1.NInavec :
P n=y0+y2ω-2nN+···+y2m-2ω-(2m-2)n
NetIn=y1+y3ω-2n
N+···+y2m-1ω-(2m-2)n
N On remarque alors les relations :Pn+m=PnetIn+m=In. Il suffit donc de calculerPnetInpourn= 0...m-1 et remarquer queω-(n+m)N=-ω-n
Npour former :
Y n=Pn+ω-n NIn etYn+m=Pn+ω-(n+m)NIn=Pn-ω-n
NIn 2. En se rapp elantqu eω2N=ωm, une lecture attentive des nombresPnetInnous permet d"écrire :L"algorithme.On décrit le principe d"une fonctionFFT(y,N)qui prend en entrée une listeyde tailleNet retourne la
transformée de Fourier discrète dey. On suppose queNest une puissance de2.•Diviser :on découpe la liste en deux sous-listes, celle des termes de rang pair et celle des termes de rang impair.
•Régner :si une sous-liste ne contient qu"un seul élément le résultat est immédiat, sinon on le trouve de manière
récursive;•Combiner :ayant trouvé la TFD des deux sous-listes, on combine les listes selon le point 1 de la méthode décrite
ci-dessus. 9 PC 2014-2015InformatiqueLycée Bertran de BornFonctionFFT(y,N).Analyse de la complexité. 10quotesdbs_dbs45.pdfusesText_45[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