Discussion :

[Neckara]

MAIS C'EST LE CAS SUR TOUTES LES MACHINES DEPUIS LE DEBUT DE L'INFORMATIQUE.....

Non.

D'ailleurs, j'ai quelques peu tord quand je dis "tous les processeurs", certains, très simples, sont déterministes. Mais c'est pour l'embarqué, rien à voir avec ceux que tu trouves dans un ordinateur fixe.

Les compilateurs et les "loaders" ça sert à ça..

Non, le compilateur peut effectivement changer l'ordre des instructions, optimiser, etc. mais aussi le processeur.

Ce qui n'empêche pas que si un algo est en O(N), et un autre en O(N²), quelle que que soit la machine et la configuration, si tu les roules successivement ou en //, l'un ira N fois plus lentement que l'autre...

Désolé, mais là tu dis n'importe quoi.

Pour N entrées :

• 10N boucles, c'est en O(N).
• N² boucles, c'est en O(N²).

Pour une durée d'itération de boucle identique, je te laisse calculer lequel est le plus rapide pour N < 10.

Le budget dépend de là où tu es... Une carte mémoire ou une extension DD ne vaut pas la même chose en France, en Espagne, en Angleterre, aux US, en Chine ou en Inde... etc etc.... surtout pas en termes relatifs par rapport au pouvoir d'achat

Et alors ? Si tu donnes ta configuration, chacun est capable d'estimer le budget que cela représente où qu'il se trouve et même quelques mois après la publication.

LE TEMPS INDIQUE N'A AUCUNE VALEUR...

Si je te dis que le calcul de N hash est en O( log N ), c'est pas mal.
Mais si je te dis, que grâce à cela, j'ai pu calculer un hash toutes les X secondes en moyenne, cela te permet déjà d'estimer les attaques possibles.

Cela te donne déjà un ordre de grandeur de ce qui est possible. Du O(N), cela peut te prendre des secondes comme des années.

[Matthieu Vergne]

J'ai dit :

Si il peut arriver à B d'être provoqué par Z

alors cela provoque l'effondrement de

A => B

en tant que seule explication ou théorie... ou assertion si tu préfères, ou encore en maths "A implique B" est faux puisque "il existe des cas où Z implique B"...

Euh... il me semble que c'est faux. En l'occurrence, si Z => A et A => B, alors on a d'office Z => B. Le fait d'avoir Z => B ne remet pas en cause le fait que A => B aussi. C'est le fait que A => !B qui le remet en cause.

Neckara, je te reprends sur le coup de l'addition.

Non, on s'en fout que le français ou l'anglais soit ambigüe. Ce qu'on considère est la formalisation, qui elle ne l'est pas. Une théorie ne se construit pas en français ou en anglais, elle se construit au travers de relations mathématiques, qui elles n'ont rien d'ambigües.

En l'occurrence, quand tu dis que "l'addition des entiers naturel conduit toujours aux mêmes résultats, c'est absolu car on s'est tous mis d'accord sur cette "convention"." tu mets justement le doigt sur le point important tout en refusant de l'admettre. La formalisation de l'addition est une convention. C'est un modèle parmi tant d'autres, établit par des hommes pour représenter certains phénomènes, qui se sont retrouvés à être applicables aussi à d'autres, mais pas à tous.

Et tu te contredis encore en disant qu'on a déjà décidé du sens de =, => et <=>, alors que tu admets qu'on a plusieurs lectures de +. D'ailleurs, en général on utilise + avec =, alors qu'avec => on utilise v et ^. Tu tentes de voir de l'absolu là où il n'y en a pas. De même je ne vois pas d'où tu sors ton "Le vert n'est que la manière dont on va se représenter ces deux longueurs d'ondes dans un esprit humain "normal".". Non, le vert c'est une longueur d'onde, pas deux.

