Liste

[pm42]

une mesure du désordre d'un vecteur x = (x1,...,xn) pourrait être fondée sur le coefficient de corrélation de Spearman entre x et le vecteur y = (1,...,n)

Outre la même objection que plus haut, c'est à dire que ça ne marche que pour les nombres, cela veut dire qu'on ne peut pas calculer le désordre d'un vecteur constant ?
Et vu l'importance de la monotonie en Spearman, si je prends (9,2,3,4,5,6,7,8,1), j'ai comme résultat -0.067 donc un désordre fort alors qu'avec une seule permutation, je passe à (1,2,3,4,5,6,7,8,9) qui lui donne 1, aucun désordre.
Cela parait cohérent ?

Encore un cas de "on a donné des liens, je ne vais pas les lire, je vais réinventer la roue mais la faire carré".
-----

[Liet Kynes]

Une page très sympa d'explication simple des algos de tri : https://www.jesuisundev.com/comprend...-en-7-minutes/
Par exemple, mon post #5 est un tri à bulles.

ET le complément : https://www.jesuisundev.com/comprend...-en-7-minutes/

[MissJenny]

Outre la même objection que plus haut, c'est à dire que ça ne marche que pour les nombres

ben non, on regarde juste les rangs.

Encore un cas de "on a donné des liens, je ne vais pas les lire, je vais réinventer la roue mais la faire carré".

qu'est-ce que t'as contre les roues carrées?

[pm42]

ben non, on regarde juste les rangs.

Qui ne sont pas définis univoquement si on a plusieurs fois le même élément (et je ne vais même pas parler de la complexité).

Belle façon d'ignorer l'autre objection qui marche même si on considère les rangs.

[Liet Kynes]

Chercher des recettes miracles est la première intention , la frustration est très (trop) souvent la première constatation: on recommence et on incrémente

[ArchoZaure]

Chercher des recettes miracles est la première intention , la frustration est très (trop) souvent la première constatation: on recommence et on incrémente

On appelle souvent les choses "miracles" du fait de l'ignorance.

Abstract:Quantum algorithms have gained a lot of consideration especially for the need of searching unsorted database in a faster way rather than using the classical search mechanisms. This paper introduces a new quantum sort algorithm by employing the quantum features to expedite the searching process in conventional environments. The proposed efficient sorting algorithm emphasizes entanglement qubits property to sort N positive integers.

https://ieeexplore.ieee.org/document/7494107

Un exemple concret.
https://128mots.com/2021/01/13/quantum-sort-algorithm/

[Liet Kynes]

On appelle souvent les choses "miracles" du fait de l'ignorance.


https://ieeexplore.ieee.org/document/7494107

Un exemple concret.
https://128mots.com/2021/01/13/quantum-sort-algorithm/

1er lien en anglais, second "page web dangereuse bloquée ".

L'ignorance est la porte d'entrée de l'exploration, essayer c'est apprendre.

[ArchoZaure]

L'ignorance est la porte d'entrée de l'exploration, essayer c'est apprendre.

Certainement un problème lié au manque d'autonomie.
Votre navigateur est-il lui aussi allergique à la connaissance ?
La discussion (en anglais à nouveau, désolé pour la haute technicité) où il est question du tri quantique.
https://quantumcomputing.stackexchan...ing-algorithms

[polo974]

Et comme nos ordis ont environ 0 qbits, ça ne va pas faire avancer la (non) question posée ici.

[Juzo]

Bonjour, le problème posé est : comment caractériser le niveau de désordre aléatoire d'une liste courte de nombres par rapport à l'ordre croissant ? (A quel point la liste est mélangée par rapport à l'ordre croissant).
Dans le cas général d'un ordre O et d'une liste L, c'est un problème complexe de statistiques et d'algorithmique, on se limite ici à une liste de quelques nombres et à l'ordre croissant. L'idée est de proposer des solutions pour se "faire les dents" en tenant compte des contre-arguments, sans prétention sur le fait de réinventer la théorie.

2 objectifs :
1) caractériser ce niveau de désordre mathématiquement
2) chercher une méthode statistique ou algorithmique pour évaluer ce désordre sur une liste, qui ne donne pas de résultat aberrant pour certaines listes (à priori impossible dans le cas général comme dit plus haut).

1) Pour la caractérisation mathématique je propose l'idée suivante, testée sur quelques listes de 5 nombres.

.
est le vecteur "ordonné" avec les coordonnées de X dans l'ordre croissant, est la matrice de passage telle que .
On définit 2 opérations élémentaires sur P : permutation de deux colonnes adjacentes ou rotation d'une sous-matrice de P.

