Qui aime la physique ou les mathématiques?

Page 6 sur 11 Précédent  1, 2, 3 ... 5, 6, 7 ... 9, 10, 11  Suivant

Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par stupeflip666 le Mer 23 Déc 2015 - 21:47

Stauk a écrit:Une question que m'a proposé quelqu'un :
Est t'il possible de construire une relation "inférieur ou égal", avec un plus petit élément sur l'ensemble des X

La contrainte "avec un plus petit élément" n'apporte rien car une fois que tu as une relation d'ordre, tu peux toujours ajouter un nouvel élément "0" et décréter qu'il est plus petit que tous les autres.
Donc la vrai question vraissemblablement était de savoir si l'ensemble en question, qui est équivalent à l'ensemble des réels R peut être bien ordonné. Et si mes souvenirs sont bons, ce doit être le genre de question où on peut démontrer de façon indirecte et abstraite que R peut être bien ordonné, mais il est absolument impossible d'exhiber une construction qui implémente concrêtement ce bon ordre. J'ai pas vérifié donc possible que je raconte n'importe quoi ce sont justes de vagues pseudos souvenirs....

stupeflip666

Messages : 98
Date d'inscription : 25/06/2015

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par Stauk le Mar 29 Déc 2015 - 4:19

En poussant un peu la réfléxion (la psychanalyse dirait mon interlocuteur mathématicien ..), je me rend compte que le problème que j'ai, est avec le concept d'égalité. Le signe =

Quand on me dit soit deux nombres entiers a et b, n'importe lesquels, tels que a=b .. j'arrive à comprendre.

Quand on me dit, soit deux éléments de l'ensemble des parties des parties de N (entiers naturels), a et b, tels que a=b, je n'ai pas trop de doutes que je ne comprends pas de quoi on cause ...

Quand on me dit, soit deux parties de n distinctes, a et b, telles que a=b, j'ai le sentiment qu'on est en train de m'entourlouper sévère.




