Projeto de Algoritmos com Implementações em Pascal e C

Um projeto de Nivio Ziviani, Ph.D. Professor Emérito do Departamento de Ciência da Computação Universidade Federal de Minas Gerais

Editora: Pioneira Thomson


» capítulos


1 Introdução

  • 1.1 Algoritmos, Estruturas de Dados e Programas
  • 1.2 Tipos de Dados e Tipos Abstratos de Dados
  • 1.3 Medida do Tempo de Execução de um Programa
    • 1.3.1 Comportamento Assintótico de Funções
    • 1.3.2 Classes de Comportamento Assintótico
  • 1.4 Técnicas de Analise de Algoritmos
  • 1.5 Pascal
  • Notas Bibliograficas
  • Exercícios

2 Paradigmas de Projeto de Algoritmos

  • 2.1 Indução
  • 2.2 Recursividade
    • 2.2.1 Como Implementar Recursividade
    • 2.2.2 Quando Não Usar Recursividade
  • 2.3 Algoritmos Tentativa e Erro
  • 2.4 Divisão e Conquista
  • 2.5 Balanceamento
  • 2.6 Programação Din‰mica
  • 2.7 Algoritmos Gulosos
  • 2.8 Algoritmos Aproximados
  • Notas Bibliográficas
  • Exercícios
  • Programação Dinâmica
  • Algoritmos Gulosos
  • Algoritmos Aproximados
  • Notas Bibliograficas
  • Exercícios

3 Estruturas de Dados Básicas

  • 3.1 Listas Lineares
    • 3.1.1 Implementação de Listas por meio de Arranjos
    • 3.1.2 Implementação de Listas por meio de Apontadores
  • 3.2 Pilhas
    • 3.2.1 Implementação de Pilhas por meio de Arranjos
    • 3.2.2 Implementação de Pilhas por meio de Apontadores
  • 3.3 Filas
    • 3.3.1 Implementação de Filas por meio de Arranjos
    • 3.3.2 Implementação de Filas por meio de Apontadores
  • Notas Bibliográficas
  • Exercícios

4 Ordenação

  • 4.1 Ordenação Interna
    • 4.1.1 Ordenação por Seleção
    • 4.1.2 Ordenação por Inserção
    • 4.1.3 Shellsort
    • 4.1.4 Quicksort
    • 4.1.5 Heapsort
    • 4.1.6 Ordenação Parcial
    • 4.1.7 Ordenação em Tempo Linear
  • 4.2 Ordenação Externa
    • 4.2.1 Intercalação Balanceada de Vários Caminhos
    • 4.2.2 Implementação por meio de Seleção por Substituição
    • 4.2.3 Considerações Práticas
    • 4.2.4 Intercalação Polifásica
    • 4.2.5 Quicksort Externo
  • Notas Bibliográficas
  • Exercícios

5 Pesquisa em Memória Primária

  • 5.1 Pesquisa Sequencial
  • 5.2 Pesquisa Binária
  • 5.3 çrvores de Pesquisa
    • 5.3.1 Arvores Binárias de Pesquisa sem Balanceamento
    • 5.3.2 Arvores Binárias de Pesquisa com Balanceamento
  • 5.4 Pesquisa Digital
    • 5.4.1 Trie
    • 5.4.2 Patricia
  • 5.5 Transformação de Chave (Hashing)
    • 5.5.1 Funções de Transformação
    • 5.5.2 Listas Encadeadas
    • 5.5.3 Endereçamento Aberto
    • 5.5.4 Hashing Perfeito com Ordem Preservada
    • 5.5.5 Hashing Perfeito Usando Espaço Quase Ótimo
  • Notas Bibliográficas
  • Exercícios

6 Pesquisa em Memória Secundária

  • 6.1 Modelo de Computação para Memória Secundária
    • 6.1.1 Memória Virtual
    • 6.1.2 Implementação de um Sistema de Paginação
  • 6.2 Acesso Sequencial Indexado
    • 6.2.1 Discos Ópticos de Apenas-Leitura
  • 6.3 Árvores de Pesquisa
    • 6.3.1 Árvores B
    • 6.3.2 Árvores B*
    • 6.3.3 Acesso Concorrente em Árvores B*
    • 6.3.4 Considerações Práticas
  • Notas Bibliográficas
  • Exercícios

7 Algoritmos em Grafos

  • 7.1 Definições Básicas
  • 7.2 O Tipo Abstrato de Dados Grafo
    • 7.2.1 Implementação por meio de Matrizes de Adjacência
    • 7.2.2 Implementação por meio de Listas de Adjacência Usando Apontadores
    • 7.2.3 Implementação por meio de Listas de Adjacência Usando Arranjos
    • 7.2.4 Programa Teste para as Três Implementações
  • 7.3 Busca em Profundidade
  • 7.4 Teste para Verificar se Grafo é Acíclico
    • 7.4.1 Usando Busca em Profundidade
    • 7.4.2 Usando o Tipo Abstrato de Dados Hipergrafo
  • 7.5 Busca em Largura
  • 7.6 Ordenação Topológica
  • 7.7 Componentes Fortemente Conectados
  • 7.8 Árvore Geradora Mínima
    • 7.8.1 Algoritmo Genérico para Obter a Arvore Geradora Mínima
    • 7.8.2 Algoritmo de Prim
    • 7.8.3 Algoritmo de Kruskal
  • 7.9 Caminhos mais Curtos
  • 7.10 O Tipo Abstrato de Dados Hipergrafo
    • 7.10.1 Implementação por meio de Matrizes de Incidência
    • 7.10.2 Implementação por meio de Listas de Incidência Usando Arranjos
  • Notas Bibliográficas
  • Exercícios

8 Processamento de Cadeias de Caracteres

  • 8.1 Casamento de Cadeias
    • 8.1.1 Casamento Exato
    • 8.1.2 Casamento Aproximado
  • 8.2 Compressão
    • 8.2.1 Por Que Usar Compressão
    • 8.2.2 Compressão de Textos em Linguagem Natural
    • 8.2.3 Codificação de Huffman Usando Palavras
    • 8.2.4 Codificação de Huffman Usando Bytes
    • 8.2.5 Pesquisa em Texto Comprimido
  • Notas Bibliográficas
  • Exercícios

9 Problemas NP-Completo e Algoritmos Aproximados

  • 9.1 Problemas NP-Completo
    • 9.1.1 Algoritmos Não Deterministas
    • 9.1.2 As Classes NP-Completo e NP-Difícil
  • 9.2 Heurísticas e Algoritmos Aproximados
    • 9.2.1 Algoritmos Exponenciais Usando Tentativa e Erro
    • 9.2.2 Heurísticas para Problemas NP-Completo
    • 9.2.3 Algoritmos Aproximados para Problemas NP-Completo
  • Notas Bibliográfica
  • Exercícios

Produzido por Tambor Comunicação