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


» Prefácio

Prefácio

Este livro apresenta um estudo de algoritmos computacionais. As principais técnicas de projeto de algoritmos são ensinadas mediante explicação detalhada de algoritmos e estruturas de dados para o uso eficiente do computador. Essas explicações são dadas do modo mais simples possível, mas sem perder a profundidade e o rigor matemático.

O conteúdo é dirigido principalmente para ser utilizado como livro-texto em disciplinas sobre algoritmos e estruturas de dados. Pelo fato de apresentar muitas implementações de algoritmos práticos, o texto é igualmente útil para profissionais engajados no desenvolvimento de sistemas de computação e de programas de aplicação.

Os algoritmos são apresentados por meio de reÞnamentos sucessivos até uma implementação na linguagem Pascal. A vantagem de usar a linguagem Pascal é que os programas se tornam fáceis de ser lidos e de ser traduzidos para outras linguagens. Além disso, todos os algoritmos implementados na linguagem Pascal são também implementados na linguagem C. Todo programa Pascal de um capítulo tem um programa O correspondente no Apêndice.

Conteúdo

O livro apresenta as técnicas utilizadas para a implementação dos principais algoritmos conhecidos na literatura. Os t—picos estão agrupados em nove capítulos, cada um com o seguinte conteúdo: conceito de algoritmo, técnicas de analise de algoritmos, linguagem Pascal; (ii) paradigmas de projeto de algoritmos; (iii) estruturas de dados básicas; (iv) métodos de ordenação em mem—ria primaria e mem—ria secundaria; (v) métodos de pesquisa em mem—ria primaria; (vi)

métodos de pesquisa em mem—ria secundária; (vii) algoritmos em grafos; (viii) processamento de cadeias de caracteres; (ix) problemas NP-completo.

Palavras ou frases que aparecem em negrito no texto estão no êndice remissivo. Isso permite utilizar o livro como um hipertexto, possibilitando uma leitura não-linear, baseada em associações de ideias e conceitos. As palavras ou frases em negrito agem como portas virtuais que abrem caminhos para outras informações.

Ao final de cada capítulo são incluídos exercícios, e 0 Apêndice K apresenta respostas para uma parte considerável dos exercícios propostos. Alguns exercícios são questões curtas, para testar os conhecimentos básicos sobre o material apresentado. Outros são questões mais elaboradas, podendo exigir do leitor um trabalho de vários dias, devendo ser realizados em casa ou em laborat—rio. Assim, os exercícios propostos podem ser utilizados em testes e trabalhos práticos para avaliação da aprendizagem.

Também ao final de cada capítulo é apresentada uma discussão da literatura, apontando as principais referências relacionadas com o capítulo em questão. O objetivo da seção não é esgotar as referências bibliográÞcas sobre cada assunto, mas apenas apresentar um pequeno hist—rico da bibliograÞa, procurando relatar as referências mais signiÞcativas em cada momento.

Ao Professor

Para cada capítulo existe um conjunto de slides para serem usados em sala de aula pelo professor. Cada um desses conjuntos segue fielmente o texto correspondente no livro. Existe um conjunto de slides usando a linguagem Pascal e outro usando a linguagem C. Assim, os cursos podem ser baseados na linguagem C em vez da linguagem Pascal.

Os slides estão nos formatos PostScript ou PDF, podendo ser projetados diretamente de um computador usando um navegador (browser), com o uso de um leitor de arquivos PostScrípt ou um leitor de arquivos PDF. Eles podem ser obtidos diretamente do site do livro no endereço wu1u1.dcc.ufmg.br/ algoritmos.

O material apresentado é adequado para ser utilizado como livro-texto em cursos técnicos, de graduação, p—s-graduação e extensão para formação de profissionais na área de Algoritmos e Estruturas de Dados. O conteúdo de cada capítulo e sugestões de como usá-lo em sala de aula é apresentado a seguir. Sugerimos que o estudo de algoritmos ocorra em três níveis de disciplinas, a saber:

  • Capítulo 2 Paradigmas de Projeto de Algoritmos: Indução, recursividade, algoritmos tentativa e erro, divisão e conquista, balanceamento, programação din‰mica, algoritmos gulosos e algoritmos aproximados.
    Sugestões: O ensino de alguns paradigmas, tais como indução e recursividade, podem ocorrer logo na primeira disciplina sobre algoritmos. Os outros paradigmas podem ser ensinados em disciplinas subsequentes. O ensino de algoritmos é usualmente dividido por t—picos ou tipos de problemas. O mesmo acontece com este livro. Entretanto, um curso aprofundado de projeto e análise de algoritmos pode ser dividido em paradigmas de projeto de algoritmos, em vez da divisão por t—picos ou tipos de problemas. Nesse caso, o Capítulo 2 pode ser usado como guia.
  • Capitulo 3 Estruturas de Dados Básicas: Listas lineares, pilhas e filas.

    Sugestões: As estruturas de dados básicas podem ser ensinadas em uma primeira disciplina sobre algoritmos, tomando o cuidado de ensinar, nesse momento, a implementação de listas por meio de arranjos, deixando a implementação de listas por meio de apontadores para uma disciplina subsequente. Em especial, o conceito e implementação de pilhas é importante para o entendimento de recursividade.
  • Capitulo 4 Ordenação: Ordenação interna (inserção, seleção, shellsort, quicksort, heapsort, parcial, em tempo linear); ordenação externa (intercalação balanceada de vários caminhos, implementação por meio de seleção por substituição, considerações práticas, intercalação polifásica e quicksort externo).

    Sugestões: Os algoritmos mais simples de ordenação em mem—ria principal, tais como inserção, seleção e contagem, podem ser ensinados em uma primeira disciplina sobre algoritmos. Os algoritmos mais eficientes (quicksort e radixsort) podem ser cuidadosamente ensinados em uma segunda disciplina sobre algoritmos, assim como heapsort e ordenação em mem—ria secundária.
  • Capitulo 5 Pesquisa em Mem—ria Primária: Pesquisa sequencial, pesquisa binária, árvores de pesquisa, pesquisa digital, transformação de chave (funções de transformação, listas encadeadas, endereçamento aberto, hashing perfeito com ordem preservada e hashing perfeito usando espaço quase —timo).

    Sugestões: Os algoritmos de pesquisa sequencial e binária podem ser ensinados em uma primeira disciplina sobre algoritmos, enquanto árvores de pesquisa e hashing podem ser ensinados em uma segunda disciplina. Pesquisa digital e hashing perfeito podem ser ensinados em uma disciplina avançada sobre algoritmos.
  • Capitulo 6 Pesquisa em Mem—ria Secundária: Modelo de computação para mem—ria secundária (mem—ria virtual, implementação de um sistema de paginação), acesso sequencial indexado (discos —pticos de apenas leitura) e árvores de pesquisa (árvores B, árvores B*, acesso concorrente em árvores B*, considerações práticas).

    Sugestões: Nesse capítulo o t—pico mais importante é sobre as árvores B e B*, que pode ser ensinado em uma segunda disciplina sobre algoritmos. Apesar de menos importante o estudo de mem—ria virtual ode ser útil 7 para o entendimento de como ocorre a transferência de dados entre a mem—ria principal e a mem—ria secundária nos sistemas operacionais de hoje.
  • Capítulo 7 Algoritmos em Grafos: Definições básicas, o tipo abstrato de dados grafo, busca em profundidade, teste para verificar se o grafo é acíclico, busca em largura, ordenação topol—gica, componentes fortemente conectados, árvore geradora mínima, caminhos mais curtos e o tipo abstrato de dados hipergrafo.

    Sugestões: A representação e os algoritmos mais básicos sobre grafos podem ser ensinados em uma segunda disciplina sobre algoritmos. Um estudo mais aprofundado sobre grafos pode ocorrer em uma disciplina avançada sobre algoritmos.
  • Capítulo 8 Processamento de Cadeias de Caracteres: Casamento de cadeias (casamento exato e casamento aproximado), compressão (por que usar compressão, compressão de textos em linguagem natural, codificação de Huffman usando palavras, codificação de Huffman usando bytes, pesquisa em texto comprimido).

    Sugestões: Os algoritmos sobre casamento de cadeias de caracteres podem ser ensinados em uma segunda disciplina sobre algoritmos, com destaque para o algoritmo BMHS para casamento exato. Os algoritmos sobre casamento aproximado e compressão de textos em linguagem natural podem ser parte de uma disciplina avançada sobre algoritmos.
  • Capítulo 9 Problemas NP-completo e Algoritmos Aproximados: Problemas NP-completo (algoritmos não-deterministas, as classes NP-completo e NP-difícil), heurísticas e algoritmos aproximados (algoritmos exponenciais usando tentativa e erro, heurísticas para problemas NP-completo, algoritmos aproximados para problemas NP-completo).

    Sugestões: Problemas considerados intratáveis ou difíceis são muito comuns na natureza e nas diversas áreas do conhecimento. Saber distinguir entre problemas que podem ser resolvidos e problemas que não podem ser resolvidos por um computador deve ser ensinado desde as disciplinas básicas sobre algoritmos, podendo ser mais detalhado em uma segunda disciplina. A teoria de complexidade de algoritmos pode ser ensinada em uma disciplina de t—picos avançados sobre algoritmos.