Du coup mon problème avec les histoires de diagonalisation est sans doute là :
- Soit une liste de nombres réels (ou parties de N mettons, c'est pareil).
- Nous construisons maintenant un nouvel élément (appelons le b) par le procédé diagonal, à partir de cette liste ...

Et on propose : quelque soit "a" de la liste, alors on peut affirmer que (a=b) est faux.
Sauf que je me sens arnaqué, du fait qu'on ne m'a pas vraiment convaincu de ce qui est entendu précisément par le soit disant booléen (a=b).
Stauk
Stauk

Messages : 6462
Date d'inscription : 16/01/2015

http://www.staukwood.com/

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par fragmentation le Mar 29 Déc 2015 - 4:35

stupeflip666 a écrit:ce doit être le genre de question où on peut démontrer de façon indirecte et abstraite que R peut être bien ordonné

Wikipedia nous informe :
Mr Wikipedia a écrit:
L'axiome du choix est souvent utilisé par l'intermédiaire de l'un des deux énoncés suivants qui lui sont équivalents :

Théorème de Zermelo : « Tout ensemble non vide peut être muni d'une structure de bon ordre » ;
Lemme de Zorn : « Tout ensemble inductif non vide admet un élément maximal ».
On montre facilement que le théorème de Zermelo implique l'axiome du choix : comme pour les entiers naturels, si E est muni d'un bon ordre, le minimum pour celui-ci fournit une fonction de choix sur l'ensemble des parties non vides de E (second énoncé équivalent). De même le lemme de Zorn a également facilement pour conséquence l'axiome du choix.


Another argument against the axiom of choice is that it implies the existence of objects that may seem counterintuitive.[8] One example is the Banach–Tarski paradox which says that it is possible to decompose the 3-dimensional solid unit ball into finitely many pieces and, using only rotations and translations, reassemble the pieces into two solid balls each with the same volume as the original. The pieces in this decomposition, constructed using the axiom of choice, are non-measurable sets.

https://fr.wikipedia.org/wiki/Paradoxe_de_Banach-Tarski


En mathématiques, et plus précisément en géométrie, le paradoxe de Banach-Tarski est un théorème, démontré en 1924 par Stefan Banach et Alfred Tarski, qui affirme qu'il est possible de couper une boule de l'espace usuel R^3 en un nombre fini de morceaux et de réassembler ces morceaux pour former deux boules identiques à la première, à un déplacement près. Ce résultat paradoxal implique que ces morceaux soient non mesurables, sans quoi on obtiendrait une contradiction (le volume étant un exemple de mesure, cela veut plus simplement dire que ces morceaux n'ont pas de volume).

La démonstration de ce résultat utilise l’axiome du choix, nécessaire pour construire des ensembles non mesurables.

fragmentation
fragmentation

Messages : 146
Date d'inscription : 05/09/2015

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par paela le Mar 29 Déc 2015 - 17:14

Pour dire les choses rapidement, en maths, tous les objets ou presque sont définis comme des ensembles ayant certaines propriétés. L'axiome d'extensionnalité de la théorie des ensembles dit que deux ensembles sont égaux si et seulement s'ils ont les mêmes éléments.

Cela s'applique aux réels, mais les définitions d'un réel en tant qu'ensemble sont un peu compliquées (pour la plus simple que je connais, ce sont des ensembles d'ensembles d'ensembles d'ensembles d'ensembles d'ensembles d'ensembles d'ensembles ou seul le rez-de-chaussée peut être l'ensemble vide) qu'on utilise des critères pour montrer rapidement que deux réels sont différents. En particulier, deux réels sont différents si et seulement si leurs développements binaires (voir précédemment) sont différents en au moins une valeur.
paela
paela

Messages : 2312
Date d'inscription : 30/05/2011
Age : 26
Localisation : Bordeaux

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par fragmentation le Mar 29 Déc 2015 - 18:37

paela a écrit:En particulier, deux réels sont différents si et seulement si leurs développements binaires (voir précédemment) sont différents en au moins une valeur.

Si je comprends bien la question, l'op ne comprend pas la notion d'égalité entre deux développements binaires de réels quelconques dont on ne connait rien d'autre que leur développement binaire. C'est à dire qu'étant donné deux boîtes noires qu'on peut interroger pour en extraire les coefficients binaires un par un, comment faire pour déterminer que les deux développement associés sont égaux ? (c'est impossible, phénomène bien connu en programmation, on ne teste jamais l'égalité entre deux nombres à virgules flottantes : ça ne sert à rien). A partir de là la notion de "différent en au moins une valeur", devient suspecte (il se trouve qu'en prime pour les Réels, elle est parfaitement fausse, mais c'est un détail, on peut toujours ne considérer que les suites des coefficients, sans passer par les bizarreries des égalités entre réels). Parler de différence, quand on n'a pas de moyen de décrire ce que c'est qu'une égalité, ça ressemble soit à un abus de langage, soit à une tautologie (qui affirmerait grosso modo que deux réels dont on en connait que le développement binaire sont toujours différents, à moins d'être supposés égaux)

Enfin c'est mon interprétation.

Donc grosso modo, tu poses ici la notion de "différence", mais qui est toujours vrai. Puisqu'on est toujours libre de supposer que deux réels dont on ne connait que la liste des coefficient binaires sous la forme d'une suite infinie de 0 et de 1 non reliés par une formule vérifie la propriété "sont différents en au moins une valeur" (c'est en tout cas ce qui est fait dans les simulations informatiques).


Autrement formulé, le test de l'égalité entre deux réels par la comparaison des chaines binaires infinie associées , semble indécidable en pratique, ce qui rend caduque et illusoire la notion de différence.

De façon amusante, si on décide d'un procédé particulier pour tirer deux Entiers au hasard avec la propriété de pouvoir choisir n'importe lequel, la probabilité de tirer deux fois le même, sera non nulle (pour autant que le procédé ne conserve aucune information entre les deux tirages). A contrario si on fait la même chose avec des réels en se laissant la possibilité de tirer n'importe lequel parmi un sous ensemble continu non ponctuel de réels, on est 100% certain de ne jamais tirer deux fois le même (dans la mesure ou on accepte l'idée que la notion a un sens bien défini - ce qui est vrai dans l'intuition qu'on a de ce qu'est un réel).

C'est un peu comme si en passant de PI à son développement binaire on perdait une information ... le fait qu'il s'agit de PI avec toutes ses propriétés, et de rien d'autre. On ne peut pas reconnaître PI, et en déduire l'ensemble de ses propriétés en observant sont développement binaire en base deux.   Bref le "si et seulement si" semble totalement faux dans ta phrase.
fragmentation
fragmentation

Messages : 146
Date d'inscription : 05/09/2015

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par Pieyre le Mar 29 Déc 2015 - 19:04

Normalement, un réel est appréhendé selon une formule :
— Sn(0), autrement dit n;
— n/p;
— telle solution d'une équation algébrique;
— pi, e ou autre transcendant défini notamment par une série;
— etc.

À partir d'une telle caractérisation, on peut démontrer que deux réels sont égaux.

Le développement décimal (ou binaire) correspond à divers usages, mais il n'est jamais qu'une façon de caractériser les réels, notamment de les comparer jusqu'à un certain rang, en relation avec la notion de mesure physique.

Pieyre

Messages : 20530
Date d'inscription : 17/03/2012
Localisation : Quartier Latin

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par stupeflip666 le Mar 29 Déc 2015 - 19:40

Grosso modo, un réel et une suite d'entiers c'est la même chose. Deux suites d'entiers U et V sont égales si pour tout indice i, Ui = Vi. Moi ça me semble à peu près clair comme concept, où est le problème exactement ?

stupeflip666

Messages : 98
Date d'inscription : 25/06/2015

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par Invité le Mar 29 Déc 2015 - 19:44

fragmentation a écrit:
Si je comprends bien la question, l'op ne comprend pas la notion d'égalité entre deux développements binaires de réels quelconques dont on ne connait rien d'autre que leur développement binaire. C'est à dire qu'étant donné deux boîtes noires qu'on peut interroger pour en extraire les coefficients binaires un par un, comment faire pour déterminer que les deux développement associés sont égaux ?

Là tu regardes le coté informatique et du "comment faire un algo qui soit capable de répondre à la question". Et puis le "une par "une"... pourquoi ? On est tout à fait capable de comparer instantanément 512 bits si ça nous amuse... Pas besoin de proc, de simples portes logiques font l'affaire. Et de toutes façons c'est ce qui est déjà implémenté dans les proc : quand on veut comparer deux réels dans les codes, heureusement qu'il ne faille qu'un seul temps d'horloge et qu'on ne parcoure pas les 64 bits de chaque nombre...

fragmentation a écrit:
(c'est impossible, phénomène bien connu en programmation, on ne teste jamais l'égalité entre deux nombres à virgules flottantes : ça ne sert à rien).

Si, pour les tests de non régression stricts, et aussi pour les systèmes de compression sans perte où c'est bien l'écart (un XOR pour etre plus précis) qui est utilisé entre deux flottants pour encoder l'erreur.

fragmentation a écrit:
quand on n'a pas de moyen de décrire ce que c'est qu'une égalité,  

S'il existe un nombre dans le XOR qui est non nul, ça irait ?

fragmentation a écrit:
Donc grosso modo, tu poses ici la notion de "différence", mais qui est toujours vrai. Puisqu'on est toujours libre de supposer que deux réels dont on ne connait que la liste des coefficient binaires sous la forme d'une suite infinie de 0 et de 1 non reliés par une formule vérifie la propriété "sont différents en au moins une valeur" (c'est en tout cas ce qui est fait dans les simulations informatiques).

Non, pas toujours vrai... du moins pas en informatique, puisque leur codage est fini.

fragmentation a écrit:
Autrement formulé, le test de l'égalité entre deux réels par la comparaison des chaines binaires infinie associées , semble indécidable en pratique, ce qui rend caduque et illusoire la notion de différence.

Toujours pareil : dans le sens du logicien qui cherche une méthode pour le calculer. On parle de maths là, pas d'informatique. Dans ce cas on peut généraliser ce que tu dis à "on ne connait pas pi", "on ne connait pas e", "on ne connait pas sqrt(2)", etc...

fragmentation a écrit:
C'est un peu comme si en passant de PI à son développement binaire on perdait une information ... le fait qu'il s'agit de PI avec toutes ses propriétés, et de rien d'autre. On ne peut pas reconnaître PI, et en déduire l'ensemble de ses propriétés en observant sont développement binaire en base deux.   Bref le "si et seulement si" semble totalement faux dans ta phrase.

Pourtant pi est parfaitement connu et défini dans une base variable (d'euler il me semble, je vais regarder pour le nom).


Dernière édition par hobb le Mar 29 Déc 2015 - 19:59, édité 1 fois

Invité
Invité


Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par Invité le Mar 29 Déc 2015 - 19:46

Je confirme : dans la base d'Euler (http://www.gecif.net/articles/mathematiques/pi/#euler), pi est intégralement connu, il sagit du nombre 2,222222222222222222222222222222...

Invité
Invité


Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par fragmentation le Mar 29 Déc 2015 - 20:15

hobb a écrit:
pour les systèmes de compression sans perte où c'est bien l'écart (un XOR pour etre plus précis) qui est utilisé entre deux flottants pour encoder l'erreur.

... je veux bien la source qui illustrerait ton propos. De quel système de compression sans perte tu parles précisément ici ? J'en connais quelques uns, mais aucun qui utilise des flottants. Même les systèmes de corrections automatiques d'erreurs n'utilisent pas de flottants à ma connaissance.

Le xor est une opération bit à bit (donc non applicable aux flottants du fait des contraintes de types, il faut convertir le flottant en autre chose pour pouvoir lui appliquer le XOR) ... donner le nom de l'algorithme auquel tu fais référence me permettrait peut être d'apprendre quelque chose.  

Le coté "non" régression n'est pas tellement pertinent, il s'agit juste de comparer une invariance d'un certain résultat (en gros que les fichiers de sorties sont les même si rien n'a changé).  Si on considère une simulation Montecarlo par exemple, et en supposant qu'on a décidé d'optimiser quelque chose avant de pratiquer la non régression, les valeurs seront bien comparées avec la prise en compte de l'égalité à une marge d'erreur près au moment de la validation par non régression.


Et puis le "une par "une"... pourquoi ? On est tout à fait capable de comparer instantanément 512 bits si ça nous amuse... Pas besoin de proc, de simples portes logiques font l'affaire.
Une par une, ou 512 par 512, c'est pareil en effet, lorsqu'il s'agit de comparer deux chaines infinies.  Le une par une, insiste sur le coté fini de la comparaison partielle, et sur l'aspect incrémental du procédé.



Pourtant pi est parfaitement connu et défini dans une base variable (d'euler il me semble, je vais regarder pour le nom).
Dans la base d'euler, le nombre Pi devient un nombre particulier, je l'ai choisis pour illustrer une chaîne de bits particulièrement chaotique. Si on se met dans la base d'Euler, on peut remplacer Pi par 2 j'imagine, afin d'obtenir une telle chaîne infinie "quelconque" mais dotée par effet de sémantique de propriétés particulières.




stupeflip666 a écrit:Grosso modo, un réel et une suite d'entiers c'est la même chose. Deux suites d'entiers U et V sont égales si pour tout indice i, Ui = Vi. Moi ça me semble à peu près clair comme concept, où est le problème exactement ?
Le problème est que la formule de récurrence (ou autre) qui défini la suite, ne semble pas être équivalente à la liste qui donne les éléments de la suite un par un.
La "preuve" en étant, qu'en disposant uniquement des éléments de la suite sous la forme d'une liste infini (ou chaque terme est fourni, mais de manière indépendante des autres termes, sans formule aucune qui relie les termes), il est impossible de conclure à l'équivalence avec la formule. Dire que les deux représentations sont équivalentes, semble donc inapproprié, en toute rigueur. L'ensemble des formules peut être injectée dans l'ensemble des chaines infinies (les suites infinies d'entiers étant équivalentes aux suites infinies de bits à une transformation près), mais l'ensemble des chaînes infinies ne peut pas être injecté dans l'ensemble des formules.

Ce n'est pas très étonnant, puisque l'ensemble des formules (par récurrence par exemple) est dénombrable, et l'ensemble des chaines infinies d'éléments à valeurs dans un ensemble fini est indénombrable.
Il est donc assez clair qu'il serait faux de supposer une équivalence entre les deux "représentations".
fragmentation
fragmentation

Messages : 146
Date d'inscription : 05/09/2015

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par Invité le Mar 29 Déc 2015 - 20:26

fragmentation a écrit:
... je veux bien la source qui illustrerait ton propos. De quel système de compression sans perte tu parles précisément ici ? J'en connais quelques uns, mais aucun qui utilise des flottants. Même les systèmes de corrections automatiques d'erreurs n'utilisent pas de flottants à ma connaissance.

Compression de signaux (image, son, etc). Une publi au pif : https://users.ices.utexas.edu/~burtscher/papers/dcc06.pdf (figure 2).

fragmentation a écrit:
Le xor est une opération bit à bit (donc non applicable aux flottants du fait des contraintes de types, il faut convertir le flottant en autre chose pour pouvoir lui appliquer le XOR) ... donner le nom de l'algorithme auquel tu fais référence me permettrait peut être d'apprendre quelque chose.  

Non, tu peux très bien faire un XOR en C : A ^= B te donne A XOR B dans A, quelque soit le type de A et B (c'est d'ailleurs l'intéret du C : c'est non-typé).

fragmentation a écrit:
Le coté "non" régression n'est pas tellement pertinent, il s'agit juste de comparer une invariance d'un certain résultat (en gros que les fichiers de sorties sont les même si rien n'a changé).  Si on considère une simulation Montecarlo par exemple, et en supposant qu'on a décidé d'optimiser quelque chose avant de pratiquer la non régression, les valeurs seront bien comparées avec la prise en compte de l'égalité à une marge d'erreur près au moment de la validation par non régression.

Il est parfaitement pertinent pour voir si tu n'as pas collé une erreur dans le code quelque part sur une bibliothèque qui n'a pas à intéferer sur les résultats (type MPI, HDF5, ou peu importe). monte-Carlo est un truc marginal, et avec lequel on fait quand meme des tests de non régression stricts (suffit que le seed de la suite est le meme). Par exemple : quand j'ai parallélisé mon code, le fait que le tirage de nombre aléatoires pour chaque proc puisse etre différent a immédiatement foutu en l'air les tests de non-régression. Et en arrangenat ça, ben résultat j'ai corrigé une erreur, et en plus j'ai exactement la meme chose quelque soit le nombre de procs.


Une par une, ou 512 par 512, c'est pareil en effet, lorsqu'il s'agit de comparer deux chaines infinies.  Le une par une, insiste sur le coté fini de la comparaison partielle, et sur l'aspect incrémental du procédé.

si tu connais l'intégralité d'un nombre (en octet), tu n'as pas besoin d'un procédé incrémental. Meme si ça s'apparente plus à une puce dédiée (=> VHDL) qu'à un proc à nombre fixe de bits.

Invité
Invité


Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par fragmentation le Mar 29 Déc 2015 - 20:45

hobb a écrit:
fragmentation a écrit:
... je veux bien la source qui illustrerait ton propos. De quel système de compression sans perte tu parles précisément ici ? J'en connais quelques uns, mais aucun qui utilise des flottants. Même les systèmes de corrections automatiques d'erreurs n'utilisent pas de flottants à ma connaissance.
Compression de signaux (image, son, etc). Une publi au pif : https://users.ices.utexas.edu/~burtscher/papers/dcc06.pdf (figure 2).

Je ne connaissais pas du tout ce domaine qui consiste à compresser de grandes listes de flottants, avec un algorithme dédié.
Ton algorithme tend plutôt à confirmer ce que je disais qu'à l'infirmer.

L'algorithme repère une régularité dans la liste des flottants (à compresser), et en déduit une approximation (non exacte ...) du flottant suivant. Si l'approximation est bonne, alors on peut simplement encoder le facteur d'erreur entre la prédiction et le flottant, ce qui peut être fait dans une enveloppe mémoire inférieure à celle qui est nécessaire pour stoker les 64 bits de la double précision des éléments de la liste à compresser.

La particularité de ton algorithme est de ne s'appliquer qu'aux listes de flottants (de taille constante), c'est donc une instance tout à fait particulière d'algorithme sans perte, dont la majorité sont génériques et ne font aucune hypothèse sur la nature des données à compresser. J'ai été troublé je pense par le pluriel, qui laissait pour moi supposer qu'il existait de nombreux algorithmes sans perte génériques, et qui utiliseraient des flottants pour effectuer la compression.

C'est pas facile la communication bom
fragmentation
fragmentation

Messages : 146
Date d'inscription : 05/09/2015

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par Invité le Mar 29 Déc 2015 - 20:49

Heu non, ces algos sans perte comme ça, il y en a pléthore : le FLAC, le JPEG2000, etc... Et c'est pas si simple parce qu'il faut aussi envoyer les données compressées en plus des erreurs.

Invité
Invité


Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par fragmentation le Mar 29 Déc 2015 - 20:51

hobb a écrit:Heu non, ces algos sans perte comme ça, il y en a pléthore.
Je ne comprends pas. A quoi tu dis non exactement ? J'ai l'impression qu'on ne parle décidément pas le même langage.
Enfin si tu as d'autres thèses (.pdf en lignes gratuits) à proposer, ça m'intéresse Smile
fragmentation
fragmentation

Messages : 146
Date d'inscription : 05/09/2015

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par Invité le Mar 29 Déc 2015 - 20:57

fragmentation a écrit: c'est donc une instance tout à fait particulière d'algorithme sans perte, dont la majorité sont génériques et ne font aucune hypothèse sur la nature des données à compresser. J'ai été troublé je pense par le pluriel, qui laissait pour moi supposer qu'il existait de nombreux algorithmes sans perte génériques, et qui utiliseraient des flottants pour effectuer la compression.

Quand tu dis "la majorité". A part la détection des redondances qui ne marche pas pour des images ou des sons (justement parce que ce sont des flottants pour la plupart), quasiment tous les algos sans perte de signaux fonctionnent sur ce principe là. Evidement ce n'est pas applicable à du texte, par exemple. Mais pour l'estimation, le mp3 marche très bien par exemple. Tu rajoutes les sorties XOR et hop ! du FLAC. Idem pour le JPEG => JPEG2000.

Après tu tape sur ton moteur de recherche préféré "compression lossless algorithm XOR PDF" et tu auras ton bonheur ;-)

Invité
Invité


Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par fragmentation le Mar 29 Déc 2015 - 21:10

hobb a écrit:
fragmentation a écrit: c'est donc une instance tout à fait particulière d'algorithme sans perte, dont la majorité sont génériques et ne font aucune hypothèse sur la nature des données à compresser. J'ai été troublé je pense par le pluriel, qui laissait pour moi supposer qu'il existait de nombreux algorithmes sans perte génériques, et qui utiliseraient des flottants pour effectuer la compression.

Quand tu dis "la majorité". A part la détection des redondances qui ne marche pas pour des images ou des sons (justement parce que ce sont des flottants pour la plupart), quasiment tous les algos sans perte de signaux fonctionnent sur ce principe là. Evidement ce n'est pas applicable à du texte, par exemple. Mais pour l'estimation, le mp3 marche très bien par exemple. Tu rajoutes les sorties XOR et hop ! du FLAC. Idem pour le JPEG => JPEG2000.

Après tu tape sur ton moteur de recherche préféré "compression lossless algorithm XOR PDF" et tu auras ton bonheur ;-)

