(Parte 1 de 8)

Apostila Introdutoria de Algoritmos

Celina M. H. de Figueiredo Guilherme D. da Fonseca

Projeto financiado em parte pela FAPERJ em 2003

Conteudo

Capıtulo 1. Introducao 3 1.1. Os Problemas 3 1.2. Algoritmos e Paradigmas 4 1.3. Provas de Corretude 6 1.4. Complexidade de Tempo 8 1.5. Complexidade de Tempo de Pior Caso 9 1.6. Complexidade Assintotica 10 1.7. Analise de Complexidade 1 1.8. Resumo e Observacoes Finais 13 Exercıcios 13

Capıtulo 2. Estruturas de Dados 15 2.1. Estruturas Elementares 15 2.2. Grafos e Arvores 16 2.3. Subdivisoes do Plano e Poliedros 18 2.4. Lista de Prioridades - Heap Binario 19

2.5. Arvores Binarias de Busca 23 2.6. Resumo e Observacoes Finais 26 Exercıcios 26

Capıtulo 3. Busca Binaria 28 3.1. Busca em vetor 28 3.2. Busca em vetor ciclicamente ordenado 29 3.3. Ponto extremo de polıgono convexo 30 3.4. Funcao de vetor 32 3.5. Resumo e Observacoes Finais 34 Exercıcios 34

Capıtulo 4. Metodo Guloso 37 4.1. Fecho convexo: Algoritmo de Jarvis 37

4.2. Arvore geradora mınima: Algoritmo de Prim 38

4.3. Compactacao de dados: Arvores de Huffman 41 4.4. Compactacao de dados: LZSS 45 4.5. Resumo e Observacoes Finais 47 Exercıcios 48

Capıtulo 5. Divisao e Conquista 50 5.1. Envelope Superior 50 5.2. Par de Pontos Mais Proximos 52 5.3. Conjunto Independente de Peso Maximo em Arvores 54 5.4. Multiplicacao de Matrizes: Algoritmo de Strassen 5 5.5. Resumo e Observacoes Finais 57 Exercıcios 58

Capıtulo 6. Programacao Dinamica 60 6.1. Ordem de Multiplicacao de Matrizes 60

CONTEUDO 2

6.2. Todos os caminhos mais curtos 61 6.3. Resumo e Observacoes Finais 63 Exercıcios 63

Capıtulo 7. Simplificacao 65

7.1. Centro de Arvore 65 7.2. Selecao do k-esimo 6 7.3. Ponte do Fecho Convexo 69 7.4. Resumo e Observacoes Finais 70 Exercıcios 71

Capıtulo 8. Construcao Incremental 73 8.1. Arranjo de Retas 73 8.2. Fecho Convexo: Algoritmo de Graham 75 8.3. Programacao Linear com Duas Variaveis 7 8.4. Resumo e Observacoes Finais 80 Exercıcios 80

Capıtulo 9. Refinamento de Solucao 83 9.1. Fluxo em Redes 83 9.2. Resumo e Observacoes Finais 87 Exercıcios 87

Capıtulo 10. Problemas NP-Completos 89 10.1. Tempo Polinomial no Tamanho da Entrada 89 10.2. Problemas de Decisao e Reducoes 90 10.3. Certificados Polinomiais e a Classe NP 91 10.4. Os Problemas NP-Completos 92 10.5. Satisfabilidade 94 10.6. Clique e Conjunto Independente 95 10.7. Resumo e Observacoes Finais 97 Exercıcios 97

CAPıTULO 1

Introducao

Segundo o dicionario Aurelio, um algoritmo e um “processo de calculo, ou de resolucao de um grupo de problemas semelhantes, em que se estipulam, com generalidade e sem restricoes, regras formais para obtencao do resultado ou da solucao do problema”. Embora os algoritmos nao sejam necessariamente executados por computadores, este e o tipo de algoritmo que trataremos neste livro. O proposito deste livro e que o leitor nao so conheca e entenda diversos algoritmos para problemas variados, como tambem que seja capaz de desenvolver por si proprio algoritmos eficientes. As sessoes deste livro, em sua maioria, explicam cinco itens:

• Problema: a explicacao de que problema esta sendo resolvido na sessao. • Algoritmo: o metodo computacional para a resolucao do problema.

• Prova de corretude: a argumentacao de que o algoritmo apresentado resolve corretamente o problema. • Complexidade: o tempo que o algoritmo leva para resolver o problema.

• Analise de complexidade: o calculo deste tempo.

Nao necessariamente os itens sao explicados nesta ordem, ou de modo completamente separado. Muitas vezes, a prova de corretude e apresentada junto com a explicacao do algoritmo, justificando o modo como ele e desenvolvido e facilitando seu entendimento.

Nesta introducao, falamos destes cinco itens, fornecendo a base necessaria para o entendimento dos demais capıtulos do livro.

1.1. Os Problemas

Problemas precisam ser resolvidos constantemente, em todas as areas do conhecimento humano. Muitos problemas, principalmente de areas sociais, humanas ou artısticas, nao podem ser resolvidos por um computador. Porem, a maioria dos problemas das areas chamadas de ciencias exatas podem ser resolvidos de modo mais eficaz com o auxılio dos computadores. Este livro visa fornecer conhecimentos necessarios para programar um computador de modo a resolver problemas nao triviais eficientemente. Antes disso, devemos formalizar o que e um problema.

Todo o problema tem uma entrada, tambem chamada de instancia. Nos problemas que estudamos, existem infinitas entradas possıveis. A entrada pode ser bastante simples como no problema cuja entrada e um numero inteiro e desejamos descobrir se ele e primo. Em outros problemas, a entrada pode ser bastante complexa, tendo varios elementos relacionados, como grafos, vertices especiais dos grafos, particionamentos dos vertices etc.

Alem da entrada, todo problema tem uma saıda correspondente, que e a resposta do problema. Os algoritmos devem ser capazes de manipular a entrada para obter a saıda.

O tipo de problema mais elementar e o chamado problema de decisao. Neste tipo de problema, formula-se uma pergunta cuja resposta e sim ou nao. Vejamos alguns exemplos de problemas de decisao:

• Dado um numero inteiro, dizer se este numero e primo. • Dado um conjunto, dizer se um elemento x pertence a este conjunto.

• Dado um conjunto de segmentos no plano, dizer se dois segmentos se interceptam.

• Dado um grafo, dizer se o grafo possui ciclos.

Embora a resposta para um problema de decisao seja sim ou nao, e natural formular a chamada versao de construcao de alguns desses problemas. Em um problema de construcao, nao se deseja apenas saber se uma estrutura existe ou nao, mas construir a estrutura que satisfaca algumas propriedades. As versoes de construcao dos dois ultimos problemas de decisao apresentados e:

• Dado um conjunto de segmentos no plano, encontrar dois segmentos que se interceptam, se existirem. • Dado um grafo, exibir um ciclo deste grafo, se existir.

Em outros problemas de construcao, nao ha uma versao de decisao relacionada. Nos exemplos abaixo, nao ha duvida que a estrutura exista, a unica dificuldade e exibı-la:

• Dados dois numeros inteiros, calcular seu produto. • Dado um conjunto de numeros reais, ordenar seus elementos.

• Dado um conjunto de pontos nao colineares no plano, encontrar 3 pontos que formem um triangulo sem nenhum outro ponto em seu interior. • Dada uma arvore, encontrar seu centro.

Um tipo especial de problema de construcao e chamado de problema de otimizacao. Nestes problemas, nao queremos construir uma solucao qualquer, mas sim aquela que maximize ou minimize algum parametro. Vejamos alguns exemplos:

• Dados dois numeros inteiros, calcular seu maior divisor comum. • Dado um conjunto de numeros reais, encontrar o menor.

• Dado um conjunto de pontos nao colineares no plano, encontrar os 3 pontos que formem um triangulo sem nenhum outro ponto em seu interior que tenha perımetro mınimo. • Dado um grafo, encontrar sua arvore geradora mınima.

A diferenca entre esses problemas e os problemas de construcao e sutil, e nem sempre precisamente definida. Por exemplo, o problema de construcao onde se deseja encontrar o centro de uma arvore e um problema de otimizacao, pois o centro de uma arvore e o conjunto dos vertices cuja distancia ao vertice mais distante e mınima. Ainda assim, e util diferenciar estes tipos basicos de problemas, pois algumas tecnicas que apresentaremos, se mostram especialmente eficientes para determinado tipo de problema.