Ton discours est plein d'approximations, et ce sont tes approximations qui t'amènent à tout mélanger et à partir du principe que si c'est mélangé c'est normal, ce que tu rattaches ensuite à l'ambigüité de la langue. Mais non, c'est pas comme ça que ça marche. Tu observe des phénomènes, et de là tu décides de les modéliser en les formalisant. Dès lors, tu vas tenter de choisir une modélisation qui colle, ce qui veut dire définir des concepts et relations qui permettent effectivement de représenter ce que tu observes. Les modèles formels ne sont pas là, pré-existants, et en train de se révéler à nous au travers de nos observations. C'est l'observateur qui décide du modèle qu'il applique, et il peut en choisir différents selon ce qu'il souhaite mettre en avant. Dans le cadre des couleurs par exemple, tu peux les représenter au moyen du modèle RVB, CMJN ou d'autres encore. Le modèle ne nous "apparait" pas, on le choisit. Soit parce qu'il s'appuie sur ce qu'on connait déjà et donc il nous semble naturel, soit parce qu'on a besoin d'en faire quelque chose de précis.

Et tant que tu ne te seras pas retiré de la tête qu'aucun modèle n'est "absolu" au sens qu'un phénomène donné ne peut se représenter qu'au travers d'un modèle donné ou strictement équivalent, tu seras bien obligé de résoudre tes problèmes d'incohérence par des approximations de langage. Fait de la logique et il n'y a plus d'ambigüité. Fait des maths et il n'y a plus d'ambigüité. Si tu persistes à en voir, c'est parce que tu mélanges observation et formalisation. Une formalisation se base sur des règles définies à l'avance et de manière exacte, y'a pas d'ambigüité qui tienne.

[Matthieu Vergne]

Bon je vois que j'ai loupé le coche. {'^_^}

Foutu thèse.

[Neckara]

La formalisation de l'addition est une convention. C'est un modèle parmi tant d'autres, établit par des hommes pour représenter certains phénomènes, qui se sont retrouvés à être applicables aussi à d'autres, mais pas à tous.

Et en ce, elle a le même sens pour tous, et quelque soit le lieu où elle est utilisée.

De même je ne vois pas d'où tu sors ton "Le vert n'est que la manière dont on va se représenter ces deux longueurs d'ondes dans un esprit humain "normal".". Non, le vert c'est une longueur d'onde, pas deux.

De la manière de percevoir les couleurs d'un être humain. Quand tu vois deux longueurs d'ondes, tu ne vois pas deux couleurs, mais une seule.
Des pulls verts peuvent renvoyer plusieurs longueurs d'ondes ou une seule.

Tu n'as que 3 capteurs pour les couleurs qui s’excitent plus ou moins selon la longueur d'onde reçue. Avec plusieurs longueurs d'ondes, tu peux arriver à des résultats similaires ce que cela serait si tu n'avais qu'une seule longueur d'onde.
C'est un peu sur ce principe que fonctionnent les écrans pour représenter les couleurs.

Le modèle ne nous "apparait" pas, on le choisit.

Cela ne me paraît pas incompatible avec certaines définitions d'absolu, mais bon, cela a plus sa place dans le sujet sur la relativité.

Bon je vois que j'ai loupé le coche. {'^_^}

Foutu thèse.

Ouais, tu devrais l'abandonner pour pouvoir débattre avec nous, aie un peu le sens des priorités quoi !

Cela me fait penser qu'il faut que je te réponde sur l'autre sujet... mais avec celui-ci, vous ne me laissez pas le temps de me reposer .

[souviron34]

Non, le compilateur peut effectivement changer l'ordre des instructions, optimiser, etc. mais aussi le processeur.

Je te dis que les loaders et schedulers ont toujours fait ça : évaluer en fonction de la charge (le nombre et la taille et la fréquence des progarmmes) quels programmes ou parties de programmes ils éxécutaient...

Ca ce faisait sur PDP 11, sur Sun, Vax, IBM, ça se fait sur Linux, Windows, etc erc...

Et ça ne compte pas dans les mesures relatives dont on a besoin pour comparer...

Désolé, mais là tu dis n'importe quoi.

Parce que j'ai pas le temps... Oui c'est en N2.. ce que je voulais dire c'est que c'etait plus lent ,,,

Et alors ? Si tu donnes ta configuration, chacun est capable d'estimer le budget que cela représente où qu'il se trouve et même quelques mois après la publication.

Mais il faudrait alors préciser la date à laquelle tu l'as acheté et le lieu, les mêmes ordis vendus aux mêmes dates n'ont pas eu les mêmes processeurs ou versions de processeurs suivant les pays...