Comment est ce que tu peux dire ça ? Quand la thèse que tu m'as fourni contredit frontalement ce que tu affirmes ????
Je ne comprends pas. La thèse par exemple compare l'algorithme dédiés aux flotants 64 bits aux algorithmes suivants :


We compare our algorithm to six general-purpose and one special-purpose compressor.

This section briefly introduces these compressors.

rar is an increasingly popular compressor that incorporates a combination of Huffman , LZ77 , and Prediction by Partial Matching  algorithms.
7-zip  is based on the Lempel-Ziv-Markov Chain Algorithm (LZMA)
lzpx  is based on the Lempel-Ziv compression algorithm and uses arithmetic coding.
zzip is a compressor based on the Burrows-Wheeler Transform (BWT)
gzip and bzip2 are a combination of LZ77 and Huffman coding
fragmentation
fragmentation

Messages : 146
Date d'inscription : 05/09/2015

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par Invité le Mar 29 Déc 2015 - 23:06

Ces algos ne sont pas faits pour ça. Tu compares un algo dédié à une suite de réels a des algos type Huffman. Faut comparer ce qui est comparable...

Alors oui, je persiste et signe, LZ et algos similaires ne sont pas utilisés pour les signaux audio/vidéo/etc.

Le xor pour la compression, on l'utilise depuis les années 70, pour te dire...

