Algorithmes du livre.

Paul Erdos a parlé du "livre" où Dieu conserve la preuve la plus élégante de chaque théorème mathématique. Cela a même inspiré un livre (qui, à mon avis, en est à sa quatrième édition): Proofs from the Book .

Si Dieu avait un livre similaire pour les algorithmes, quel (s) algorithme (s) pensez-vous être candidat (s)?

Si possible, veuillez également fournir une référence cliquable et les informations clés qui le permettent.

Un seul algorithme par réponse, s'il vous plaît.

Union-find est un beau problème dont le meilleur algorithme / structure de données (Disjoint Set Forest ) est basé sur une pile de spaghettis. Bien que très simple et suffisamment intuitif pour expliquer à un enfant intelligent, il a fallu plusieurs années pour obtenir une limite d'exécution. En fin de compte, il a été découvert que son comportement était lié à la fonction inverse d’Ackermann, une fonction dont la découverte marquait un changement de perspective du calcul (et qui était en fait incluse dans On the Infinite de Hilbert ).

Wikipedia fournit une bonne introduction aux forêts disjointes .

Correspondance de chaîne Knuth-Morris-Pratt . Les huit lignes de code les plus lisses que vous puissiez voir.

L'algorithme de Blum, Floyd, Pratt, Rivest et Tarjan pour trouver le k ème élément d'une liste non triée en temps linéaire est un bel algorithme, qui ne fonctionne que parce que les nombres sont parfaitement adaptés au théorème principal. Cela va comme suit:

1. Triez chaque séquence de cinq éléments.
2. Choisissez la médiane dans chacun.
3. Revenez à trouver la médiane de cette liste.
4. Pivot sur la médiane des médianes (comme dans Quicksort)
5. Sélectionnez le bon côté de la liste et la position dans cette liste, et répétez.

La recherche binaire est l'algorithme le plus simple, le plus beau et le plus utile que j'ai jamais rencontré.

Je suis surpris de ne pas voir l' algorithme de Floyd-Warshall pour les chemins les plus courts pour toutes les paires ici:

d[]: 2D array. d[i,j] is the cost of edge ij, or inf if there is no such edge.

for k from 1 to n:
  for i from 1 to n:
    for j from 1 to n:
      d[i,j] = min(d[i,j], d[i,k] + d[k,j])

L'un des algorithmes non triviaux les plus courts et les plus clairs, et les performances de sont très rapides si vous considérez qu'il pourrait y avoir des arêtes O ( n 2 ) . Ce serait mon enfant d'affiche pour la programmation dynamique!$O(n^3)$$O(n^2)$

Algorithme euclidien pour calculer le plus grand commun diviseur (GCD)

Cela peut sembler un peu trivial (surtout en comparaison avec les autres réponses), mais je pense que Quicksort est vraiment élégant. Je me souviens que lorsque je l’ai vu pour la première fois, j’ai pensé que c’était vraiment compliqué, mais maintenant cela semble trop simple.

Huffman codant pour la compression de données.

Le test de primalité de Miller-Rabin (et des tests similaires) devrait figurer dans le livre. L'idée est de tirer parti des propriétés des nombres premiers (c'est-à-dire en utilisant le petit théorème de Fermat) pour rechercher de manière probabiliste un témoin du nombre non premier. Si aucun témoin n'est trouvé après suffisamment de tests aléatoires, le nombre est considéré comme premier.

Sur cette note, le test de primalité AKS qui a montré que PRIMES est en P devrait certainement figurer dans The Book!

Test d'identité polynomiale avec le lemme de Schwartz-Zippel :

Si quelqu'un vous réveillait au milieu de la nuit et vous demandait de tester l'identité de deux expressions polynomiales univariées, vous les réduiriez probablement à la forme normale de la somme des produits et compareriez l'identité structurelle. Malheureusement, la réduction peut prendre un temps exponentiel. c'est analogue à la réduction des expressions booléennes à une forme normale disjonctive.