Encore une fois, on s'en fout de la valeur absolue...

Si je te dis que le calcul de N hash est en O( log N ), c'est pas mal.

Mais si je te dis, que grâce à cela, j'ai pu calculer un hash toutes les X secondes en moyenne, cela te permet déjà d'estimer les attaques possibles.

Cela te donne déjà un ordre de grandeur de ce qui est possible. Du O(N), cela peut te prendre des secondes comme des années.

NON ça ne me dit rien de plus.. Il faudrait que je sache la fréquence des attaques, leur nombre, la vitesse du réseau sur lequel tu es connecté, est-ce que tu es le seul point d'entrée d'un reseau local, est-ce que tu es connecté via cable, via ethernet, via Wifi, si oui quel serveur ou quel modem ou quel fabriquant avec quelles caractéristiques, etc etc etc...

Euh... il me semble que c'est faux. En l'occurrence, si Z => A et A => B, alors on a d'office Z => B. Le fait d'avoir Z => B ne remet pas en cause le fait que A => B aussi. C'est le fait que A => !B qui le remet en cause.

Je n'ai jamais parlé de Z => A

Je ne dis pas que Z => B remet en cause A => B dans l'absolu... ça le remet en cause simplement si de A => B on déduit que B ne peut provenir que de A...

(application : RC et origine humaine. On parlait de la notion de "consensus scientifique" ou pas)

[Neckara]

Je te dis que les loaders et schedulers ont toujours fait ça : évaluer en fonction de la charge (le nombre et la taille et la fréquence des progarmmes) quels programmes ou parties de programmes ils éxécutaient...

Ca ce faisait sur PDP 11, sur Sun, Vax, IBM, ça se fait sur Linux, Windows, etc erc...

Ah, je ne voyais pas ce que tu entendais par "loaders", tu veux parler de l'étage de récupération du code dans le processeur ?

Pour avoir fait de l'embarqué, ce n'est pas toujours le cas, mais ce sont des cas spécifiques. Mais inutile de pinailler dessus.

Parce que j'ai pas le temps... Oui c'est en N2.. ce que je voulais dire c'est que c'etait plus lent ,,,

Mais de manière "asymptotique" (?). Pour des jeux de données avec un nombre d'entré suffisamment faible, ce n'est pas nécessairement le cas.

Dès lors, il faut voir en fonction des besoins.

Mais il faudrait alors préciser la date à laquelle tu l'as acheté et le lieu, les mêmes ordis vendus aux mêmes dates n'ont pas eu les mêmes processeurs ou versions de processeurs suivant les pays...

Pourquoi ne pas préciser toutes les références du matériel ?

NON ça ne me dit rien de plus.. Il faudrait que je sache la fréquence des attaques, leur nombre, la vitesse du réseau sur lequel tu es connecté, est-ce que tu es le seul point d'entrée d'un reseau local, est-ce que tu es connecté via cable, via ethernet, via Wifi, si oui quel serveur ou quel modem ou quel fabriquant avec quelles caractéristiques, etc etc etc...

Pourquoi tu pars tout de suite vers le réseau ?

Une attaque sur les hashs peut consister simplement en connaissant un hash, essayer de retrouver la pré-image correspondante par brute force.
Tu vas calculer les hashs de toutes les pré-images possibles et regarder quelle pré-image produit le hash recherché.

Désolé, je n'ai pas été assez précis dans mon dernier post.

[souviron34]

Ah, je ne voyais pas ce que tu entendais par "loaders", tu veux parler de l'étage de récupération du code dans le processeur ?

Pour avoir fait de l'embarqué, ce n'est pas toujours le cas, mais ce sont des cas spécifiques. Mais inutile de pinailler dessus.

Ben ça dépend puisque c'est ton argument pour dire que seule la mesure de la vitesse est cohérente...

Je veux parler du fait que un ordi fonctionne comme (qu'on soit en embarqué ou en normal, la seule différence est le nombre de processus externes et les niveaux de priorités qu'on peut affecter) :

