On me présente un réseau de comparaison. Comment déterminer si le réseau de comparaison est un réseau de tri? Dans l'image ci-dessous, il y a un exemple de réseau de tri par sélection et de tri par insertion. L'objectif est d'avoir un réseau de comparaison et de trier les valeurs numériques. Si je teste 2 ^ n valeurs dans ce cas 2 ^ 8. C'est beaucoup de travail | moyen non efficace de le tester. Je recherche un modèle mathématique / preuve pour vérifier qu'il s'agit d'un réseau de tri valide.

En général, vérifier si un réseau de comparaison particulier est effectivement un réseau de tri correct est un problème complet de Co-NP. Si vous souhaitez vérifier en testant, vous devez essayer de manière exponentielle de nombreux tests.

En particulier, il existe des réseaux de tri qui trient correctement toutes les valeurs sauf une, de sorte que vous ne pouvez pas espérer tester si le réseau est correct ou non simplement en l'alimentant en quelques entrées.

Une méthode standard consiste à tester s'il trie correctement toutes les entrées composées uniquement de zéros et de uns. Si c'est le cas, il s'avère qu'il triera toutes les entrées (même celles qui ne sont pas limitées aux zéros et aux uns). Cependant, cela nécessite de manière exponentielle de nombreux tests. De plus, le nombre de tests ne peut pas être réduit de manière significative: pour des entrées nulles, il est possible de prouver qu'au moins tests sont nécessaires, à tel point que le réseau de tri est correct.$2^n$$2^n-n-1$

Alternativement, on peut utiliser des tests où les entrées sont des permutations de . Cela réduit quelque peu le nombre de tests nécessaires, mais vous avez encore besoin de manière exponentielle de nombreux tests. En particulier, les tests sont nécessaires et suffisants.$1,2,\dots,n$$C(n, \lfloor n/2 \rfloor)-1$

Pour des preuves de ces faits, consultez les documents suivants:

Sur la complexité informatique de la vérification du réseau de tri optimal . Ian Parberry. Parle'91 Parallel Architectures and Languages ​​Europe, 1991.

Limites sur la taille des jeux de tests pour le tri et les réseaux associés . Moon Jung Chung et B. Ravikumar. Discrete Mathematics, vol 81, pp.1--9, avril 1990.

Citant votre question:

Je recherche un modèle mathématique / preuve pour vérifier qu'il s'agit d'un réseau de tri valide.

Alors que (l'excellente) réponse de DW concerne le cas général, je considérerai votre exemple spécifique. Un réseau de cette forme avec entrées peut être montré comme un réseau de tri par induction: (voir l'image pour l'illustration)$n$

1. $n=1$ entrée est toujours triée;
2. Supposons qu'un réseau de taille de cette forme soit un réseau de tri et considérons un réseau de taille . $n-1$$n$
   1. Le plus à gauche apportera toujours correctement « diagonale » le plus grand élément à la position de -ème (dans votre cas, );$n$$b_8$
   2. Vous vous retrouvez avec un réseau similaire plus petit avec les éléments restants ;$n-1$
   3. Ce réseau plus petit triera tous les éléments restants par l'hypothèse inductive.

Lorsque vous regardez sur un réseau de tri général, vous ne savez peut-être pas comment prouver qu'il trie correctement chaque séquence de valeurs (ayant la bonne longueur pour le réseau de tri). Mais j'ai appris ce truc sympa, comment simplifier la tâche:

Le principe 0-1

Lorsqu'un réseau de tri trie correctement chaque séquence (avec la bonne longueur) composée uniquement de "0" et "1", il trie correctement toute séquence (avec la bonne longueur). Bien sûr, "0" et "1" sont des espaces réservés pour tous les éléments distincts dans le domaine du réseau de tri.

Vous pouvez donc construire une preuve comme celle-ci:

1. Prenez deux éléments distincts du domaine du réseau de tri et appelez-les "0" et "1", de sorte que "0" <"1"
2. Construire toutes les chaînes binaires avec la longueur exacte du réseau de tri
3. Dans ces chaînes, remplacez le 0-bit et le 1-bit par "0" et "1"
4. Appliquer ces chaînes au réseau de tri
5. Chaque chaîne doit être triée en quelque chose comme 000..01 ... 1

Essai $2^n$ valeurs

Pour un test exhaustif d'un réseau de tri de longueur $n$vous devrez généralement tester toutes les combinaisons d'entrée. Mais avec le principe 0-1, vous pouvez ramener cela à$2^n$ tests (test de toutes les chaînes binaires de longueur $n$).

Pouvons-nous le faire moins cher?

Malheureusement, nous ne pouvons probablement pas obtenir beaucoup moins cher que des tests exhaustifs, du moins pas lors de l'utilisation d'une machine de Turing pour construire les épreuves. Bien sûr, lorsque vous regardez un réseau de tri spécifique, vous pouvez avoir une idée créative sur la façon de faire une simple preuve. Mais en général, un algorithme pour construire de telles preuves est très probablement aussi complexe que de tester toutes les chaînes binaires. La raison en est que le réseau de tri de vérification est lié à la classe de complexité complète NP, comme indiqué dans les autres réponses.

«Beaucoup moins cher» dans ce contexte signifie «temps polynomial». Il pourrait être possible de trouver un algorithme qui puisse le faire "légèrement" plus rapidement que le temps exponentiel mais qui a besoin de plus que du temps polynomial. Voir les commentaires pour un exemple:$2^{\sqrt n}$ pas est (légèrement) plus rapide que le temps exponentiel mais toujours (beaucoup) plus lent que le temps polynomial.

Prospect / Outlook

Votre cerveau est-il une machine de Turing

Une conséquence philosophique est la suivante: lorsque vous croyez pouvoir trouver une preuve créative de l'exactitude de chaque réseau de tri, vous pensez également que votre cerveau n'est probablement pas une machine de Turing.

Tri parallèle

Le "principe 0-1" est également utilisé pour prouver l'exactitude des algorithmes de tri parallèle. J'ai (espérons-le) une belle présentation à ce sujet sur Github .

Correction du réseau de tri

Si l'une des chaînes n'est pas triée correctement (vous avez donc prouvé que le réseau de tri est incorrect), vous pouvez l'utiliser pour construire un réseau de tri sans ce bogue. Ajoutez simplement une comparaison supplémentaire sur la position de la "bordure 1-0" dans la mauvaise chaîne de résultat.