salut , parmi les définitions de la complexité je propose celle là :
on décrit un atome sous forme d'un algorithme informatique , on le compresse pour éliminer les répétitions , puis on compte le nombre d'octets .
je vous invite à décrire l'atome d’hydrogène , en algorithme informatique et d'estimer combien sera sa capacité en octet .
donc savoir la quantité d'information que contient l'atome d’hydrogène , merci .
je propose d'utiliser le qbit ,
pendant la téléportation d'un état quantique , on dira qu' un qbit a été téléporté .
et pour téléporter un atome d’hydrogène on aura combien de qbit à téléporter ? merci .
Dernière modification par noureddine2 ; 05/05/2012 à 12h44.
la question est compliquée , je vais simplifier :
comment mesurer la complexité d'une forme géométrique en octet ?
exemple , le cercle , le carré , le triangle ..ect
j'aimerais bien avoir des liens qui parlent de mesure de complexité comme celui là http://www.afscet.asso.fr/msc/textes...tz-19nov07.pdf
il parle d'algorithme , j'aimerai savoir quelle est l'unité de mesure de la complexité ? merci
Bjr à toi,Envoyé par noureddine2
Ce qui peut etre "complexe" pour toi, ne l'est pas forcément pour ton voisin
qui lui "comprends" mieux.
L'inverse peut etre vrai dans un domaine différent entre toi et ton voisin.
C'est donc...subjectif.
Ce n'est pas parce que la "description" (algortyme) est longue que c'est forcément...complexe. (mon sentiment perso)
Maintyenant si tu "juges" la complexicité aux nombres de " données" pour définir ton objet, il est sur qu'un objet de forme SIMPLE
nécessitera moins de données à définir qu'un objet "tarabiscoté".
Bonne Journée
salut , je pense que par respect pour les autres forumeurs , on doit toujours commencer un nouveau sujet par une introduction , et une question claire et simple , et au cours de la discution approfondir de plus en plus .
dans ce sujet je veux commencer par mesurer la complexité des formes géométriques , je cherche des liens ou même des discutions qui parlent de mesure de complexité pour se familiariser avec le sujet . merci .
Dernière modification par noureddine2 ; 06/05/2012 à 11h39.
je cherche des liens :
http://forums.futura-sciences.com/de...omplexite.html
http://fr.wikipedia.org/wiki/Suite_al%C3%A9atoire
http://forums.futura-sciences.com/de...omplexite.html
je cherche toujours l'unité de mesure de cette complexité .
d’après ce lien http://fr.wikipedia.org/wiki/Algorithme_de_tri
on a
je commence par Tri à bulles : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, stable et en place ; amusant mais pas efficaceTris par comparaison[modifier]
Algorithmes lents[modifier]
Ces algorithmes sont lents pour plus de 20 éléments parce qu'ils sont en O(n2).
Tri à bulles : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, stable et en place ; amusant mais pas efficace
Tri par sélection : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, pas stable si tri sur place ; rapide lorsque l'on a moins de 7 éléments
Tri par insertion : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, stable et en place. C'est le plus rapide et le plus utilisé pour des listes de moins de 15 éléments ;
Algorithmes plus rapides[modifier]
Tri de Shell (shell sort) : Amélioration du tri par insertion, mais pas stable. Complexité: au pire pour la série de pas et pour la série de pas . On ne connaît pas de série donnant .
Tri fusion (merge sort) : en moyenne et dans le pire des cas, stable mais pas en place3 ;
Tri rapide (quick sort) : en moyenne, mais en (quadratique) au pire cas4, en place mais pas stable
Introsort : Amélioration du tri rapide, qui permet une exécution en dans tous les cas.
Tri par tas (heap sort) : en moyenne et dans le pire des cas, en place mais pas stable. Toujours environ deux fois plus lent que le tri rapide, c'est-à-dire aux alentours de , il est donc intéressant de l'utiliser si l'on soupçonne que les données à trier seront souvent des cas quadratiques pour le tri rapide ;
Tri par ABR : en moyenne, dans le pire des cas. Ce tri est un des plus lents (parmi les tris rapides) et des plus gourmands en mémoire à cause de la structure d'arbre binaire à manipuler. Il est possible de le rendre dans tous les cas en maintenant un arbre équilibré (Arbre AVL).
Smoothsort : tri inspiré du tri par tas en utilisant un arbre non inversé, ce tri est très rapide pour les ensembles déjà presque triés, sinon, il est en . Tri en place mais pas stable
http://fr.wikipedia.org/wiki/Tri_%C3%A0_bulles
Le tri à bulles est souvent enseigné en tant qu'exemple algorithmique. Cependant, sa complexité est de l'ordre de n² en moyenne (où n est la taille du tableau), ce qui le classe parmi les mauvais algorithmes de tri. Il n'est donc quasiment pas utilisé en pratique.donc pour trier une série de n nombre , il faut un temps maximal proportionnel à n2 .Complexité[modifier]
Pour un tableau de taille n, le nombre d'itérations de la boucle externe « répéter … tant que aucun_échange = faux » est compris entre 1 et n. En effet, on peut démontrer qu'après la i-ème étape, les i derniers éléments du tableau sont à leur place. À chaque itération, il y a exactement n-1 comparaisons et au plus n-1 échanges.
Le pire cas (n itérations) est atteint lorsque le plus petit élément est à la fin du tableau. La complexité est alors Θ(n2).
En moyenne, la complexité est aussi Θ(n2). En effet, le nombre d'échanges de paires d'éléments successifs est égal au nombre d'inversions, c'est-à-dire de couples (i,j) tels que i < j et T(i) > T(j). Ce nombre est indépendant de la manière d'organiser les échanges. Lorsque l'ordre initial des éléments du tableau est aléatoire, il est en moyenne égal à n(n-1)/4 1.
Le meilleur cas (une seule itération) est atteint quand le tableau est déjà trié. Dans ce cas, la complexité est linéaire.
je vois que la complexité dépend du nombre d’étapes d’exécutions donc du temps d'exécutions .
je passe au : Tri par sélection : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, pas stable si tri sur place ; rapide lorsque l'on a moins de 7 éléments
http://fr.wikipedia.org/wiki/Tri_par_s%C3%A9lection
Description
Animation représentant le tri par sélection
Sur un tableau de n éléments (numérotés de 1 à n), le principe du tri par sélection est le suivant :
rechercher le plus petit élément du tableau, et l'échanger avec l'élément d'indice 1 ;
rechercher le second plus petit élément du tableau, et l'échanger avec l'élément d'indice 2 ;
continuer de cette façon jusqu'à ce que le tableau soit entièrement trié.
je retiens que le tri par sélection Sa complexité est donc Θ(n2).Complexité
Dans tous les cas, pour trier n éléments, le tri par sélection effectue n(n-1)/2 comparaisons. Sa complexité est donc Θ(n2). De ce point de vue, il est inefficace puisque les meilleurs algorithmes1 s'exécutent en temps O(nlog n). Il est même moins bon que le tri par insertion ou le tri à bulles, qui sont aussi quadratiques dans le pire cas mais peuvent être plus rapides sur certaines entrées particulières.
Par contre, le tri par sélection n'effectue que peu d'échanges :
et aussi : les meilleurs algorithmes1 s'exécutent en temps O(nlog n)
je veux étudier les algorithmes de tri , et après je vais passer à d'autres algorithmes , vous pouvez donner des remarques .
Salut,
Le n² n'est pas la complexité maximale du tri. Si tu veux je peux te pondre un algorithme en n³. On peut toujours faire pire
Le n.logn c'est le meilleur pour le tri. Mais j'ignore si c'est démontré (dans ce domaine les démonstrations sont parfois assez rare. Exemple, il n'y a pas si longtemps on n'était pas sur que les tests de primalité avaient une complexité polynomiale. Elle aurait pu être exponentielle. Jusqu'à ce que des informaticiens trouvent un algorithme en n^6 si je me souviens bien. Le 6 rend pratiquement l'algorithme inexploitable, mais ça donne de gros espoir d'améliorer. Jusqu'où ? Personne ne le sait).
Des remarques sur quoi ??? Il n'y a rien de spécial à dire. A part peut-être cela :
Vu la manière dont tu es partis avec l'atome, ne te casse pas la tête avec les algorithmes. Il y a plus simple.
Fait une liste des données nécessaire à la description d'un atome. Ca dépend du niveau de détail (et personne ne sait vraiment jusqu'où on peut / doit aller, je te propose de te limiter aux électrons, c'est déjà pas mal).
=> tu as la complexité maximale en bits
Maintenant il existe des liens entre ces données (par exemple entre le spin des électrons et leurs états). Ca peut diminuer le nombre de bits. Mais ça peut être assez compliqué (et inextricable si tu veux décrire le noyau). Et encore, c'est bien la méthode la plus simple que je te donne !!!!
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
La description d'un objet sans redondance d'information doit nous permettre de le re-construire, or on ne peut pas partir de rien. C'est quoi que nous devons prendre comme pré-existant ?
Patrick
Salut Patrick, pré-existant ne semble pas dans tes cordes, on peut partir de l'information (comme le font les ordinateurs), de bits pour arriver à l'intelligibilité (j'ai pas dit intelligence) !
C'est une autre façon de dire qu'il faut choisir un certain niveau de détail (sous-entendu, ce qui n'est pas détaillé, c'est ce qu'on prend pour faire cette reconstruction).
C'est impec d'expliquer de deux manières. Ca aidera peut-être Nouredinne à comprendre
Tiens, je me lance
Hydrogène atomique (sans détail des quarks) :
- position et mouvement du proton : 6 nombres réels
- état de l'électron : une série de 4 nombres entiers (n, l, m, s) indexant des nombres complexes (je considère le cas général d'une superposition quantique).
Reste à choisir une précision et un état maximal (n = un million serait quelque peu absurde, de même une précision de la position de a0/un milliard) et on peut calculer un nombre de bits
Si on se place dans le référentiel de l'atome, on peut enlever position et mouvement du proton.
Si on choisit volontairement l'état de base, reste deux nombres complexes pour l'état de spin (j'oubliais qu'il faut aussi préciser celui du proton => ajouter deux nombres complexes. Mais si on ne choisit pas de direction préférentielle seul compte l'orientation relative, ne reste plus que les deux nombres pour les deux états de spin).
Je choisir arbitrairement de coder mes nombres (réels) sur 8 bits (c'est peu). L'état de mon atome nécessite 32 bits.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
Oui, c'est en mon sens le point faible de se baromètre (description informationnelle) qui vise à fournir un référentiel de la complexité.
Patrick
merci , - position et mouvement du proton : 6 nombres réels je suppose que c'est : x, y , z , t ,m , v ,Hydrogène atomique (sans détail des quarks) :
- position et mouvement du proton : 6 nombres réels
- état de l'électron : une série de 4 nombres entiers (n, l, m, s) indexant des nombres complexes (je considère le cas général d'une superposition quantique).
Reste à choisir une précision et un état maximal (n = un million serait quelque peu absurde, de même une précision de la position de a0/un milliard) et on peut calculer un nombre de bits
est ce que c'est ça ?
- état de l'électron : une série de 4 nombres entiers (n, l, m, s) indexant des nombres complexes
je ne sais pas ce que veut dire : (n, l, m, s) , masse? spin ? orbital ?
Ah, non, pas tout à fait. Je ne considérais par le temps car j'avais en tête la description à un instant donné.
Je n'avais pas pensé à la masse. Mais celle-ci étant toujours la même pour l'hydrogène....
J'avais en tête la position x, y, z et la vitesse vx, vy, vz.
Si tu inclus le temps, alors ça donne trois fonctions x(t), y(t), z(t) (ça fait un paquet de nombres). Plus besoin de la vitesse (c'est la dérivée).
n = nombre quantique principal (n = 1 étant l'état de base, on l'appelle aussi "couche K", un nom qui vient des notations en spectroscopie est qui est très utilisé, autant en physique atomique qu'en chimie)
l = nombre quantique orbital (il vaut 0 pour l'état de base)
m = nombre quantique magnétique (il vaut 0 pour l'état de base)
s = nombre quantique de spin (-1/2 ou +1/2 pour l'électron de l'hydrogène. A noter que pour une orientation donnée du spin du proton il y a une toute petite différence d'énergie de l'état, c'est l'état antiparallèle qui est l'état de base, et la différence d'énergie appelée raie hyperfine est extrêmement petite).
Les énergies des états peuvent être dégénérées, ainsi si l'orientation du spin du proton est négligée, seul le nombre n donne l'énergie de l'électron dans l'atome d'hydrogène.
http://fr.wikipedia.org/wiki/Nombre_quantique
Tout ça complique un peu le calcul du nombre de bits. D'autant que cela dépend du niveau de détail (décrit-on le proton ou pas ? Et l'intérieur du proton ?), de la situation considérée (état de base ou pas ? Dans un référentiel donné ou pas ?) et de la précision (pour les nombres réels ou complexes). Mais ça donne une idée
L'idée que tu avais en tête, je suppose, est de TOUT décrire de l'atome. Mais dans ce cas, il faut prendre en compte les quarks du proton. Et j'ignore totalement comment décrire leur état dans le proton. Pour un noyau d'atome, c'est un peu plus facile, ça fonctionne grosso modo comme pour les électrons, avec quelques complications. Et il y a peut-être encore un niveau plus fondamental qu'on ignore.
Je pense que pour savoir comment aborder la complexité de la définition de la complexité () la toute première question que tu dois te poser, une question absolument capitale, est :
pourquoi est-ce que je veux décrire la complexité d'un atome (ou autre) ?
Savoir ce que tu veux en faire peut te servir de guide dans toutes ces difficultés.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
pour téléporter un atome , on doit le scanner en qbit ( états quantiques ), j'ai voulus connaitre le nombre de qbit que contient un atome d'hydrogène , j'ai sentis que ça doit être complexe , alors j'ai voulu me familiariser avec la les formules de la complexité .Je pense que pour savoir comment aborder la complexité de la définition de la complexité (
pourquoi est-ce que je veux décrire la complexité d'un atome (ou autre) ?
je me demande est ce qu'on peut utiliser les algorithmes pour représenter ou simuler un atome ? merci .
décrire l'atome est compliqué , je peux me contenter des formes géométriques , et pour me familiariser , je propose de continuer la révision des algorithmes de tri .
je suis arrivé au Tri par insertion : Algorithme quadratique, T(n) = O(n2), en moyenne et dans le pire des cas, stable et en place. C'est le plus rapide et le plus utilisé pour des listes de moins de 15 éléments ;
http://fr.wikipedia.org/wiki/Tri_par_insertion
Le tri par insertion est un algorithme de tri classique dont le principe est très simple. C'est le tri que la plupart des personnes utilisent naturellement pour trier des cartes : prendre les cartes mélangées une à une sur la table, et former une main en insérant chaque carte à sa place.vous pouvez donner des définitions sur la complexité .La complexité du tri par insertion est Θ(n2) dans le pire cas et en moyenne, et linéaire dans le meilleur cas. Plus précisément :
Dans le pire cas, atteint lorsque le tableau est trié à l'envers, l'algorithme effectue de l'ordre de n2/2 affectations et comparaisons1.
Si les éléments sont distincts et que toutes leurs permutations sont équiprobables, alors en moyenne, l'algorithme effectue de l'ordre de n2/4 affectations et comparaisons1.
Si le tableau est déjà trié, il y a n-1 comparaisons et O(n) affectations.
Il me semble qu'auparavant tu as un petit problème à résoudre, qui s'avère par contre très utile pour la cryptographie quantique.
Patrick
je sais que le clonage est impossible , et il y a destruction de la particule source pendant la téléportation , ça m’intéresse de connaitre l'information quantique
http://fr.wikipedia.org/wiki/Information_quantique
il y a aussi la cryptographie quantique http://fr.wikipedia.org/wiki/Cryptographie_quantique
les algorithmes jouent un rôle très important , dans le traitement de l'information .
Salut,
J'avais déjà lu qu'on avait calculé le nombre de bits à transmettre (par le canal classique) pour une hypothétique téléportation quantique d'un corps macroscopique (n'oublions pas que c'est l'état qui est téléporté et pas la matière, ce qui va justement dans le sens de ce qui a été dit). En particulier un corps humain.
Dans le cas des atomes, c'est plus simple car on suppose les composants près. On n'envisage pas (en tout cas à ma connaissance) de téléporter l'état des protons et neutrons. Trop couteux en énergie (nucléaire !). Les atomes étant dans leur état de base sauf les ions. La principale information à transmettre c'est l'état atomique simple (ionisation, quelques bits), l'agencement des atomes dans les molécules, etc...
Je ne connais pas le calcul complet et je n'ai plus trace de la référence. Désolé. Je me souviens juste que le chiffre était considérable (des milliards de milliards de milliards de bits).
Si tu veux transmettre l'état complet de l'atome, alors les indications que j'ai donné plus haut devraient suffire (en creusant un peu la description de l'atome).
Ne te casse pas la tête avec la algorithme et tout et tout. Il y a plus simple. Pour connaitre l'information, il suffit de savoir compter. Point barre. Tu comptes le nombre de possibilités. C'est tout. Tu as ta réponse.
Après, si tu veux réduire le chiffre par compression, tu écrits un petit programme qui énumère les possibilités. Un petit coup de winzip (r). Et hop tu as ta réponse.
Pourquoi vouloir te casser la tête quand la solution est si facile et évidente.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
salut , des appareils vont mesurer et compter des signaux , et vont utiliser des algorithmes pour organiser cette information , on doit comprendre leurs algorithme pour savoir ce qu'ils mijotent ,
j'aimerai bien avoir un lien qui explique comment mesurer l’état quantique et le convertir en bit , merci .
Salut,
Je pensais que ton but était de comprendre/connaitre la complexité/quantité d'information qu'il y avait dans un atome.
Je ne savais pas que ton but était de comprendre ce que font les machines.
De toute façon, il faut éviter de mettre la charrue avant les bœufs (pauvre bête, déjà qu'on leur enlève leur joie de vivre, si en plus on les met derrière la charrette
Il vaut mieux :
1) Etudier la complexité et la quantité d'information
PUIS :
2) Etudier les algorithmes pour utiliser cette information
Je l'ai dit : compter le nombre de possibilités que peut avoir l'état => tu as directement le nombre de bits (par exemple avec l'atome comme cela a été discuté plus haut).
Exemple, si tu vois que l'état de l'objet peut prendre 256 valeurs possibles, alors décrire l'état de l'objet demande 8 bits.
"Il ne suffit pas d'être persécuté pour être Galilée, encore faut-il avoir raison." (Gould)
il y'a par exemple le scanner 3D http://fr.wikipedia.org/wiki/Scanner_3D
il y a aussi l'imprimante 3D http://fr.wikipedia.org/wiki/Imprimante_3DUn scanner tridimensionnel est un appareil qui analyse les objets ou leur environnement proche pour recueillir des informations précises sur la forme et éventuellement sur l'apparence (couleur, texture, …) de ceux-ci. Les données ainsi collectées peuvent alors être utilisées pour construire des images de synthèse en trois dimensions (objets numériques) à des fins diverses. Ces appareils sont beaucoup utilisés par les industries du divertissements pour des films ou des jeux vidéo. Des images numériques en 3D d'objets scannés servent également à la conception industrielle, à la conception d'orthèses et de prothèses, à la rétro-ingénierie, pour le contrôle qualité (référentiel numérique) ou pour la documentation d'objets culturels.
je suppose que ce scanner branché à une machine de tour ,pourra cloner des pièces métallique .L'impression tridimensionnelle, ou stéréolithographie, est une technique de production industrielle développée pour le prototypage rapide en plastique, cire ou métal1. Issue du MIT (Massachusetts Institute of Technology), elle permet de produire un objet réel à partir d'un fichier CAO en le découpant en tranches puis en déposant ou solidifiant de la matière couche par couche pour, en fin de compte, obtenir la pièce terminée. Le principe est donc assez proche de celui d'une imprimante 2D classique : les buses utilisées, qui déposent de la colle, sont d'ailleurs identiques aux imprimantes de bureau. C'est l'empilement de ces couches qui crée un volume.
