Inscription / Connexion Nouveau Sujet
Niveau calculatrices
Partager :

algorithme

Posté par nzilegrand (invité) 04-05-06 à 12:35

bonjours à  tous .mon exercice set le suivant:  ecrire un algorithme  qui recherche parmis 3 nombres le plus petits.en fait l'algorithme est un  programme qu'on veut integrer dans une machine.


                                                                                                  

Posté par philoux (invité)re : algorithme 04-05-06 à 12:42

bonjour

a, b, c les 3 nombres

X désigne comme le plus petit

début

X=a

Si X>b alors X=b

Si X>c alors X=c

fin

Y'a sûrement plus simple et plus structuré

Philoux

Posté par
Ksilver
re : algorithme 04-05-06 à 14:34

"Y'a sûrement plus simple et plus structuré"


non, je pense que la on aproche de la perfection ! (en tous cas en nombre d'operation a executé on peut pas faire mieux je pense )

Posté par
enzo
re : algorithme 04-05-06 à 14:39

Il n'y a pas d'algo de complexité inférieure en effet.

Posté par philoux (invité)re : algorithme 04-05-06 à 14:42

bonjour

comment est définie la complexité d'un algorithme ?

nombre d'opérations, natures des opérations, nombre de lignes, nombre de variables, routines/subroutines... ?

Philoux

Posté par
enzo
re : algorithme 04-05-06 à 14:49

En fait, c'est assez difficile à définir.

Disons que c'est le nombre d'opérations élémentaires (que ce soit une opération arithmétique, une comparaison, un accès à une source externe)...

généralement, on se concentre sur une ou deux opérations précises (celles qui sont "intéressantes")

Par exemple, dans un algo de tri, tu t'intéresse au nombre de comparaison effectuées.

Posté par philoux (invité)re : algorithme 04-05-06 à 14:51

merci

celà dépend-t-il du processeur ? du langage ?  de la structure des données ?

Philoux

Posté par
enzo
re : algorithme 04-05-06 à 14:53

pour le temps de calcul oui, mais le calcul de la complexité ne doit pas faire intervenir la vitesse du processeur, le langage,...

L'utilité de la théorie de la complexité est de comparer des algos qui sont sensés faire la même chose sur les mêmes données. Elle doit donc s'affranchir de toutes source de "perturbation" externe..

Posté par philoux (invité)re : algorithme 04-05-06 à 14:54

...toutes choses égales par ailleurs...

Philoux

Posté par
enzo
re : algorithme 04-05-06 à 14:55

exactement

Posté par
Ksilver
re : algorithme 04-05-06 à 16:47

sa depend de quoi on parle en fait... on compte ce qu'on apelle une operation elementaires... mais "l'operation elementaire" n'est pas toujour tres bien definit... (et de toute facon un temps de calcule est toujour sous la forme d'un O(g(n)), j'aimmais de valeur precise)


par exemple l'exponentiation modulair pour le calcule de x^n est en O(lg n) si on travaille sur une representation des nombres a p bit fixé, en O(lg x * n^2) si on travaille sur un entier x "long" alors que a la base, c'est exactement le meme algo



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !