Qu'est-ce qui est plus difficile: mélanger un jeu trié ou trier un jeu mélangé?

Vous avez un tableau de éléments distincts. Vous avez accès à un comparateur (une fonction de boîte noire prenant deux éléments et et retournant vrai ssi ) et une source de bits vraiment aléatoire (une fonction de boîte noire ne prenant aucun argument et retournant un bit aléatoire uniformément indépendant). Considérez les deux tâches suivantes: $n$ $a$ $b$ $a < b$

Le tableau est actuellement trié. Produire une permutation choisie au hasard de manière uniforme (ou approximativement uniforme).
Le tableau se compose d'une permutation sélectionnée uniformément au hasard par nature. Produisez un tableau trié.

Ma question est

Quelle tâche nécessite plus d'énergie de manière asymptotique?

Je ne suis pas en mesure de définir la question plus précisément parce que je ne connais pas suffisamment le lien entre la théorie de l'information, la thermodynamique ou tout ce qui est nécessaire pour répondre à cette question. Cependant, je pense que la question peut être bien définie (et j'espère que quelqu'un m'aidera avec une réponse!).

Maintenant, algorithmiquement, mon intuition est qu'ils sont égaux. Notez que chaque tri est un shuffle à l'envers, et vice versa. Le tri nécessite comparaisons, tout en mélangeant, car il choisit une permutation aléatoire dechoix, nécessite bits aléatoires. Le brassage et le tri nécessitent environ échanges. $\log n! \approx n \log n$ $n!$ $\log n! \approx n \log n$ $n$

Cependant, je pense qu'il devrait y avoir une réponse appliquant le principe de Landauer , qui dit qu'il faut de l'énergie pour "effacer" un peu. Intuitivement, je pense que cela signifie que le tri du tableau est plus difficile, car il nécessite "d'effacer" bits d'information, passant d'un état de trouble fondamental à faible énergie et haute entropie à un état de désordre hautement ordonné. Mais d'un autre côté, pour un calcul donné, le tri transforme simplement une permutation en une autre. Comme je ne suis pas un expert complet ici, j'espérais que quelqu'un ayant une connaissance de la connexion à la physique pourrait aider à "trier" cela! $n \log n$

(La question n'a reçu aucune réponse sur math.se , donc je la republie ici. J'espère que ça va.)

algorithms algorithm-analysis information-theory permutations entropy usul
la source

Je n'y ai pas réfléchi du tout, alors avertissez le lecteur. Si nous commençons avec un tableau trié, puis utilisons le tri par fusion, mais au lieu de comparer, nous utilisons les bits aléatoires pour effectuer la fusion (donc au lieu de renvoyer true ssi

nous renvoyons true ssi le bit aléatoire est

). Le cas de base où nous avons deux tableaux de taille un produit les deux tableaux possibles de taille deux avec une probabilité uniforme. Je ne suis pas allé plus loin que ça.

a < b

$a<b$

1

$1$

Luke Mathieson

Je pense que pour répondre à cette question, il faut d'abord définir les coûts relatifs de fonctionnement; combien cela coûte-t-il de lire des données, d'écrire des données et de générer / obtenir un nombre aléatoire?

mitchus

@mitchus: Je suis principalement curieux de connaître les limites physiques si nous supposons des ordinateurs "optimaux et efficaces". Ma compréhension approximative est qu'il existe une limite inférieure physique sur la quantité d'énergie requise pour «effacer» un peu d'informations, tandis que d'autres opérations nécessitent beaucoup moins d'énergie. Je me demande donc si cette intuition est suffisamment correcte et formalisable pour donner une réponse.

usul

Que voulez-vous dire par effacer un peu? Le remplacer? Autant que je sache, les ordinateurs n'effacent généralement rien (sauf pour des raisons de confidentialité) mais simplement "l'oublient" en désallouant la région de mémoire associée. Mais peut-être que je ne saisis pas correctement le niveau d'abstraction ici :)

mitchus

@ Patrick87 Malheureusement, un modèle énergétique uniforme est trop éloigné de la vérité pour l'utiliser; voir Évaluation des algorithmes en fonction de leur consommation d'énergie par Fudeus née Bayer et Nebel (2009).

Raphael

Réponses:

Selon le principe de Landauer, si vous voulez prendre une permutation aléatoire uniforme de clés en une clé triée, et ne pas conserver de bits dans l'ordinateur qui révèlent quelle était la permutation aléatoire uniforme, vous devez effacer bits. Cela prendra énergie D'autre part, le calcul en prenant le tableau trié et bits aléatoires dans le tableau aléatoire est réversible, et ainsi l'énergie dépensée peut être rendue arbitrairement petite. $n$ $log n! \approx n \log_2 n$ $(n \ln n) k T$ $n \log_2 n$

Notez que ce ne sont que des bornes inférieures théoriques. L'énergie actuellement consommée par ces processus sur un ordinateur numérique réel n'a aucun rapport avec l'analyse ci-dessus.

Peter Shor
la source

Merci beaucoup! Puis-je demander un suivi éventuellement naïf? Supposons que je modifie le libellé de la question de sorte que l'algorithme de tri reçoive une permutation fixe des éléments et doive les trier. Maintenant, si vous souscrivez à une philosophie bayésienne et avez une croyance uniforme sur cette entrée, il semble que la réponse devrait être la même. Mais selon une philosophie selon laquelle il n'y a pas d'aléatoire dans l'entrée (bien que je ne sache pas ce que c'est), l'argument semble échouer. Comment résoudre le paradoxe? Merci encore!!

usul

(n \ln n) k T

$(n \ln n) kT$

Ni. Tout circuit peut être rendu réversible en gardant une trace de l'entrée, et la dissipation d'énergie du calcul réversible peut être rendue arbitrairement petite .

rphv
la source

mais le rendre réversible pourrait le rendre non efficace. Quelle est la relation entre les algorithmes optimaux . BTW, je ne pense pas qu'ils se comparent. Le brassage nécessite intrinsèquement un caractère aléatoire (et tout caractère aléatoire différent produira une sortie différente). Le tri peut être déterministe. Le tri "inversé" sera mélangé de manière déterministe.

Ran G.

Par «efficace», voulez-vous dire le temps, l'espace ou une combinaison des deux? Rendre un calcul réversible n'ajoute pas nécessairement une complexité temporelle asymptotique, et il existe des versions réversibles de chaque calcul qui n'utilisent pas plus d'espace que l'original [Vitányi05] .

rphv

Tant que vous gardez l'entrée autour, n'importe quel circuit peut être rendu réversible. Si vous ne souhaitez pas conserver d'informations permettant de reconstruire la permutation d'origine, le circuit de tri ne peut pas être rendu réversible.

Peter Shor