PS : et la publi (ce n'est pas une thèse) que je t'ai passé ne contredit rien à ce que j'ai dit. Ou alors je serai curieux de savoir où... (mais là tu vas droit dans le mur, je te préviens d'avance...).


Dernière édition par hobb le Mer 30 Déc 2015 - 12:44, édité 2 fois

Invité
Invité


Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par fragmentation le Jeu 31 Déc 2015 - 1:43

hobb a écrit:Ces algos ne sont pas faits pour ça. Tu compares un algo dédié à une suite de réels a des algos type Huffman. Faut comparer ce qui est comparable...
PS : et la publi (ce n'est pas une thèse) que je t'ai passé ne contredit rien à ce que j'ai dit. Ou alors je serai curieux de savoir où... (mais là tu vas droit dans le mur, je te préviens d'avance...).

- Ce n'est pas moi qui compare l'algo dédié à une suite de réels aux algos de Huffman, c'est la publi, que tu m'as proposé pour illustrer les propos. Par ailleurs tu semblais parler des algos généraux de compression (Donc avec même domaine d'application que Huffman), mais tu m'as fourni une publi qui s'applique aux suites de réels de 64 bits.  

Le problème c'est surtout que visiblement tu ne comprends pas grand chose à ce que je raconte (peut être du fait d'un manque d'intérêt ou de temps). Et apparemment tu étais venu sur ce fil à la base, en expliquant que les conversations ne t'intéressaient de toute façon pas. Cela dit j'ai apprécié le fait que tu fournisses cette publi en exemple (j'ignore si tu l'as lu ou si c'était juste un truc pris au hasard sur le net). Certe j'aurais pu la trouver moi même, mais il y a(vait) un coté stimulant à lire un truc qui intervenait spontanément au cours d'une conversation.

