cours 2:Complexité des algorithmes récursifs
Algorithmes récursifs. Calcul de complexité. ?. Exemple 1 : La fonction factorielle. Pour calculer la solution générale de cette équation on peut procéder
Chapitre 18 Algorithmique de base
Cet appel de fonction récursif va finir par planter un jour car (d) on peut maintenant calculer i*factorielle(1) i (sommet de la pile) vaut 2
Récursivité
Oct 4 2017 2.1 Algorithmes récursifs . ... 4 Complexité d'un algorithme récursif ... Implémentation Python de la factorielle récursive :.
Algorithmique Récursivité
On appelle récursive toute fonction ou procédure qui s'appelle elle même. Algorithme Fact. Entrée : un entier positif N. Sortie : factorielle de N.
Cours No 4 : Fonctions Récursives.
Exemple : l'ensemble des valeurs de la fonction “factorielle” sur les entiers Exemple : Algorithme récursif de calcul du pgcd de deux nombres non nuls :.
Correction et complexité des algorithmes récursifs
Un algorithme récursif est constitué par une fonction dont la définition contient des appels `a elle même. Un exemple : Calcul de la factorielle d'un nombre.
Cours algorithmique avancée (WI) - cours 2:La récursivité et le
Algorithmes récursifs. ?. Application: factorielle. ?. Application: tours de Hanoi. ?. Paradigme ''diviser pour régner''.
IFT1015 — Philippe Langlais
Un algorithme récursif est un algorithme qui résout un problème en calculant des solutions d'instances plus @return factorielle de n (version itérative).
Complexité
Complexité d'un algorithme récursif (1). Soit l'algorithme : fonction factorielle (n: Naturel) : Naturel début si n=0 alors retourner 1.
La récursivité Lalgorithme dEuclide Implémentation en Python
La fonction factorielle est de complexité O(n). 14 / 29. La pile d'exécution : le cas factoriel. A chaque appel récursif de la
Algorithmique avancée - Cours/Formations informatique à
Un meilleur algorithme Algorithme FibLineaire(k) Si k = 1 alors retourner (k0) sinon (ij) := FibLinaire(k-1) retourner (i+j i) Entrées: Une entier k >= 0 Sortie: (F kF k?1) Complexité en temps: O(k)
Algorithmique Récursivité
Algorithme Fact Entrée : un entier positif N Sortie : factorielle de N si N = 0 retourner 1 sinon retourner N x Fact(N-1) 4 de 11 (paramètres changés
CHAPITRE 1 LA RECURSIVITE
Un algorithme (une fonction une procédure) est dit récursif si sa définition (son code) contient un appel à lui-même Un algorithme qui n’est pas récursif est dit itératif Utilisations variées (liste non exhaustive) : o Calcul de suite récursive (numérique graphique Fibonacci Factorielle etc )
Cours 2 : La récursivité - LRI
Tout objet est dit récursif s’il se définit à partir de lui-même Ainsi une fonction est dite récursive si elle comporte dans son corps au moins un appel à elle-même De même une structure est récursive si un de ses attributs en est une autre instance 2013-2014 Algorithmique 2
Comment définir un algorithme récursif?
Un algorithme est dit récursif lorsqu’il est défini en fonction de lui-même. Dans le cadre de ce cours, nous ne nous intéresserons qu’aux programmes et algorithmes récursifs. Mais la notion de définition récursive est beaucoup plus générale : en mathématiques : définition de l’exponentielle : ? x ? R, f 0 ( x) = f ( x) et f (0) = 1.
Quelle est la définition récursive de la fonction factorielle ?
Il est cependant possible de donner une définition récursive de la fonction factorielle : La factorielle d'un nombre N vaut 1 si N est égal à 0, et N multiplié par la factorielle de N - 1 sinon. Cette définition est parfaitement équivalente à la précédente, et peut se traduire en code par une fonction récursive :
Quel est l’algorithme d’une fonction récursive de dérivation?
Voici (une esquisse) de l” algorithme d’une fonction récursive de dérivation (nommée ici derivee ). sinon si … 2.2.4. Exemple 3 : Les tours de Hanoï ¶ Et voici un algorithme récursif pour résoudre le problème des tours de Hanoi. Cet algorithme est celui d’une fonction nommée hanoi à trois paramètres
Quel est le principe de récursivité ?
Le principe de récursivité. Tout objet est dit récursif s’il se définit à partir de lui-même Ainsi, une fonction est dite récursive si elle comporte, dans son corps, au moins un appel à elle-même De même, une structure est récursive si un de ses attributs en est une autre instance. 2013-2014 Algorithmique 2.
Algorithmique...
Complexité
Luc Brun
luc.brun@greyc.ensicaen.frA partir de travaux de
Habib Abdulrab(Insa de Rouen)
Complexit
´e - p.1/25
Plan...
Notion de complexitéComment évaluer la complexité d'un algorithmeExemple de calculs de complexité
Complexit
´e - p.2/25
Notion de complexité (1)
Comment évaluer les performances d'un algorithmedifférents algorithmes ont des coûts différents en termes de
temps d'exécution (nombre d'opérations effectuées par l'algorithme),taille mémoire (taille nécessaire pour stocker les différentes structures de
données pour l'exécution). Ces deux concepts sont appelé la complexité en temps et en espace de l'algorithme.Complexit
´e - p.3/25
Notion de complexité (2)
La complexité algorithmique permet de mesurer les performances d'un algorithme et de le comparer avec d'autres algorithmes réalisant les mêmefonctionnalités.La complexité algorithmique est un concept fondamental pour toutinformaticien, elle permet de déterminer si un algorithmeaet meilleur
qu'un algorithmebet s'il est optimal ou s'il ne doit pas être utilisé...Complexit
´e - p.4/25
Temps d'exécution (1)
Le temps d'exécution d'un programme dépend : 1. du nombre de données, 2. de la taille du code, 3. du type d'ordinateur utilisé (processeur,mémoire),4. de la complexité en temps de l'algorithme "abstrait» sous-jacent.
Complexit
´e - p.5/25
Temps d'exécution (2)
Soitnla taille des données du problème etT(n)le temps d'exécution de l'algorithme. On distingue :Le temps du plus mauvais casTmax(n)
Correspond au temps maximum pris par l'algorithme pour un problème de taillen. Le temps moyenTmoy:Temps moyen d'exécution sur des données de taillen(?suppositions sur la distribution des données). T moy(n) =r? i=1p iTsi(n)piprobabilité que l'instructionsisoit exécutée,Tsi(n): temps requis pour l'exécution desi.
Complexit
´e - p.6/25
Temps d'exécution
Règles générales :
1. le temps d'exécution (t.e.) d'une affectation ou d'un test est considéré
comme constantc,2. Le temps d'une séquence d'instructions est la somme dest.e.des
instructions qui la composent,3. le temps d'un branchement conditionnel est égal au t.e. du test plus le max
des deux t.e. correspondant aux deux alternatives (dans le cas d'un temps max).4. Le temps d'une boucle est égal à la somme du coût du test + du corps de la
boucle + test de sortie de boucle.Complexit
´e - p.7/25
Problèmes du temps d'exécution (1)
Soit l'algorithme suivant :
Nom:Calcul d'une somme de carrés
Role:Calculer la valeur moyenne d'un tableau
Entrée:n : entier
Sortie:somme : réel
Déclaration:i: Naturel
début somme←0.0 pouri←0àn-1faire somme←somme+i*i finpour finComplexit
´e - p.8/25
Problèmes du temps d'exécution (2)
T moy(n) =Tmax(n) =c1+c1+n(c2+c3+c4+c5+c1) = 2c1+n??5i=1ci? avecc1: affectation,c2: incrémentation,c3test,c4addition,c5multiplication. Trop précis?1. Faux,2. Inutilisable.Notion de complexité : comportement asymptotique du t.e.:Tmax(n) =Tmoy(n)≈nC
Complexit´e - p.9/25
Estimation asymptotique
Définition 1Une fonction f est de l'ordre de g , écrit avec la notation Grand-O , pour toutn≥n0 selon la définition ci-dessus, on aura: f1(n) = 2n+ 3 =O(n3),2n+ 3 =O(n2),2n+ 3 =O(n)au plus juste
f2(n) = 7n2=O(2n),7n2=O(n2)au plus juste
mais,7n2N'EST PASO(n)Complexit
´e - p.10/25
Égalité de complexité
Définition 22 fonctions f et g sont d'égale complexité, ce qui s'écrit comme:O( f )= O( g ) (ouf=θ(g)), ssi
f =O(g)et g =O(f) exemples:n,2n, et0,1nsont d'égale complexité:O(n)=O(2n)=O(0,1n)O(n2)etO(0,1n2+n)sont d'égale complexité:O(n2)=O(0,1n2+n)par contre:2netn3se sont PAS d'égale complexité:O(2n)?=O(n3)
Définition 3une fonction f est de de plus petite complexité que g, ce qui s'écrit comme:O(f)2nest de plus petite complexité quen:O(log2n) =O(10n2) Complexit
´e - p.11/25
Propriétés
Réflexivité:
g=O(g)Transitivité : sif=O(g)etg=O(h)alorsf=O(h)Produit par un scalaire :O(λf) =O(f),λ >0.Somme et produit de fonctions :
O(f)+O(g)=O(max{f,g})O(f).O(g)=O(f.g)
Complexit
´e - p.12/25
Complexité d'une boucle
pouri←1ànfaire s finpour avec s=O(1). Temps de calcul des:Ts=CNombre d'appels des: nTemps de calcul total :T(n) =nTs=O(n)Complexité :O(n)
Complexit
´e - p.13/25
Boucles imbriquées
Théorème 1La complexité depboucles imbriquées de 1 ànne contenant que des instructions élémentaires est en O(np) Preuve:
vrai pourp= 1,supposons la ppt vrai à l'ordrep. Soit : pouri←1ànfaire instruction finpour Complexit´e - p.14/25
Boucles tant que
h←1 h←2*h fintantque Test, multiplication, affectation :O(1):T=CNombre d'itérations :log2(n).Temps de calcul :T(n) =Clog2(n) =O(log2(n))
Complexit
´e - p.15/25
Complexité d'un algorithme récursif (1)
Soit l'algorithme :
fonctionfactorielle(n: Naturel) :Naturel début sin = 0alors retourner1 sinon retournern*factorielle(n-1) finsi fin Complexit
´e - p.16/25
Complexité d'un algorithme récursif (2)
c 1test,c2multiplication.
T(0)=c1T(n)=c1+c2+T(n-1)
?T(n) =nc2+ (n+ 1)c1 SoitC= 2max{c1,c2}
Complexité enO(n).
Les calculs de complexité d'algorithmes récursifs induisent naturellement des suites. Complexit
´e - p.17/25
Algorithmes récursifs enO(log2(n))(1)
Théorème 2Soient,debut,finetn=fin-debuttrois entiers. La complexité de l'algorithme ci dessous est enO(log2(n)). procéduref(debut,fin) Déclaration Entiermilieu
début milieu←debut+fin 2sifin-milieu>1 et milieu-debut>1alors
s sinon sitestalors f (debut,milieu) sinon f (milieu,fin) finsi finsi fin Complexit´e - p.18/25
Algorithmes récursifs enO(log2(n))(2)
Tests, s :O(1)
T(n) =T(n
2) +C T(n 2) =T(n
4) +C...=...
T(1) =T(0) +C
T(n) =T(0) +Clog2(n)
Complexit´e - p.19/25
Algorithmes récursifs enO(nlog2(n))(1)
procéduref(debut,fin) Déclaration Entiermilieu
début milieu←debut+fin 2sifin-milieu>1 et milieu-debut>1alors
s 1sinon
pouri←1ànfaire s 2finpourf(début,milieu)f(milieu,fin)
finsi fin Complexit
´e - p.20/25
Algorithmes récursifs enO(nlog2(n))(2)
Tests, s :O(1)Boucle :O(n).
T(n) =n+ 2T(n
2) 2T(n 2) n+ 4T(n 4)...=...
2 p-1T(2) =n+ 2pT(1) T(n) =n?p+ 2p?T(1)
avecp= [log2(n)] On a de plus:O(nlog2(n) +nT(1)) =O(nlog2(n))
Complexit´e - p.21/25
Principales complexités
O(1): temps constant,O(log(n)): complexité logarithmique (Classe L), O(n): complexité linaire
(Classe P), O(nlog(n))O(n2),O(n3),O(np): quadratique, cubique,polynomiale (Classe P), O(pn)complexité exponentielle
(Classe EXPTIME)".
O(n!)complexité factorielle.
Complexit
´e - p.22/25
Influence de la complexité
n→2n. O(1) O(log2(n))
O(n) O(nlog2(n))
O(n2) O(n3) O(2n) t t+ 1 2t 2t+ 2n
4t 8t t2 1 log2(n) n nlog2(n) n2 n3 2n n= 102 1μs
6μs
0.1ms 0.6ms 10ms 1s 4×1016a
n= 103 1μs
10μs
1ms 10ms 1s 16.6min
n= 104 1μs
13μs
10ms 0.1s 100s
11,5j n= 105 1μs
17μs
0.1s 1.6s 2.7h 32a
n= 106 1μs
20μs
1s 19.9s 11,5j 32×103a
∞Complexit´e - p.23/25 Limites de la complexité
La complexité est un résultat asymptotique : un algorithme enO(Cn2)peut être plus efficace qu'un algorithme enO(C?n)pour de petites valeurs den siC?C?,Les traitements ne sont pas toujours linéaires?Il ne faut pas supposer d'ordres de grandeur entre les différentes constantes. Complexit
´e - p.24/25
Conseils
Qualités d'un algorithme :
1. Maintenable (facile à comprendre, coder, déboguer),
2. Rapide
Conseils :
1. Privilégier le point 2 sur le point 1 uniquement si on gagne en complexité.
2. "ce que fait» l'algorithme doit se lire lors d'une lecture rapide : Une idée
par ligne. Indenter le programme. 3. Faire également attention à la précision, la stabilité et la sécurité.
La rapidité d'un algorithme est un élément d'un tout définissant les qualités de celui-ci. Complexit
´e - p.25/25
quotesdbs_dbs41.pdfusesText_41
Complexit
´e - p.11/25
Propriétés
Réflexivité:
g=O(g)Transitivité :sif=O(g)etg=O(h)alorsf=O(h)Produit par un scalaire :O(λf) =O(f),λ >0.Somme et produit de fonctions :
O(f)+O(g)=O(max{f,g})O(f).O(g)=O(f.g)
Complexit
´e - p.12/25
Complexité d'une boucle
pouri←1ànfaire s finpour avec s=O(1).Temps de calcul des:Ts=CNombre d'appels des: nTemps de calcul total :T(n) =nTs=O(n)Complexité :O(n)
Complexit
´e - p.13/25
Boucles imbriquées
Théorème 1La complexité depboucles imbriquées de 1 ànne contenant que des instructions élémentaires est en O(np)Preuve:
vrai pourp= 1,supposons la ppt vrai à l'ordrep. Soit : pouri←1ànfaire instruction finpourComplexit´e - p.14/25
Boucles tant que
h←1 h←2*h fintantqueTest, multiplication, affectation :O(1):T=CNombre d'itérations :log2(n).Temps de calcul :T(n) =Clog2(n) =O(log2(n))
Complexit
´e - p.15/25
Complexité d'un algorithme récursif (1)
Soit l'algorithme :
fonctionfactorielle(n: Naturel) :Naturel début sin = 0alors retourner1 sinon retournern*factorielle(n-1) finsi finComplexit
´e - p.16/25
Complexité d'un algorithme récursif (2)
c1test,c2multiplication.
T(0)=c1T(n)=c1+c2+T(n-1)
?T(n) =nc2+ (n+ 1)c1SoitC= 2max{c1,c2}
Complexité enO(n).
Les calculs de complexité d'algorithmes récursifs induisent naturellement des suites.Complexit
´e - p.17/25
Algorithmes récursifs enO(log2(n))(1)
Théorème 2Soient,debut,finetn=fin-debuttrois entiers. La complexité de l'algorithme ci dessous est enO(log2(n)). procéduref(debut,fin)Déclaration Entiermilieu
début milieu←debut+fin2sifin-milieu>1 et milieu-debut>1alors
s sinon sitestalors f (debut,milieu) sinon f (milieu,fin) finsi finsi finComplexit´e - p.18/25
Algorithmes récursifs enO(log2(n))(2)
Tests, s :O(1)
T(n) =T(n
2) +C T(n2) =T(n
4) +C...=...
T(1) =T(0) +C
T(n) =T(0) +Clog2(n)
Complexit´e - p.19/25
Algorithmes récursifs enO(nlog2(n))(1)
procéduref(debut,fin)Déclaration Entiermilieu
début milieu←debut+fin2sifin-milieu>1 et milieu-debut>1alors
s1sinon
pouri←1ànfaire s2finpourf(début,milieu)f(milieu,fin)
finsi finComplexit
´e - p.20/25
Algorithmes récursifs enO(nlog2(n))(2)
Tests, s :O(1)Boucle :O(n).
T(n) =n+ 2T(n
2) 2T(n 2) n+ 4T(n4)...=...
2 p-1T(2) =n+ 2pT(1)T(n) =n?p+ 2p?T(1)
avecp= [log2(n)]On a de plus:O(nlog2(n) +nT(1)) =O(nlog2(n))
Complexit´e - p.21/25
Principales complexités
O(1): temps constant,O(log(n)): complexité logarithmique (Classe L),O(n): complexité linaire
(Classe P), O(nlog(n))O(n2),O(n3),O(np): quadratique, cubique,polynomiale (Classe P),O(pn)complexité exponentielle
(ClasseEXPTIME)".
O(n!)complexité factorielle.
Complexit
´e - p.22/25
Influence de la complexité
n→2n. O(1)O(log2(n))
O(n)O(nlog2(n))
O(n2) O(n3) O(2n) t t+ 1 2t2t+ 2n
4t 8t t2 1 log2(n) n nlog2(n) n2 n3 2n n= 1021μs
6μs
0.1ms 0.6ms 10ms 1s4×1016a
n= 1031μs
10μs
1ms 10ms 1s16.6min
n= 1041μs
13μs
10ms 0.1s 100s11,5j n= 105
1μs
17μs
0.1s 1.6s 2.7h 32an= 106
1μs
20μs
1s 19.9s 11,5j32×103a
∞Complexit´e - p.23/25Limites de la complexité
La complexité est un résultat asymptotique : un algorithme enO(Cn2)peut être plus efficace qu'un algorithme enO(C?n)pour de petites valeurs den siC?C?,Les traitements ne sont pas toujours linéaires?Il ne faut pas supposer d'ordres de grandeur entre les différentes constantes.Complexit
´e - p.24/25
Conseils
Qualités d'un algorithme :
1. Maintenable (facile à comprendre, coder, déboguer),
2. Rapide
Conseils :
1. Privilégier le point 2 sur le point 1 uniquement si on gagne en complexité.
2. "ce que fait» l'algorithme doit se lire lors d'une lecture rapide : Une idée
par ligne. Indenter le programme.3. Faire également attention à la précision, la stabilité et la sécurité.
La rapidité d'un algorithme est un élément d'un tout définissant les qualités de celui-ci.Complexit
´e - p.25/25
quotesdbs_dbs41.pdfusesText_41[PDF] exercice récursivité algorithme
[PDF] exercices corrigés récursivité python
[PDF] exercices récursivité
[PDF] exercice algorithme avec solution recursivité
[PDF] fonction récursive exercice corrigé python
[PDF] algorithme récursif exemple
[PDF] fonction recursive langage c
[PDF] fonction récursive exercice corrigé
[PDF] recursivite java
[PDF] la récursivité en algorithme exercice corrigé
[PDF] leo traduction
[PDF] récursivité python exercices corrigés
[PDF] exercices récursivité python
[PDF] récursivité algorithme exercice corrigé