Algorithmique Notion de complexité









Logarithme binaire : rappel sur la représentation des entiers en

Le logarithme binaire ou logarithme de base 2 d'un entier positif n est (approximativement) le nombre de chiffres dans l'écriture binaire de n. Définition 
.Logarithme base


Algorithmique Notion de complexité

logarithme de base a : loga(x) = lnx lna log fonction logarithme sans base précise à une constante multiplicative près log2 logarithme binaire
Complexite


Neper et le calcul binaire

Neper et le calcul binaire. Michel Mouyssinat 1. L'utilisation des logarithmes par Neper en 1612 pour constituer des tables propres à simplifier les calculs 


V.607-2 - Termes et symboles relatifs aux quantités d'information en

événements s'excluant mutuellement exprimée par un logarithme binaire. Exemple: La quantité de décision sur un jeu de caractères de huit caractères est 
R REC V. S!!PDF F





math202 : mathématiques pour le numérique TD 1 : binaire codage

Partie 2 : exponentielle et logarithme binaires. Question 1. Sur Youtube en 2014
td


Algorithmique Notion de complexité

log fonction logarithme sans base précise à une constante multiplicative près log2 fonction logarithme binaire
Complexite


Mathématiques pour l'Informatique I (Notes de cours) L1 UMLV

10 févr. 2014 Pour le cas binaire il faut. ⌈log2 n⌉ bits. 1.4 Rappels sur le logarithme en base 2. On rappelle que pour tout réel x > 0
L


Analyse d'une variable binaire et de plusieurs variables continues

la distribution conjointe d'une variable aléatoire binaire et de plusieurs où : LI (y; P V) est le logarithme de la vraisemblance d'un modèle linéaire.
RSA





ALGO1 – File de priorité et tas binaire