En dépit de ces moments agréables, je remarque qu'il est vain qu'on poursuive, car ta façon de communiquer ne me permet pas de rester calme, et il serait tout à fait innoportun qu'on s'enlise plus avant. Ce qui n'est pas à prendre comme un reproche, puisqu' apparemment je fais le même effet à pas mal de monde. J'aimerais juste insister sur mon souhait de clore la conversation et idéalement ne plus en avoir d'autres avec toi.

Je te remercie donc d'avance de ne plus me répondre (étant bien entendu que je lirais ta réponse à ce message s'il y en a une, je la lirais, mais je te répondrais en privée plutôt qu'en public - je m'éfforcerais à l'avenir de ne plus m'adresser à toi en publique, au moins pour un temps) sur des sujets techniques, car le contenu informatif n'est pas à la hauteur du désagréments de tes commentaires.

Pour te donner un exemple :

mais là tu vas droit dans le mur, je te préviens d'avance...
Il n'y a aucune information technique dans cette phrase.
Il y a par contre une menace. Et je n'aime pas qu'on me menace. Je ne vais pas relire tes propos précédents pour tenter de mettre en avant les autres formules qui m'ont dérangé, celle ci est à mon sens parfaitement représentative de ce que j'ai retenu de cet échange.
fragmentation
fragmentation

