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