Entendendo Algoritmos – 2ª Edição
Um guia ilustrado para programadores e outros curiosos
Descrição do livro
Os algoritmos mais utilizados já foram descobertos, testados e comprovados. O livro Entendendo Algoritmos, Segunda Edição torna o aprendizado deles algo extremamente simples. Com explicações didáticas, mais de 400 ilustrações divertidas e exemplos relevantes, esta é a maneira perfeita de dominar o poder dos algoritmos — sem exigir conhecimentos avançados de matemática!
Entendendo Algoritmos, Segunda Edição ensina os algoritmos mais importantes para acelerar seus programas, simplificar seu código e resolver problemas comuns de programação. Comece com tarefas como ordenação e busca e, em seguida, desenvolva suas habilidades para enfrentar problemas avançados, como compressão de dados e IA. Você aprenderá a analisar os trade-offs de desempenho entre diferentes algoritmos. Esta nova edição aborda árvores, problemas NP-completos e códigos atualizados para Python 3.
O que este livro inclui:
• Algoritmos de busca, ordenação e em grafos
• Estruturas de dados como arrays, listas, tabelas hash, árvores e grafos
• Problemas NP-completos e algoritmos gananciosos
• Exercícios e exemplos de código
Não são necessários conhecimentos avançados de matemática nem de programação.
Aditya Bhargava é engenheiro de software com formação em Ciência da Computação e em Belas Artes. Ele escreve sobre programação no blog adit.io.
O editor técnico deste livro foi David Eisenstat.
“Resume um semestre inteiro de Algoritmos e Estruturas de Dados em explicações e diagramas fáceis de digerir, sem exigir conhecimento profundo dos conceitos matemáticos subjacentes.” – Katie Sylor-Miller, Etsy
“Uma combinação rara de instrução eficaz com leitura prazerosa. Não existe recurso melhor do que este livro.” – Ben Vinegar, Syntax.fm
“Uma jornada lúcida e lindamente ilustrada pelo mundo dos algoritmos e estruturas de dados.” – Stephen Diehl, Zerolink
“O livro número um que recomendo a todos os novos engenheiros e também aos seniores que desejam aprimorar suas habilidades. Ele se destaca por permitir que você realmente entenda os algoritmos, em vez de apenas memorizar o código.” – Alexander Manning, BlockVer menos ▲
Sumário
- Apresentação
- Prefácio
- Agradecimentos
- Sobre este livro
- Sobre o autor
- 1 Introdução a algoritmos
- O que você aprenderá sobre desempenho
- O que você aprenderá sobre a solução de problemas
- Pesquisa binária
- Uma maneira melhor de buscar
- Tempo de execução
- Notação big O
- Tempo de execução dos algoritmos cresce a taxas diferentes
- Vendo diferentes tempos de execução big O
- A notação big O estabelece o tempo de execução para a pior hipótese
- Alguns exemplos comuns de tempo de execução big O
- O caixeiro-viajante
- Recapitulando
- 2 Ordenação por seleção
- Como funciona a memória
- Arrays e listas encadeadas
- Listas encadeadas
- Arrays
- Terminologia
- Inserindo algo no meio da lista
- Exclusões
- Qual é mais usado: arrays ou listas encadeadas?
- Ordenação por seleção
- Exemplo de código
- Recapitulando
- 3 Recursão
- Recursão
- Caso-base e caso recursivo
- A pilha
- A pilha de chamada
- A pilha de chamada com recursão
- Recapitulando
- 4 Quicksort
- Dividir para conquistar
- Quicksort
- Notação big O revisada
- Merge sort versus quicksort
- Caso médio versus pior caso
- Recapitulando
- 5 Tabelas hash
- Tabelas hash
- Funções hash
- Utilização
- Usando tabelas hash para pesquisas
- Evitando entradas duplicadas
- Utilizando tabelas hash como cache
- Recapitulando
- Colisões
- Desempenho
- Fator de carga
- Uma boa função hash
- Recapitulando
- 6 Pesquisa em largura
- Introdução a grafos
- O que é um grafo?
- Pesquisa em largura
- Encontrando o caminho mais curto
- Filas
- Implementando o grafo
- Implementando o algoritmo
- Tempo de execução
- Recapitulando
- 7 Árvores
- Sua primeira árvore
- Diretórios de arquivos
- Uma odisseia no espaço: Pesquisa em profundidade
- Uma definição mais precisa de árvores
- Árvores binárias
- Codificação de Huffman
- Recapitulando
- 8 Árvores balanceadas
- Um ato de equilíbrio
- Melhorando a velocidade de inserção com árvores
- Árvores menores são mais rápidas
- Árvores AVL: um tipo de árvore balanceada
- Rotações
- Como a árvore AVL sabe quando é hora de rotacionar?
- Árvores splay
- Árvores B
- Qual a vantagem de utilizar árvores B?
- Recapitulando
- 9 Algoritmo de Dijkstra
- Trabalhando com o algoritmo de Dijkstra
- Terminologia
- Adquirindo um piano
- Arestas com pesos negativos
- Implementação
- Recapitulando
- 10 Algoritmos gulosos
- O problema do cronograma da sala de aula
- O problema da mochila
- O problema da cobertura de conjuntos
- Algoritmos de aproximação
- Código para o exemplo
- Calculando a resposta
- Conjuntos
- De volta ao código
- Recapitulando
- 11 Programação dinâmica
- O problema da mochila (revisitado)
- A solução simples
- Programação dinâmica
- Perguntas frequentes sobre o problema da mochila
- O que acontece se você adicionar um item?
- O que acontece se você alterar a ordem das linhas?
- É possível preencher a tabela a partir das colunas, em vez das linhas?
- O que acontece se você adicionar um item menor?
- Você consegue roubar frações de um item?
- Otimizando o seu itinerário de viagem
- Lidando com itens com interdependência
- É possível que a solução requeira mais de dois subproblemas?
- É possível que a melhor solução não utilize a capacidade total da mochila?
- Maior substring comum
- Criando a tabela
- Preenchendo a tabela
- A solução
- Maior subsequência comum
- Maior subsequência comum – solução
- Recapitulando
- 12 K-vizinhos mais próximos
- Classificando laranjas versus toranjas
- Criando um sistema de recomendações
- Extração de características
- Regressão
- Escolhendo boas características
- Introdução ao aprendizado de máquina
- OCR
- Criando um filtro de spam
- Prevendo a bolsa de valores
- Recapitulando
- 13 Próximos passos
- Regressão linear
- Índices invertidos
- A transformada de Fourier
- Algoritmos paralelos
- map/reduce
- Filtro de Bloom e HyperLogLog
- Filtros de Bloom
- HyperLogLog
- HTTPS e troca de chaves de Diffie-Hellman
- Hashing sensível à localidade
- Heaps mínimos e fila de prioridade
- Programação linear
- Epílogo
- A Desempenho das árvores AVL
- B Problemas NP-difícil
- Problemas de decisão
- O problema da satisfatibilidade
- Difícil de resolver, fácil de verificar
- Reduções
- NP-difícil
- NP-completo
- Recapitulando
- C Respostas dos exercícios
- Índice remissivo
Sobre o autor
Aditya Bhargava é um engenheiro de software com experiência tanto em Ciência da Computação quanto em Artes Plásticas. Ele tem um blog sobre programação em adit.io.… Ver perfil completo ▶
Livros relacionados