Messages : 146
Date d'inscription : 05/09/2015

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par Invité le Jeu 31 Déc 2015 - 8:24

Bon, je vais reprendre :

- toutes les publis utilisant les algos de compression pour les transferts MPI les comparent à LZ (donc type Huffman) parce que ce sont les seuls déjà inclus dans les kernels (suffit de les linker avec -lz) , et dont les temps de compressions sont connus. Et crois moi, là où on fait ce genre de tests (i.e. sur des supercalculateurs, les seuls endroits où on peut espérer saturer l'infiniband), c'est tellement la croix et la bannière pour avoir une malheureuse bibliothèque supplémentaire qu'on fait tout sur ce qui est déjà inclu (enfin, le maximum). Et comme toute publi scientifique qui se respecte, la reproductibilité est de mise, donc sans pré-requis, c'est encore mieux.
Sauf que là tu compares un algo en O(N) avec un O(N log(N)). C'est une méthode de comparaison de base que tout le monde utilise. Fais un peu de biblio sur le sujet, et tu verras...
- une menace... ? Hé bah, 'faut pas grand chose... Faut arrêter d’être parano les gars : relis, il n'y a aucune menace dans ce que j'ai écris. Au lieu de jouer les vierges effarouchées et te défiler, tu dis des trucs faux, je te réponds. Ca te dérange ? Tant pis.
Non, c'est juste que je doute que tu puisse me mettre en défaut sur ce genre de problématique. Et pour le moment, à part des affirmations péremptoires (type "mais non le XOR on ne peut pas le faire sur des réels") montre que tu as beau avoir une bonne culture de ce domaine, n'en reste pas moins que contrairement à ce que tu penses, il y a toujours des choses à apprendre.

- de mon coté je suis parfaitement d'accord avec toi sur un point : je n'arrive pas à lire des pavés, et quand vraiment ils sont longs je lis vos posts en diagonale... Mais ça pour le coup c'est moi avec moi meme.

PS : d'ailleurs la publi n'en n'est sans doute meme pas une, ça doit etre un draft (ni date ni journal). M'étonnerait que les reviewers aient laissé passer une publi où on décrit la méthode de compression et pas de décompression...

Invité
Invité


Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par paela le Lun 4 Jan 2016 - 12:39

@fragmentation: Puisque cette notion d'égalité est celle de l'égalité d'ensembles, parlons d'ensembles. Deux ensembles sont dits égaux s'ils ont les mêmes éléments. L'égalité est ainsi définie, mais elle n'est pas toujours décidable (elle ne l'est même jamais entièrement).