18 févr. 2021 Proposition 3 Un arbre binaire presque complet `a n nœuds est de hauteur ... En passant au log on obtient le résultat de la proposition.
tas


Fonctions logarithmes en terminale D

Le logarithme binaire qui utilise 2 comme base
RCB Cours


211902
ou
Algorithmique Notion de complexité

1 de 27

Algorithmique

Notion de complexité

Florent Hivert

Mél :Florent.Hivert@lri.fr

Adresse universelle :http://www-igm.univ-mlv.fr/˜hivert

Outils mathématiques

2 de 27Outils mathématiques : analyse élémentaire

(Uk)k2Nsuite de terme généralUk,k2N (Uk)k2Kfamille d"indexKN; suite extraite de(Uk)k2N q X k=pU ksomme des termesUkoùkvérifiepkq(entiers); lorsquep>q, la somme estvideet vaut 0 qY k=pU kproduit des termesUkoùkvérifiepkq(entiers); lorsquep>q, le produit estvideet vaut 1

Outils mathématiques

3 de 27Identité sur les sommes et produits

q X k=pU k=0 @q1X k=pU k1 A +Uq=Up+0 @qX k=p+1U k1 A Plus généralement, siP(n)est un prédicat : q X k=pU k=qX k=p

P(k)est vraiU

k+qX k=p

P(k)est fauxU

k

Un exemple très courant :

n X k=1U k=nX k=1kest pairU k+nX k=1kest impairU k

Idem pour les produits.

Outils mathématiques

4 de 27Outils mathématiques : arithmétique

opérateurs usuels : + = Outils mathématiques

5 de 27Parties entières et égalités

Pour tout réelx, pour tout entiern:bxc=n()nxPour tout entiern:n=bn=2c+dn=2e:

Outils mathématiques

6 de 27Parties entières et inégalités

Pour tout réelx, pour tout entiern:bxcOutils mathématiques

7 de 27Fonctions usuelles

ln fonction logarithme népérien (ou naturel), de basee log afonction logarithme de basea: loga(x) =lnx=lna log fonction logarithme sans base précise,à une constante multiplicative près log

2fonction logarithme binaire, de base 2 :

log

2(x) =lnx=ln2

Outils mathématiques

8 de 27Complexités

Définitions (complexités temporelle et spatiale)

complexité temporelle: (ouen temps) : temps de calcul;complexité spatiale: (ouen espace) : l"espace mémoire

requis par le calcul.Définitions (complexités pratique et théorique) Lacomplexité pratiqueest une mesure précise des complexités temporelles et spatiales pour unmodèle de machine donné.Lacomplexité (théorique)est unordre de grandeurde ces couts, exprimé de manière la plusindépendantepossible des conditions pratiques d"exécution.

Outils mathématiques

9 de 27Un exemple

Problème (plus grand diviseur)

Décrire une méthode de calcul du plus grand diviseur autre que lui-même d"un entier n2.Notonspgd(n)le plus grand diviseur en question.

On a :1pgd(n)n1;pgd(n) =1()nest premier.

Outils mathématiques

9 de 27Un exemple

Problème (plus grand diviseur)

Décrire une méthode de calcul du plus grand diviseur autre que lui-même d"un entier n2.Notonspgd(n)le plus grand diviseur en question.On a :

1pgd(n)n1;pgd(n) =1()nest premier.

Outils mathématiques

10 de 27Algorithme (1)

Puisqu"il s"agit de trouver le plus grand diviseur, on peut procéder en décroissant sur les diviseurs possibles :

1k n1à voirvus

Algorithme

calcul du plus grand diviseur (solution 1)

Entrée : un entier n

Sortie : pgd(n)

k n1 tant que nmodk6=0: k k1 retourner k

Outils mathématiques

10 de 27Algorithme (1)

Puisqu"il s"agit de trouver le plus grand diviseur, on peut procéder en décroissant sur les diviseurs possibles :

1k n1à voirvus

Algorithme

calcul du plus grand diviseur (solution 1)

Entrée : un entier n

Sortie : pgd(n)

k n1 tant que nmodk6=0: k k1 retourner k

Outils mathématiques

10 de 27Algorithme (1)

Puisqu"il s"agit de trouver le plus grand diviseur, on peut procéder en décroissant sur les diviseurs possibles :

1k n1à voirvus

Algorithme

calcul du plus grand diviseur (solution 1)

Entrée : un entier n

Sortie : pgd(n)

k n1 tant que nmodk6=0: k k1 retourner k

Outils mathématiques

11 de 27Algorithme (2)

Remarque : le résultat cherché estnp, oùpest leplus petit diviseur supérieur ou égal à 2 den.

Notonsppd(n)le plus petit diviseur en question.

2k nvusà voir

Algorithme (calcul du plus grand diviseur (solution 2))

Entrée : un entier n

Sortie : pgd(n)

k 2 tant que nmodk6=0: k k+1 retourner n=k

Outils mathématiques

11 de 27Algorithme (2)

Remarque : le résultat cherché estnp, oùpest leplus petit diviseur supérieur ou égal à 2 den.

Notonsppd(n)le plus petit diviseur en question.

2k nvusà voir

Algorithme (calcul du plus grand diviseur (solution 2))

Entrée : un entier n

Sortie : pgd(n)

k 2 tant que nmodk6=0: k k+1 retourner n=k

Outils mathématiques

12 de 27Algorithme (3)

On peut maintenant tenir compte de ce que :

nnon premier=)2ppd(n)pgd(n)n1:

D"où il vient que :

nnon premier=)(ppd(n))2n:Proposition Si n ne possède pas de diviseur compris entre2etbpnc, c"est qu"il est premier;Cece permet d"améliorerle temps de calcul pour les nombres premiers : il est donc inutile de chercher en croissant entre bpnc+1 etn.

Outils mathématiques

13 de 27Algorithme (3)

En procédant en croissant sur les diviseurs possibles :

2kbpncnvusà voirà ne pas voir

Algorithme (calcul du plus grand diviseur (solution 3))

Entrée : un entier n

Sortie : pgd(n)

k 2 tant que nmodk6=0et kn=k : k k+1 si k>n=k retourner1sinon retourner n=k

Outils mathématiques

13 de 27Algorithme (3)

En procédant en croissant sur les diviseurs possibles :

2kbpncnvusà voirà ne pas voir

Algorithme (calcul du plus grand diviseur (solution 3))

Entrée : un entier n

Sortie : pgd(n)

k 2

1 de 27

Algorithmique

Notion de complexité

Florent Hivert

Mél :Florent.Hivert@lri.fr

Adresse universelle :http://www-igm.univ-mlv.fr/˜hivert

Outils mathématiques

2 de 27Outils mathématiques : analyse élémentaire

(Uk)k2Nsuite de terme généralUk,k2N (Uk)k2Kfamille d"indexKN; suite extraite de(Uk)k2N q X k=pU ksomme des termesUkoùkvérifiepkq(entiers); lorsquep>q, la somme estvideet vaut 0 qY k=pU kproduit des termesUkoùkvérifiepkq(entiers); lorsquep>q, le produit estvideet vaut 1

Outils mathématiques

3 de 27Identité sur les sommes et produits

q X k=pU k=0 @q1X k=pU k1 A +Uq=Up+0 @qX k=p+1U k1 A Plus généralement, siP(n)est un prédicat : q X k=pU k=qX k=p

P(k)est vraiU

k+qX k=p

P(k)est fauxU

k

Un exemple très courant :

n X k=1U k=nX k=1kest pairU k+nX k=1kest impairU k

Idem pour les produits.

Outils mathématiques

4 de 27Outils mathématiques : arithmétique

opérateurs usuels : + = Outils mathématiques

5 de 27Parties entières et égalités

Pour tout réelx, pour tout entiern:bxc=n()nxPour tout entiern:n=bn=2c+dn=2e:

Outils mathématiques

6 de 27Parties entières et inégalités

Pour tout réelx, pour tout entiern:bxcOutils mathématiques

7 de 27Fonctions usuelles

ln fonction logarithme népérien (ou naturel), de basee log afonction logarithme de basea: loga(x) =lnx=lna log fonction logarithme sans base précise,à une constante multiplicative près log

2fonction logarithme binaire, de base 2 :

log

2(x) =lnx=ln2

Outils mathématiques

8 de 27Complexités

Définitions (complexités temporelle et spatiale)

complexité temporelle: (ouen temps) : temps de calcul;complexité spatiale: (ouen espace) : l"espace mémoire

requis par le calcul.Définitions (complexités pratique et théorique) Lacomplexité pratiqueest une mesure précise des complexités temporelles et spatiales pour unmodèle de machine donné.Lacomplexité (théorique)est unordre de grandeurde ces couts, exprimé de manière la plusindépendantepossible des conditions pratiques d"exécution.

Outils mathématiques

9 de 27Un exemple

Problème (plus grand diviseur)

Décrire une méthode de calcul du plus grand diviseur autre que lui-même d"un entier n2.Notonspgd(n)le plus grand diviseur en question.

On a :1pgd(n)n1;pgd(n) =1()nest premier.

Outils mathématiques

9 de 27Un exemple

Problème (plus grand diviseur)

Décrire une méthode de calcul du plus grand diviseur autre que lui-même d"un entier n2.Notonspgd(n)le plus grand diviseur en question.On a :

1pgd(n)n1;pgd(n) =1()nest premier.

Outils mathématiques

10 de 27Algorithme (1)

Puisqu"il s"agit de trouver le plus grand diviseur, on peut procéder en décroissant sur les diviseurs possibles :

1k n1à voirvus

Algorithme

calcul du plus grand diviseur (solution 1)

Entrée : un entier n

Sortie : pgd(n)

k n1 tant que nmodk6=0: k k1 retourner k

Outils mathématiques

10 de 27Algorithme (1)

Puisqu"il s"agit de trouver le plus grand diviseur, on peut procéder en décroissant sur les diviseurs possibles :

1k n1à voirvus

Algorithme

calcul du plus grand diviseur (solution 1)

Entrée : un entier n

Sortie : pgd(n)

k n1 tant que nmodk6=0: k k1 retourner k

Outils mathématiques

10 de 27Algorithme (1)

Puisqu"il s"agit de trouver le plus grand diviseur, on peut procéder en décroissant sur les diviseurs possibles :

1k n1à voirvus

Algorithme

calcul du plus grand diviseur (solution 1)

Entrée : un entier n

Sortie : pgd(n)

k n1 tant que nmodk6=0: k k1 retourner k

Outils mathématiques

11 de 27Algorithme (2)

Remarque : le résultat cherché estnp, oùpest leplus petit diviseur supérieur ou égal à 2 den.

Notonsppd(n)le plus petit diviseur en question.

2k nvusà voir

Algorithme (calcul du plus grand diviseur (solution 2))

Entrée : un entier n

Sortie : pgd(n)

k 2 tant que nmodk6=0: k k+1 retourner n=k

Outils mathématiques

11 de 27Algorithme (2)

Remarque : le résultat cherché estnp, oùpest leplus petit diviseur supérieur ou égal à 2 den.

Notonsppd(n)le plus petit diviseur en question.

2k nvusà voir

Algorithme (calcul du plus grand diviseur (solution 2))

Entrée : un entier n

Sortie : pgd(n)

k 2 tant que nmodk6=0: k k+1 retourner n=k

Outils mathématiques

12 de 27Algorithme (3)

On peut maintenant tenir compte de ce que :

nnon premier=)2ppd(n)pgd(n)n1:

D"où il vient que :

nnon premier=)(ppd(n))2n:Proposition Si n ne possède pas de diviseur compris entre2etbpnc, c"est qu"il est premier;Cece permet d"améliorerle temps de calcul pour les nombres premiers : il est donc inutile de chercher en croissant entre bpnc+1 etn.

Outils mathématiques

13 de 27Algorithme (3)

En procédant en croissant sur les diviseurs possibles :

2kbpncnvusà voirà ne pas voir

Algorithme (calcul du plus grand diviseur (solution 3))

Entrée : un entier n

Sortie : pgd(n)

k 2 tant que nmodk6=0et kn=k : k k+1 si k>n=k retourner1sinon retourner n=k

Outils mathématiques

13 de 27Algorithme (3)

En procédant en croissant sur les diviseurs possibles :

2kbpncnvusà voirà ne pas voir

Algorithme (calcul du plus grand diviseur (solution 3))

Entrée : un entier n

Sortie : pgd(n)

k 2
12345 Next
  1. logarithme binaire musique
  2. logarithme binaire informatique
  3. logarithme binaire calculatrice
  4. logarithme binaire en base 2
  5. logarithme binaire mots fléchés
  6. logarithme binaire python
  7. logarithme binaire formule
  8. logarithme binaire exemple