[PDF] Complexité en algorithmique Complexité : suite de Fibonacci. Temps





Previous PDF Next PDF



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.
Complexité en algorithmique

Complexite en algorithmique

Gilles Aldon, Jer^ome Germoni, Jean-Manuel Meny

IREM de Lyon

Mars 2012

GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 1 / 21

Complexite

Trois questions essentielles

Un algorithme a pour objectif la resolution d'un probleme.

Est-ce que l'algorithme donne...1une reponse?;terminaison2la bonne reponse?;correction3la bonne reponse en un temps acceptable?;complexiteGA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 2 / 21

Complexite

Trois questions essentielles

Un algorithme a pour objectif la resolution d'un probleme.

Est-ce que l'algorithme donne...1une reponse?;terminaison2la bonne reponse?;correction3la bonne reponse en un temps acceptable?;complexiteGA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 2 / 21

Complexite

Trois questions essentielles

Un algorithme a pour objectif la resolution d'un probleme.

Est-ce que l'algorithme donne...1une reponse?;terminaison2la bonne reponse?;correction3la bonne reponse en un temps acceptable?;complexiteGA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 2 / 21

Complexite

Trois questions essentielles

Un algorithme a pour objectif la resolution d'un probleme.

Est-ce que l'algorithme donne...1une reponse?;terminaison2la bonne reponse?;correction3la bonne reponse en un temps acceptable?;complexiteGA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 2 / 21

ComplexiteTerminaison, correction

Terminaison

Preuve de terminaison

Mise en evidence d'un