Pour ce qui est des réels, cela n'a de sens de se demander si deux réels a,b sont égaux que si l'on suppose que a et b définis par les propriétés respectives A,B et si tout réel satisfaisant A est égal à tout réel satisfaisant B. Sinon, il manque un contexte, et cela revient à se demander si Jack et Sir Carl sont la même personne avant le début de l'enquête: pas évident en effet.

Les algorithmes réels (au sens de réalité) sont toujours limités en taille car la mémoire est limitée, ils ne peuvent donc pas comparer tous les réels et il s'agit plutôt d'en trouver qui soient efficaces.
paela
paela

Messages : 2312
Date d'inscription : 30/05/2011
Age : 26
Localisation : Bordeaux

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par Stauk le Jeu 7 Jan 2016 - 9:58

Merci de pointer l'erreur dans la démonstration suivante :




prop0 : *L'ensemble des programmes est clairement en bijection avec N

Considérons l'ensemble P des programmes qui génèrent des suites infinies de 1 et de 0. Etant donné un programme p de P, appellons exec(p) la suite infinie générée, et exec(p)(n) le bit 0 ou le bit 1 au rang n.


propA : Deux programmes qui génèrent des suites différentes, sont différents.


Enumérons les éléments de P, par une suite S de programmes. Alors on peut associer à chaque élement de la suite, la chaine issue de l'execution du programme