Le niveau de désordre d est le nombre minimum d'opérations élémentaires qu'il faut appliquer à P pour obtenir la matrice identité.

Exemples : ici
; d = 1 (1 rotation)
; d = 1 (1 rotation ou 1 permutation)
; d = 2 (2 rotations)
; d = 3 (1 permutation et 2 rotations)
; d = 5 (4 permutations et 1 rotation de l'ensemble)

Finalement

[pachacamac]

En tout cas vos discussions font avancer le smilblick pour la résolution du problème P=NP,

"le seul des 7 problèmes à un millions de dollars de la liste du millénium accessible aux non-spécialistes, dans la mesure où sa description est accessible et une idée simple pourrait suffire à le résoudre"

"Savoir si P = NP est l'un des principaux problèmes ouverts de l'informatique théorique.
Pour schématiser, en informatique, certains problèmes peuvent être résolus rapidement (problèmes P), tandis que d'autres prennent beaucoup de temps (problèmes NP). Le problème P vs NP demande si tous les problèmes dont on peut vérifier rapidement une solution peuvent également être résolus rapidement.
"Savoir si P = NP est l'un des principaux problèmes ouverts de l'informatique théorique. -wikipédia

[Liet Kynes]

Bonjour, le problème posé est : comment caractériser le niveau de désordre aléatoire d'une liste courte de nombres par rapport à l'ordre croissant ? (A quel point la liste est mélangée par rapport à l'ordre croissant).
Dans le cas général d'un ordre O et d'une liste L, c'est un problème complexe de statistiques et d'algorithmique, on se limite ici à une liste de quelques nombres et à l'ordre croissant. L'idée est de proposer des solutions pour se "faire les dents" en tenant compte des contre-arguments, sans prétention sur le fait de réinventer la théorie.

2 objectifs :
1) caractériser ce niveau de désordre mathématiquement
2) chercher une méthode statistique ou algorithmique pour évaluer ce désordre sur une liste, qui ne donne pas de résultat aberrant pour certaines listes (à priori impossible dans le cas général comme dit plus haut).

Ouf une liste de nombre, une liste de mots ou de coordonnées ou d'autre chose amène une conversion en liste de nombre pas fastoche.
Pour une liste donnée de n nombres la méthode la plus courte sui tant est que l'on puisse l'identifier peut ne pas être la même que pour une autre liste de n nombres.
Est-ce là le problème ?

[Juzo]

Ouf une liste de nombre, une liste de mots ou de coordonnées ou d'autre chose amène une conversion en liste de nombre pas fastoche.
Pour une liste donnée de n nombres la méthode la plus courte sui tant est que l'on puisse l'identifier peut ne pas être la même que pour une autre liste de n nombres.
Est-ce là le problème ?

Bonjour, désolé je n'ai pas eu le temps de me connecter ces derniers jours. Je n'ai pas bien compris "amène une conversion en liste de nombre pas fastoche", ainsi que la suite du message : veux-tu dire qu'il est malaisé voire impossible (comme dit auparavant) de trouver une méthode de tri ou d'évaluation du désordre adaptée à n'importe quelle liste de n nombres ? C'est en effet décrit aussi dans les liens sur les algorithmes fournis par des intervenants.