• un programme exécutable stocké sur disque : une suite de bits représentant une suite d'instructions assembleur.
  
  
• Quand on le "lance", le "loader" ou le "scheduler" évalue la charge déjà présente (en mémoire), la fréquence ou la durée ou la priorité des appels déjà en cours, et le loader va "préparer" une section de ces bits pour etre chargée... Le "scheduler" va évaluer les priorités des jobs tournant, et "estimer" le meilleur moment pour "insérer" cette portion du code pour qu'elle soit éxecutée.. quand vient le temps, le "loader" va charger en mémoire cette portion du code (au besoin en ayant "déchargé" une partie d'un autre code).. Ce qui continuera de se passer après... Ce qui fait que tu as différents temps : le temps "absolu", celui que tu mesures avec une horloge, le temps utilisateur (temps total mis par le programme lorsque cet utlisateur a été "connecté", y compris chargement, swap, etc etc), et le temps effectif (temps total machine purement utilisé pour l'exécution des instructions (% du temps utilisateur)...)

La vraie base est le temps effectif....

SAUF QUE...

C'est compliqué à obtenir, il faut pouvoir analyser la charge du processeur...

Si on ne tient pas compte de ça, on ne peut rien comparer, même entre 2 machines identiques... Il faudrait connaitre exactement quels programmes tournent, avec quelles priorités, à quel moment ils en sont, que les tailles de swap soient identiques, etc etc..


(je n'ai pas fait d'embarqué depuis longtemps, mais j'ai travaillé sur des processeurs temps réel, et même là, il y a la vitesse des bus, des cartes, des synchros, les priorités des cartes sur le bus, etc etc)

Mais de manière "asymptotique" (?). Pour des jeux de données avec un nombre d'entré suffisamment faible, ce n'est pas nécessairement le cas.

euhh...

O(N) est O(N) et O(N²) est O(N²) quel que soit N...

Trace voir la courbe de N², et tu vas voir que dès que N = 2, ça part en vrille...


Alors peut-être que pour toi ça n'est pas sensible, mais si on décide un jour d'utiliser ton algo pour prendre des choses qui vont de 2 à 10 000 000 000, ben y'aura une belle différence....

C'est pour ça qu'on se fout pas mal du temps en seconde et qu'on regarde la complexité...

C'est pour prévoir des souplesses ou d'autres applis...

O(N) est toujours plus rapide que O(N²) quel que soit N...


(Quant au "Dviser pour régner" le problème vient souvent de la phase "coalescence" des résultats partiels..D'autres techniques peuvent avoir d'autres inconvénients.. ou des complexités spatiales.... Donc ce n'est pas forcément la complexité du "coeur" de l'algo, mais du total qui est importante...Avoir une complexité en O(N) mais une complexité spatiale en O(N³) sera nettement moins pratique que d'avoir une complexité en O(N^1+x) avec une complexité spatiale en O(N))

Pourquoi ne pas préciser toutes les références du matériel ?

Tu peux mais ça sert à rien, à moins de préjuger / obliger tous les utilsateurs potentiels à n'avoir que exactement ton matériel...

Tu aimerais ça, toi, dans les algos ou machines que tu utilises, qu'on t'oblige à utiliser telle ou telle configuration ou matériel ??? Ou que parce que tu ne les as pas, un algo que tu as péniblement transféré dans ton programme ne donne pas du tout le résultat en temps que le mec affichait mais soit inutilisable ????

[Neckara]

Ben ça dépend puisque c'est ton argument pour dire que seule la mesure de la vitesse est cohérente...

Ah non, non, non, je n'ai pas dit cela.

Juste que la complexité ne suffit pas.

Si on ne tient pas compte de ça, on ne peut rien comparer, même entre 2 machines identiques... Il faudrait connaitre exactement quels programmes tournent, avec quelles priorités, à quel moment ils en sont, etc etc..

C'est entre autre pour cela que je dis que ce n'est pas évident/facile. Bon, d'un autre côté, on est un peu en HS ici.

(je n'ai pas fait d'embarqué depuis longtemps, mais j'ai travaillé sur des processeurs temps réel, et même là, il y a la vitesse des bus, des cartes, des synchros, les priorités des cartes sur le bus, etc etc)

Cela dépend. Dans certains cas, tu peux contrôler ton application au cycle d'horloge près. Mais ce sont des cas très particulier.

O(N) est O(N) et O(N²) est O(N²) quel que soit N...

?

Alors peut-être que pour toi ça n'est pas sensible, mais si on décide un jour d'utiliser ton algo pour prendre des choses qui vont de 2 à 10 000 000 000, ben y'aura une belle différence....

Oui, mais on ne fait pas tout le temps du "big data", parfois on peut avoir moins de valeurs à traiter. Il est bien de savoir à partir de quel moment il peut devenir intéressant d'utiliser notre algorithme.

Par exemple pour du traitement d'image, tu peux proposer un algorithme en O( n log n) qui est moins bon qu'un O(n²) pour des images 1920x1024 mais meilleurs pour les images très très hautes résolutions.

C'est pour ça qu'on se fout pas mal du temps en seconde et qu'on regarde la complexité...

Et pour des algorithmes de même complexité ? Comment tenter de savoir lequel est "meilleur" ?

O(N) est toujours plus rapide que O(N²) quel que soit N...

Non. Je t'ai même donné un contre-exemple.

Tu peux mais ça sert à rien, à moins de préjuger / obliger tous les utilsateurs potentiels à n'avoir que exactement ton matériel...

En quoi ceci les obliges ?

Quand j'achète une carte graphique, je peux regarder les benchmarks. Ce n'est pas pour autant que je suis obligé d'avoir le même processeur, même RAM, etc. pour acheter la CG.

Ou que parce que tu ne les as pas, un algo que tu as péniblement transféré dans ton programme ne donne pas du tout le résultat en temps que le mec affichait mais soit inutilisable ????

Si j'obtiens de meilleurs temps, je ne suis pas contre .

Pour certains calculs, on construit même parfois l'ordinateur en fonction de l'algorithme ! Mais cela reste exceptionnel.


Après, il ne faut pas trop exagérer non plus. La durée d'exécution devrait rester du même ordre si la configuration est "similaire". On ne va pas passer de 10 secondes à 10ans parce qu'on a un intel au lieu d'un ARM.



Si on précise les références, c'est juste pour donner les conditions de l'expérience pour éventuellement la reproduire si nécessaire. C'est un peu comme donner ses sources.

[Grogro]

Il me semble que quelques pages plus tôt, vous aviez parlé de reproductibilité et de la scientificité des études psychologiques :

http://www.slate.fr/story/115289/psy...fiques-trompes

Voilà l'exemple d'un consensus de 20 ans qui pourrait être balayé d'un revers de la main.

[souviron34]

Il me semble que quelques pages plus tôt, vous aviez parlé de reproductibilité et de la scientificité des études psychologiques :

Oui d'aileurs l'étude est citée dans cet article...

Non seulement c'est la base même de la science , que tout n'est que temporaire, mais comme je me tue à le dire, un "consensus" n'a rien a voir avec la science, et il y a une dérive depuis environ 40 ans à faire une expérience et en tirer des conclusions... et à valoriser un "consensus", alors encore une fois que on doit prouver ou infirmer , pas "être d'accord"....

Très souvent les tailles d'échantillons sont trop petites, pour ne pas dire nulles (voir le problème du RC).. **


(une des grandes études de base en psycho-socio, l'étude Masters and Johnson sur la sexualité, tire des conclusions sur 10 000 exemples tirés de plus de 500 personnes... pas 3 groupes de 40...)


** et d'ailleurs un lien sur cette page relève comme je le disais l'enormité exponentielle des articles parus, et la baisse de qualité et des articles et du temps que des gens passent à les lire, qui pourtant vont "former le consensus"..



Note : le lien sur les vidéos devrait être mis demain ou après-demain...

[Neckara]

mais comme je me tue à le dire, un "consensus" n'a rien a voir avec la science, et il y a une dérive depuis environ 40 ans à faire une expérience et en tirer des conclusions... et à valoriser un "consensus", alors encore une fois que on doit prouver ou infirmer , pas "être d'accord"....

** et d'ailleurs un lien sur cette page relève comme je le disais l'enormité exponentielle des articles parus, et la baisse de qualité et des articles et du temps que des gens passent à les lire, qui pourtant vont "former le consensus"..

Comme on l'a déjà expliqué, pour nous le consensus scientifique est une notion autrement plus complexe qu'un simple sondage d'opinion.

Note : le lien sur les vidéos devrait être mis demain ou après-demain...

On l'attend avec impatience ^^.

[r0d]

A la limite, ce serait bien d'avoir un forum du type "Philosophie des sciences et recherche" .

Depuis que je suis membre de dvp, ce qui ne me rajeunit pas, je plaide pour la création d'un sous-forum "épistémologie". J'estime qu'un forum qui se dédie à une discipline qui se revendique scientifique, quelle qu'elle soit, se doit de contenir un lieu pour discuter les méthodes scientifiques, que ce soit de façon globale, ou appliqué à la discipline en question (ici l'informatique).

[r0d]

Je suis un ingénieur, je ne connais pas le "monde de la recherche" et tout ça. Donc je suis loin de comprendre tout ce dont vous parlez ici.
Mais c'est passionnant.
Et du coup j'ai une question:

Dans cette discussion, il est question de démonstration et de consensus. Or, vous n'êtes pas sans savoir qu'il est possible de démontrer un algorithme.
Si je me souviens bien (corrigez-moi si je me trompe), démontrer un algorithme consiste à démontrer qu'il va se finir, et que son résultat est celui que l'on souhaite. ce résultat étant déterminé, et formalisé, par une équation/formule mathématique.
Pour démontrer un algorithme, on utilise un langage très formalisé, essentiellement celui des mathématiques.
Donc si je ne me trompe pas, il est possible de démontrer un algorithme, de façon définitive.
Ma question est la suivante: est-ce que selon vous, l'idée d'avoir un algorithme "validé" par consensus a un sens?

[Neckara]

Dans cette discussion, il est question de démonstration et de consensus. Or, vous n'êtes pas sans savoir qu'il est possible de démontrer un algorithme.
Si je me souviens bien (corrigez-moi si je me trompe), démontrer un algorithme consiste à démontrer qu'il va se finir, et que son résultat est celui que l'on souhaite. ce résultat étant déterminé, et formalisé, par une équation/formule mathématique.

Pour démontrer un algorithme, on utilise un langage très formalisé, essentiellement celui des mathématiques.
Donc si je ne me trompe pas, il est possible de démontrer un algorithme, de façon définitive.

Ceci est faux pour certains algorithmes où tu vas avoir besoin de résoudre des problèmes NP-complets.

C'est aussi parfois assez complexe pour savoir quand il va se finir, notamment quand tu as des algorithmes probabilistes. J'ai cru comprendre que certains algorithmes auraient de meilleurs résultats en pratique que dans la théorie, ce qu'on ne saurait pas trop expliquer pour le moment.

Ma question est la suivante: est-ce que selon vous, l'idée d'avoir un algorithme "validé" par consensus a un sens?

Cela dépend ce que tu entends par "consensus".

Si tu l'entends comme un "résumé" des différents articles parlant du sujet avec prise en compte de leur qualité et la possibilité d'avoir une réponse "on ne sait pas", a tout à fait du sens et que tous les consensus n'ont pas la même "force", alors oui.


S'il y a qu'un seul article qui le démontre, alors on a un consensus avec un seul article.
Si on a plusieurs articles qui le démontre, alors on a un consensus un peu plus fort avec plusieurs articles.
Si on a plusieurs articles de piètre qualité, alors on les écarte ou on leur attribue une importance faible et on reste prudent quant aux conclusions, tout simplement.

Ensuite, parce qu'une seule démonstration ne suffit pas. N'oublions pas qu'on est humain, et que ce sont des humains qui vont lire et accepté la démonstration. Si on ne se base que sur un seul article, quelle garantie a-t-on que l'article ne soit pas bidonné ou contienne une erreur dont on pourrait passer à côté ? Qui dit qu'il n'existe pas à côté un article faisant la démonstration inverse ?

On a plein d'exemples de pseudo-démonstrations où on met du temps avant de comprendre l'arnaque. Imaginez avec des problèmes encore plus complexes.
D'où l'importance de ne pas faire confiance aveuglément à un seul article, mais de chercher à en regarder plusieurs pour augmenter la confiance qu'on peut placer dans la démonstration.

[Neckara]

J'estime qu'un forum qui se dédie à une discipline qui se revendique scientifique, quelle qu'elle soit, se doit de contenir un lieu pour discuter les méthodes scientifiques, que ce soit de façon globale, ou appliqué à la discipline en question (ici l'informatique).

Pour un forum, il faudrait avoir quelques sujets pour justifier son ouverture.
Pour le moment, on en a au moins 2, je ne sais pas s'il en existe d'autres, c'est surtout qu'on en discute souvent dans les autres sujets j'ai l'impression.

[r0d]

Si mes souvenirs sont bons, tout ce qui est NP-complet et compagnie se traitent avec des heuristiques. Une (un?) heuristique ne se démontre pas, me semble-t-il.
Erf c'est loin tout ça... je dis certainement des âneries. C'est dommage, c'est super intéressant. Mais là j'ai pas le temps...

[souviron34]

Je suis un ingénieur, je ne connais pas le "monde de la recherche" et tout ça. Donc je suis loin de comprendre tout ce dont vous parlez ici.

Mais les problèmes sont les mêmes...

En tant qu'ingénieur (je le fus aussi ) tu dois avoir à lire/te baser sur des articles de recherche ou d'algos (IEEE ou autres)..

Pour démontrer un algorithme, on utilise un langage très formalisé, essentiellement celui des mathématiques.
Donc si je ne me trompe pas, il est possible de démontrer un algorithme, de façon définitive.
Ma question est la suivante: est-ce que selon vous, l'idée d'avoir un algorithme "validé" par consensus a un sens?

Le problème (de mon point de vue) n'est pas de démontrer un algo...

Comme une démonstration, un algo peut être juste et ne pas faire ce qu'il suppose, ou se baser sur des hypothèses fausses, ou en tirer des conclusions fausses, ou être trop compliqué, ou pas facilement utilisabe..

En d'autres termes un raisonnement juste et demontré ne tient que par la validité de ses hypothèses et la pertinence de ses conclusions... et, en informatique, par sa facilité d'utilisation

Tu peux faire un superbe raisonnement, bien étayé, mais ça n'empêche pas que cela n'a rien à voir avec la choucroute..


Donc à mon avis en termes d'algos il y a 2 choses : d'une part (malgré ce que dit Neckara ), l'analyse de la complexité (autant spatiale que temporelle), et d'autre part son utilité/facilité...

Par exemple, ça m'étonnerais que les gens du groupe MPEG aient démontré par une preuve formelle que leurs algos étaient bons, comme ceux de libjpeg ou libtiff, de ncurses, ftp, etc etc... Ou pratiquement tous les algos/codes de GraphicsGems...

Et pourtant leur popularité (consensus) est sans faille... PARCE QUE c'est du code efficace, parfois incompréhensible à moins de regarder de vraiment très très près (optimisation par shifts de bits pour MPEG)... mais surtout traitant de problèmes complexes de manière simplement "incorporable" ou utilisable... et efficace..


C'est à mon avis un des biais de l'analyse formelle (et des multiples papiers figurant sur le site ArXiV par exemple dans la rubrique que je mentionnais ou d'autres) et de l'analyse théorique de programmes...


La "preuve" n'a pas grand chose à faire avec la réalité et les tests... Grandeur nature... Un algo "prouvé bon" mais qui ne tient pas le nombre de données car complexité trop élevée (spatiale ou temporelle) ne sera pas utilisé.. De la même manière qu'une loi ou réglementation (ou modèle) trop compliquée, bien que juste., ne sera pas appliquée...



Donc en info, la réponse à ta question serait : oui le "consensus" est même la forme la plus répandue "d'approbation"..


* : exemple : dans le papier que j'ai fait donné en référence plus haut, une des techniques les plus "optimisées" et prouvées est l'algorithme de Chazelle... SAUF QUE... la structure de données et le code sont tellement complexes que, bien qu'étant en O(N), presque personne ne l'utilise...



(note : je me souviens que, ayant eu le code original du premier navigateur Web entre les mains (à l'époque NCSA Mosaic avec le code original HTML du CERN), dans le code on pouvait voir des notes "don't know why, but it needs to be done twice" ou "hack" par exemple... Même chose avec le code de xv , de gnuplot, et autres...J'ai moi même eu à mettre des commentaires du même acabit.. Par exemple, après 100 000 tests, tu sais pas pourquoi, mais si tu fais un truc dans ce sens-là ça marche, dans l'autre ça marche pas, ou si tu fais pas 2 fois ça marche pas... (exemple : les sockets "gelés" : aucun signe ne t'en averti.. sauf si tu vérifies manuellement qu'il y a erreur de lecture/écriture/poll...) )

[Neckara]

Donc à mon avis en termes d'algos il y a 2 choses : d'une part (malgré ce que dit Neckara ), l'analyse de la complexité (autant spatiale que temporelle)

Je ne dis pas que c'est à jeter, juste que c'est insuffisant. Par exemple, quand tu lis une vidéo, il faut que ton codec soit suffisamment rapide pour ne pas avoir de "lag" pendant ton visionnage. De même quand tu fais de l'enregistrement vidéo.

[souviron34]

Je ne dis pas que c'est à jeter, juste que c'est insuffisant. Par exemple, quand tu lis une vidéo, il faut que ton codec soit suffisamment rapide pour ne pas avoir de "lag" pendant ton visionnage. De même quand tu fais de l'enregistrement vidéo.

Tu confonds algorithme et implémentation...


Un algorithme est un principe de calcul, indépendant (normalement) d'une quelcquonque plateforme ou langage ...(puisqu'on peut l'écrire en pseudo-code). Il décrit les opérations mathématiques successives auxquelles procéder afin d'arriver au résultat...

Par exemple, dans le cas qui m'intéressait :

calculer l'enveloppe convexe d'un nuage de points

https://en.wikipedia.org/wiki/Convex_hull
https://en.wikipedia.org/wiki/Convex_hull_algorithms

Tu pourras regarder, tous les articles cités ne font pas référence aux implémentations.. Juste des méthodes générales, mathématiques, éventuellement avec une structure de données adaptées.. Si on fait référence à une fonction, par exemple "Is_Left", on ne fait que préciser ce que doit faire cette fonction, sans donner de code, ou alors juste en exemple.....


Et il en va ainsi de tous les algos de maths, physique, etc, de manière générale..

Autre exemple : https://en.wikipedia.org/wiki/Ramer%...cker_algorithm tu as en bas des références :

• Implementation of Ramer–Douglas–Peucker and many other simplification algorithms with open source licence in C++
• XSLT implementation of the algorithm for use with KML data.
• You can see the algorithm applied to a GPS log from a bike ride at the bottom of this page
• Interactive visualization of the algorithm
• Implementation in F#
• Ruby gem implementation
• JTS, Java Tolopogy Suite, contains Java implementation of many algorithms, including javadoc for Douglas-Peucker algorithm

Comme tu peux voir, on écrit : "implémentation de l'algorithme ZZ en langage YY"


Tu peux aussi regarder https://en.wikipedia.org/wiki/Bentle...mann_algorithm



Le problème que tu soulèves dépend purement d'aspects matériels : langage, optimisation du code, matériel adapté, etc etc..

Ca n'a strictement rien à voir avec l'algorithmie... Je crois que tu n'as pas pleinement saisi la différence...




Tout algorithme en O(N), à moins de souffrir d'une implémentation exécrable, sera plus performant que tout algorithme en O(N²) pour le même problème...

C'est bien pour ça que on utilise les complexités... QUEL QUE SOIT LE MATERIEL ET LE LANGAGE, si l'implémentation est correcte. on a une mesure de référence relative dans un langage donné et sur une plateforme donnée...

Les seules différences pourraient apparaître lors de parallélisations, si le O(N) est moins parallélisable que le O(N²)... Mais dans ce domaine aussi on compare des complexités, mais alors des algos parallèlisés et non pas linéaires..

[r0d]

<mode=friday_troll>

Tout algorithme en O(N) [...] sera plus performant que tout algorithme en O(N²)

Sauf si l'algo en O(N²) est implémenté dans un vrai langage de programmation, comme le c++ par exemple, et que celui en O(N) est implémenté dans un truc chelou de type java.

Et puis lindows c'est mieux que winux tfaçon!
</mode>