Algoritmos do livro.

Paul Erdos falou sobre o "Livro", onde Deus guarda a prova mais elegante de cada teorema matemático. Isso até inspirou um livro (que eu acredito que está agora em sua 4ª edição): Provas do livro .

Se Deus tivesse um livro semelhante para algoritmos, quais algoritmos você acha que seriam candidatos?

Se possível, forneça também uma referência clicável e os principais insights que o fazem funcionar.

Apenas um algoritmo por resposta, por favor.

A localização de união é um problema bonito, cujo melhor algoritmo / estrutura de dados (Disjoint Set Forest ) é baseado em uma pilha de espaguete. Embora muito simples e intuitivo o suficiente para explicar a uma criança inteligente, demorou vários anos para garantir um estreito vínculo com o tempo de execução. Por fim, descobriu-se que seu comportamento estava relacionado à função inversa de Ackermann, uma função cuja descoberta marcou uma mudança de perspectiva sobre a computação (e foi de fato incluída em On the Infinite, de Hilbert ).

A Wikipedia fornece uma boa introdução para Disjoint Set Forests .

Correspondência de string de Knuth-Morris-Pratt . As oito linhas de código mais lisas que você já viu.

O algoritmo de Blum, Floyd, Pratt, Rivest, e Tarjan para encontrar o k -ésimo elemento de uma lista não ordenada no tempo linear é uma bela algoritmo, e só funciona porque os números são apenas para a direita para caber no Teorema Mestre. É o seguinte:

1. Classifique cada sequência de cinco elementos.
2. Escolha a mediana em cada uma.
3. Recorra para encontrar a mediana desta lista.
4. Gire na mediana das medianas (como no Quicksort)
5. Selecione o lado apropriado da lista e a posição nessa lista e volte a aparecer.

Binary Pesquisa é o algoritmo mais simples, bonito e útil que eu já correr em.

Estou surpreso por não ver o algoritmo de Floyd-Warshall para os caminhos mais curtos de todos os pares aqui:

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])

$O(n^3)$$O(n^2)$

Algoritmo euclidiano para calcular o maior divisor comum (MDC)

Pode parecer um tanto trivial (especialmente em comparação com as outras respostas), mas acho que o Quicksort é realmente elegante. Lembro que, quando o vi pela primeira vez, pensei que era realmente complicado, mas agora parece muito simples.

Codificação de Huffman para compactação de dados.

O teste de primalidade de Miller-Rabin (e testes similares) deve estar no livro. A idéia é tirar proveito das propriedades dos números primos (isto é, usando o pequeno teorema de Fermat) para procurar probabilisticamente uma testemunha de que o número não é primo. Se nenhuma testemunha for encontrada após testes aleatórios suficientes, o número será classificado como primo.

Nessa nota, o teste de primalidade da AKS que mostrou PRIMES está em P certamente deveria estar em The Book!

Teste de identidade polinomial com o lema de Schwartz-Zippel :

Se alguém o acordasse no meio da noite e lhe pedisse para testar duas expressões polinomiais univariadas para identificar a identidade, você provavelmente as reduziria à forma normal da soma dos produtos e compararia à identidade estrutural. Infelizmente, a redução pode levar um tempo exponencial; é análogo a reduzir expressões booleanas para a forma normal disjuntiva.

Supondo que você seja do tipo que gosta de algoritmos aleatórios, sua próxima tentativa provavelmente seria avaliar os polinômios em pontos escolhidos aleatoriamente em busca de contra-exemplos, declarando que os polinômios são muito provavelmente idênticos se forem aprovados em testes suficientes. O lema de Schwartz-Zippel mostra que, à medida que o número de pontos aumenta, a chance de um falso positivo diminui muito rapidamente.

Nenhum algoritmo determinístico para o problema é conhecido que é executado no tempo polinomial.

Primeira pesquisa de profundidade . É a base de muitos outros algoritmos. Também é enganosamente simples: por exemplo, se você substituir a fila em uma implementação de BFS por uma pilha, você recebe o DFS?

Algoritmo de Dijkstra : o problema de caminho mais curto de fonte única para um gráfico com custos de caminho de borda não negativos. É usado em todos os lugares e é um dos algoritmos mais bonitos do mercado. A Internet não poderia ser roteada sem ela - é uma parte essencial dos protocolos de roteamento IS-IS e OSPF (Open Shortest Path First).

1. Atribua a cada nó um valor de distância. Defina como zero para o nosso nó inicial e infinito para todos os outros nós.
2. Marque todos os nós como não visitados. Defina o nó inicial como atual.
3. Para o nó atual, considere todos os seus vizinhos não visitados e calcule sua distância provisória (a partir do nó inicial). Por exemplo, se o nó atual (A) tem distância de 6 e uma borda que o conecta a outro nó (B) é 2, a distância de B a A será 6 + 2 = 8. Se essa distância for menor que a distância registrada anteriormente (infinito no início, zero para o nó inicial), substitua a distância.
4. Quando terminarmos de considerar todos os vizinhos do nó atual, marque-o como visitado. Um nó visitado não será verificado novamente; sua distância registrada agora é final e mínima.
5. Se todos os nós foram visitados, termine. Caso contrário, defina o nó não visitado com a menor distância (do nó inicial) como o próximo "nó atual" e continue na etapa 3.

A peneira de Eratóstenes , simples e intuitiva.

Eu também gosto da beleza do algoritmo de Horner .

