En informatique, une fonction f est récursive lorsque la définition de f utilise des Construire une fonction récursive Formuler une Nombre d'opérations en suspens limité par le langage de Recherche dichotomique dans une liste triée
Previous PDF | Next PDF |
[PDF] Récursion Récursivité - Pages Perso
factorielle, Fibonaci, exponenÄaÄon rapide, recherche dichotomique, tri fusion Exercices dirigés : arbre/pile des appels, environnements, itéraÄf → récursif,
[PDF] Algorithmes de Tris
Recherche dans un tableau, dichotomie 7 de 47 Recherche dichotomique itérative Remarque : La recherche dichotomique est récursive terminale Algorithme
[PDF] Recherche dichotomique dans un tableau dentiers - LAMSADE
13 sept 2000 · LANGAGE C - EXEMPLES DE PROGRAMMES Maude Manouvrier Programm int main() e de recherche dichotomique d'un élément dans une liste d'entiers */ Inf et Sup triés de la même manière (appel récursif) */ /* */
[PDF] Algorithmique et Recherche Dichotomique
Rajouter au programme recherchenombre py une fonction recherche_dichotomiquerec qui implé- mente de façon récursive l'algorithme de rechercher
[PDF] Fonctions récursives - Lycée Pierre Corneille
En informatique, une fonction f est récursive lorsque la définition de f utilise des Construire une fonction récursive Formuler une Nombre d'opérations en suspens limité par le langage de Recherche dichotomique dans une liste triée
[PDF] Recherche dichotomique dans un tableau [re04] Exercice - Unisciel
1 Algorithme de la recherche dichotomique 2 2 Recherche dichotomique / pgdichotab 2 3 Recherche récursive / pgdichotab2 4 3 1 Recherche dichotomique
[PDF] 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 instructions de boucle Récursivité simple : recherche dichotomique On stocke des question de goût, de style et de langage de programmation
[PDF] Thème 1 : la récursivité 1 Rappels sur les fonctions
Un langage récursif est un langage dans lequel on peut programmer des fonctions récursives Python est 3 2 Problème 2 : recherche dichotomique récursive
[PDF] Recherche dichotomique - Algo Prog Objet Python
Tableaux et matrices, recherche dichotomique Pour supprimer l'ambiguïté on va utiliser un pseudo langage Algorithme plus performant, récursif :
[PDF] Récursivité
Le choix du langage peut aussi avoir son importance : un langage fonctionnel tel Figure 11 – Une version récursive correcte de la recherche dichotomique
[PDF] organisation d une dsi type
[PDF] manuel de procédures informatiques
[PDF] cyberlux 8
[PDF] organisation d'un service informatique dans une entreprise
[PDF] cyberlux 8 crack
[PDF] exemple dossier exploitation informatique
[PDF] cyberlux 8 full
[PDF] bibliographie de max weber
[PDF] max weber pdf
[PDF] max weber économie et société tome 2 pdf
[PDF] max weber le savant et le politique pdf
[PDF] max weber économie et société fiche de lecture
[PDF] max weber économie et société tome 1 résumé
[PDF] max weber économie et société pdf
PC 2014-2015InformatiqueLycée Bertran de BornThème 1 : la récursivité " To understand recursion, you must understand recursion. »
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_dbs26.pdfusesText_32