Algoritmos do livro.

358

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.

Aryabhata
fonte
11
Ótima pergunta! [Editar:} Uma pergunta. Onde traçamos a linha entre algoritmos e estruturas de dados? E se o insight principal de um algoritmo estiver intimamente relacionado a uma estrutura de dados (por exemplo, UNION FIND na função inversa de Ackermann)?
Ross Snider
4
uma grande fonte e talvez um candidato para tal livro é "Encyclopedia of Algorithms" springer.com/computer/theoretical+computer+science/book/...
Marcos Villagra
21
Estou um pouco surpreso que algoritmos que considero bastante complicados (KMP, matrizes de sufixo linear) sejam considerados por outros como "do livro". Para mim, "do livro" significa simples e óbvio, mas apenas em retrospectiva. Estou curioso para saber como os outros interpretam "elegante".
Radu GRIGore 19/08/10
49
@supercooldave Você não precisa acreditar em Deus, mas deve acreditar no livro dele. ;-)
Ross Snider
10
Durante uma palestra em 1985, Erdős disse: "Você não precisa acreditar em Deus, mas deve acreditar no livro".
Robert Massaioli

Respostas:

116

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 .

Jukka Suomela
fonte
109

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

Jukka Suomela
fonte
4
É meio incompreensível perceber que isso era algo que não era óbvio em algum momento e só é óbvio agora porque eles criaram e aprendemos ... Acho que devemos aplicar a teoria da história de Carr à Matemática e à Ciência da Computação .
Ritwik Bose
1
Pela descrição, eu diria que isso está relacionado à pesquisa rápida de substring de Boyer-Moore.
Bart
2
@Mechko O fato de esse algoritmo ter sido descoberto simultaneamente e de forma independente por pessoas separadas é uma indicação de que é óbvio até certo ponto. Se algo é "óbvio" é uma função das restrições do projeto e do ambiente de programação mais amplo. Se você precisa de (1) pesquisa rápida de texto e (2) conhece a importância de algoritmos verdadeiramente O (n), e (3) encontrou texto com correspondências parciais antes e (4) tem tempo para fazer as coisas "corretamente", esse algoritmo provavelmente é óbvio.
precisa
Em uma entrevista, Knuth disse que a idéia do algoritmo veio do estudo do autômato finito bidirecional de Stephen Cook para palíndromos.
Kaveh
@Kaveh Leia a Seção 7 (Observações Históricas) do artigo original do KMP. Tem ótimas observações. Sobre Morris escrevendo um editor de texto que "era muito complicado para outros implementadores do sistema entenderem". Sobre Knuth "a primeira vez na experiência de Knuth que a teoria dos autômatos o havia ensinado a resolver um problema de programação real melhor do que ele poderia resolver antes". E "Knuth ficou decepcionado ao saber que Morris já havia descoberto o algoritmo, sem conhecer o teorema de Cook;". DIVERSÃO.
Hendrik Jan
93

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.
Derrick Stolee
fonte
3
Este é um dos meus algoritmos favoritos. Eu gosto de uma intuição para ele que eu aprendi do livro de discrepância de Chazelle: o conjunto de medianas de grupos de elementos é como um ε -net para intervalos na lista ordenada dos números de entrada. Assim, o algoritmo segue um paradigma geral: computar uma ε -net rápido, resolver o problema na rede, recurse em alguma parte da entrada para refinar a solução, até que você tenha a solução exata. é técnica muito útil1/ϵϵϵ
Sasho Nikolov
5
Aliás, depois de parametrizar o tamanho dos grupos, as constantes não são tão mágicas. eles são naturalmente otimizado para dar a coisa certa no teorema mestre
Sasho Nikolov
Implementação do Ruby, gist.github.com/chadbrewbaker/7202412 Existe uma versão do algoritmo que usa espaço (constante, log), ou você precisa usar espaço de rascunho linear para manter as medianas?
Chad Brewbaker
2
5n13/40n5
88

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

michalmocny
fonte
Eu substituiria elegante por intuitivo. Não há nada de elegante nisso; sua simplicidade é sua verdadeira beleza.
Robert Massaioli
@ Robert Massaili: Substituí elegante por bonito. Você estava certo sobre isso.
michalmocny
2
E insanamente difícil escrever correctly- ver " Você é um dos 10% dos programadores que pode escrever uma pesquisa binária? "
Jon
No meu primeiro curso de algoritmos de pós-graduação, tivemos 15 minutos de testes, onde tivemos que resolver 2-3 problemas manualmente. O primeiro questionário desse tipo incluiu uma árvore de pesquisa binária e duas perguntas sobre pilhas. Fiquei envergonhado e consternado ao saber que havia errado no problema de pesquisa binária, antes de me dizerem que em uma classe de cerca de 30 pessoas havia duas respostas corretas. Mas mesmo sabendo disso, o fato de que a comunidade profissional levou 15 anos para acertar é impressionante.
Stella Biderman
84

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(n3)O(n2)

user651
fonte
2
Este algoritmo também pode ser generalizado de uma maneira realmente interessante. Veja, por exemplo, r6.ca/blog/20110808T035622Z.html e cl.cam.ac.uk/~sd601/papers/semirings.pdf
Mikhail Glushenkov
73

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.

Jukka Suomela
fonte
10
O Quicksort também levanta questões interessantes sobre o que exatamente é a essência de um algoritmo. Por exemplo, a elegante implementação padrão de Haskell se parece exatamente com a definição padrão de pseudo-código, mas possui uma complexidade assintótica diferente. Então, o Quicksort é apenas sobre dividir e conquistar ou o engenheiro inteligente in-situ é uma parte essencial do Quicksort? O Quicksort pode mesmo ser implementado em um ambiente puramente funcional ou requer mutabilidade?
Jörg W Mittag
2
A idéia da "essência" ou da "moral" de um algoritmo vem, é claro, do belo artigo A Peneira Genuína de Eratóstenes, de Melissa E. O'Neill ( cs.hmc.edu/~oneill/papers/Sieve-JFP. pdf ) e a discussão do quicksort vem da discussão do LtU sobre esse documento ( lambda-the-ultimate.org/node/3127 ), começando especificamente neste comentário: lambda-the-ultimate.org/node/3127/#comment-45549
Jörg W Mittag
8
@ Jörg: implementar o quicksort em listas vinculadas é totalmente sensato e tem o mesmo tempo de execução assintótico que sua implementação no local em matrizes (diabos, até mesmo a ingênua implementação fora do local em matrizes tem o mesmo tempo de execução) - ambas média e no pior dos casos. Quanto ao uso do espaço, isso é realmente diferente, mas deve-se dizer que mesmo a versão "no local" requer espaço extra constante (pilha de chamadas!), Um fato facilmente esquecido.
Konrad Rudolph
Também vale a pena mencionar o Quicksort Dual-Pivot de Vladimir Yaroslavskiy. Isso deve ser pelo menos 20% mais rápido quicksort original permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/…
SaveTheRbtz
O Quicksort na teoria é simples (pode ser descrito em 4 etapas) e pode ser altamente otimizado, mas na prática é muito difícil codificar corretamente. É por isso que não recebe meu voto.
Dennis
50

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!

Jukka Suomela
fonte
49

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.

Per Vognsen
fonte
Isso deveria ter sido sugerido há muito tempo! Obrigado!
Ar23
1
Existem vários outros algoritmos aleatórios que merecem um lugar de destaque no livro. Para estes, o contraste entre as alternativas determinística e probabilística é menos impressionante: um algoritmo determinístico geralmente existe, mas é muito mais complicado.
Por Vognsen
Inventei independentemente o mesmo algoritmo enquanto trabalhava em um artigo há alguns anos, até que alguém me perguntou, não é o lema de Schwartz-Zippel? E eu disse, o que é isso? :)
Hélio
46

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?

Radu GRIGore
fonte
1
É também a base da execução do Prolog!
muad 19/08/10
1
Qual o sentido do BFS com uma pilha que está faltando? Eu teria pensado que a resposta é "sim, você recebe o DFS".
Omar Antolín-Camarena
1
Bem, todo mundo parece pensar que esse problema é trivial. Além disso, todo mundo parece pensar que a resposta é "sim", o que está errado. A resposta é realmente "depende de qual implementação do BFS você inicia". Veja cs.stackexchange.com/questions/329/... (Esta é uma pergunta que eu postei para ajudar com a fase beta do CS.SE)
Radu Grigore
É também brevemente discutidos aqui: ics.uci.edu//~eppstein/161/960215.html
Radu Grigore
42

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.
David Sifry
fonte
40

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

Ross Snider
fonte
38

Algoritmo de Strassen para multiplicação de matrizes.

Kaveh
fonte
Provavelmente esperaria até sabermos se é o ideal.
21411 Thomas Ahle
Não é ideal, pelo menos, assintoticamente ... Acho que incluir o algoritmo de Strassen obriga a incluir o algoritmo de Karatsuba primeiro.
Timothy Dom
35

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.