O esquema de criptografia totalmente homomórfica de Gentry (sobre treliças ideais ou sobre números inteiros) é incrivelmente bonito. Ele permite que terceiros executem cálculos arbitrários em dados criptografados sem acesso a uma chave privada.

O esquema de criptografia é devido a várias observações aguçadas.

• Para obter um esquema de criptografia totalmente homomórfico, é necessário apenas um esquema homomórfico sobre adição e multiplicação. Isso ocorre porque adição e multiplicação (mod 2) são suficientes para obter portas AND, OR e NOT (e, portanto, Turing Completeness).
• Que, se um esquema desse tipo fosse adotado , mas devido a algumas limitações só pudesse ser executado para circuitos de alguma profundidade finita, é possível avaliar homomorficamente o procedimento de descriptografia e reentrada para redefinir a limitação da profundidade do circuito sem sacrificar a privacidade das chaves.
• Que, ao "esmagar" a profundidade da versão em circuito da função de descriptografia para o esquema, é possível habilitar um esquema originalmente limitado a circuitos finitos e rasos, um número arbitrário de cálculos.

Em sua tese, Craig Gentry resolveu um problema aberto de longa data (e deslumbrante) em criptografia. O fato de existir um esquema totalmente homomórfico exige que reconheçamos que existe alguma estrutura inerente à computabilidade que, de outra forma, poderíamos ter ignorado.

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

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

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

O algoritmo Cooley-Tukey FFT .

Algoritmo de Strassen para multiplicação de matrizes.

O algoritmo de casamento estável de Gale-Shapley . Esse algoritmo é ganancioso e muito simples, não é óbvio a princípio por que funcionaria, mas a prova de correção é novamente fácil de entender.

O algoritmo de tempo linear para a construção de matrizes de sufixos é realmente bonito, embora não tenha realmente recebido o reconhecimento que merecia http://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf

Eliminação gaussiana. Ele completa a sequência de generalização do algoritmo Euclidean GCD para Knuth-Bendix.

Fiquei impressionado quando vi pela primeira vez o algoritmo para amostragem de reservatórios e sua prova. É o típico quebra-cabeça do tipo "quebra-cabeças" com uma solução extremamente simples. Eu acho que definitivamente pertence ao livro, tanto para algoritmos quanto para teoremas matemáticos.

Quanto ao livro, a história conta que, quando Erdös morreu e foi para o céu, ele pediu para se encontrar com Deus. O pedido foi atendido e, para a reunião, Erdös tinha apenas uma pergunta. "Posso procurar no livro?" Deus disse que sim e levou Erdös a ele. Naturalmente muito empolgado, Erdös abre o livro apenas para ver o seguinte.

Teorema 1: ...
Prova: Óbvio.

Teorema 2: ...
Prova: Óbvio.

Teorema 3: ...
Prova: Óbvio.

O algoritmo da tartaruga e da lebre . Gosto disso porque tenho certeza de que, mesmo que desperdicei minha vida inteira tentando encontrá-la, não há como surgir essa idéia.

Um exemplo tão fundamental e "trivial" quanto a prova de Euclides de infinitos primos:

Aproximação 2 para MAX-CUT - Independentemente de cada vértice, atribua-o a uma das duas partições com igual probabilidade.

Eu sempre fui parcial ao algoritmo de Christofides, que fornece uma aproximação (3/2) para o TSP métrico. Na verdade, me chame de fácil agradar, mas eu até gostei do algoritmo de 2 aproximações que veio antes dele . O truque de Christofides de fazer uma euleriana de árvore de abrangência de peso mínimo adicionando uma correspondência de seus vértices de grau ímpar (em vez de duplicar todas as arestas) é simples e elegante, e é preciso pouco para convencer a pessoa de que essa correspondência não tem mais da metade do peso de um passeio ideal.

Mesclar Classificação . Simples, elegante, eficiente.

$O(\sqrt N)$

Algoritmos para programação linear : métodos simplex, elipsóide e de ponto interior.

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

Algoritmo Robin Moser para resolver uma determinada classe de instâncias SAT. Tais instâncias são solucionáveis ​​pelo Lovasz Local Lemma. O algoritmo de Moser é de fato uma des randomização da declaração do lema.

Penso que há alguns anos seu algoritmo (e a técnica para sua prova de correção) será bem digerido e refinado a ponto de ser um candidato viável para um algoritmo do livro .

Esta versão é uma extensão de seu artigo original, escrito com Gábor Tardos.

O algoritmo mais rápido e mais curto de Marcus Hutter para todos os problemas bem definidos .

Isso meio que contraria o espírito das outras ofertas desta lista, uma vez que é apenas de interesse teórico e não prático, mas, novamente, o título diz tudo. Talvez deva ser incluído como um relato de advertência para aqueles que observariam apenas o comportamento assintótico de um algoritmo.

O algoritmo X de Knuth encontra todas as soluções para o problema exato de cobertura . O que há de mais mágico nisso é a técnica que ele propôs para implementá-lo com eficiência: Dancing Links .

Penso que devemos incluir os de Schieber-Vishkin , que respondem às consultas mais baixas de ancestrais comuns em tempo constante, pré-processando a floresta em tempo linear.

Gosto da exposição de Knuth no volume 4, fascículo 1, e de sua reflexão . Ele disse que levou dois dias inteiros para entender completamente, e eu lembro de suas palavras:

Eu acho isso muito bonito, mas surpreendentemente tem uma má imprensa na literatura (..) É baseado em matemática que me excita.