Algo de classement

Répondre

Messages : 1

Enregistré le : 15 mai 2019 23:06

Classe : MP*

Algo de classement

Message par tomdalton6868 » 13 févr. 2022 12:28

Hello tout le monde !

Etant en spé option info, l'étude des arbres m'a beaucoup intéressé et je pense que les arbres binaires peuvent être la solution à un problème auquel je pense depuis la terminale.

C'est assez ridicule donc je vais ici parler de tableaux artistiques mais les plus tordus comprendront à quoi je fais allusion :
Admettons que j'ai une liste de 100 tableaux. J'aimerais en faire un classement par beauté mais cela semble impossible à faire. Plutôt que de choisir le plus beau, de l'enlever de la liste et de rechoisir le plus beau et ainsi de suite, je m'étais dit qu'il serait plus judicieux de le faire en un nombre réduit de questions à deux choix.
Je m'explique : l'algo me proposerait deux tableaux et j'en choisirais le plus beau des deux. Ainsi, la tâche répétée le moins de fois permettrait de faire un classement global des plus beaux tableaux.

Exemple : 4 tableaux A, B, C et D
Au lieu de prendre le plus beau parmi les 4 qui serait C, puis de choisir parmi les 3 et ainsi de suite pour avoir finalement le classement C A B D, l'algo ferait ça :
A ou C : C
B ou D : B
A ou D : A
A ou B : A

trouvé : C A B D


Ma question est donc la suivante :
Pour n tableaux, combien faudrait-il de questions à deux choix en moyenne pour classer les n tableaux ?

Ma culture en info est limitée mais j'ai fait des recherches et je n'ai pas trouvé d'article traitant ce problème de classement.

Amicalement,
Tom

Messages : 105

Enregistré le : 09 août 2018 20:57

Re: Algo de classement

Message par GrosGillouDu92 » 13 févr. 2022 13:14

Bonjour,

Le terme exact est plus algorithme de tri que algorithme de classement.

Il me semble que ce que tu as en tête pourrait être un tri arborescent qui consiste à insérer successivement chacun des n éléments dans un arbre binaire de recherche. Tu as dans ce cas une complexité en moyenne en O(n * ln (n)) comparaisons, puisque pour chacun des n éléments tu dois trouver sa place dans l'ABR ce qui a une complexité en ln(n).

C'est donc effectivement meilleur que la première méthode qui me semble être un tri par sélection pour lequel tu vas faire n*(n-1)/2 comparaisons et donc une complexité en O(n²).
Parent
L3 Gestion Dauphine / EMLV
MP* Info Hoche / X
MP2I Hoche

Messages : 3

Enregistré le : 16 janv. 2022 10:41

Re: Algo de classement

Message par emeric.tourniaire » 14 févr. 2022 23:47

Il s'agit effectivement d'un algorithme de tri par comparaisons. Beaucoup existent avec des avantages ou des inconvénients, mais on peut raisonnablement montrer qu'on ne peut pas espérer faire moins de O(n ln n) comparaisons.

Si on considère l'arbre binaire dont les nœuds sont les comparaisons effectuées et les feuilles sont les classements complets, alors la hauteur maximale h de l'arbre correspond au nombre maximal de comparaisons, et limite le nombre de feuilles à 2^h. Par ailleurs, chacune des n! permutations doit figurer sur une feuille, ce qui donne donc 2^h > n! d'où (...) h > n/2 log_2(n/2).

Messages : 9675

Enregistré le : 30 juil. 2008 16:59

Classe : Dr.-Ing

Re: Algo de classement

Message par fakbill » 28 févr. 2022 10:22

puisque pour chacun des n éléments tu dois trouver sa place dans l'ABR ce qui a une complexité en ln(n).
Ca n'aide pas beaucoup à comprendre le pourquoi je trouve :(.
Il y a 2^N classements possibles.
Un choix permet de sélectionner une alternative parmi 2.
On calcule donc facilement le nombre minimal de choix (comparaisons) qu'il va falloir effectuer....et ça explique facilement le 'n log n'
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Messages : 31

Enregistré le : 01 nov. 2021 21:16

Re: Algo de classement

Message par chamaerops » 07 août 2022 12:41

Pour n tableaux il y a n! permutations dont une seule (par hypothèse) représente le classement ordonné des tableaux par beauté. Une preuve que j'aime bien est celle qui utilise la théorie de l'information.
Une comparaison (ou question à deux choix) te donne un bit d'information. Donc le nombre de comparaisons nécessaires pour discriminer la bonne permutation est logbase2(n!) \equiv n ln(n) / ln(2). Donc effectivement un algorithme de tri basé sur des comparaisons que le PO évoque bien a une complexité asymptotique en comparaisons en O(n log n) (qui vaut aussi dans le pire cas) comme l'ont dit les autres, ce qui équivaut à descendre un arbre binaire complet, dont la profondeur est aussi de l'ordre de O(n log n) pour représenter n! permutations, c'est un résultat bien connu.
Le tri fusion est un algorithme présentant la complexité asymptotique optimale pour ce problème.

C'est bizarre que tu n'aies pas trouvé en cherchant, ce résultat est dans tous les livres d'informatique, je pense que tu n'as pas dû utiliser les bons mots clés. Pour une entrée en matière, wikipédia (anglais c'est mieux souvent) donne de bonnes idées et sources.

[que qqn me corrige si j'ai raconté des ânneries qqpart]

Répondre