Árvores
Uma árvore de busca binária guarda os itens de forma que cada comparação descarta metade dos que sobram, como a busca binária, mas sem o custo de inserir no meio de um array. Bancos de dados costumam usar variações, como as árvores B.
Relacionado: Busca binária e Arrays e listas
Índices invertidos
Uma tabela hash que liga cada palavra às páginas em que ela aparece. É a ideia básica por trás de um mecanismo de busca: em vez de ler todas as páginas, consulta-se a palavra.
Relacionado: Tabelas hash
Transformada de Fourier
Separa um sinal, como uma música, nas frequências que o compõem. Serve para compressão de áudio, reconhecimento de música e análise de sinais.
Relacionado: Sem equivalente neste app
Algoritmos paralelos
Dividir o trabalho entre vários processadores. Quase sempre é mais difícil do que parece: o ganho raramente é proporcional ao número de núcleos, e dividir e juntar o trabalho também tem custo.
Relacionado: Quicksort
MapReduce
Um modelo para distribuir cálculos em muitas máquinas. A função map transforma cada item de forma independente e a função reduce junta os resultados, por exemplo para contar palavras em milhões de documentos.
Relacionado: Dividir para conquistar
Filtros de Bloom e HyperLogLog
Estruturas probabilísticas que trocam um pouco de precisão por muito menos memória. Um filtro de Bloom pode dar falsos positivos (diz que viu algo que não viu), mas nunca falsos negativos. O HyperLogLog estima quantos itens distintos existem.
Relacionado: Tabelas hash
Funções SHA e hash sensível à localidade
O SHA é uma família de funções hash seguras: dá para comparar arquivos ou verificar senhas sem guardar o conteúdo original. Já o hash sensível à localidade faz o contrário: entradas parecidas geram hashes parecidos, útil para detectar documentos semelhantes.
Relacionado: Tabelas hash
Troca de chaves Diffie-Hellman
Permite que duas pessoas combinem uma chave secreta por um canal que outros podem espiar. Faz parte da base da criptografia de chave pública, usada nas conexões seguras da internet.
Relacionado: Sem equivalente neste app
Programação linear
Maximiza (ou minimiza) um objetivo sujeito a restrições, como obter o maior lucro com recursos limitados. O algoritmo Simplex resolve esse tipo de problema, e os algoritmos de grafos do livro são casos particulares dele.
Relacionado: Algoritmo de Dijkstra