Discussion :

[Guesset]

Bonjour Anapurna,

...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Fonction recherche_dichotomique(tab, val)
FAIRE
   gauche = 0
   droite = len(tab) - 1
   Tanque gauche <= droite Faire 
   FAIRE                                              
      milieu = (gauche + droite) / 2  # on a besoin que du quotient
      SI tab[milieu] = val ALORS       # on a trouvé val dans le tableau,
         retourne milieu   # à la position milieu
      SINON 
         SI  tab[milieu] > val ALORS  # on cherche entre gauche et milieu - 1
           droite = milieu - 1
         SINON                             # on a tab[milieu] < val
             gauche = milieu + 1    # on cherche entre milieu + 1 et droite
        FINSI
     FINSI
   FINFAIRE
   retourne -1 # on est sorti de la boucle sans trouver val
FINFAIRE

Il me semble qu'il manque le critère de sortie de boucle (hors égalité à val trouvée) et une précision sur le calcul du pivot.

Salut

[Philtheform]

Bon, je n'arrive toujours pas à me faire comprendre. Le plus simple, comme le dis Tcb92, c'est d'oublier tout l'aspect «informatique».

Bien évidemment je cherche une méthode générale. La liste de 66 est juste un «appui» pour me faire comprendre et comprendre une éventuelle réponse.
Mes capacités d'abstraction sont certainement bien plus limitées que les vôtres.

Basiquement, vous me conseillerais quoi comme «entrée» dans un moteur de recherche ?

Je regarderais le «sinus cardinal normalisé» quand je serais en forme parce que, là, c'est du Chinois.
De but en blanc, je ne vois pas comment de la trigo. se raccroche au truc, mais pourquoi pas.

[Flodelarab]

c'est d'oublier tout l'aspect «informatique».

C'est là ton erreur. Soit on oublie le caractère informatique et n'importe quelle homothétie ratatine l'espace aussi petit que l'on veut. Soit on est en informatique et la bijection nécessaire pousse à utiliser un tableau associatif qui donne instantanément le résultat.

Basiquement, vous me conseilleriez quoi comme «entrée» dans un moteur de recherche ?

À ta place, , un tableau associatif avec le score en clé et l'indice du premier tableau en valeur. Si plusieurs objets ont le même score, il faut gérer la multitude.

Exemple script bash avec awk : Le premier nombre est le score de recherche, le second, le nom de l'objet recherché.

Code bash :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
$ cat moteur.txt 
47;objet1
58;objet2
58;objet3
201;objet4
50;objet5
201;objet6
67;objet7

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
$ awk -F';' '{scores[$1]++;lignes[$1,scores[$1]]=NR;noms[NR]=$2;} END{n=asorti(scores,tri,"@ind_num_desc"); for (i=1;i<=n;i++) for (j=1;j<=scores[tri[i]];j++) print noms[lignes[tri[i],j]]; }' moteur.txt 
objet4
objet6
objet7
objet2
objet3
objet5
objet1

Tu vois, une fois les scores calculés, ça prend une ligne. Ils sont triés dans l'ordre décroissants du score.

[Guesset]

Bonjour,

Sous le seul aspect mathématiques, ce qui est recherché est une bijection entre l'espace des entiers [0, 66[ et l'ensemble des 66 valeurs.

Il faut que cette bijection existe ce qui interdit que l'ensemble des valeurs ait des doublons.

La bijection peut être décrite par 66 couples qui associent chacun des entiers de l'espace [0, 66[ à chacun des élément de l'ensemble de valeurs (le cardinal est nécessairement le même).

Si les valeurs sont ordonnées et que l'on souhaite conserver cet ordre dans l'espace associé, la bijection devient unique.

Si on souhaite que des fonctions (directe et inverse) décrivent la bijection, c'est toujours possible quand on reste entre ensembles d'entiers. Mais ce n'est pas nécessairement intéressant notamment dans le cas où n'existe aucune fonction simple. Une fonction simple se décrit comme une fonction qui possède moins de paramètres que le cardinal de l'ensemble de valeurs. Cela semble le cas ici. Par exemple, l'approche polynomiale donne autant de coefficients qu'il y a d'éléments. De plus, la fonction inverse n'est pas nécessairement plus simple.

En résumé, ici la bijection se décrit par un ensemble de 66 couples.

Informatiquement, c'est ce que propose un tableau 66 valeurs.

Salutations

[Philtheform]

Je le redis la fonction inverse, je n'en ai pas vraiment besoin. J'ai dit comment la court-circuiter.
«n'importe quelle homothétie ratatine l'espace aussi petit que l'on veut» ?? C'est pas possible, il y a un truc super évident que je ne capte pas. Cela commence à me faire peur cette histoire. En plus, j'ai une désagréable sensation de «déjà-vu». Je m'interroge sur le fait d'avoir déjà demandé de l'aide sur ce sujet, je ne sais plus quand et je ne sais plus où. En tout cas, si je reviens dans 6 mois/1 an avec la même question, faites le moi savoir immédiatement et j'irai consulté. Et je ne blague qu'a moitié.

