Analyse d'un algorithme de cas moyen à l'aide de la méthode d'incompressibilité de Kolmogorov

La méthode d'incompressibilité simplifierait l'analyse des algorithmes pour le cas moyen. D'après ce que je comprends, c'est parce qu'il n'est pas nécessaire de calculer toutes les combinaisons possibles d'entrée pour cet algorithme et de dériver ensuite une complexité moyenne. Au lieu de cela, une seule chaîne incompressible est prise en entrée. Comme une chaîne incompressible est typique, nous pouvons supposer que cette entrée peut agir comme une approximation précise du cas moyen.

Je suis perdu quant à l'application effective de la méthode d'incompressibilité à un algorithme. Soit dit en passant, je ne suis pas mathématicien, mais je pense que cette théorie a des applications pratiques dans la programmation quotidienne.

En fin de compte, je voudrais savoir comment je peux déduire le cas moyen d'un algorithme donné, qu'il soit trivial ou complexe. Quelqu'un pourrait-il me montrer comment la méthode peut être appliquée à un algorithme simple? Par exemple, étant donné une chaîne d'entrée S, stockez tous les caractères uniques dans S, puis imprimez chacun individuellement:

void uniqueChars(String s) {
    char[] chars = chars[ s.length() ]
    int free_idx = 0;

    for (int i = 0; i < s.length(); i++) {
       if (! s[i] in chars) {
          chars[free_idx] = s[i]
          free_idx++;
       }
    }

    for (int i = 0; i < chars.length(); i++) {
        print (chars[i])
    }
}

Supposons une recherche linéaire pour vérifier si le tableau contient un élément.

L'extrait de code ci-dessus est uniquement à des fins d'argument. De meilleurs algorithmes permettant de démontrer la théorie sont bien sûr acceptables.

J'ai posé cette question sur StackOverflow ( https://stackoverflow.com/q/24619383/3813812 ) en juillet 2014 et j'ai reçu quelques commentaires utiles mais pas une réponse définitive. Comme l'a souligné l'un des commentateurs, cette question convient mieux à l'informatique StackExchange, alors je pose la question ici aujourd'hui.

Certains documents que j'ai passés en revue comprennent:

1. Une introduction à la complexité de Kolmogorov et à ses applications, par Ming Li et Paul MB Vitányi

2. https://www.cs.duke.edu/~reif/courses/complectures/Li/KC-Lecture1.pdf

3. http://www.detectingdesign.com/PDF%20Files/Kolmogorov%20Complexity%202.pdf

Parmi quelques autres ressources auxquelles je n'ai pas de liens en main.

Si ma compréhension de l'applicabilité de la complexité de Kolmogorov est inexacte ou ce que je demande est impraticable, j'apprécierais une déclaration à ce sujet.

L'idée de la méthode d'incompressibilité est qu'une entrée incompressible satisfait certaines propriétés qui peuvent être utiles dans l'analyse. Dans votre cas, la complexité de l'algorithme dépend du nombre de caractères qui apparaissent dans la chaîne. Lors du traitement du$k$e caractère, le "temps d'exécution" (ou plutôt son proxy, le nombre de comparaisons lors de la vérification de la liste) est $\approx \alpha_k/2$ comparaisons en moyenne, où $\alpha_k$est le nombre de personnages différents qui ont été vus jusqu'à présent. Afin d'estimer$\alpha_k$, notons que nous pouvons encoder le premier $k$ caractères utilisant à peu près $8\alpha_k + k\log \alpha_k$ bits, et nous en déduisons que $8\alpha_k + k\log_2 \alpha_k \geq 8k$. Par conséquent, à moins que$k$ est très petit, $\alpha_k$ doit être très proche de $256$, et on peut en déduire qu'il y a en moyenne $128$comparaisons par caractère. Nous pouvons utiliser l'inégalité pour déterminer la taille$k$ doit être, et aussi ce qui se passe lorsque $k$ est petite.

La raison pour laquelle nous essayons de compter la complexité exacte dans le cas de votre algorithme est que ses temps d'exécution dans le pire et le meilleur des cas sont à la fois $\Theta(n)$. Nous avons utilisé l'incompressibilité pour estimer$\alpha_k$, qui peut également être estimée directement à l'aide de méthodes probabilistes, mais le calcul de l'incompressibilité est probablement plus simple. Pourtant, l'incompressibilité n'élimine pas la nécessité d'analyser l'algorithme de manière probabiliste - elle rend simplement l'analyse plus maniable dans certains cas.

Comme autre commentaire (mais légèrement plus long qu'un commentaire réel) sur la réponse acceptée:

1. La complexité de Kolmogorov (ou complexité algorithmique ) traite des descriptions optimales des "chaînes" (au sens général des chaînes en tant que séquences de symboles )

2. Une chaîne est (suffisamment) incompressible ou (suffisamment) algorithmiquement aléatoire si sa description (algorithmique) (kolmogorov comlplexity K ) n'est pas inférieure à sa taille (littérale) . En d'autres termes, la description optimale de la chaîne est la chaîne elle-même .

3. Le principal résultat de la théorie est que la plupart des chaînes sont (algorithmiquement) aléatoires (ou typiques) (ce qui est également lié à d'autres domaines comme les théorèmes de Goedel, à travers le travail de Chaitin)

4. La complexité de Kolmogorov est liée à l' entropie probabiliste (ou Shannon) , en fait, l'entropie est une limite supérieure sur KC. Et cela relie l'analyse basée sur la complexité descriptive à l'analyse probabiliste. Ils peuvent être interchangeables.

5. Parfois, il pourrait être plus facile d'utiliser l'analyse probabiliste, d'autres la complexité descriptive (des vues du même disons)

Donc, à la lumière de ce qui précède, en supposant une entrée algorithmiquement aléatoire dans un algorithme, on suppose ce qui suit:

1. L'entrée est typique , donc l'analyse décrit un scénario de cas moyen (point 3 ci-dessus)
2. La taille d' entrée est liée d'une certaine manière à sa probabilité (point 2 ci-dessus)
3. On peut passer de la vue algorithmique à la vue probabiliste (point 4 ci-dessus)