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