Mon interrogation du tout départ (que j'aurais peut-être dû formuler ainsi...) était que si je fait tomber un paquet de feuillets rangées avec des mots dans l'ordre alphabétique et que les feuillets se mélangent, comment évaluer le niveau de désordre de mon paquet de feuillets par rapport à l'ordre précédent - autrement qu'en rangeant le paquet et en regardant le "temps" que cela m'a pris ?

Une intuition était que le paquet est parfaitement en désordre aléatoire si les déplacements des feuillets par rapport à leurs positions initiales sont des nombres aléatoires.
Or (corrigez-moi *gentiment* si je me trompe), mais une manière de définir le caractère totalement aléatoire d'une suite de nombres est qu'il est impossible de décrire cette suite plus efficacement qu'en l'énonçant.

Décrire al suite des déplacements de feuillets est "un peu" comme ranger le paquet, c'est pourquoi je me demandais s'il était possible de décrire le désordre d'un paquet de feuillets plus rapidement qu'en le rangeant... Question qui bien trop complexe pour le cas général (donc pas si mauvaise que ça, n'en déplaise à certains), mais que j'applique maintenant à une liste de quelques nombres et à l'ordre croissant. La question était posée dans le forum science ludique au départ et je trouvais ludique de chercher des solutions sur un cas simple à propos d'un problème complexe en toute connaissance de cause.

Les deux solutions "mathématiques" que j'ai proposées (messages 17 et 40) sont totalement dérisoires et très probablement fausses, mais je dois dire en toute modestie qu'elles ne m'ont pas valu d'être traité de naïf, d'ignorant, d'être accusé de réinventer la roue carrée ou de bavarder comme un canard épileptique.

Ce que je remarque dans ces solutions, c'est que pour éviter le problème qu'une méthode "peut ne pas être la même que pour une autre liste de n nombres" comme dit Liet Kynes, je mesure le désordre aléatoire d'une liste de 5 nombres par rapport à la même liste ordonnée... Et on ne s'affranchit donc pas du problème du tri de la liste.

Une autre proposition intéressante était celle de Deedee81, de regarder si chaque élément n est ordonnée par rapport à n+1, mais il me semble que la liste anti-alphabétique obtient le pire score, alors qu'elle se range en retournant le paquet. Désolé pour le long message.

[oxycryo]

je prend la discussion en cours, sans trop tout comprendre

toutefois, je me demande comment il se pourrait que la notion d'ordre ou de désordre ne soient pas complètement relative à la définition que l'on veux bien lui prêter
par exemple: l'ordre alphabétique, est si l'on y regarde bien qu'un tas de signe en désordre, une simple convention, et idem pour les chiffres...

delà, comment la mesure du désordre, via informatique, pourrait-elle différente quantitativement au nombre d'opérande nécessaire pour permuter vers le nouveaux désordre (appellé new_order ) arbitrairement choisie avec raison...

donc cette quantification, toujours relative à la méthode choisie, pour ces permutations...

[Liet Kynes]

Mon interrogation du tout départ (que j'aurais peut-être dû formuler ainsi...) était que si je fait tomber un paquet de feuillets rangées avec des mots dans l'ordre alphabétique et que les feuillets se mélangent, comment évaluer le niveau de désordre de mon paquet de feuillets par rapport à l'ordre précédent - autrement qu'en rangeant le paquet et en regardant le "temps" que cela m'a pris ?

Il y a obligatoirement une manière de ranger qui prend le moins de temps, si les feuilles sont numérotées et que tu peux comparer tous les numéros simultanément, tu vas pouvoir classer très vite ; dans l'idée, tu as cinq objets de tailles différentes non classés dans l'ordre de leur taille, d'un simple coup d'œil tu peux les classer mais élaborer un algorithme efficient dépend de la nature de l'ordre et il est possible que l'algorithme le plus efficient ne soit pas la méthode la plus efficiente.

[ArchoZaure]

En fait justement vous soulevez une question que je me pose également.
Est-ce qu'il n'y aurait pas plusieurs manières de définir l'ordre ?

Par exemple, chez moi, quelqu'un qui viendrait visiter ma maison trouverait un désordre absolument inimaginable.
Aucun voleur ne s'y retrouverait, et son larcin nécessiterait une longue recherche pour dénicher des objets de valeur.
Me concernant par contre, tout est "à sa place".
Celle en rapport avec l'usage pratique, l'historique de l'usage, sans aucun souci d'esthétique.
C'est mémorisé dans ma mémoire et l'ordre c'est ma mémoire qui la définie.

Donc par exemple la chaine suivante
8 ,5, 0, 3, 4, 1, 6, 9, 2
peut tout à fait constituer la chaine la plus ordonnée et tout ce qui s'en éloignerait serait de plus en plus désordonné.

[Liet Kynes]

Dans une liste de n éléments, l'ordre croissant est un arrangement parmi les n! arrangements possibles .
À mon avis, la manière de "définir l'ordre" consiste juste à choisir un arrangement particulier comme étant l'ordre souhaité.

[pm42]

Dans une liste de n éléments, l'ordre croissant est un arrangement parmi les n! arrangements possibles .
À mon avis, la manière de "définir l'ordre" consiste juste à choisir un arrangement particulier comme étant l'ordre souhaité.

Cela va plus loin que ça. Si on prenait autre chose que des nombres, par exemple des pays, on pourrait pour se simplifier la vie attribuer à chacun un numéro qui traduirait cet ordre.
Si on change l'ordre, on renumérote ou pour parler informatique, on réindexe.

Et on constate que le problème ne change pas du tout puisque qu'on est à une bijection prêt.

Dire "mon meilleur classement est 8 ,5, 0, 3, 4, 1, 6, 9, 2" revient à faire cette bijection et cela n'a aucun impact ni aucun intérêt pour la résolution du problème.

[Liet Kynes]

Cela va plus loin que ça. Si on prenait autre chose que des nombres, par exemple des pays, on pourrait pour se simplifier la vie attribuer à chacun un numéro qui traduirait cet ordre.
Si on change l'ordre, on renumérote ou pour parler informatique, on réindexe.

Et on constate que le problème ne change pas du tout puisque qu'on est à une bijection prêt.

Dire "mon meilleur classement est 8 ,5, 0, 3, 4, 1, 6, 9, 2" revient à faire cette bijection et cela n'a aucun impact ni aucun intérêt pour la résolution du problème.

On peut indexer les pays en fonction de leur ordre alphabétique, mais on peut aussi le faire sur les coordonnées géographiques de la capitale (latitude / longitude) ou des couleurs du drapeau, une difficulté qui me vient à l'esprit est de donner une identité unique dans certains cas.

[Ikhar84]

Mon interrogation du tout départ (que j'aurais peut-être dû formuler ainsi...) était que si je fait tomber un paquet de feuillets rangées avec des mots dans l'ordre alphabétique et que les feuillets se mélangent, comment évaluer le niveau de désordre de mon paquet de feuillets par rapport à l'ordre précédent - autrement qu'en rangeant le paquet et en regardant le "temps" que cela m'a pris ?

Les questions à se poser, à mon humble avis :

1. Comment ferais-tu pour ranger manuellement dans un ordre arbitraire ces feuillets.
A. Dans le cas où ils portent un mot (quel langue, quel ensemble de symboles alphbétique).
B. Dans le cas où ils portent une image (photo, dessin, etc...)
C. Dans le cas où ils portent un symbole (ou ensemble de symboles) arbitraires (texte, idéogramme, chiffres, dessin,...)

2. Comment élaborer une méthode pour qu'un système automatisé puisse reproduire les manipulations de façon optimisée et systématique...

À noter que si une lettre peut être assimilée (codée) en un nombre, un mot ou une chaîne de caractère quelconque ne peut pas l'être (c'est une matrice 1d, une suite, un vecteur, ce que tu souhaites comme definition, mais ce n'est pas réductible, sauf opération supplémentaire, comme un hachage ou une compression, radicale).

[ArchoZaure]

À noter que si une lettre peut être assimilée (codée) en un nombre, un mot ou une chaîne de caractère quelconque ne peut pas l'être (c'est une matrice 1d, une suite, un vecteur, ce que tu souhaites comme definition, mais ce n'est pas réductible, sauf opération supplémentaire, comme un hachage ou une compression, radicale).

Un mot ne peut-il pas juste être considéré comme un nombre en base 26 ? (sans les caractères spéciaux, mais sinon ça ne change rien, c'est dans ce cas une base plus grande c'est tout)

Ah oui je vois, vous écrivez les nombres de droite à gauche et les mots de gauche à droite...
Pour classer pareil c'est pas top.

[Ikhar84]

Dans ce cas (sauf si tu veux des opérations de "réduction de dimention"), tu n'as qu'à indexer les mots (post de pm), notes que tu devra préalablement repertorier tous les mots et leur affecter un nombre (index). Ce qui sera (presque) équivalent à précalculer et stocker en mémoire un dictionnaire, en plus de la mémoire de travail (ordonner, trier, ...).

[pm42]

Dans ce cas (sauf si tu veux des opérations de "réduction de dimention"), tu n'as qu'à indexer les mots (post de pm),

Oui d'autant que la base 26 (qui ne prend pas en compte les accents, différents alphabets, etc) ne se prête pas bien au stockage sur des bits.
On doit donc prendre de la base 32 et si on fait ce genre de choses, on vient de réinventer le calcul en précision infinie.

Cela revient à ignorer tout l'avantage d'utiliser des entiers sur un ordinateur : la vitesse et la capacité à stocker tout ce qu'on utilise couramment sur 32 à 64 bits ce pourquoi le hardware est optimisé : comparaison, stockage, etc.

notes que tu devra préalablement repertorier tous les mots et leur affecter un nombre (index).

Ce qui est en effet un grand classique des tous les programmes qui travaillent avec des dictionnaires depuis les méthodes de hash, d'arbre trié, etc jusqu'au méthodes actuelles d'embedding en IA (qui transforment les mots, phrases, et plus précisément les tokens vaguement assimilables à des unités lexicales en vecteurs d'entiers).

[ArchoZaure]

Dans ce cas (sauf si tu veux des opérations de "réduction de dimention"), tu n'as qu'à indexer les mots (post de pm), notes que tu devra préalablement repertorier tous les mots et leur affecter un nombre (index). Ce qui sera (presque) équivalent à précalculer et stocker en mémoire un dictionnaire, en plus de la mémoire de travail (ordonner, trier, ...).

Non rien à voir avec une question d'index.
Si vous considérez le mot comme étant un nombre en base 26 C'EST UN NOMBRE.
Pour une phrase passez en base 27 pour tenir compte des espaces.

Rien à voir non plus avec le binaire qui ferait qu'on travaille mieux en base 10 avec du binaire qu'en base 26, bien sûr.

[pm42]

Au final, tout est un nombre en binaire pour les ordinateurs actuels.
Mais ça nous fait une belle jambe quand on fait du yakafokon pour proposer des solutions inefficaces à souhait à tous les niveaux.
Et c'est mignon de prendre en compte les espaces pour les phrases en oubliant majuscules/minuscules, accents, virgules, etc.

[Ikhar84]

Reste plus qu'à trouver un dispositif qui travaille en base 26...
Et ignorer tous les algos de codage/chiffrage/hachage... en base 2...

Non rien à voir avec une question d'index.
Si vous considérez le mot comme étant un nombre en base 26 C'EST UN NOMBRE.
Pour une phrase passez en base 27 pour tenir compte des espaces.

Rien à voir non plus avec le binaire qui ferait qu'on travaille mieux en base 10 avec du binaire qu'en base 26, bien sûr.

[ArchoZaure]

Reste plus qu'à trouver un dispositif qui travaille en base 26...
Et ignorer tous les algos de codage/chiffrage/hachage... en base 2...

Un... dispositif ?
vous voulez parler d'un programme ?
Il y en a plein déjà.
faites vous plaisir.
https://www.translatorscafe.com/unit...cimal-base-26/

[ArchoZaure]

Oui d'autant que la base 26 (qui ne prend pas en compte les accents, différents alphabets, etc) ne se prête pas bien au stockage sur des bits.

Rien avoir avec les bits.
Regardez comment ça marche.

Vous me dite qu'il manque des caractères.
Je vous l'ai déjà dit plus haut mais vous faites comme si vous n'avez pas lu.
OK
Donc comme vous ne voyez pas comment contourner cette limitation je vais vous aider.

On prend une base 256.
Voir le code ASCIIi ici
https://web.maths.unsw.edu.au/~lafay...base/ascii.htm

Et donc vous prenez le mot.
Caractère 1 depuis la, DROITE vous multipliez sa valeur (0-255) par... 256⁰
Caractère 2 depuis la, DROITE vous multipliez sa valeur (0-255) par... 256¹
Caractère 3 depuis la, DROITE vous multipliez sa valeur (0-255) par... 256²
....
Caractère n depuis la, DROITE vous multipliez sa valeur (0-255) par... 256ⁿ

Vous additionnez tout ça et ça vous donne la valeur de la chaine ASCII.

C'est pas sorcier.
Encore faut-il être informaticien ?

[Ikhar84]

On parle toujours de trier et d'ordonner ?
Convertir entre bases n'a jamais posé de problème...

Un dispositif matériel automatisable (logiciel) capable de remplir la tâche demandée par le primo posteur...

Une machine de turing (pas nécessairement avec une archi Von Neumann).

Edit :
Croisement...
Vous avez inventé le hachage...

[ArchoZaure]

On parle toujours de trier et d'ordonner ?
Convertir entre bases n'a jamais posé de problème...

Un dispositif matériel automatisable (logiciel) capable de remplir la tâche demandée par le primo posteur...

Une machine de turing (pas nécessairement avec une archi Von Neumann).

Je répondais juste à votre remarque :

À noter que si une lettre peut être assimilée (codée) en un nombre, un mot ou une chaîne de caractère quelconque ne peut pas l'être (c'est une matrice 1d, une suite, un vecteur, ce que tu souhaites comme definition, mais ce n'est pas réductible, sauf opération supplémentaire, comme un hachage ou une compression, radicale).

Et je vous ai répondu :

Un mot ne peut-il pas juste être considéré comme un nombre en base 26 ? (sans les caractères spéciaux, mais sinon ça ne change rien, c'est dans ce cas une base plus grande c'est tout)

Ah oui je vois, vous écrivez les nombres de droite à gauche et les mots de gauche à droite...
Pour classer pareil c'est pas top.

Et je vous l'ai prouvé.

Mais peut-être ne nous sommes nous pas compris ?
Dans ce cas n'hésitez pas à développer.