CHAPITRE III Programmation Dynamique III.1 Exemple introductif
La suite de Fibonacci est la suite d'entier (un)n?0 définie Pour analyser la complexité de cet algorithme on remarque que chaque appel `a Fibonacci().
Complexité (suite)
Nombres de Fibonacci. Définition. F0 = 1. F1 = 1. Fn = Fn?2 + Fn?1 pour n ? 2. Question. Quelle est la complexité des algorithmes de calcul des.
Complexité en algorithmique
Complexité : suite de Fibonacci. Temps de calcul avec l'algorithme récursif. Algorithme fib rec(n: entier) si n<2 alors renvoyer 1.
Calcul des nombres de Fibonacci [cx03] - Exercice
Montrez par récurrence que la complexité (en nombre d'additions) de cet algorithme est en ?(2n/2). Solution simple. On veut montrer qu'il existe une constante c
Récursivité
4 oct. 2017 4 Complexité d'un algorithme récursif ... 4.4 Complexité exponentielle . ... Implémentation Python de la suite de Fibonacci récursive ...
Calcul des nombres de Fibonacci [cx03] - Exercice
Montrez par récurrence que la complexité (en nombre d'additions) de cet algorithme est en ?(2n/2). Solution simple. On veut montrer qu'il existe une constante c
Complexité de lalgorithme dEuclide
Même si la complexité algorithmique est un domaine qui a connu un essor En appliquant cet algorithme `a deux nombres de Fibonacci consécutifs ...
Trois algorithmes de calcul des nombres de Fibonacci
Dans cette série d'exercices nous nous intéressons de la complexité dite arithmétique. Ce modèle prend en compte uniquement le nombre des opérations.
TD dalgorithmique avancée Corrigé du TD 2 : récursivité
Montrez que la complexité (en nombre d'additions) de cet algorithme est Écrire un algorithme récursif qui calcule pour n > 0
Escapade algorithmique avec Fibonacci
Nous aborderons des thèmes au coeur du programme commun d'informatique des classes préparatoires notamment : algorithme d'Euclide
[PDF] Complexité (suite) - IREM Clermont-Ferrand
La complexité du tri par base est alors en O(n) puisqu'on applique un nombre fixe de fois un algorithme linéaire Page 89 Les nombres de Fibonacci Les tris
[PDF] la suite de Fibonacci - IGM
Pour analyser la complexité de cet algorithme on remarque que chaque appel `a Fibonacci() se fait en temps constant (si on ne tient pas compte des appels
[PDF] Définition de la complexité algorithmique - exemple Fibonacci - limsi
La complexité d'un algorithme est la fonction mathématique qui décrit en fonction de la taille des données d'entrées (par exemple le nombre de mots)
[PDF] Calcul des nombres de Fibonacci [cx03] - Exercice - Unisciel
Solution simple La complexité de l'algorithme fibRt en nombre d'additions est donnée par la récurrence T(n) = 1+ T(n ? 1) On a donc T(n) = n ? 1 pour
[PDF] Trois algorithmes de calcul des nombres de Fibonacci - LaBRI
Dans cette série d'exercices nous nous intéressons de la complexité dite arithmétique Ce modèle prend en compte uniquement le nombre des opérations
[PDF] Complexité en algorithmique
Complexité : suite de Fibonacci Temps de calcul avec l'algorithme récursif Algorithme fib rec(n: entier) si n
[PDF] irem de lyon
Complexité d'un algorithme Trois questions à se poser quand on fabrique un algorithme : raisonnable? i complexité 1 Calculs des nombres de Fibonacci
[PDF] Calculs de complexité dalgorithmes
?Complexité des algorithmes ?Un algorithme à partir d'une donnée établit un résultat Leonardo de Pise surnommé Fibonacci
[PDF] Complexité des algorithmes — - Pascal Delahaye
L'analyse de la complexité d'un algorithme consiste `a évaluer : de la fonction récursive donnant la valeur du terme un de la suite de Fibonacci
[PDF] TD : La complexité temporelle Exemple 1 : Fibonacci
24 nov 2017 · Nous allons évaluer le temps de calcul de chacun des algorithmes de calcul précédents de façon expérimentale et théorique 1) Etude
Quelle est la complexité de l'implémentation de Fibonacci ?
La complexité est en O(n × m) en temps et en espace. On remarque qu'on peut faire le calcul en ne gardant en mémoire que deux lignes ou deux colonnes (puisqu'on ne regarde que dans la colonne d'avant et la ligne d'avant), ce qui permet de ne stocker que O(n) valeurs.Comment déterminer la complexité d'un algorithme ?
Pour calculer la complexité d'un algorithme: On calcule la complexité de chaque partie de l'algorithme. On combine ces complexités conformément aux règles déjà vues. On effectue sur le résultat les simplifications possibles déjà vues.Quelle est la complexité de la fonction factorielle ?
La complexité d'un algorithme récursif se fait par la résolution d'une équation de récurrence en éliminant la récurrence par substitution de proche en proche. Exemple 1 : La fonction factorielle (avec T(n) le temps d'exécution nécessaire pour un appel à Facto(n)).- On mesure alors la complexité en temps d'un algorithme comme le nombre de ces opérations élémentaires. Par exemple, en considérant élémentaire l'addition de 2 chiffres, poser l'addition de deux nombres de n chiffres nous fera effectuer n additions à 1 chiffre, la complexité sera donc de n.
TD d'algorithmique avancee
Corrige du TD 2 : recursivite
Jean-Michel Dischler et Frederic Vivien
Suite de Fibonacci
La suite de Fibonacci est denie comme suit :
Fib(n) =8
:1 sin= 01 sin= 1
Fib(n1) + Fib(n2) sinon:1.Ecrivez un algorithme recursif calculant Fib(n).Fibonacci(n) sin= 0 oun= 1alors renvoyer1sinon renvoyerFibonacci(n1) +Fibonacci(n2)2.Montrez que la complexite (en nombre d'additions) de cet algorithme est en
(2n2). On procede par recurrence. On veut montrer qu'il existe une constantecstrictement positive telle que T(n)c:2n2, pour des valeurs densuperieures a une certaine bornen0(a determiner). Supposons le resultat demontre jusqu'au rangn1. Alors : T(n) =T(n1) +T(n2) + 1c:2n12+c2n22+ 1c:2n22+c:2n22+ 12c:2n22=c:2n2 Il nous reste juste a montrer que cette equation est vraiedonc des casn= 2etn= 3(la recurrence necessitedeuxvaleurs de depart) :{Casn= 2:Fibonacci(2) =Fibonacci(1)+Fibonacci(0), etT(2) = 1. Pour que la propriete
desiree soit vraie,cdoit donc verier :1c:222= 2c,c12{Casn= 3:Fibonacci(3) =Fibonacci(2)+Fibonacci(1), etT(3) = 2. Pour que la propriete
desiree soit vraie,cdoit donc verier :2c:232= 2p2c,cp22
Donc sic=12, pourn2, on aT(n)c2n2et doncT(n) =
(2n2).3.Ecrire un algorithme recursif qui calcule, pourn >0, le couple (Fibonacci(n),Fibonacci(n1)).Fib-Paire(n)
sin= 1alors renvoyer(1, 1) sinon(x,y) =Fib-Paire(n1)renvoyer(x+y,x)4.Utilisez l'algorithme precedent pour ecrire un nouvel algorithme calculantFibonacci(n).1
Fibonacci(n)
sin= 0alors renvoyer1 sinon(x,y) =Fib-Paire(n) renvoyerx5.Qu'elle est la complexite (en nombre d'additions) de cet algorithme? La complexite de l'algorithmeFib-Paire, en nombre d'additions, est donnee par la recurrenceT(n) =1 +T(n1). On a doncT(n) =n1pourFib-Paire, et par extension pour la nouvelle version de
Fibonacci.
Operations ensemblistes
Dans cette partie on considere des ensembles representes par des tableaux, certains ensembles seront tries
et d'autres pas.Toutes les solutions proposees doivent ^etre recursives.1.Nous voulons un algorithmeAppartenance(A,x) qui recherche si un elementxappartient a l'en-
sembleA. Sixappartient eectivement aA, l'algorithme renverraVrai, etFauxsinon.(a)Cas des ensembles non tries :i.Ecrivez un tel algorithme.Recherche(A,rang,x)
sirang>longueur(A)alors renvoyerFaux siA[rang] =xalors renvoyerVrai sinon renvoyerRecherche(A,rang+ 1,x)L'appel initial de l'algorithme est alorsRecherche(A, 1,x).ii.Quelle est sa complexite en nombre de comparaisons?
Dans le pire cas, l'element n'appartient pas a l'ensemble et tout le tableau est parcouru. La complexite au pire est donc en(n), ounest la longueur du tableau (et donc la taille del'ensemble).(b)Cas des ensembles tries (dans l'ordre croissant) :i.Ecrivez un tel algorithme.Recherche(A,rang,x)
sirang>longueur(A) ouA[rang]> x alors renvoyerFaux sinon siA[rang] =x alors renvoyerVrai sinon renvoyerRecherche(A,rang+ 1,x)L'appel initial de l'algorithme est alorsRecherche(A, 1,x).ii.Quelle est sa complexite en nombre de comparaisons?
Le pire cas est aussi en(n): il intervient quand l'element recherche n'appartient pas al'ensemble mais est plus grand que tous les elements de l'ensemble.iii.Utilisez une recherche dichotomique pour ameliorer votre algorithme.Recherche(A,x,inf,sup)
milieu jinf+sup2k siA[milieu] =x alors renvoyerVrai sinon siA[milieu]> xalors renvoyerRecherche(A,x,inf,milieu- 1) sinon renvoyerRecherche(A,x,milieu+ 1,sup)2 iv.Quelle est la complexite de votre nouvel algorithme? Posonsn=supinf+1le nombre d'elements dans la partie du tableau a etudier. Consideronsla taille du tableau lors de l'eventuel appel recursif. Nous avons deux cas a considerer :{L'appel eectue est :Recherche(A,x, inf, milieu - 1). Le nombre d'elements concernes
est alors : milieu1inf+ 1 =jsupinf2k =n12n2.{L'appel eectue est :Recherche(A,x, milieu + 1, sup). Le nombre d'elements concernes est alors : sup(milieu+ 1) + 1 =lsupinf2m =n12n2: On passe donc d'un ensemble de taillena un ensemble de taille au plusn2. D'ouT(n)2T(n2)(la fonctionT(n)etant croissante, on peut se permettre l'approximation). Par
consequent :T(n)2log2(n)T(n2log2n)etT(n) =O(log2n).2.Nous voulons maintenant un algorithmeUnion(A,B) qui nous renvoie l'union des deux ensembles qui
lui sont passes en argument.(a)Cas des ensembles non tries :i.Ecrivez un tel algorithme.Union(A,B,rang,C)
siRecherche(A,B[rang]) =Faux alorslongueur(C) longueur(C) + 1C[longueur(C)] B[rang]
Union(A,B,rang+ 1,C)
L'appel initial est alorsUnion(A,B, 1,C) ouCest un tableau de taillelongueur(A) +longueur(B), et dont leslongueur(A) premieres cases contiennent les elements deA.ii.Quelle est sa complexite?
La recopie deAdansCest de co^ut longueur(A).
L'algorithmeUnionest appele longueur(B)fois, chacun de ces appels eectuant un appel a RecherchesurA, dont le co^ut au pire est en longueur(A). La complexite au pire deUnion est donc en(longueur(A)longueur(B))ou(nm),netmdenotant la taille des deuxtableaux. Ce pire cas appara^t quand les tableauxAetBsont disjoints.(b)Cas des ensembles tries (dans l'ordre croissant) :i.Ecrivez un tel algorithme.Union(A,a,B,b,C)
sia >longueur(A) etb >longueur(B)alors renvoyerC sib >longueur(B) ouB[b]> A[a] alorslongueur(C) longueur(C) + 1C[longueur(C)] A[a]
Union(A,a+ 1,B,b,C)
sinonlongueur(C) longueur(C) + 1C[longueur(C)] B[b]
sialongueur(A) etA[a] =B[b]alorsUnion(A,a+ 1,B,b+ 1,C) sinonUnion(A,a,B,b+ 1,C) L'appel initial estUnion(A, 1,B, 1,C).ii.Quelle est sa complexite? La complexite de cet algorithme est au pire en(longueur(A)+longueur(B))ou(n+m):a chaque appel on decremente au moins de un l'ensemble des valeurs a considerer.3.Nous voulons maintenant un algorithmeIntersection(A,B) qui nous renvoie l'intersection des deux
ensembles qui lui sont passes en argument.(a)Cas des ensembles non tries :i.Ecrivez un tel algorithme.3
Intersection(A,B,rang,C)
siRecherche(A,B[rang]) =Vrai alorslongueur(C) longueur(C) + 1C[longueur(C)] B[rang]
Intersection(A,B,rang+ 1,C)
L'appel initial est alorsIntersection(A,B, 1,C) ouCest un nouveau tableau, de taille min(longueur(A);longueur(B)), et ne contenant initialement aucun element (longueur(C) =0).ii.Quelle est sa complexite?
L'algorithmeIntersectionest appele longueur(B)fois, chacun de ces appels eectuant un appel aRecherchesurA, dont le co^ut au pire est en longueur(A). La complexite au pire deIntersectionest donc en(longueur(A)longueur(B))ou(nm),netmdenotant lataille des deux tableaux. Ce pire cas appara^t quand les tableauxAetBsont disjoints.(b)Cas des ensembles tries (dans l'ordre croissant) :i.Ecrivez un tel algorithme.Intersection(A,a,B,b,C)
sia >longueur(A) oub >longueur(B)alors renvoyerC siA[a] =B[b]alorslongueur(C) longueur(C) + 1C[longueur(C)] A[a]
renvoyerIntersection(A,a+ 1,B,b+ 1,C) sinon siB[b]> A[a]alors renvoyerIntersection(A,a+ 1,B,b,C) sinon renvoyerIntersection(A,a,B,b+ 1,C) L'appel initial estIntersection(A, 1,B, 1,C, 0).ii.Quelle est sa complexite? La complexite de cet algorithme est au pire en(longueur(A)+longueur(B))ou(n+m):a chaque appel on decremente au moins de un l'ensemble des valeurs a considerer.4.Nous voulons maintenant un algorithmeDifference(A,B) qui nous renvoie la dierence des deux
ensembles qui lui sont passes en argument (La dierence deAet deB, noteeAnBest l'ensemble deselements deAn'appartenant pas aB).(a)Cas des ensembles non tries :i.Ecrivez un tel algorithme.Difference(A,rang,B,C)
siRecherche(B,A[rang]) =Faux alorslongueur(C) longueur(C) + 1C[longueur(C)] A[rang]
Diff erence(A,rang+ 1,B,C) L'appel initial est alorsDifference(A, 1,B,C) ouCest un tableau de taillelongueur(A), ne contenant initialement aucun element (longueur(C) = 0).ii.Quelle est sa complexite? L'algorithmeDifferenceest appele longueur(A)fois, chacun de ces appels eectuant un appel aRecherchesurB, dont le co^ut au pire est en longueur(B). La complexite au pire deDifferenceest donc en(longueur(A)longueur(B))ou(nm),netmdenotant lataille des deux tableaux. Ce pire cas appara^t quand les tableauxAetBsont disjoints.(b)Cas des ensembles tries (dans l'ordre croissant) :i.Ecrivez un tel algorithme.4
Difference(A,a,B,b,C)
sia >longueur(A)alors renvoyerC siA[a] =B[b]alors renvoyerDifference(A,a+ 1,B,b+ 1,C) sinon siA[a]< B[b]alorslongueur(C) longueur(C) + 1C[longueur(C)] A[a]
renvoyerDifference(A,a+ 1,B,b,C) sinon renvoyerDifference(A,a,B,b+ 1,C) L'appel initial estDifference(A, 1,B, 1,C, 0).ii.Quelle est sa complexite? La complexite de cet algorithme est au pire en(longueur(A)+longueur(B))ou(n+m): a chaque appel on decremente au moins de un l'ensemble des valeurs a considerer.5quotesdbs_dbs33.pdfusesText_39[PDF] différence entre motivation et mobilisation
[PDF] plan daction mobilisation du personnel
[PDF] mobilisation du personnel définition
[PDF] suite fibonacci
[PDF] mobilisation des employés définition
[PDF] trouver les racines d'un polynome de degré 2
[PDF] polynome degré n
[PDF] définition de la mobilisation
[PDF] factoriser un polynome de degré n
[PDF] polynome degré 2
[PDF] phyllotaxie spiralée
[PDF] définition société civile organisée
[PDF] comment expliquer l'abstention électorale
[PDF] mobilisation des civils première guerre mondiale