Os três níveis de disciplinas discutidos anteriormente podem ser encontrados em diversos cursos no país. Para exemplificar, versões preliminares deste livro foram utilizadas em disciplinas na Universidade Federal de Minas Gerais, a saber:


  • Algoritmos e Estruturas de Dados I, lecionada para o curso de Bacharelado com ênfase em Ciência da Computação, Matemática Computacional e Sistemas de Informação, para as Engenharias de Computação, Controle e Automação, Elétrica, Eletrônica e Mecânica, com carga horária de 60 horas e um semestre de duração. Além do estudo de uma primeira linguagem de programação, tipicamente Pascal ou Java, são ensinados tipos abstratos de dados; introdução à análise de algoritmos; indução matemática; algoritmos recursivos; listas lineares, pilhas e filas.
  • Algoritmos e Estruturas de Dados II, lecionada para o curso de Bacharelado com ênfase em Ciência da Computação, Matemática Computacional e Sistemas de Informação, para as Engenharias de Computação, Controle e Automação, Elétrica, Eletrônica e Mecânica, com carga horária de 60 horas e um semestre de duração, possui a seguinte ementa: introdução à análise de algoritmos; ordenação em memória primária: seleção direta, inserção direta, shellsort, quicksort, heapsort, mergesort, radixsort e ordenação parcial; pesquisa em memória primária: seqüencial, binária e transformação de chave (hashing); árvores de pesquisa: sem balanceamento, com balanceamento, tries e patricia; ordenação externa; pesquisa em memória secundária: memória virtual, indexado seqüencial e árvore B.
  • Algoritmos e Estruturas de Dados III, lecionada para o curso de Bacharelado com ênfase em Ciência da Computação, Matemática Computacional e Sistemas de Informação, com carga horária de 60 horas e um semestre de duração, possui a seguinte ementa: estudo mais elaborado de projeto e análise de algoritmos; paradigmas de projeto de algoritmos; algoritmos em grafos; problemas NP-completo, heurísticas e algoritmos aproximados; processamento de cadeias de caracteres.
  • Projeto e Análise de Algoritmos, lecionada para os cursos de Mestrado e Doutorado em Ciência da Computação, com carga horária de 60 horas, possui a seguinte ementa: técnicas de análise de algoritmos; paradigmas de projeto de algoritmos; algoritmos em grafos; problemas NP-completo, heurísticas e algoritmos aproximados; processamento de cadeias de caracteres; algoritmos paralelos.