S(0) = p0 -->    exec(S(0))
..
S(n) = Pn -->    exec(S(n))

Alors par diagonalisation, on peut toujours trouver un programme x qui n'est égal à aucun S(n) quelque soit n. Il suffit de considérer le programme qui au rang 0 génère le bit inverse de S(0)(0), au rang 1 génère le bit inverse de S(1)(1) ... au rang n génère le bit inverse de S(n)(n).

Le procédé diagonal stipule que la suite générée par le programme x n'est pas dans la liste des chaines générées par les programmes déjà listés. En application de la propA, le programme x n'est donc l'image d'aucun n par la suite S. Quelque soit n, S(n) != x

L'ensemble des programmes qui générent des suites infinies de 0 et de 1 n'est donc pas dénombrables.
La prop0 affirme qu'ils sont dénombrables (on peut clairement les énumérer, du fait de la définition d'un programme).

Il y a contradiction.
Stauk
Stauk

Messages : 6462
Date d'inscription : 16/01/2015

http://www.staukwood.com/

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par stupeflip666 le Jeu 7 Jan 2016 - 13:55

Bon j'ai du faire une fausse manip car ma réponse s'est perdue dans le vide intersidéral, et j'ai pas le courage de la re-pondre. Pour faire rapide, ta suite obtenue par diagonalisation ne peut pas être générée par un programme, sinon contradiction comme tu l'as remarqué.

stupeflip666

Messages : 98
Date d'inscription : 25/06/2015

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par stupeflip666 le Jeu 7 Jan 2016 - 13:58

Par ce genre de raisonnement je crois qu'il est possible d'arriver à une preuve de l'indécidabilité du problème de l'arrêt, du moins il me semble que j'avais vu un truc à ce sujet un jour.

stupeflip666

Messages : 98
Date d'inscription : 25/06/2015

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par paela le Jeu 7 Jan 2016 - 13:59

Il y a trois lacunes majeures:
-définition d'un programme qui énumère ls suites (est-ce un objet de la vie réelle, un programme informatique? Si oui, aucun programme d'énumère une suite infinie car la mémoire est toujours finie.)
-preuve claire de la proposition 0
-preuve de la proposition A
paela
paela

Messages : 2312
Date d'inscription : 30/05/2011
Age : 26
Localisation : Bordeaux

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par stupeflip666 le Jeu 7 Jan 2016 - 14:03

Oh oh oh oh en fait en relisant mieux ton truc, je me rend compte que tu es exactement retombé sur ça. Il y a bien une contradiction, et le seul moyen de la lever, c'est de réaliser qu'il n'y a pas moyen de savoir pour ton algorithme diagonal qui génère à l'étape n S(n)(n) de savoir si le programme S(n) va un jour pondre l'élément S(n)(n) ou pas. Donc bravo tu viens de trouver une démonstration du problème de l'arrêt tout seul, c'est pas donné à tout le monde.

stupeflip666

Messages : 98
Date d'inscription : 25/06/2015

Revenir en haut Aller en bas

Re: Qui aime la physique ou les mathématiques?

Message par stupeflip666 le Jeu 7 Jan 2016 - 14:12

paela a écrit: Si oui, aucun programme d'énumère une suite infinie car la mémoire est toujours finie.)
On parle de programmes théoriques qui ont accès à une mémoire non bornée. La théorie des programmes ayant une mémoire finie n'est pas très intéressante : C'est simplement la théorie des automates finis.

paela a écrit: -preuve claire de la proposition 0
Il suffit d'énumérer les programmes par ordre lexicographique. C'est du niveau CE1.

paela a écrit: -preuve de la proposition A
Si f(a) != g(a) alors f != g. Il te faut vraiment une preuve pour ça ?

stupeflip666

Messages : 98
Date d'inscription : 25/06/2015

Revenir en haut Aller en bas

Page 6 sur 11 Précédent  1, 2, 3 ... 5, 6, 7 ... 9, 10, 11  Suivant

Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum