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

Este livro apresenta uma introdu√ß√£o ao estudo de algoritmos. 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.

As t√©cnicas de projeto de algoritmos s√£o ensinadas seguindo o paradigma de orienta√ß√£o a objetos, por meio de refinamentos sucessivos at√© o n√≠vel de uma implementa√ß√£o na linguagem Java. Todo programa Java tem um programa C++ correspondente nos ap√™ndices. Existe tamb√©m uma vers√£o dispon√≠vel do livro para as linguagens Pascal e C, intitulado Projeto de Algoritmos com Implementa√ß√Ķes em Pascal e C.

Conte√ļdo

O livro apresenta as principais t√©cnicas utilizadas para a implementa√ß√£o de estruturas de dados e de algoritmos para ordena√ß√£o e pesquisa em mem√≥ria prim√°ria e mem√≥ria secund√°ria, grafos, processamento de cadeias de caracteres, problemas NP-completo e heur√≠sticas. Os t√≥picos est√£o agrupados em nove cap√≠tulos, cada um com o seguinte conte√ļdo:

  1. Conceito de algoritmo, estrutura de dados e tipo abstrato de dados, medida do tempo de execução de um programa, técnicas de análise de desempenho de algoritmos, linguagem Java.
  2. Paradigmas de projeto de algoritmos: indu√ß√£o, recursividade, algoritmos tentativa e erro, divis√£o e conquista (teorema mestre), balanceamento, programa√ß√£o din√Ęmica, algoritmos gulosos e algoritmos aproximados.
  3. Estruturas de dados b√°sicas: listas lineares, pilhas e filas.
  4. Métodos de ordenação em memória primária: por inserção, por seleção, shellsort, quicksort, heapsort e ordenação parcial; métodos de ordenação em memória secundária: intercalação balanceada, intercalação polifásica e quicksort externo.
  5. M√©todos de pesquisa em mem√≥ria prim√°ria: pesquisa seq√ľencial, pesquisa bin√°ria, √°rvores de pesquisa, hashing universal e hashing perfeito.
  6. M√©todos de pesquisa em mem√≥ria secund√°ria: seq√ľencial indexado e √°rvores B.
  7. Algoritmos em grafos: representação, busca em profundidade, busca em largura, ordenação topológica, componentes fortemente conectados, árvore geradora mínima, caminhos mais curtos e hipergrafos.
  8. Processamento de cadeias de caracteres: busca exata e aproximada de padr√Ķes, compress√£o de textos em linguagem natural.
  9. Problemas NP-completo: classes NP-completo e NP-difícil, transformação polinomial, teorema de Cook, algoritmos exponenciais usando tentativa e erro, heurísticas e algoritmos aproximados para o problema do caixeiro-viajante.

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 id√©ias e conceitos. As palavras ou frases em negrito agem como portas virtuais que abrem caminhos para outras informa√ß√Ķes.

Linguagens de Programação

A linguagem de programa√ß√£o utilizada para apresenta√ß√£o do refinamento final dos algoritmos apresentados √© a Java, e todo programa Java tem um programa C++ correspondente. Este livro utiliza extensivamente tipos abstratos de dados como base para o projeto de algoritmos. Um tipo abstrato de dados √© como um modelo matem√°tico, acompanhado das opera√ß√Ķes definidas sobre o modelo. O conjunto dos inteiros acompanhado das opera√ß√Ķes de adi√ß√£o e subtra√ß√£o forma um exemplo de um tipo abstrato de dados.

A vantagem de se usar Java e C++ √© que os programas podem ser escritos usando o conceito de programa√ß√£o orientada a objetos. A programa√ß√£o orientada a objetos permite que objetos do mundo real que compartilham propriedades, atributos e comportamentos comuns sejam agrupados em classes que podem ser usadas em diferentes aplica√ß√Ķes.

Resumindo, os programas ao longo do livro são baseados em tipos abstratos de dados, programação modular e programação orientada a objetos, o que facilita o encapsulamento e a independência de implementação de tipos abstratos de dados e permite o reaproveitamento de código. Por exemplo, nos algoritmos de ordenação, o tipo da chave de ordenação dos itens de um conjunto é genérico, permitindo que os usuários dos algoritmos possam definir um tipo de dados qualquer que atenda às suas necessidades, sem causar nenhum impacto nos códigos dos algoritmos de ordenação. Outro exemplo, os algoritmos em grafos utilizam operadores de um tipo abstrato de dados, o que permite implementar os algoritmos de forma independente da representação escolhida para o grafo.

Ao Professor

O material apresentado √© adequado para ser utilizado como livro-texto em cursos de gradua√ß√£o, p√≥s-gradua√ß√£o e extens√£o para forma√ß√£o de programadores na √°rea de Algoritmos e Estruturas de Dados. √Č recomend√°vel que o estudante j√° tenha tido um curso de programa√ß√£o (ou experi√™ncia equivalente) em uma linguagem de alto n√≠vel, tal como Java ou C++, assim como conhecimentos de utiliza√ß√£o de sistemas de computa√ß√£o.

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.
  • =-1 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 K 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 realizados 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 um desses conjuntos 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-java.

Ao Estudante

O estudo do comportamento dos algoritmos tem um papel decisivo no projeto de algoritmos eficientes. T√©cnicas de an√°lise de algoritmos s√£o consideradas partes integrantes do processo moderno de resolver problemas, permitindo escolher, de forma racional, um dentre 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. As t√©cnicas de projeto de algoritmos s√£o ensinadas de forma simples, seguindo o paradigma de orienta√ß√£o a objetos, por meio de refinamentos sucessivos, passo a passo, procurando fazer com que aqueles mais dif√≠ceis possam ser entendidos facilmente. Al√©m disso, uma grande √™nfase √© dada aos principais paradigmas de projeto de algoritmos. Esperamos, assim, que este livro proporcione ao aluno uma inicia√ß√£o agrad√°vel √† √°rea de projeto e an√°lise 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 algoritmos 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 é autocontida e exige muito pouco conhecimento matemático prévio para ser entendida. Algumas partes do texto demandam pequeno conhecimento de cálculo 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 pr√°tica, e considera√ß√Ķes sobre implementa√ß√£o s√£o discutidas ao longo do texto. Para muitos dos problemas discutidos s√£o apresentadas v√°rias alternativas de solu√ß√Ķes, e em muitos casos existe um estudo comparativo do comportamento dos algoritmos envolvidos em cada alternativa.

Os algoritmos propostos s√£o completamente implementados nas linguagens Java e C++ e as opera√ß√Ķes envolvidas s√£o descritas mediante a apresenta√ß√£o de exemplos de execu√ß√£o. Os c√≥digos em Java e C++ podem ser obtidos diretamente do site do livro no endere√ßo www.dcc.ufmg.br/algoritmos-java, no qual os m√©todos em Java e C++ j√° v√™m acompanhados de um programa principal que permite executar imediatamente um pequeno teste.

Agradecimentos

Muitos amigos e colegas contribu√≠ram para a qualidade das muitas vers√Ķes deste livro ao longo dos √ļltimos 15 anos. Agrade√ßo a todos pela ajuda e pelas cr√≠ticas construtivas, em especial a Alberto Henrique Frade Laender, Ant√īnio Alfredo Loureiro, Berthier Ribeiro-Neto, Carlos Eduardo Corradi Fonseca, Carlos Jos√© Pereira de Lucena, Cilio Rosa Ziviani, Cleber Hostal√°cio de Melo, Dorgival Olavo Guedes Neto, Eduardo Fernandes Barbosa, Gonzalo Navarro, Jos√© Monteiro da Mata, Jos√© Nagib Cotrim √Ārabe, Jussara Marques de Almeida, Let√≠cia Simonetti Garcia, Lilia Tavares Mascarenhas, Luiz Carlos de Abreu Albuquerque, M√°rcio Luiz Bunte de Carvalho, Mariza Bigonha, Maur√≠cio Ant√īnio de Castro Lima, Murilo Silva Monteiro, Osvaldo S√©rgio Farhat de Carvalho, Regina Helena Bastos Cabral, Renato Antonio Celso Ferreira, Roberto da Silva Bigonha, Roberto M√°rcio Ferreira de Souza, Ros√Ęngela Fernandes, Routo Terada, Virgilio Augusto Fernandes Almeida, Wagner Meira Jr. e Wagner Toledo Corr√™a.