O ensino de algoritmos é usualmente dividido por tópicos ou tipos de problemas. O mesmo acontece com este livro. Entretanto, um curso aprofundado de projeto e análise de algoritmos pode ser dividido em paradigmas de projeto de algoritmos, em vez da divisão por tópicos ou tipos de problemas. Nesse caso, o Capítulo 2 pode ser usado como guia. Essa mudança na forma de ensinar pode levar a melhores projetos e realça a importância da análise de algoritmos.

Ao final de cada capítulo são incluídos exercícios e o Apêndice L apresenta respostas para uma parte considerável dos exercícios propostos. Alguns exercícios são do tipo questões curtas, para testar os conhecimentos básicos sobre o material apresentado. Outros exercícios são do tipo questões mais elaboradas, podendo exigir do leitor um trabalho de vários dias, devendo ser realizado em casa ou em laboratório. Assim, os exercícios propostos devem ser utilizados em testes e trabalhos práticos para avaliação da aprendizagem.

Também ao final de cada capítulo é apresentada uma discussão da literatura, apontando as principais referências relacionadas com o capítulo em questão. O objetivo da seção não é esgotar as referências bibliográficas sobre cada assunto, mas apenas apresentar um pequeno histórico da bibliografia, procurando relatar as referências mais significativas em cada momento.

Para cada capítulo existe um conjunto de transparências para serem usadas em sala de aula pelo professor. Cada conjunto de transparências segue fielmente o texto correspondente no livro, e o formato é de uma transparência por página. Para facilitar a distribuição impressa de cópias das transparências para os estudantes existe um conjunto equivalente contendo quatro transparências por página. As transparências estão nos formatos PostScript ou PDF, podendo ser projetadas diretamente de um computador usando um navegador (browser), com o uso de um leitor de arquivos PostScript, ou um leitor de arquivos PDF. As transparências podem ser obtidas diretamente do site do livro no endereço www.dcc.ufmg.br/algoritmos.

Ao Estudante

O estudo do comportamento dos algoritmos tem papel decisivo no projeto de algoritmos eficientes. Técnicas de analise de algoritmos são consideradas partes integrantes do processo moderno de resolver problemas, permitindo escolher, de forma racional, um entre vários algoritmos disponíveis para uma mesma aplicação. Por isso, neste livro são apresentadas informações sobre as características de desempenho de cada algoritmo apresentado. Os algoritmos são introduzidos por meio de refinamentos sucessivos, passo a passo, procurando fazer com que aqueles mais difíceis possam ser entendidos facilmente. Além disso, grande ênfase é dada aos principais paradigmas de projeto de algoritmos.

Com relação aos pré-requisitos necessários para a leitura deste livro, o ideal é ter alguma experiência em programação de computadores. Em particular, é necessário entender procedimentos recursivos e também saber lidar com estruturas de dados mais simples usando arranjos e apontadores. A parte matemática utilizada para apresentar os resultados analíticos e autocontida e exige muito pouco conhecimento matemático prévio para ser entendida. Algumas partes do texto demandam pequeno conhecimento de calculo elementar e matemática discreta.

Ao Profissional

Este texto pode também ser utilizado como manual para programadores que já tenham familiaridade com o assunto, pois são apresentadas implementações de algoritmos de utilidade geral. A maioria dos algoritmos mostrados tem grande utilidade pratica, tais como os algoritmos Quicksort e Radixsort de ordenação e o algoritmo BMHS de casamento de cadeias de caracteres. Considerações sobre implementação são discutidas ao longo do texto. Para muitos dos problemas discutidos são apresentadas varias alternativas de soluções e, em muitos casos, um estudo comparativo do comportamento dos algoritmos envolvidos em cada alternativa.

