Meta Narratives: Essays on Philosophy and Symbolism

Um guia ilustrado para programadores e outros curiosos. Um algoritmo nada mais é do que um procedimento passo a passo para a resolução de um problema. Os algoritmos que você mais utilizará como um programador já foram descobertos, testados e provados. Se você quer entendê-los, mas se recusa a estudar páginas e mais páginas de provas, este é o livro certo. Este guia cativante e completamente ilustrado torna simples aprender como utilizar os principais algoritmos nos seus programas. O livro Entendendo Algoritmos apresenta uma abordagem agradável para esse tópico essencial da ciência da computação. Nele, você aprenderá como aplicar algoritmos comuns nos problemas de programação enfrentados diariamente. Você começará com tarefas básicas como a ordenação e a pesquisa. Com a prática, você enfrentará problemas mais complexos, como a compressão de dados e a inteligência artificial. Cada exemplo é apresentado em detalhes e inclui diagramas e códigos completos em Python. Ao final deste livro, você terá dominado algoritmos amplamente aplicáveis e saberá quando e onde utilizá-los. O que este livro inclui A abordagem de algoritmos de pesquisa, ordenação e algoritmos gráficos Mais de 400 imagens com descrições detalhadas Comparações de desempenho entre algoritmos Exemplos de código em Python Este livro de fácil leitura e repleto de imagens é destinado a programadores autodidatas, engenheiros ou pessoas que gostariam de recordar o assunto. Prefácio Agradecimentos Sobre este livro 1 Introdução a algoritmos Introdução 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 Deleções Ordenação por seleção 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 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 mínimo Filas Implementando o grafo Implementando o algoritmo Tempo de execução Recapitulando 7 Algoritmo de Dijkstra Trabalhando com o algoritmo de Dijkstra Terminologia Adquirindo um piano Arestas com pesos negativos Implementação Recapitulando 8 Algoritmos gulosos O problema do cronograma da sala de aula O problema da mochila O problema da cobertura de conjuntos Algoritmos de aproximação Problemas NP-completos Caixeiro-viajante, passo a passo Como faço para saber se um problema é NP-completo? Recapitulando 9 Programação dinâmica O problema da mochila 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ê modificar a ordem das linhas? É possível preencher a tabela a partir das colunas, em vez de a partir 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 10 K-vizinhos mais próximos Classificando laranja 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 11 Próximos passos Árvores Índices invertidos A transformada de Fourier Algoritmos paralelos MapReduce Por que os algoritmos distribuídos são úteis? Função map Função reduce Filtro de Bloom e HyperLogLog Filtros de Bloom HyperLogLog Algoritmos SHA Comparando arquivos Verificando senhas Hash sensitivo local Troca de chaves de Diffie-Hellman Programação linear Epílogo Respostas dos exercícios