O trabalho realizado junto com Fabiano Cupertino Botelho para criar o estilo de programar em Java usado neste livro sempre foi muito prazeroso. Além disso, meus agradecimentos para Fabiano, pela redação da seção sobre Quicksort externo, participação da redação e criação dos programas sobre compressão de textos e trabalho com as respostas de exercícios.

A Ricardo Baeza-Yates agrade√ßo a sugest√£o de criar o cap√≠tulo sobre paradigmas de projeto de algoritmos e o texto de apresenta√ß√£o deste livro. Um agradecimento especial para Bruno Augusto Vivas e P√īssas e Roberto da Silva Bigonha pelas sugest√Ķes sobre os programas nas linguagens Java e C++.

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.

As diversas vers√Ķes deste livro foram realizadas 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. Os estudantes de gradua√ß√£o e p√≥s-gradua√ß√£o contribu√≠ram significativamente e a eles sou grato. Dos monitores das disciplinas Algoritmos e Estruturas de Dados II, Algoritmos e Estruturas de Dados III e Projeto e An√°lise de Algoritmos, agrade√ßo particularmente a Bruno Augusto Vivas e P√īssas, Claudine Santos Badue, Cl√°udio Ricardo Guimar√£es Sant'Ana, Cristina Duarte Murta, Daniel Tavares de Castro, Edleno Silva de Moura, Fabiano Cupertino Botelho, Fabr√≠cio Benevenuto de Souza, Helv√©cio Guimar√£es Ribeiro, Ilm√©rio Reis, Maria Cl√°udia Guimar√£es Guatimosim, Maria Dalva Resende, Patricia Seno Fusaro, Robert Pereira Pinto, Rodrigo Lima Carceroni, S√©rgio Augusto √Āvila Maria e Thierson Couto Rosa.

Aos estudantes de p√≥s-gradua√ß√£o que me auxiliaram na elabora√ß√£o desta obra meus agradecimentos, especialmente para Adriano C√©sar Machado Pereira, Bruno Dias Abrah√£o, Bruno Diniz de Paula, Cristiane Amorim Mendes, Fernando Caixeta Sanches, Fl√°via Perigrinelli Ribeiro, Goedson Teixeira Paix√£o, Gustavo Menezes Siqueira, Ligiane Alves de Souza, M√°rcio Drumond Ara√ļjo, Pavel Calado, Patricia Correia Saraiva, Ramurti Barbosa e Wesley Dias Maciel. Um agradecimento especial para os seguintes estudantes: Charles Ornelas Almeida, pela cria√ß√£o do estilo LATEX, desenho de todas as figuras do livro, formata√ß√£o de todo o texto, teste de programas e participa√ß√£o na se√ß√£o sobre hashing perfeito; Danilo Ferreira e Silva, pelo teste exaustivo dos programas em Java e C++; Davi de Castro Reis, pelo estudo comparativo dos algoritmos de ordena√ß√£o parcial; Juliano Palmieri, pela participa√ß√£o da reda√ß√£o e cria√ß√£o dos programas sobre compress√£o de textos; Leonardo Henrique Machado, pelo suporte computacional e Thierson Couto Rosa, pelo trabalho com as respostas de exerc√≠cios.

Entre as pessoas que gentilmente apontaram erros nas diversas vers√Ķes agrade√ßo a Alessandro Justiniano Mendes, Andr√© Gustavo dos Santos, An√≠sio Mendes Lacerda, Bruno Muller J√ļnior, Daniel Pablo Herschel, Daniel Walter Berns, Elisa Tuler de Albergaria, Fabiano M. Atalla da Fonseca, Frederico Paiva Quint√£o, Gustavo Cota Guimar√£es Mendon√ßa, H√©ctor Alejandro Virgolini, Ichiro Aoki, Juan Luis Almar√°, K√™mio de Oliveira Couto, Klaus de Geus, Leonardo Chaves Dutra da Rocha, Luis Joaquin Vazquez, Marco Ant√īnio Pinheiro de Cristo, Marco Aur√©lio Barreto Modesto, Marco Aur√©lio de Souza Mendes, Maria Gabriela Maidana, Pablo Velo e Ruiter Braga Caldas.