Existem outros tipos de problemas que nao resolveremos neste livro. Os problemas de enumeracao sao um exemplo. Nestes problemas deseja-se listar todas as estruturas que satisfazem uma propriedade. Associado a todo o problema de enumeracao, existe um problema de contagem. No problema de contagem, nao se esta interessado em listar todas as solucoes, mas apenas descobrir quantas solucoes distintas existem. Alguns exemplos destes dois tipos de problema sao:

• Dado um numero inteiro, listar todos os seus fatores (primos ou nao). • Dado um conjunto, contar o numero de sub-conjuntos com determinado numero de elementos.

• Dado um conjunto de segmentos no plano, calcular o numero de intersecoes entre os segmentos. • Dado um grafo, exibir todos os seus ciclos.

1.2. Algoritmos e Paradigmas

Um algoritmo e uma maneira sistematica de resolver um problema. Algoritmos podem ser usados diretamente por seres humanos para diversas tarefas. Ao fazer uma conta de dividir sem usar calculadora, por exemplo, estamos executando um algoritmo. Porem, os algoritmos ganharam importancia muito maior com os computadores. Varios problemas cuja solucao era praticamente inviavel sem um computador passaram a poder ser resolvidos em poucos segundos. Mas tudo depende de um bom algoritmo para resolver o problema.

Ao recebermos um problema, como fazemos para desenvolver um bom algoritmo para resolvelo? Nao ha resposta simples para esta pergunta. Todo este livro visa preparar o leitor para este desenvolvimento. Sem duvida, conhecer bons algoritmos para muitos problemas ajuda bastante no desenvolvimento de novos algoritmos. Por isso, praticamente todos os livros sobre o assunto apresentam varios problemas, junto com suas solucoes algoritmicas. Geralmente, os problemas sao organizados de acordo com a area do conhecimento a que pertencem (teoria dos grafos, geometria computacional, sequencias, algebra...). Neste livro fazemos diferente.

Embora nao exista uma receita de bolo para projetar um algoritmo, existem algumas tecnicas que frequentemente conduzem a “bons” algoritmos. Este livro esta organizado segundo estas tecnicas, chamadas de paradigmas. Vejamos, de modo simplificado, dois exemplos de paradigmas: “construcao incremental” e “divisao e conquista”.

• Construcao incremental: Resolve-se o problema para uma entrada com apenas um elemento. A partir daı, acrescenta-se, um a um, novos elementos e atualiza-se a solucao.

• Divisao e conquista: Quando a entrada tem apenas um elemento, resolve-se o problema diretamente. Quando e maior, divide-se a entrada em duas entradas de aproximadamente o mesmo tamanho, chamadas sub-problemas. Em seguida, resolvem-se os dois sub-problemas usando o mesmo metodo e combinam-se as duas solucoes em uma solucao para o problema maior.

Vamos exemplificar estes dois paradigmas no problema de ordenacao:

Problema 1. Dado um conjunto de numeros reais, ordene o conjunto do menor para o maior elemento.

Neste problema, a entrada consiste de um conjunto de numeros reais e a saıda e uma lista desses numeros, ordenada do menor para o maior. Nos dois paradigmas, precisamos saber resolver o caso em que a entrada possui apenas um elemento. Isto e facil. Neste caso, a lista ordenada contem apenas o proprio elemento.

No paradigma de construcao incremental, precisamos descobrir como acrescentar um novo elemento x em uma lista ja ordenada. Para isto, podemos percorrer os elementos a partir do menor ate encontrar um elemento que seja maior que x. Entao, deslocamos todos os elementos maiores que x de uma posicao, e colocamos o elemento x na posicao que foi liberada. Este algoritmo e chamado de ordenacao por insercao. No paradigma de divisao e conquista, precisamos descobrir como combinar duas listas or- denadas L1 e L2 em uma unica lista L. Podemos comecar comparando o menor elemento de