En supposant que vous soyez du genre à aimer les algorithmes aléatoires, votre prochaine tentative consisterait probablement à évaluer les polynômes à des points choisis au hasard à la recherche de contre-exemples, en déclarant que les polynômes sont très probablement identiques s'ils passent suffisamment de tests. Le lemme de Schwartz-Zippel montre qu’à mesure que le nombre de points augmente, le risque de faux positif diminue très rapidement.

On ne connaît aucun algorithme déterministe pour le problème qui s'exécute en temps polynomial.

Recherche approfondie en profondeur . C'est la base de nombreux autres algorithmes. Il est également trompeusement simple: Par exemple, si vous remplacez la file d' attente dans une implémentation BFS par une pile, vous obtenez DFS?

Algorithme de Dijkstra : problème du chemin le plus court avec une source unique pour un graphe avec des coûts de chemin de bord non négatifs. Il est utilisé partout et est l'un des plus beaux algorithmes du marché. Internet ne pourrait pas être routé sans elle - c'est une partie essentielle des protocoles de routage IS-IS et OSPF (Open Shortest Path First).

1. Attribuez à chaque nœud une valeur de distance. Réglez-le à zéro pour notre nœud initial et à l'infini pour tous les autres nœuds.
2. Marquez tous les nœuds comme non visités. Définir le noeud initial comme courant.
3. Pour le nœud actuel, considérez tous ses voisins non visités et calculez leur distance provisoire (à partir du nœud initial). Par exemple, si le noeud actuel (A) a une distance de 6 et qu'un bord le reliant à un autre noeud (B) vaut 2, la distance entre B et A sera de 6 + 2 = 8. Si cette distance est inférieure à la distance précédemment enregistrée (infini au début, zéro pour le nœud initial), écrasez la distance.
4. Lorsque nous avons terminé d’envisager tous les voisins du nœud actuel, marquez-le comme visité. Un nœud visité ne sera plus vérifié; sa distance enregistrée maintenant est finale et minimale.
5. Si tous les nœuds ont été visités, terminez. Sinon, définissez le nœud non visité avec la plus petite distance (à partir du nœud initial) comme "prochain nœud" et continuez à partir de l'étape 3.

Le crible d'Eratosthenes , simple et intuitif.

J'aime aussi la beauté de l'algorithme de Horner .

Le schéma de cryptage entièrement homomorphique de Gentry (sur des réseaux idéaux ou sur des entiers) est terriblement beau. Il permet à un tiers d'effectuer des calculs arbitraires sur des données chiffrées sans accès à une clé privée.

Le schéma de chiffrement est dû à plusieurs observations attentives.

• Pour obtenir un schéma de chiffrement entièrement homomorphique, il suffit d'avoir un schéma homomorphique sur l'addition et la multiplication. En effet, l'addition et la multiplication (mod 2) suffisent pour obtenir les portes AND, OR et NOT (et donc la complétude de Turing).
• Que si un tel système devait être eu, mais en raison de certaines limitations ne pouvaient être exécutées pour les circuits d' une certaine profondeur finie, alors on peut homomorphically évaluer la procédure de décryptage et reencyption pour réinitialiser la limitation de la profondeur de circuit sans sacrifier la vie privée clé.
• En "écrasant" la profondeur de la version de circuit de la fonction de déchiffrement pour le schéma, on pourrait activer un schéma initialement limité aux circuits finis peu profonds à un nombre arbitraire de calculs.

Dans sa thèse, Craig Gentry a résolu un problème de longue date (et magnifique) en matière de cryptographie. Le fait qu'il existe un schéma totalement homomorphique exige que nous reconnaissions qu'il existe une structure inhérente à la calculabilité que nous aurions pu autrement ignorer.

http://crypto.stanford.edu/craig/craig-thesis.pdf

http://eprint.iacr.org/2009/616.pdf

http://portal.acm.org/citation.cfm?id=1666420.1666445

L' algorithme FFT de Cooley-Tukey .

Algorithme de Strassen pour la multiplication matricielle.

L' algorithme de mariage stable de Gale-Shapley . Cet algorithme est gourmand et très simple, il n’explique pas au premier abord pourquoi cela fonctionnerait, mais la preuve de l’exactitude est à nouveau facile à comprendre.