Diversas vers√Ķes preliminares do livro foram encadernadas por Alexandre Guimar√£es Dias, Geraldo Fel√≠cio de Oliveira, Sheila L√ļcia dos Santos e Orlando Rodrigues da Silva, a quem agrade√ßo.

Foi importante o apoio recebido do CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico e da Finep - Financiadora de Estudos e Projetos, mediante os seguintes projetos: CNPq/CT-INFO/Gerindo - Gerência e Recuperação de Informação em Documentos, processo CNPq 55.2087/02-5 e Bolsa de pesquisa - Ambientes para Recuperação de Informação na WWW, processo CNPq 520.916/94-8.

Trabalhar com a Thomson tem sido um prazer. Desde os primeiros contatos, a fase de revisão e de formatação do texto, até a impressão final do livro, sempre houve um suporte leve, ágil, competente e profissional.

Nivio Ziviani
Belo Horizonte
Julho de 2006

Pref√°cio do Consultor Java e C++

Minha paix√£o por algoritmos surgiu na gradua√ß√£o, durante o curso de Projeto e An√°lise de Algoritmos. Eu fiquei fascinado ao perceber que em um √ļnico curso eu poderia exercitar a criatividade, o pensamento l√≥gico e muita matem√°tica para analisar o desempenho dos algoritmos projetados. Desde ent√£o, tenho estudado e me especializado na √°rea de algoritmos e foi com imensa satisfa√ß√£o que aceitei o convite do Professor Nivio Ziviani para trabalhar com ele neste livro. Obrigado, Nivio, pela oportunidade.

Nas implementa√ß√Ķes dos algoritmos e estruturas de dados em Java priorizamos a obten√ß√£o de c√≥digos de f√°cil compreens√£o. Portanto, foram evitadas constru√ß√Ķes que poderiam comprometer a compreens√£o dos algoritmos apresentados. Pr√°ticas de programa√ß√£o defensiva para detec√ß√£o e corre√ß√£o de erros foram evitadas, embora estejam presentes nas situa√ß√Ķes mais simples nas quais a did√°tica dos c√≥digos n√£o foi comprometida.

Os códigos em Java e C++ foram escritos de forma ortogonal sempre que possível. Por exemplo, em Java todo vetor possui um atributo chamado length que armazena o seu tamanho e, portanto, não seria necessário passar o tamanho de um vetor para um método. No entanto, como tal característica não existe em C++, optamos por passar os tamanhos dos vetores para os métodos em Java quando necessário.

Sempre que poss√≠vel procuramos gerar c√≥digos eficientes em Java. Assim, as implementa√ß√Ķes podem ser facilmente incorporadas em sistemas computacionais a serem desenvolvidos para os mais diversos cen√°rios. Cabe ressaltar que os c√≥digos em C++ apresentados nos ap√™ndices foram escritos para estarem o mais pr√≥ximo poss√≠vel dos respectivos c√≥digos em Java. Por conseq√ľ√™ncia, nem sempre os c√≥digos s√£o t√£o eficientes quanto poderiam ser. Mas, em contrapartida, fica f√°cil compreender os c√≥digos em C++ a partir da descri√ß√£o feita para os respectivos c√≥digos em Java.

Eu gostaria de agradecer à minha família pelo apoio emocional recebido durante a realização deste trabalho. Em especial, gostaria de agradecer à minha amável esposa Janaína, pelo carinho e compreensão por tantas noites de trabalho dedicadas ao livro. Também gostaria de agradecer aos professores Marcus Vinícius Alvim Andrade, por ter despertado em mim o prazer pelo estudo de algoritmos e estruturas de dados, José Luis Braga, pela enorme influência na minha formação, e orientador Nivio Ziviani, que tem me ensinado a estudar algoritmos e estruturas de dados com profundidade e dedicação.

Fabiano Cupertino Botelho
Belo Horizonte
Julho de 2006


Produzido por Tambor ComunicaÁ„o