Prefácio

Este livro apresenta uma introdução ao 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 refinamentos sucessivos até o nível de uma implementação na linguagem Pascal, o que permite que qualquer pessoa com um mínimo de experiência em programação possa ler o código.

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 e problemas NP-completo e heurísticas. Os tópicos estão agrupados em nove capítulos, cada um com o seguinte conteúdo: (i) 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 Pascal; (ii) paradigmas de projeto de algoritmos; (iii) estruturas de dados básicas: listas lineares, pilhas e filas; (iv) 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; (v) métodos de pesquisa em memória primária: pesquisa seqüencial, pesquisa binária, árvores de pesquisa, hashing universal e hashing perfeito; (vi) métodos de pesquisa em memória secundária: seqüencial indexado e árvores B; (vii) algoritmos em grafos: representação, busca em profundidade, busca em largura, ordenação topológica, componentes fortemente conectados, árvore geradora mínima e caminhos mais curtos; (viii) processamento de cadeias de caracteres: busca exata e aproximada de padrões, compressão de textos em linguagem natural; (ix) 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.

A linguagem de programação utilizada para apresentação do refinamento final dos algoritmos apresentados é a Pascal. A vantagem de se 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 C correspondente no Apêndice.

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.

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 Pascal 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 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 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. 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, 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 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 é 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 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á vêm acompanhados de um programa principal que permite executar imediatamente um pequeno teste.

Mudanças para a Segunda Edição

=-1 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.
• Foram introduzidos quatro capítulos novos:
• Capítulo 2: apresenta paradigmas de projeto de algoritmos.
• Capítulo 7: apresenta algoritmos em grafos. Os algoritmos utilizam operadores de um tipo abstrato de dados, o que permite implementar os algoritmos de forma independente da representação escolhida para o grafo.
• Capítulo 8: apresenta algoritmos eficientes para casamento exato e aproximado de cadeias de caracteres, bem como algoritmos para compressão de textos em linguagem natural.
• Capítulo 9: é dedicado ao estudo da teoria de complexidade, cobrindo problemas NP-completo, heurísticas e algoritmos aproximados.
• Nos capítulos que já existiam na primeira edição foram introduzidas novas seções sobre os seguintes tópicos:
• Ordenação parcial (Seção 4.1.7).
• Intercalação polifásica (Seção 4.2.4).
• Quicksort externo (Seção 4.2.5).
• hashing perfeito (Seção 5.5.4).
• Em várias seções que já existiam na primeira edição foram adicionados novos assuntos sobre os seguintes tópicos:
• Passagem de parâmetros (Seção 1.5).
• Notações $\theta$, $o$, $\omega$ (Seção 1.3.1).
• Novos operadores sobre filas de prioridades usando heaps (Seção 4.1.5).
• Novo algoritmo para obter a função hash universal (Seção 5.5).
• Adição de dezenas de novos problemas.
• Um apêndice contendo a solução de muitos dos problemas propostos ao final de cada capítulo.
• Praticamente todas as seções sofreram alterações de edição para corrigir, simplificar ou clarificar explicações, algoritmos, implementações em Pascal e C, e refazer figuras para fins de padronização.

Agradecimentos para a Primeira Edição

Uma versão inicial deste texto foi escrita para ser usada no curso Estruturas de Dados e Algoritmos da I Escola Brasileiro-Argentina de Informática em fevereiro de 1986, publicada pela Editora da Unicamp com o título Projeto de Algoritmos e Estruturas de Dados. Gostaria de agradecer a Carlos José Pereira de Lucena e Routo Terada por lembrarem do meu nome para participar da I Escola Brasileiro-Argentina de Informática, o que motivou o desenvolvimento da semente deste texto. Gostaria de agradecer a Cilio Rosa Ziviani, Cleber Hostalácio de Melo, José Monteiro da Mata, Lilia Tavares Mascarenhas, Luiz Carlos de Abreu Albuquerque, Regina Helena Bastos Cabral e Rosângela Fernandes pelas contribuições para a primeira versão do texto.

Muitos amigos e colegas me auxiliaram na elaboração deste livro. Agradeço a todos pela ajuda e pelas críticas construtivas. O Departamento de Ciência da Computação da Universidade Federal de Minas Gerais tem proporcionado um excelente ambiente de trabalho. Os meus alunos de extensão, graduação, especialização e pós-graduação, especialmente os alunos das disciplinas Técnicas de Programação, Algoritmos e Estruturas de Dados e Projeto e Análise de Algoritmos contribuíram significativamente.