L1 com o menor elemento de L2. O menor elemento dentre esses dois e certamente o menor elemento de L. Colocamos entao este elemento na lista L e removemos o elemento de sua lista de origem, L1 ou L2. Seguimos sempre comparando apenas o menor elemento de L1 com o menor elemento de L2 e colocando o menor elemento dentre esses dois no final da lista L, ate que uma das listas L1 ou L2 se torne vazia. Quando uma das listas se tornar vazia, a outra lista e copiada integralmente para o final da lista L. Este algoritmo e chamado de mergesort.

As vezes, explicar um algoritmo em paragrafos de texto pode ser confuso. Por isto, normalmente apresentamos tambem o chamado pseudo-codigo do algoritmo. Este pseudo-codigo e uma maneira estruturada de descrever o algoritmo e, de certa forma, se parece com sua implementacao em uma linguagem de programacao. O pseudo-codigo do algoritmo de ordenacao por insercao esta na figura 1.1. Ha varias maneiras de escrever o pseudo-codigo para um mesmo algoritmo. Vejamos dois pseudo codigos diferentes para o algoritmo de divisao e conquista que acabamos de apresentar, escritos nas figuras 1.2 e 1.3.

O primeiro pseudo-codigo (figura 1.2) e mais curto e muito mais facil de entender que o segundo (figura 1.3). Por outro lado, o segundo pseudo-codigo se parece mais com uma implementacao real do algoritmo. Mas note que, mesmo o segundo pseudo-codigo ainda e bastante diferente de uma implementacao real. Afinal, nao nos preocupamos em definir os tipos de variaveis ou fazer as alocacoes de memoria. Neste livro, quase sempre optaremos por um pseudo-codigo no estilo do primeiro, pois consideramos o entendimento do algoritmo mais importante que um pseudo-codigo “pronto para implementar”. Embora a implementacao do primeiro pseudo-codigo nao seja imediata, qualquer bom programador deve ser capaz de compreende-lo e implementa-lo em um tempo relativamente pequeno.

1.3. PROVAS DE CORRETUDE 6

Entrada: S: Conjunto de numeros reais a serem ordenados armazenado em um vetor. Saıda: L: Conjunto S ordenado do menor para o maior.

Ordenar(S)

Para j de j ate i

Troque valores de L[j] e x Retorne L

Figura 1.1. Pseudo-codigo do algoritmo de ordenacao por insercao.

Entrada: S: Conjunto de numeros reais a serem ordenados armazenado em um vetor. Saıda: L: Conjunto S ordenado do menor para o maior.

Ordenar(S)

Coloque L1[1] no final da lista L

Coloque L2[1] no final da lista L Remova L2[1] de L2

Coloque elementos de L1 no final de L, na mesma ordem Senao

Coloque elementos de L2 no final de L, na mesma ordem Retorne L

Figura 1.2. Primeiro pseudo-codigo do algoritmo mergesort.

1.3. Provas de Corretude

Em alguns algoritmos, como os algoritmos de ordenacao que acabamos de ver, e bastante claro que o algoritmo resolve corretamente o problema. Porem, em muitos outros, nao e tao obvio que a resposta encontrada realmente esta correta. De fato, a diferenca entre um algoritmo que funciona corretamente e outro que fornece respostas erradas pode ser bastante sutil. Por isso, e essencial provarmos que o algoritmo funciona corretamente, ou seja, faz aquilo que se propoe a fazer.

1.3. PROVAS DE CORRETUDE 7

Entrada: S: Conjunto de numeros reais a serem ordenados armazenado em um vetor. n: Tamanho de S. Saıda:: L: Conjunto S ordenado do menor para o maior.

Retorne S Para i de 1 ate bn/2c

Se i1 6= bn/2c Para i de i ate n

Para i de i ate n

Figura 1.3. Segundo pseudo-codigo do algoritmo mergesort.

Um exemplo que demonstra como a diferenca entre um algoritmo funcionar e nao funcionar pode ser sutil e o problema do troco. Neste problema, deseja-se formar uma quantia x em dinheiro, usando o mınimo de moedas possıvel. Provar que um algoritmo para este problema esta correto significa provar que a quantia fornecida pelo algoritmo e x e que o numero de moedas usado e realmente mınimo.

(Parte 1 de 8)

Comentários