[Philtheform]

(...)
En fait, il y a même des formules qui vont permettre de réduire ces 66 nombres aux nombres 0 à 65. C'est certain, c'est mathématique (un polynôme de degré 65 va convenir). (...)

ça veut vraiment dire que n'importe quelle liste de valeurs peut se "ramener" a sa "liste cardinale" ??? Avec le même traitement mathématique ??? Quelle est cette diablerie encore ?
Pourriez-vous me donner des noms/entrées pour que je puisse faire des recherches seul, SVP.
Je vais commencer par tan et arctan mais la technique du polynôme me parait tellement "dingue" que je voudrais le voir pour le croire.

[tbc92]

L'histoire des homothéties qui ratatinent ... oui. Sauf que les homothéties ne vont pas donner des nombres entiers, et quand on va utiliser 'arrondi', on n'a pas l'assurance que tous les entiers obtenus soient différents.

il y a même des formules qui vont permettre de réduire ces 66 nombres aux nombres 0 à 65 un polynôme de degré 65 va convenir

Oui. A partir de N 'contraintes', il y a un polynôme de degré N-1 qui permet de vérifier ces N contraintes. La recherche de ce polynôme est un peu compliquée. Et évidemment, si tu changes ton jeu de N valeurs, il faut rechercher à nouveau le polynôme.

Par exemple, avec 3 valeurs , on part de 45, 70 et 91 et on veut 'ratatiner ça en 0,1,2, avec un polynôme.
On cherche donc 3 réels a,b,c tels que :
a*45²+b*45+c=0
a*70²+b*70+c=0
a*91²+b*91+c=0
C'est un système à 3 équations et 3 inconnues, et ça se résout. Et ça se généralise à tout système à N équations et N inconnues

[Philtheform]

Merci, c'est beaucoup plus clair !

J'abuse mais la complexité pour définir le polynôme de degré N-1 dépend-elle de la nature/profil des valeurs de la liste ou pas du tout ?

[tbc92]

La complexité reste toujours 'haute'.

Mais je redis : trouver cette formule pour ratatiner les données, c'est pour le fun, c'est un jeu. Concrètement, si tu veux faire quelque chose d'opérationnel, quelque chose qui fonctionne, ce n'est pas une piste à retenir. La piste à retenir, c'est celle des dictionnaires (tableaux associatifs, c'est pareil).

[wiwaxia]

... Je regarderais le «sinus cardinal normalisé» quand je serais en forme parce que, là, c'est du Chinois.
De but en blanc, je ne vois pas comment de la trigo. se raccroche au truc, mais pourquoi pas.

Il suffit d'observer que la fonction citée s'annule pour toute valeur entière de (x) différente de zéro:

https://www.wolframalpha.com/input?i...B+y%3D-0.3to+1.
Elle convient donc particulièrement à la constitution d'une somme dont tous les termes sont nuls à l'exception de l'un d'entre eux, lorsque (x) prend l'une des valeurs [0, 1, 2, ... 65} .

... il y a même des formules qui vont permettre de réduire ces 66 nombres aux nombres 0 à 65 un polynôme de degré 65 va convenir

Oui. A partir de N 'contraintes', il y a un polynôme de degré N-1 qui permet de vérifier ces N contraintes. La recherche de ce polynôme est un peu compliquée. Et évidemment, si tu changes ton jeu de N valeurs, il faut rechercher à nouveau le polynôme ...

... Par exemple, l'approche polynomiale donne autant de coefficients qu'il y a d'éléments. De plus, la fonction inverse n'est pas nécessairement plus simple ...

Les polynômes interpolateurs de Lagrange conduiront immanquablement à des oscillations énormes entre les 66 points imposés au graphe de F(x), compte tenu de l'irrégularité de la forme du nuage; ces oscillations ôteront toute signification au graphe obtenu, et interdiront l'existence de la fonction réciproque de F(x), cette dernière n'étant pas monotone.
https://fr.wikipedia.org/wiki/Interp...n_lagrangienne
https://fr.wikipedia.org/wiki/Ph%C3%...%A8ne_de_Runge

L'intervention d'une fonction trigonométrique (il y en a d'autres) permet une meilleure maîtrise de l'explosion numérique

La solution est de nature algorithmique, comme vient de le rappeler tbc92

... Mais je redis : trouver cette formule pour ratatiner les données, c'est pour le fun, c'est un jeu. Concrètement, si tu veux faire quelque chose d'opérationnel, quelque chose qui fonctionne, ce n'est pas une piste à retenir. La piste à retenir, c'est celle des dictionnaires (tableaux associatifs, c'est pareil).

[Philtheform]

Excellent, merci ! Je raccroche au problème maintenant !
Sans comprendre/voire ce qui était utilisé avec Sc, je ne comprenais pas l'expression: F(x) = Σk=0k=65(yk*Sc2(x - xk))

Je n'aurais jamais pensé à utiliser de la trigo. de cette façon dans ce contexte. C'est fortiche quand même !