Pular para o conteúdo
</> Entendendo Algoritmos

Próximos passos

O último capítulo do livro apresenta, de forma rápida, assuntos para estudar depois de dominar o básico. Aqui vai um resumo de cada um, sem demonstração interativa: são pontos de partida, não explicações completas.

Explicação do algoritmo: escolha um nível para ler.

Á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