Konrad Swanepoel
fonte
+1 porque há também um capítulo nas provas publicadas do livro sobre casamentos ...
ixtmixilix
34

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

zotachidil
fonte
Eu não acho que ele tem recebido o reconhecimento que merece - o que o faz pensar o contrário? Por exemplo, ele é implementado na biblioteca de análise de sequência C ++, SeqAn.
Konrad Rudolph
Vale ressaltar que agora existem vários outros algoritmos de construção de matriz de sufixos de tempo lineares e não lineares que, embora nem de longe tão bonitos, podem ser muito mais rápidos na prática. "Uma abordagem eficiente e versátil para a classificação de sufixos", Journal of Experimental Algorithmics (JEA), volume 12, junho de 2008, apresenta alguns resultados experimentais nesse sentido.
Raphael
@ Rafael: Estou um pouco desconfiado do fato de que na p. 3 desse artigo da JEA, eles fornecem apenas o que "acreditam" como um limite "solto" de O (n ^ 2 log n) ... Você conhece algum artigo com algoritmos de tempo linear comprovadamente mais rápidos na prática do que o Algoritmo de inclinação?
user651
32

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

Mitch
fonte
BTW, qual é a sequência de generalização e onde o algoritmo de Buchberger para a base de Grobner se encaixa nele? (Parece análogo ao Knuth-Bendix, mas eu vi uma menção em algum lugar que tipo de generaliza eliminação de Gauss ...)
ShreevatsaR
6
a sequência é: GCD Euclidiano -> Eliminação Gaussiana -> Buchberger -> Knuth-Bendix. Também se pode colocar (em vez de Eliminação Gaussiana) a divisão polinomial univariada e o módulo (na ordem de generalização que é "à parte" da Eliminação Gaussiana, a GE é o grau multivariado 1, o anel polinomial é o grau ilimitado univariado, o de Buchberger é o grau ilimitado multivariado. generalização salto é maior do EGCD a GE ou anel polinomial por causa da adição de variáveis, e depois também grande de Buchberger para KB por causa da assinatura ilimitada.
Mitch
+1: o algoritmo euclidiano resolve a equação mais famosa ax-by = 1 em matemática. Por que ele não aparece no CS com mais frequência é um mistério.
Tegiri Nenashi
32

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.

Arnar
fonte
4
Teorema 4:… Prova: exercício para o leitor.
21613 jon
31

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.

Tobias Neukom
fonte
6
Você conhece o algoritmo burro que resolve o problema com os mesmos assintóticos e segue um padrão de design algorítmico? Estou falando de aprofundamento iterativo. Na enésima iteração, você inicia no 2º enésimo sucessor da raiz e olha 2 ^ n sucessores para a frente em busca de uma recorrência. Mesmo que você esteja refazendo algumas de suas etapas a cada iteração, a taxa de crescimento geométrico do raio da pesquisa significa que ela não afeta os assintóticos.
Por Vognsen
30

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.

arnab
fonte
6
Sim, um algoritmo muito bom. Menos trivialmente, ao custo de outro fator 2, esse algoritmo também funciona para maximizar qualquer função submodular, não apenas a função de corte de gráfico. Isso é resultado de Feige, Mirrokni e Vondrak do FOCS 07
Aaron Roth
30

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.

James King
fonte
De fato, também existem muitos outros algoritmos de aproximação simples e elegantes com garantias de aproximação decentes.
Janne H. Korhonen
27

O(N)

Joe Fitzsimons
fonte
25

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

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

Kaveh
fonte
E, de fato, vários prêmios Nobel foram dados por promover nossa compreensão desses problemas.
Ross Snider
@Ross Kantorovich ganhou o prêmio Nobel de Economia por inventar o LP e aplicá-lo à alocação de recursos. Em que outros prêmios você estava pensando?
Mark Reitblatt
Mark Koopermans recebeu o prêmio nobel com Kantorovich, mas ainda era impreciso da minha parte dizer "vários".
Página
22

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.

MassimoLauria
fonte
21

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.

Kurt
fonte
21

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 .

Diego de Estrada
fonte
20

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.

Diego de Estrada
fonte
10
Espere, pode ser bonito, mas se Knuth levou dois dias inteiros para entendê-lo completamente, é realmente "do livro"?
ShreevatsaR
@ShreevatsaR O livro tem letras miúdas nas notas de rodapé :)
hsmyers