book

Aprender algoritmos

by George Heineman

April 2025

Intermediate to advanced

280 pages

7h 29m

Portuguese (Portugal, Brazil)

O'Reilly Media, Inc.

Book available

Read now

Unlock full access

A quem se destina este livroSobre o CódigoConvenções utilizadas neste livroAprendizagem em linha da O'ReillyComo contactar-nosAgradecimentos
O que é um algoritmo?Encontrando o maior valor em uma lista arbitráriaContagem de operações-chaveOs modelos podem prever o desempenho do algoritmoEncontra os dois maiores valores de uma lista arbitráriaAlgoritmo de torneioComplexidade temporal e complexidade espacialResumoExercícios de desafio
Utilização de modelos empíricos para prever o desempenhoA multiplicação pode ser mais rápidaAulas de desempenhoAnálise assimptóticaContagem de todas as operaçõesContagem de todos os bytesQuando uma porta se fecha, outra se abrePesquisa de matriz bináriaQuase tão fácil como πDois pássaros com uma pedraJunta tudoAjuste de curvas versus limites inferiores e superioresResumoExercícios de desafio
Como associar valores a chavesFunções de hash e códigos de hashUma estrutura de tabela de hash para pares (chave, valor)Deteção e resolução de colisões com sondagem linearEncadeamento separado com listas ligadasRemover uma entrada de uma lista ligadaAvaliaçãoCrescimento de HashtablesAnalisando o desempenho de tabelas de hash dinâmicasHashing perfeitoIterar sobre pares (chave, valor)ResumoExercícios de desafio
Max Binary HeapsInserir um (valor, prioridade)Remover o valor com a prioridade mais elevadaRepresentando um heap binário em uma matrizImplementação do Swim and SinkResumoExercícios de desafio
Ordenar por trocaSeleção OrdenarAnatomia de um algoritmo de ordenação quadráticaAnalisar o desempenho da ordenação por inserção e da ordenação por seleçãoRecursão e Dividir e ConquistarMesclar ordenaçãoSeleção rápidaClassifica em heapComparação do desempenho dos algoritmos O(N log N)Tim SortResumoExercícios de desafio
Começar a trabalharÁrvores de pesquisa bináriaPesquisa de valores em uma árvore de pesquisa bináriaRemoção de valores de uma árvore de pesquisa bináriaPercorrendo uma árvore bináriaAnalisar o desempenho de árvores de pesquisa bináriasÁrvores binárias auto-equilibradasAnálise do desempenho de árvores auto-equilibradasUtiliza a árvore binária como tabela de símbolos (chave, valor)Utilização da árvore binária como uma fila de espera prioritáriaResumoExercícios de desafio
Os gráficos armazenam informações úteis de forma eficienteUsar a pesquisa de profundidade para resolver um labirintoA pesquisa de amplitude em primeiro lugar oferece uma estratégia de pesquisa diferenteGrafos direcionadosGrafos com pesos de arestasAlgoritmo de DijkstraCaminho mais curto para todos os paresAlgoritmo de Floyd-WarshallResumoExercícios de desafio
Tipos de dados incorporados em PythonImplementando a pilha em PythonImplementando Filas de Espera em PythonImplementações de heap e fila de espera prioritáriaExploração futura

Content preview from Aprender algoritmos

Capítulo 7. Gráficos: Conecta apenas!

Este trabalho foi traduzido com recurso a IA. Agradecemos o teu feedback e comentários: translation-feedback@oreilly.com

Neste capítulo, aprenderás:

O tipo de dados abstrato da pilha.
O tipo de dados de fila de prioridade mínima indexada, que é o último tipo de dados incluído neste livro.
Como modelar um grafo utilizando nós e arestas. Num grafo dirigido, as arestas têm uma orientação. Num grafo ponderado, as arestas têm um valor numérico associado.
Como a Pesquisa em Profundidade utiliza uma pilha para organizar a pesquisa num gráfico.
Como o Breadth First Search usa uma fila para pesquisar em um grafo. Se existir um caminho entre um nó de origem e um nó de destino, o Breadth First Search retornará o caminho mais curto que existe.
Como detetar se um grafo dirigido contém um ciclo: uma sequência de arestas que começa e termina num nó específico.
Como usar o Topological Sort num grafo dirigido para produzir uma ordenação linear de nós compatível com todas as dependências no grafo dirigido.
Como determinar o caminho acumulado mais curto num grafo ponderado de um nó para todos os outros nós.
Como determinar o caminho acumulado mais curto num grafo ponderado entre dois nós quaisquer.

Os gráficos armazenam informações úteis de forma eficiente

Já falei sobre algoritmos para resolver problemas comuns em sistemas de informação relacionados com o armazenamento e processamento de dados. Estes algoritmos podem resolver inúmeros ...