Os algoritmos propostos são completamente implementados nas linguagens Pascal e C e as operações envolvidas são descritas mediante a apresentação de exemplos de execução. Os c—digos em Pascal e C podem ser obtidos diretamente do site do livro no endereço www.dcc.ufmg.br/algoritmos, no qual os procedimentos em Pascal e C já são acompanhados de um programa principal que permite executar imediatamente um pequeno teste.

Mudanças da Segunda para a Terceira Edição

As mudanças realizadas entre a primeira e a segunda edição são muitas. Uma simples verificação do sumário mostra que várias novas seções foram introduzidas nos capítulos da edição anterior. Entretanto, a grande mudança está na introdução de quatro novos capítulos. Outra mudança significativa está relacionada com a adição de novos exercícios, bem como a solução de uma parte dos exercícios propostos.

Entretanto, o material novo adicionado à segunda edição preserva toda a característica da primeira edição, que é a de apresentar as principais técnicas de projeto de algoritmos por meio da explicação detalhada de algoritmos e estruturas de dados, mantendo as explicações do modo mais simples possível, preservando contudo a profundidade e o rigor matemático.

A seguir, apresentamos um resumo das principais mudanças para a segunda edição, a saber:

  • Todos os erros conhecidos foram devidamente corrigidos.
  • Adição de novos exercícios ao final de cada capítulo.
  • Solução de muitos dos novos exercícios propostos.
  • Os programas em Pascal e C foram revisados e melhorados.
  • Nos capítulos que já existiam na segunda edição foram introduzidas novas seções sobre os seguintes t—picos:
    • Teorema mestre (Seção 2.4).
    • Ordenação em tempo linear (Seção 4.1.7).
    • Uma nova função hash (Seção 5.5).
    • Hashing perfeito com ordem preservada (Seção 5.5.4).
    • Hashing perfeito usando espaço quase îtimo (Seção 5.5.5).
    • Estruturas de dados sucintas (Seção 5.5.5).
    • Teste para verificar se um hipergrafo é acíclico (Seção 74).
    • Tipo abstrato de dados hipergrafo (Seção 710).

      Agradecimentos para a Terceira Edição

      Agradeço aos amigos e colegas que contribuíram para a qualidade desta terceira edição, em especial a Alberto Henrique Frade Laender, Antônio Alfredo Loureiro, Berthier Ribeiro-Neto, Dorgival Olavo Guedes Neto, Edleno Silva de Moura, Luiz Chaimowicz, Mariza Bigonha, Renato Antonio Celso Ferreira, Roberto da Silva Bigonha e Virgilio Augusto Fernandes Almeida. Um agradecimento especial para Jussara Marques de Almeida e Wagner Meira Jr pelas diversas sugestões de novos exercícios e leitura crítica de partes do livro. Dos professores que me ensinaram muito sobre algoritmos, agradeço particularmente a Antônio Luz Furtado, Frank Tompa, Gaston Gonnet, Ian Munro e Pal Larson.

      Esta terceira edição foi realizada em um ambiente excelente para a elaboração de um livro-texto, o Departamento de Ciência da Computação da Universidade Federal de Minas Gerais. Em nome de Lászl— Ernesto de Miranda Pinto, Murilo Silva Monteiro e Pollyana do Amaral Ferreira agradeço o suporte técnico do CRC - Centro de Recursos Computacionais do Departamento para manter o ambiente LATEX e o site do livro no endereço www.dcc.ufmg.br/algoritmos. Agradeço o apoio sempre competente da bibliotecária Belkiz Inez Costa e das secretarias Claudia Lourenço Viana, Emília Soares da Silva, Gilmara Viviane Silva Stole, Lizete da Conceição Barrêto Paula, Maria Aparecida Scaldaferri Lages, Maristela Soares Marques, Renata Viana Moraes Rocha, Sheila Lúcia dos Santos, Sônia Lúcia Borges Vaz de Melo, Stella Mara Marques, Túlia Andrade Silva Resende. Diversas versões preliminares do livro foram encadernadas por Alexandre Guimarães Dias, Geraldo Felício de Oliveira, e Orlando Rodrigues da Silva, a quem agradeço.

      Os estudantes de graduação e p—s-graduação contribuíram significativamente e a eles sou grato. Dos monitores da disciplina Projeto e Analise de Algoritmos e bolsistas do LATIN - Laborat—rio para Tratamento da Informação, agradeço particularmente a Álvaro Rodrigues Pereira Júnior, Anísio Mendes Lacerda, Bruno Augusto Vivas e Pôssas, Bruno Maciel Fonseca, Charles Ornelas Almeida, Claudine Santos Badue, Denilson Alves Pereira, Fabiano Cupertino Botelho, Guilherme Vale Ferreira Menezes, Hendrickson Reiter Langbehn, Marco Aurélio Barreto Modesto, Rickson Guidolini, Thierson Couto Rosas, Wallace Favoreto Henrique, Wladmir Cardoso Brandão.

      Um agradecimento para Fabiano Cupertino Botelho, pela ajuda na redação das seções sobre ordenação em tempo linear, hashing perfeito e hipergrafos, Guilherme Vale Ferreira Menezes, pelo trabalho com as respostas de exercícios, criação e teste do c—digo de alguns programas, desenho das novas figuras e tradução de programas em Pascal para C; Israel Guerra de Moura e João Victor dos Anjos Barbara, pela revisão e teste de todos os c—digos em C; Wallace Favoreto Henrique, pelo estudo comparativo dos algoritmos de ordenação em tempo linear e tradução de programas em Pascal para C. Importante ressaltar o trabalho de design do site do livro de Eduardo Luppi e Poliana Rabelo, da Tambor Comunicação.

      Entre as pessoas que gentilmente apontaram erros na segunda edição agradeço a Alessandro Mendes, Álvaro Rodrigues Pereira Júnior, Anísio Mendes Lacerda, Ariovaldo Dias de Oliveira, Cleber Mira, David Menotti, Elisa Tuler de Albergaria, Fabiano Cupertino Botelho, Fabiano M. Atalla da Fonseca, João Rafael Moraes Nicola, José Augusto Nacif, Leonardo Chaves Dutra da Rocha, Marco Aurélio Barreto Modesto, Marco Antônio Pinheiro de Cristo.

      Um agradecimento especial para Carlos Eduardo Corradi Fonseca, pela forma de ser e pela competência e brilhantismo no exercício profissional.

      Foi importante o apoio recebido do CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnol—gico, do Ministério de Ciência e Tecnologia e da Finep Financiadora de Estudos e Projetos, mediante os seguintes projetos: CNPq/ CTINFO/Gerindo - Gerência e Recuperação de Informação em Documentos, processo CNPq 55.2087/02-5, CNPq/CT-INFO/InfoWeb - Métodos e Ferramentas para Tratamento de Informação Disponível na Web, processo CNPq 550874 / 2007-O, MCT/CNPq/INCT - Instituto Nacional de Ciência e Tecnologia para a Web, processo CNPq 573871 / 2008-6, e Bolsa de Produtividade em Pesquisa - Ambientes para Recuperação de Informação na WWW, processo CNPq 30.5237/O2-0.

      Trabalhar com a Cengage Learning tem sido um prazer. Desde a fase de revisão e de formatação do texto até a impressão final do livro, sempre houve um suporte competente e profissional.

      Um agradecimento muito carinhoso para Márcia de Mendonça Jorge, pelo seu amor e suporte durante a redação da terceira edição deste livro.

      Nivio Ziviani Belo Horizonte
      Junho de 2010
      Site Web do livro: www.dcc.ufmg.br/algoritmos


Produzido por Tambor Comunicação