Vários erros foram corrigidos como conseqüência da leitura cuidadosa de várias pessoas, em especial Alberto Henrique Frade Laender, Eduardo Fernandes Barbosa, José Nagib Cotrim Árabe, Márcio Luiz Bunte de Carvalho, Osvaldo Sérgio Farhat de Carvalho, Roberto Márcio Ferreira de Souza e Virgílio Augusto Fernandes Almeida, aos quais gostaria de registrar meus agradecimentos. Gostaria de agradecer a Cristina Duarte Murta pela leitura crítica de todo o texto, pelos testes dos programas Pascal e pela execução dos programas, que permitiu o estudo comparativo dos algoritmos de ordenação.

A versão C dos algoritmos existe graças ao trabalho paciente de tradução dos programas Pascal conduzido por Maurício Antônio de Castro Lima e Wagner Toledo Corrêa, realizado com o auxílio do programa p2c para tradução automática de programas em Pascal para programas em C, desenvolvido por Dave Gillespie, do California Institute of Technology, EUA. O livro foi formatado com LATEX, um conjunto de macros para o TEX. Um agradecimento todo especial para Márcio Luiz Bunte de Carvalho pela imensa ajuda durante todo o trabalho de formatação, incluindo a criação de ambientes especiais em LATEX para este texto, sendo que esta etapa contou também com a ajuda de Murilo Silva Monteiro. Um agradecimento muito especial para Maria, esposa e companheira, Patricia e Paula, nossas filhas.

Agradecimentos para a Segunda Edição

Agradeço aos amigos e colegas que contribuíram para a qualidade deste livro, em especial a Alberto Henrique Frade Laender, Antônio Alfredo Loureiro, Berthier Ribeiro-Neto, Dorgival Olavo Guedes Neto, Gonzalo Navarro, Jussara Marques de Almeida, Letícia Simonetti Garcia, Márcio Luiz Bunte de Carvalho, Mariza Bigonha, Renato Antonio Celso Ferreira, Roberto da Silva Bigonha e Virgilio Augusto Fernandes Almeida. 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 Wagner Meira Jr. pelas diversas sugestões e primeira leitura crítica de tudo que era produzido.

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 segunda 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. 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, 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 e Sérgio Augusto Ávila Maria.

Aos estudantes de pós-graduação que me auxiliaram na elaboração desta segunda edição 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: Bruno Augusto Vivas e Pôssas, pelo trabalho com as respostas de exercícios; 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; Davi de Castro Reis, pelo estudo comparativo dos algoritmos de ordenação parcial; Fabiano Cupertino Botelho, 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; 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, pela tradução dos programas para a linguagem C e trabalho com as respostas de exercícios.

Dentre as pessoas que gentilmente apontaram erros na primeira edição agradeço a André Gustavo dos Santos, Bruno Muller Júnior, Daniel Pablo Herschel, Daniel Walter Berns, 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, Luis Joaquin Vazquez, Marco Aurélio de Souza Mendes, Maria Gabriela Maidana e Pablo Velo.

Quero ainda citar o pessoal do Hotel Aquário, na praia de Ubu, Espírito Santo, onde estive por vários períodos de uma semana durante o ano de 2003 para trabalhar no livro, a quem agradeço pelo tratamento carinhoso recebido. Agradeço a Gabriela da Silva Conceição pela divulgação desta edição durante o Congresso da Sociedade Brasileira de Computação de 2003. Diversas versões preliminares do livro foram encadernadas por Alexandre Guimarães Dias, Geraldo Felício de Oliveira, Gustavo Moura de Oliveira e Orlando Rodrigues da Silva, a quem agradeço.

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 e da FINEP - Financiadora de Estudos e Projetos, mediante os seguintes projetos: PRONEX/FINEP/CNPq/SIAM - Sistemas de Informação em Ambientes de Computação Móvel, processo CNPq 00418.00/00; 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 Pioneira Thomson tem sido um prazer. Desde os primeiros contatos, a divulgação da segunda edição, a fase de revisão e de formatação do texto até a impressão final do livro, sempre houve um suporte leve, competente e profissional.

Nivio Ziviani
Belo Horizonte
Dezembro de 2003