L'algorithme temporel linéaire pour la construction de tableaux de suffixes est vraiment magnifique, bien qu'il n'ait pas reçu la reconnaissance qu'il méritait http://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf

Élimination gaussienne. Il complète la séquence de généralisation de l'algorithme Euclidean GCD à Knuth-Bendix.

J'ai été impressionné quand j'ai vu pour la première fois l'algorithme d' échantillonnage de réservoir et sa preuve. C’est le casse-tête typique du type "casse-tête" avec une solution extrêmement simple. Je pense que cela appartient définitivement au livre, celui des algorithmes ainsi que celui des théorèmes mathématiques.

En ce qui concerne le livre, on raconte que quand Erdös est mort et est allé au paradis, il a demandé à rencontrer Dieu. La demande fut acceptée et Erdös n'avait qu'une question pour la réunion. "Puis-je regarder dans le livre?" Dieu a dit oui et a conduit Erdös à cela. Naturellement très excité, Erdös ouvre le livre uniquement pour voir ce qui suit.

Théorème 1: ...
Preuve: Évident.

Théorème 2: ...
Preuve: Évident.

Théorème 3: ...
Preuve: Évident.

L' algorithme Tortue et lièvre . J'aime ça parce que je suis sûr que même si je perdais toute ma vie à essayer de la trouver, il était impossible que je trouve une telle idée.

Un exemple aussi fondamental et "trivial" que la preuve par Euclide d'une infinité de nombres premiers:

2 approximations pour MAX-CUT - Indépendamment pour chaque sommet, affectez-le à l'une des deux partitions avec une probabilité égale.

J'ai toujours été partisan de l'algorithme de Christofides qui donne une approximation (3/2) du TSP métrique. En fait, appelez-moi facile à satisfaire, mais j’ai même aimé l’algorithme à 2 approximations qui l’a précédé . L'astuce de Christofides consistant à créer un arbre de poids minimal Eulerian en ajoutant une correspondance à ses sommets de degré impair (au lieu de dupliquer toutes les arêtes) est simple et élégante, et il suffit de peu pour convaincre une personne que cette correspondance n'a pas plus de la moitié du poids. d'un tour optimum.

Fusionner le tri . Simple, élégant, efficace.

$O(\sqrt N)$ . Il est prouvé de manière optimale et surpasse de manière prouvée tout algorithme classique. Pour un bonus, il est très facile à comprendre et intuitif.

Algorithmes de programmation linéaire : méthodes simplex, ellipsoïde et ponctuelle.

http://en.wikipedia.org/wiki/Linear_programming#Algorithms

Algorithme Robin Moser pour résoudre une certaine classe d'instances SAT. Ces cas peuvent être résolus par Lovasz Local Lemma. L'algorithme de Moser est en effet une désaléotisation de l'énoncé du lemme.

Je pense que cela fait quelques années que son algorithme (et la technique pour la preuve de son exactitude) sera bien digéré et peaufiné au point d’être un candidat viable pour un algorithme tiré du livre .

Cette version est une extension de son papier original, écrit avec Gábor Tardos.

Marcus Hutter L'algorithme le plus rapide et le plus rapide de pour tous les problèmes bien définis .

Cela va à l’encontre de l’esprit des autres offres de cette liste, puisqu’il n’ya qu’un intérêt théorique et non pratique, mais le titre en dit tout. Peut-être faudrait-il l'inclure dans un récit édifiant pour ceux qui ne s'intéresseraient qu'au comportement asymptotique d'un algorithme.

L'algorithme X de Knuth trouve toutes les solutions au problème exact de la couverture . Ce qui est vraiment magique, c’est la technique qu’il a proposée pour l’appliquer efficacement: Dancing Links .

Je pense que nous devons inclure Schieber-Vishkin , qui répond requêtes des ancêtres communs les plus basses en temps constant, en prétraitant la forêt en temps linéaire.

J'aime l’exposition de Knuth dans le volume 4, fascicule 1, et sa rêverie . Il a dit que cela lui avait pris deux jours entiers pour bien le comprendre, et je me souviens de ses mots:

Je pense que c'est assez beau, mais étonnamment, il a une mauvaise presse dans la littérature (..) C'est basé sur les mathématiques qui m'excite.