converge nt , i.e. une quantite qui diminue a chaque passage, vivant dans un ensemble bien fonde (ou il n'existe pas de suites innies strictement decroissantes).AlgorithmePGCD

Entree: a , b entiers

Sortie: un entier

Variables locales: x , y , r

x := a ; y := b ; tant quey != 0faire r := restedela divisiondex par y x := y y := r// renvoyerxGA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 3 / 21

ComplexiteTerminaison, correction

Terminaison

Preuve de terminaison

Mise en evidence d'un

converge nt , i.e. une quantite qui diminue a chaque passage, vivant dans un ensemble bien fonde (ou il n'existe pas de suites innies strictement decroissantes).AlgorithmePGCD

Entree: a , b entiers

Sortie: un entier

Variables locales: x , y , r

x := a ; y := b ; tant quey != 0faire r := restedela divisiondex par y x := y y := r//nouvellevaleur de y ComplexiteTerminaison, correction

Correction - validite

Preuve de correction

Mise en evidence d'un

inva riantde b oucle , i.e. une assertion qui est vraie avant l'entree dans la boucle et qui, si elle est vraie au debut d'un passage, reste vraie en n de passage. Donc vraie en sortie.AlgorithmePGCD

Entree: a , b entiers

Sortie: un entier//

Variables locales: x , y , r

x := a ; y := b ;// tant quey != 0faire r := restedela divisiondex par y x := y// y := r// renvoyerx//GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 4 / 21

ComplexiteTerminaison, correction

Correction - validite

Preuve de correction

Mise en evidence d'un

inva riantde b oucle , i.e. une assertion qui est vraie avant l'entree dans la boucle et qui, si elle est vraie au debut d'un passage, reste vraie en n de passage. Donc vraie en sortie.AlgorithmePGCD

Entree: a , b entiers

Sortie: un entier// D(a;b) =diviseurs communs

Variables locales: x , y , r

x := a ; y := b ;//D (a;b) =D(x;y) tant quey != 0faire r := restedela divisiondex par y x := y// y := r// renvoyerx//GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 4 / 21

ComplexiteTerminaison, correction

Correction - validite

Preuve de correction

Mise en evidence d'un

inva riantde b oucle , i.e. une assertion qui est vraie avant l'entree dans la boucle et qui, si elle est vraie au debut d'un passage, reste vraie en n de passage. Donc vraie en sortie.AlgorithmePGCD

Entree: a , b entiers

Sortie: un entier//

Variables locales: x , y , r

x := a ; y := b ;// D(a;b) =D(x;y) tant quey != 0faire r := restedela divisiondex par y x := y//x =qy+r;0rComplexiteTerminaison, correction

Correction - validite

Preuve de correction

Mise en evidence d'un

inva riantde b oucle , i.e. une assertion qui est vraie avant l'entree dans la boucle et qui, si elle est vraie au debut d'un passage, reste vraie en n de passage. Donc vraie en sortie.AlgorithmePGCD

Entree: a , b entiers

Sortie: un entier//

Variables locales: x , y , r

x := a ; y := b ;// D(a;b) =D(x;y) tant quey != 0faire r := restedela divisiondex par y x := y// x=qy+r;0rComplexiteComplexite : suite de Fibonacci

Complexite : la suite de Fibonacci

Calcul des nombres de Fibonacci (fn)n2Ndenis par

f

0=f1= 1;8n2Nn f0;1g;fn=fn1+fn2:

Trois algorithmes :algorithme recursif,

algorithme iteratif, calcul de puissances. GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 5 / 21

ComplexiteComplexite : suite de Fibonacci

Temps de calcul avec l'algorithme recursif

Algorithmefibrec (n : entier )

sin<2alors renvoyer1 sinon renvoyerfibrec (n1)+fibrec (n2) Mise en place et mesure des temps de calculInstructions utiles

XcasSage

dessin de listeslistplot(L)list_plot(L) mesure du tempstime(calcul)t = cputime() calculs t = cputime()-t GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 6 / 21

ComplexiteComplexite : suite de Fibonacci

Temps de calcul avec l'algorithme recursif

Algorithmefibrec (n : entier )

sin<2alors renvoyer1 sinon renvoyerfibrec (n1)+fibrec (n2) Mise en place et mesure des temps de calculInstructions utiles

XcasSage

dessin de listeslistplot(L)list_plot(L) mesure du tempstime(calcul)t = cputime() calculs t = cputime()-t GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 6 / 21

ComplexiteComplexite : suite de Fibonacci

Complexite de l'algorithme recursif

Algorithmefibrec (n : entier )

sin<2alors renvoyer1 sinon renvoyerfibrec (n1)+fibrec (n2)

Operations elementaires :a

nappels a la fonctionfib_rec(et tests),s nsommes.

Evaluation de (an)a

0=a1= 0;8n2;an= 1 +an1+ 1 +an2;

La suite (an+ 2) satisfait a une relation de recurrence lineaire.

Consequence :an=Cn+C00nCn, ou=1+p5

2 ,C;C0>0.GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 7 / 21

ComplexiteComplexite : suite de Fibonacci

Complexite de l'algorithme recursif

Algorithmefibrec (n : entier )

sin<2alors renvoyer1 sinon renvoyerfibrec (n1)+fibrec (n2)

Operations elementaires :a

nappels a la fonctionfib_rec(et tests),s nsommes.

Evaluation de (an)a

0=a1= 0;8n2;an= 1 +an1+ 1 +an2;

La suite (an+ 2) satisfait a une relation de recurrence lineaire.

Consequence :an=Cn+C00nCn, ou=1+p5

2 ,C;C0>0.GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 7 / 21

ComplexiteComplexite : suite de Fibonacci

Complexite de l'algorithme recursif

Algorithmefibrec (n : entier )

sin<2alors renvoyer1 sinon renvoyerfibrec (n1)+fibrec (n2)

Operations elementaires :a

nappels a la fonctionfib_rec(et tests),s nsommes.

Evaluation de (an)a

0=a1= 0;8n2;an= 1 +an1+ 1 +an2;

La suite (an+ 2) satisfait a une relation de recurrence lineaire.

Consequence :an=Cn+C00nCn, ou=1+p5

2 ,C;C0>0.GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 7 / 21

ComplexiteComplexite : calcul de puissances

Aparte : calcul de puissances

Probleme : calculerxn(nentier) en minimisant le nombre de multiplications.

AlgorithmeNaive (x , n : entier )

sin=0alors renvoyer1 sinon renvoyerNaive (x ,n1)x

AlgorithmepuissRec (x , n : entier )

sin=0alors renvoyer1 sinon sin pair y = puissRec (x , n/2) renvoyeryy sinon y = puissRec (x ,( n1)/2) renvoyerxyyGA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 8 / 21

ComplexiteComplexite : calcul de puissances

Nombre d'operations dans un calcul de puissances

Probleme : calculerxn(nentier) en minimisant le nombre de multiplications.

AlgorithmenbPuissanceNaive (n : entier )

sin=0alors renvoyer0 sinon renvoyernbPuissanceNaive (n1)+1

AlgorithmenbPuissanceRec (n : entier )

sin=0alors renvoyer0 sinon sin pair renvoyerpuissRec (n/2)+1 sinon renvoyerpuissRec ((n1)/2)+2GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 9 / 21

ComplexiteComplexite : calcul de puissances

Nombre d'operations dans un calcul de puissances

Comptage des operations

Soitnun entier non nul, [ar;ar1;:::;a1;a0] ses chires en base 2. Le nombre de produits faits par l'algorithme recursif est :M(n) =r1 +ar+ar1++a1+a0:

Il est donc compris entrer= log(n) et 2log(n).Par recurrence surr.Sinest pair :a0= 0 etn=2 = [ar;:::;a1], d'ou :

M(n) =M(n2

)+1 =r2+ar++a1+1 =r1+ar++a1+a0:Sinest impair :a0= 1 et (n1)=2 = [ar;:::;a1], d'ou :

M(n) =M(n12

)+2 =r2+ar++a1+2 =r1+ar++a1+a0:GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 10 / 21

ComplexiteComplexite : calcul de puissances

Nombre d'operations dans un calcul de puissances

Comptage des operations

Soitnun entier non nul, [ar;ar1;:::;a1;a0] ses chires en base 2. Le nombre de produits faits par l'algorithme recursif est :M(n) =r1 +ar+ar1++a1+a0:

Il est donc compris entrer= log(n) et 2log(n).Par recurrence surr.Sinest pair :a0= 0 etn=2 = [ar;:::;a1], d'ou :

M(n) =M(n2

)+1 =r2+ar++a1+1 =r1+ar++a1+a0:Sinest impair :a0= 1 et (n1)=2 = [ar;:::;a1], d'ou :

M(n) =M(n12

)+2 =r2+ar++a1+2 =r1+ar++a1+a0:GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 10 / 21

ComplexiteComplexite : calcul de puissances

Application : suite de Fibonacci par les puissances

Pose, pour toutnentier :

F n=fnfn+1:

Alors :

F n+1=fn+1fn+fn+1=FnAouA=0 1 1 1 :D'ou : F n=F0An=F1An+1ouF1=f1f0=0 1:

Ainsi,Fnest la deuxieme ligne deAn+1.Inter^et

Calcul deAn+1enO(logn) operations arithmetiques.

NB : Formule de Binet en diagonalisantA.GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 11 / 21

ComplexiteComplexite : calcul de puissances

Application : suite de Fibonacci par les puissances

Pose, pour toutnentier :

F n=fnfn+1:

Alors :

F n+1=fn+1fn+fn+1=FnAouA=0 1 1 1 :D'ou : F n=F0An=F1An+1ouF1=f1f0=0 1:

Ainsi,Fnest la deuxieme ligne deAn+1.Inter^et

Calcul deAn+1enO(logn) operations arithmetiques.

NB : Formule de Binet en diagonalisantA.GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 11 / 21

ComplexiteComplexite :

les trianglesComplexite en seconde ou premiere : un exemple simple pour le lycee

Ecrireleprogramme suivant :

Entree: un entier naturelp>0.

Sortie: les triangles a c^otes entiers, rectangles, de perimetrep.Premiere version :

Algorithmetrianglesentiersv0 (p : entier )

pourade1jusquep : pourbde1jusquep : pourcde1jusquep : tester le t r i p l e t (a ,b , c) stocker (a ,b , c)sisatisfaisant renvoyerl i s t e des t r i p l e t sGA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 12 / 21

ComplexiteComplexite :

les trianglesComplexite en seconde ou premiere : un exemple simple pour le lycee

Ecrireleprogramme suivant :

Entree: un entier naturelp>0.

Sortie: les triangles a c^otes entiers, rectangles, de perimetrep.Premiere version :

Algorithmetrianglesentiersv0 (p : entier )

pourade1jusquep : pourbde1jusquep : pourcde1jusquep : tester le t r i p l e t (a ,b , c) stocker (a ,b , c)sisatisfaisant renvoyerl i s t e des t r i p l e t sGA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 12 / 21

ComplexiteComplexite :

les trianglesPremiere approche experimentale

Sur une calculatrice Ti82, plus de 5 secondes pour un perimetrep= 10.Hypothese de proportionnalite temps { nombre de boucles.

Quel temps pour un perimetrep= 1000?

5100336002458 joursGA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 13 / 21

ComplexiteComplexite :

les trianglesPremiere approche experimentale

Sur une calculatrice Ti82, plus de 5 secondes pour un perimetrep= 10.Hypothese de proportionnalite temps { nombre de boucles.

Quel temps pour un perimetrep= 1000?

5100336002458 joursGA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 13 / 21

ComplexiteComplexite :

les trianglesComplexite : les triangles entiers

Amelioration de l'algorithme :

Algorithmetrianglesentiersv1 (p : entier )

pourade1jusquep/3: pourbdeajusque floor((pa)/2) tester le t r i p l e t (a ,b ,pab) stocker (a ,b ,pab)sisatisfaisant renvoyerl i s t ed e st r i p l e t s Comparer les temps de calcul experimentalement et expliquer.

FICHIER SAGE

GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 14 / 21

ComplexiteComplexite :

les trianglesComplexite : les triangles entiers

Evaluation de la complexite

Premiere version :

Nombre de tests :p3.Seconde version :

Nombre de tests :

dp=3eX a=1 p2 a+ 1 619
p(p+ 3)GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 15 / 21

ComplexiteComplexite :

les trianglesComplexite : les triangles entiers

Evaluation de la complexite

Premiere version :

Nombre de tests :p3.Seconde version :

Nombre de tests :

dp=3eX a=1 p2 a+ 1 619
p(p+ 3)GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 15 / 21

ComplexiteComplexite : tri par selection

Complexite et ISN : tri par selection

Le principe du tri par selection d'une listeT= (T[1];T[2];:::;T[n]) : Pour chaque entierj(16j6n1) :parcourir les elementsT[j],T[j+ 1], ...,T[n], retenir l'indicekdu plus petit.placer au rangjle plus petit des elementsT[j],T[j+ 1], ...,T[n] (en echangeantT[j] etT[k]).GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 16 / 21

ComplexiteComplexite : tri par selection

Tri par selection : illustration

215094

1594

015294

012594

012495

012459

GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 17 / 21

ComplexiteComplexite : tri par selection

Tri par selection : illustration

215094

015294

015294

012594

012495

012459

GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 17 / 21

ComplexiteComplexite : tri par selection

Tri par selection : illustration

215094

015294

015294

012594

012495

012459

GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 17 / 21

ComplexiteComplexite : tri par selection

Tri par selection : illustration

215094

015294

015294

012594

012495

012459

GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 17 / 21

ComplexiteComplexite : tri par selection

Tri par selection : illustration

215094

015294

015294

012594

012495

012459

GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 17 / 21

ComplexiteComplexite : tri par selection

Tri par selection : illustration

215094

015294

015294

012594

012495

012459

GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 17 / 21

ComplexiteComplexite : tri par selection

Tri par selection : illustration

215094

015294

015294

012594

012495

012459

GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 17 / 21

ComplexiteComplexite : tri par selection

Tri par selection

Entree: T liste de nombres de taillen

Sortie: liste T triee

Traitement:

Pourjde 1 an1

indiceMin :=j

Pourkdej+ 1 an

siT[k]Echange deT[j] etT[indiceMin] sij6= indiceMin nPour GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 18 / 21

ComplexiteComplexite : tri par selection

Complexite : tri par selection

Complexite experimentale : chier SAGE ou chier XCAS...second degre

Nombre de comparaisons :

n1X j=10 nX k=j+111 A =n1X j=1(nj) =12 n(n1) Nombre d'echanges : au plus le nombre de comparaisons. GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 19 / 21

ComplexiteComplexite : tri par selection

Complexite : tri par selection

Complexite experimentale :second degre

Nombre de comparaisons :

n1X j=10 nX k=j+111 A =n1X j=1(nj) =12 n(n1) Nombre d'echanges : au plus le nombre de comparaisons. GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 19 / 21

ComplexiteComplexite : tri par selection

Complexite : tri par selection

Complexite experimentale :second degre

Nombre de comparaisons :

n1X j=10 nX k=j+111 A =n1X j=1(nj) =12 n(n1) Nombre d'echanges : au plus le nombre de comparaisons. GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 19 / 21

ComplexiteComplexite : tri par selection

Complexite en 1

e: evaluation d'un polyn^ome en une valeur Entree: un polyn^omep(liste de ses coecients) et une valeur reellex.

Sortie:p(x)

Exemples avec SAGE.

GA, JG, JMM (IREM de Lyon)ComplexiteMars 2012 20 / 21

ComplexiteComplexite : tri par selection

Quelques remarques sur la complexite

Notion d'operation elementaire dependante du contexte. Principe : evaluer (majorer) le nombre d'operations en fonction de la taille des donnees (valeur d'un argument, nombre de mots, nombre d'inconnues, nombre de chires...).Exemples : Cryptographie RSA et factorisation : pour un nombre a 100 chires, 10

50tests nafs = trop!Algorithme de Gauss : complexite enO(n3) si les nombres ont une

taille xe ( ottants, corps nis; pas rationnels...).quotesdbs_dbs33.pdfusesText_39
[PDF] leviers de mobilisation

[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