Apostila Introdutória de Algoritmos, Manuais, Projetos, Pesquisas de Algoritmos

Baixe Apostila Introdutória de Algoritmos e outras Manuais, Projetos, Pesquisas em PDF para Algoritmos, somente na Docsity! Apostila Introdutória de Algoritmos Celina M. H. de Figueiredo Guilherme D. da Fonseca Projeto financiado em parte pela FAPERJ em 2003 Conteúdo Caṕıtulo 1. Introdução 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 Assintótica 10 1.7. Análise de Complexidade 11 1.8. Resumo e Observações Finais 13 Exerćıcios 13 Caṕıtulo 2. Estruturas de Dados 15 2.1. Estruturas Elementares 15 2.2. Grafos e Árvores 16 2.3. Subdivisões do Plano e Poliedros 18 2.4. Lista de Prioridades - Heap Binário 19 2.5. Árvores Binárias de Busca 23 2.6. Resumo e Observações Finais 26 Exerćıcios 26 Caṕıtulo 3. Busca Binária 28 3.1. Busca em vetor 28 3.2. Busca em vetor ciclicamente ordenado 29 3.3. Ponto extremo de poĺıgono convexo 30 3.4. Função de vetor 32 3.5. Resumo e Observações Finais 34 Exerćıcios 34 Caṕıtulo 4. Método Guloso 37 4.1. Fecho convexo: Algoritmo de Jarvis 37 4.2. Árvore geradora mı́nima: Algoritmo de Prim 38 4.3. Compactação de dados: Árvores de Huffman 41 4.4. Compactação de dados: LZSS 45 4.5. Resumo e Observações Finais 47 Exerćıcios 48 Caṕıtulo 5. Divisão e Conquista 50 5.1. Envelope Superior 50 5.2. Par de Pontos Mais Próximos 52 5.3. Conjunto Independente de Peso Máximo em Árvores 54 5.4. Multiplicação de Matrizes: Algoritmo de Strassen 55 5.5. Resumo e Observações Finais 57 Exerćıcios 58 Caṕıtulo 6. Programação Dinâmica 60 6.1. Ordem de Multiplicação de Matrizes 60 1 1.2. ALGORITMOS E PARADIGMAS 4 não se deseja apenas saber se uma estrutura existe ou não, mas construir a estrutura que satisfaça algumas propriedades. As versões de construção dos dois últimos problemas de decisão apresentados é: • 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 construção, não há uma versão de decisão relacionada. Nos exem- plos abaixo, não há dúvida que a estrutura exista, a única dificuldade é exib́ı-la: • Dados dois números inteiros, calcular seu produto. • Dado um conjunto de números reais, ordenar seus elementos. • Dado um conjunto de pontos não colineares no plano, encontrar 3 pontos que formem um triângulo sem nenhum outro ponto em seu interior. • Dada uma árvore, encontrar seu centro. Um tipo especial de problema de construção é chamado de problema de otimização. Nestes problemas, não queremos construir uma solução qualquer, mas sim aquela que maximize ou minimize algum parâmetro. Vejamos alguns exemplos: • Dados dois números inteiros, calcular seu maior divisor comum. • Dado um conjunto de números reais, encontrar o menor. • Dado um conjunto de pontos não colineares no plano, encontrar os 3 pontos que formem um triângulo sem nenhum outro ponto em seu interior que tenha peŕımetro mı́nimo. • Dado um grafo, encontrar sua árvore geradora mı́nima. A diferença entre esses problemas e os problemas de construção é sutil, e nem sempre preci- samente definida. Por exemplo, o problema de construção onde se deseja encontrar o centro de uma árvore é um problema de otimização, pois o centro de uma árvore é o conjunto dos vértices cuja distância ao vértice mais distante é mı́nima. Ainda assim, é útil diferenciar estes tipos básicos de problemas, pois algumas técnicas que apresentaremos, se mostram especialmente eficientes para determinado tipo de problema. Existem outros tipos de problemas que não resolveremos neste livro. Os problemas de enu- meração são um exemplo. Nestes problemas deseja-se listar todas as estruturas que satisfazem uma propriedade. Associado a todo o problema de enumeração, existe um problema de conta- gem. No problema de contagem, não se está interessado em listar todas as soluções, mas apenas descobrir quantas soluções distintas existem. Alguns exemplos destes dois tipos de problema são: • Dado um número inteiro, listar todos os seus fatores (primos ou não). • Dado um conjunto, contar o número de sub-conjuntos com determinado número de elementos. • Dado um conjunto de segmentos no plano, calcular o número de interseções entre os segmentos. • Dado um grafo, exibir todos os seus ciclos. 1.2. Algoritmos e Paradigmas Um algoritmo é uma maneira sistemática 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. Porém, os algoritmos ganharam importância muito maior com os computadores. Vários problemas cuja solução era praticamente inviável 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 resolvê- lo? Não há resposta simples para esta pergunta. Todo este livro visa preparar o leitor para este desenvolvimento. Sem dúvida, conhecer bons algoritmos para muitos problemas ajuda bastante no desenvolvimento de novos algoritmos. Por isso, praticamente todos os livros sobre o assunto 1.2. ALGORITMOS E PARADIGMAS 5 apresentam vários problemas, junto com suas soluções algoritmicas. Geralmente, os problemas são organizados de acordo com a área do conhecimento a que pertencem (teoria dos grafos, geometria computacional, seqüências, álgebra...). Neste livro fazemos diferente. Embora não exista uma receita de bolo para projetar um algoritmo, existem algumas técnicas que freqüentemente conduzem a “bons” algoritmos. Este livro está organizado segundo estas técnicas, chamadas de paradigmas. Vejamos, de modo simplificado, dois exemplos de paradig- mas: “construção incremental” e “divisão e conquista”. • Construção incremental: Resolve-se o problema para uma entrada com apenas um ele- mento. A partir dáı, acrescenta-se, um a um, novos elementos e atualiza-se a solução. • Divisão e conquista: Quando a entrada tem apenas um elemento, resolve-se o problema diretamente. Quando é maior, divide-se a entrada em duas entradas de aproximada- mente o mesmo tamanho, chamadas sub-problemas. Em seguida, resolvem-se os dois sub-problemas usando o mesmo método e combinam-se as duas soluções em uma solução para o problema maior. Vamos exemplificar estes dois paradigmas no problema de ordenação: Problema 1. Dado um conjunto de números reais, ordene o conjunto do menor para o maior elemento. Neste problema, a entrada consiste de um conjunto de números reais e a sáıda é uma lista desses números, ordenada do menor para o maior. Nos dois paradigmas, precisamos saber resolver o caso em que a entrada possui apenas um elemento. Isto é fácil. Neste caso, a lista ordenada contém apenas o próprio elemento. No paradigma de construção incremental, precisamos descobrir como acrescentar um novo elemento x em uma lista já ordenada. Para isto, podemos percorrer os elementos a partir do menor até encontrar um elemento que seja maior que x. Então, deslocamos todos os elementos maiores que x de uma posição, e colocamos o elemento x na posição que foi liberada. Este algoritmo é chamado de ordenação por inserção. No paradigma de divisão e conquista, precisamos descobrir como combinar duas listas or- denadas L1 e L2 em uma única lista L. Podemos começar comparando o menor elemento de L1 com o menor elemento de L2. O menor elemento dentre esses dois é certamente o menor elemento de L. Colocamos então 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, até que uma das listas L1 ou L2 se torne vazia. Quando uma das listas se tornar vazia, a outra lista é copiada integralmente para o final da lista L. Este algoritmo é chamado de mergesort. Às vezes, explicar um algoritmo em parágrafos de texto pode ser confuso. Por isto, nor- malmente apresentamos também o chamado pseudo-código do algoritmo. Este pseudo-código é uma maneira estruturada de descrever o algoritmo e, de certa forma, se parece com sua im- plementação em uma linguagem de programação. O pseudo-código do algoritmo de ordenação por inserção está na figura 1.1. Há várias maneiras de escrever o pseudo-código para um mesmo algoritmo. Vejamos dois pseudo códigos diferentes para o algoritmo de divisão e conquista que acabamos de apresentar, escritos nas figuras 1.2 e 1.3. O primeiro pseudo-código (figura 1.2) é mais curto e muito mais fácil de entender que o segundo (figura 1.3). Por outro lado, o segundo pseudo-código se parece mais com uma imple- mentação real do algoritmo. Mas note que, mesmo o segundo pseudo-código ainda é bastante di- ferente de uma implementação real. Afinal, não nos preocupamos em definir os tipos de variáveis ou fazer as alocações de memória. Neste livro, quase sempre optaremos por um pseudo-código no estilo do primeiro, pois consideramos o entendimento do algoritmo mais importante que um pseudo-código “pronto para implementar”. Embora a implementação do primeiro pseudo-código não seja imediata, qualquer bom programador deve ser capaz de compreendê-lo e implementá-lo em um tempo relativamente pequeno. 1.3. PROVAS DE CORRETUDE 6 Entrada: S: Conjunto de números reais a serem ordenados armazenado em um vetor. Sáıda: L: Conjunto S ordenado do menor para o maior. Ordenar(S) Para i de 1 até |S| x← S[i] j ← 1 Enquanto j < i e L[j] < x j ← j + 1 Para j de j até i Troque valores de L[j] e x Retorne L Figura 1.1. Pseudo-código do algoritmo de ordenação por inserção. Entrada: S: Conjunto de números reais a serem ordenados armazenado em um vetor. Sáıda: L: Conjunto S ordenado do menor para o maior. Ordenar(S) Se |S| = 1 Retorne S[1] Divida S em S1 e S2 aproximadamente de mesmo tamanho L1 ← Ordenar(S1) L2 ← Ordenar(S2) Enquanto |L1| 6= 0 e |L2| 6= 0 Se L1[1] 6 L2[1] Coloque L1[1] no final da lista L Remova L1[1] de L1 Senão Coloque L2[1] no final da lista L Remova L2[1] de L2 Se |L1| 6= 0 Coloque elementos de L1 no final de L, na mesma ordem Senão Coloque elementos de L2 no final de L, na mesma ordem Retorne L Figura 1.2. Primeiro pseudo-código do algoritmo mergesort. 1.3. Provas de Corretude Em alguns algoritmos, como os algoritmos de ordenação que acabamos de ver, é bastante claro que o algoritmo resolve corretamente o problema. Porém, em muitos outros, não é tão óbvio que a resposta encontrada realmente está correta. De fato, a diferença entre um algoritmo que funciona corretamente e outro que fornece respostas erradas pode ser bastante sutil. Por isso, é essencial provarmos que o algoritmo funciona corretamente, ou seja, faz aquilo que se propõe a fazer. 1.5. COMPLEXIDADE DE TEMPO DE PIOR CASO 9 flutuante extremamente rápidas pode se beneficiar de algoritmos que usem fortemente ponto flutuante, enquanto outra máquina pode se beneficiar de algoritmos que façam menos operações de ponto flutuante. Em máquinas com um cache de memória pequeno, um algoritmo que acesse os dados com maior localidade pode ser prefeŕıvel, enquanto em máquinas com um cache maior, ou sem nenhum cache, outro algoritmo pode ser prefeŕıvel. • Dependência da implementação: Digamos que você crie um algoritmo a e resolva escrever um artigo argumentando que seu algoritmo é mais rápido que o algoritmo b. Como criador do algoritmo a, você provavelmente conhece muito bem este algoritmo e é capaz de implementá-lo de modo extremamente eficiente. A sua implementação do algoritmo a será provavelmente muito melhor que a sua implementação do algoritmo b. Deste modo, a comparação é bastante injusta. • Incomparabilidade: Digamos que alguém apresente o tempo que uma implementação de um determinado algoritmo levou em uma determinada máquina com uma entrada espećıfica e outra pessoa apresente o tempo que outro algoritmo para o mesmo problema levou com outra entrada em outra máquina. É completamente imposśıvel comparar estes dois resultados para determinar qual algoritmo será mais rápido no seu caso. • Alto custo: Devido a impossibilidade de comparar execuções dos algoritmos com en- tradas diferentes ou em máquinas diferentes, é necessário implementar e testar diversos algoritmos para determinar qual é mais rápido no seu caso espećıfico. O tempo e o custo dessas tarefas podem ser bastante elevados. A seguir, vamos introduzir a complexidade de tempo assintótica de pior caso, que usamos para avaliar a eficiência dos algoritmos. Esta análise tem se mostrado extremamente útil por fornecer uma expressão simples que permite comparar facilmente dois algoritmos diferentes para o mesmo problema, independente da máquina, implementação ou da entrada. 1.5. Complexidade de Tempo de Pior Caso Primeiro vamos explicar como fazemos a análise independer da entrada. Para isto, consi- deramos sempre a pior entrada posśıvel, ou seja, a que leva mais tempo para ser processada. Como estamos lidando com entradas ilimitadamente grandes, precisamos fixar o tamanho da en- trada, ou alguma outra propriedade dela. Por enquanto, não vamos considerar a dependência da máquina ou da implementação. Vamos considerar que estamos falando sempre de uma máquina previamente definida e de uma implementação espećıfica. Podemos falar, no problema de ordenação, da lista de n elementos que leva mais tempo para ser ordenada por um determinado algoritmo (com relação a todas as listas com n elementos). No problema de, dado um conjunto de n pontos no plano, determinar o par de pontos mais próximos, podemos expressar a complexidade de tempo em função do número n de pontos da entrada. No problema de, dado um conjunto de poĺıgonos, dizer se dois poĺıgonos se interceptam, não é razoável expressar a complexidade de tempo em função do número de poĺıgonos da entrada. Afinal, um poĺıgono pode ter qualquer número de vértices. Uma entrada com apenas 2 poĺıgonos pode ser extremamente complexa se estes poĺıgonos tiverem muitos vértices. Já uma entrada com vários triângulos pode ser bem mais simples. Por isso, neste problema, é razoável expressar a complexidade de tempo em função do número total de vértices dos poĺıgonos. Em todos estes casos, queremos definir uma função T (n) que representa o tempo máximo que o algoritmo pode levar em uma entrada com n elementos. Às vezes, podemos expressar o tempo em função de vários parâmetros da entrada, simultaneamente. Quando a entrada é um grafo, por exemplo, podemos expressar a complexidade de tempo em função do número n de vértices e do número m de arestas do grafo. Assim, desejamos obter uma função T (n,m). Por enquanto, porém, vamos desconsiderar este caso de várias variáveis. Há outras alternativas para a complexidade de pior caso, mas, na maioria das situações, a complexidade de pior caso é considerada a melhor opção. Uma alternativa é a chamada complexidade de caso médio. Esta opção é motivada pela idéia que, se um algoritmo é rápido 1.6. COMPLEXIDADE ASSINTÓTICA 10 para a esmagadora maioria das entradas, então pode ser aceitável que este algoritmo seja lento para algumas poucas entradas. Há algumas desvantagens da complexidade de caso médio. A primeira delas é que, na complexidade de caso médio, é necessário ter uma distribuição de probabilidade para as entradas. Outra desvantagem é que o cálculo da complexidade de caso médio pode ser extremamente complicado. Não adianta ter uma medida de complexidade que ninguém consegue calcular. 1.6. Complexidade Assintótica Neste ponto, já definimos que a nossa função T (n) corresponde ao tempo que uma de- terminada implementação do algoritmo leva em uma determinada máquina para a entrada de tamanho n mais demorada. Vamos agora nos livrar da dependência da máquina espećıfica e dos detalhes de implementação. Para isto, lançamos mão da hierarquia assintótica, que explicamos nos próximos parágrafos. Dizemos que f(n) 4 g(n) se existem constantes positivas c e n0 tais que f(n) 6 cg(n), para todo n > n0. Analogamente, dizemos que f(n) < g(n) se existem constantes positivas c e n0 tais que f(n) > cg(n), para todo n > n0. Se f(n) 4 g(n) e f(n) < g(n), dizemos que f(n) ³ g(n). Se f(n) 4 g(n), mas não é verdade que f(n) ³ g(n), então dizemos que f(n) ≺ g(n). Analogamente, se f(n) < g(n), mas não é verdade que f(n) ³ g(n), então dizemos que f(n) Â g(n). Vejamos alguns exemplos com polinômios: 3n2 + 2n + 5 4 n2 3n2 + 2n + 5 ³ n2 3n2 + 2n + 5 ≺ n3 1 ≺ n ≺ n2 ≺ n3 ≺ · · · Com algumas funções mais complexas, podemos escrever, por exemplo: 1 ≺ lg lg n ≺ lg n ≺ lg2 n ≺ n1/3 ≺ √n ≺ n/ lg n ≺ n n ≺ n lg n ≺ n2 ≺ n3 ≺ 2n ≺ en ≺ n! ≺ nn Esta notação assintótica que acabamos de apresentar, embora correta, é raramente utilizada em computação. No seu lugar, utiliza-se a comumente chamada notação O. Denota-se por O(g(n)) uma função f(n) qualquer que satisfaça f(n) 4 g(n). Denota-se por Ω(g(n)) uma função f(n) qualquer que satisfaça f(n) < g(n). Denota-se por Θ(g(n)) uma função f(n) qualquer que satisfaça f(n) ³ g(n). Denota-se por o(g(n)) uma função f(n) qualquer que satisfaça f(n) ≺ g(n). Denota-se por ω(g(n)) uma função f(n) qualquer que satisfaça f(n) Â g(n). Esta equivalência está resumida a seguir: f(n) = O(g(n)) ≡ f(n) 4 g(n) f(n) = Ω(g(n)) ≡ f(n) < g(n) f(n) = Θ(g(n)) ≡ f(n) ³ g(n) f(n) = o(g(n)) ≡ f(n) ≺ g(n) f(n) = ω(g(n)) ≡ f(n) Â g(n) Esta notação tem alguns aspectos extremamente práticos e outros extremamente confusos. Um ponto forte da notação O é que ela pode ser usada diretamente dentro de equações. Podemos dizer, por exemplo que 2n4 + 3n3 + 4n2 + 5n + 6 = 2n4 + 3n3 + O(n2). Um ponto negativo é que a notação O anula a reflexividade da igualdade. Podemos dizer que n2 = O(n3), mas não podemos dizer que n3 = O(n2). Uma propriedade importante da notação O é que ela despreza constantes aditivas e multi- plicativas. Sejam c1 e c2 constantes, então c1f(n) + c2 = Θ(f(n)). Desta propriedade seguem algumas simplificações como lg nk = Θ(lg n) e logk n = Θ(lg n), para qualquer constante k. Sempre que usamos um logaritmo dentro da notação O, optamos pela função lg n, o logaritmo 1.7. ANÁLISE DE COMPLEXIDADE 11 de n na base 2. Afinal, como logk n = Θ(lg n), qualquer logaritmo é equivalente nesse caso e o logaritmo na base 2 é o mais natural em computação. Agora podemos terminar de definir o método que usamos para medir o tempo gasto por um algoritmo, independente da máquina. Certamente, uma máquina mais rápida está limitada a executar qualquer programa um número de vezes mais rápido que outra máquina. Assim, se expressarmos a função T (n) usando notação O, não é necessário depender de uma máquina espećıfica. Com isto, também não dependemos de muitos detalhes de implementação, embora alguns detalhes de implementação possam alterar a complexidade assintótica. Esta avaliação do algoritmo é chamada de complexidade de tempo assintótica de pior caso, mas muitas vezes nos referimos a ela apenas como complexidade de tempo, ou mesmo complexidade. Como o próprio nome diz, a complexidade de tempo assintótica avalia o tempo gasto pelo algoritmo para entradas cujo tamanho tende a infinito. Se um algoritmo a tem complexidade de tempo O(f(n)) e outro algoritmo b tem complexidade de tempo O(g(n)), com f(n) ≺ g(n), então, certamente, a partir de algum valor de n o algoritmo a se torna mais rápido que o algoritmo b. Porém, pode ser verdade que o algoritmo a seja mais lento que o algoritmo b para entradas “pequenas”. 1.7. Análise de Complexidade Vamos agora mostrar algumas técnicas usadas para analisar a complexidade de um algoritmo através de dois exemplos simples: os dois algoritmos de ordenação vistos anteriormente. Primeiro vamos analisar a ordenação por inserção, cujo pseudo-código está na figura 1.1. Temos 3 loops neste algoritmo. O loop mais externo é repetido exatamente n vezes, onde n é o número de elementos da entrada. O número exato de repetições dos loops mais internos depende da entrada, porém é possivel notar que o primeiro loop realiza no máximo i−1 repetições e o segundo loop realiza no máximo i repetições. De fato, o número de repetições dos dois loops internos somados é exatamente i, mas não precisamos entrar nesse ńıvel de detalhes para obtermos um limite superior para a complexidade. O que importa é que os loops internos realizam O(i) repetições e, dentro deles, só há operações cujo tempo independe do valor de n. Assim, a complexidade de tempo do algoritmo é n∑ i=1 O(i) = n∑ i=1 O(n) = nO(n) = O(n2). Neste cálculo, substituimos O(i) por O(n), pois i 6 n. Claro que podeŕıamos estar perdendo precisão nesta substituição. Se quisermos fazer os cálculos justos, não podemos usar este truque e também precisamos garantir que há caso em que os loops internos realizam Ω(i) repetições, o que é verdade já que os dois loops somados realizam exatamente i repetições para qualquer entrada. Como 1 + 2 + . . . + n = n(n− 1)/2 = Θ(n2), temos n∑ i=1 Θ(i) = Θ(n2). Deste modo, finalizamos a análise do algoritmo de ordenação por inserção. Outra análise que podemos fazer é a chamada complexidade de espaço, ou seja, a quantidade de memória necessária para a execução do algoritmo. No caso da ordenação por inserção, a complexidade de memória é claramente Θ(n), pois só temos 2 vetores com n elementos, além de um número constante de variáveis cujo tamanho independe de n. A análise do algoritmo de ordenação por divisão e conquista é mais complicada. Este algo- ritmo divide a entrada em duas partes aproximadamente iguais, executa-se recursivamente para essas duas partes e depois combina as duas soluções. A fase de combinação das duas soluções leva tempo linear no tamanho da entrada. Com isso, podemos dizer que T (n) = { 2T (n/2) + Θ(n) para n > 1 O(1) para n 6 1 EXERCÍCIOS 14 1.5) Considere a recorrência T (n) = T (n/2) + 1. A solução correta desta recorrência satisfaz T (n) = Θ(lg n). Ache o erro na demos- tração abaixo, que prova que T (n) = O(lg lg n): Vamos supor, para obter uma prova por indução, que T (i) = O(lg lg i) para i 6 n. Vamos calcular T (n + 1). Temos: T (n + 1) = T (n/2) + 1 = O(lg lg(n/2)) + 1. Como lg lg(n/2) = O(lg lg(n + 1)) temos T (n + 1) = O(lg lg(n + 1)) + 1 = O(lg lg(n + 1)), finalizando a indução. 1.6) Prove que a recorrência T (n) = T (n/2) + 1 satisfaz T (n) = O(lg n). *1.7) Prove que a recorrência abaixo satisfaz f(n) = n, considerando o caso base f(1) = 1: f(n) = n−2∑ i=0 ( n− 2 i ) 1 2n−3 f(i + 1). CAṔıTULO 2 Estruturas de Dados Este caṕıtulo não visa introduzir o leitor ao tópico de estruturas de dados, mas apenas revisar este tópico, estabelecer a notação usada nos demais caṕıtulos e servir como referência sucinta. Recomendamos a quem não tiver estudado o assunto que consulte um livro espećıfico. Uma estrutura de dados é normalmente vista como uma caixa preta capaz de realizar um conjunto de operações, que incluem o armazenamento de dados. Neste caṕıtulo, examinamos o que acontece dentro dessas caixas pretas, analisando a complexidade de tempo das operações. 2.1. Estruturas Elementares A estrutura de dados mais elementar é uma variável. Variáveis podem ser de diversos tipos básicos, como: • booleana ou binária: Armazena apenas dois valores, como 0 ou 1, ou possivelmente verdadeiro ou falso. • caractere: Armazena uma letra ou śımbolo. • inteira: Armazena um número inteiro. • real : Armazena um número real. • ponteiro: Aponta para uma posição da memória da máquina. Há outros tipos básicos de variáveis como, por exemplo, uma variável que só armazene inteiros positivos. Além disso, em uma máquina real, uma variável inteira está limitada a um intervalo dos números inteiros, possuindo valores mińımo e máximo armazenáveis. Geralmente, ao longo deste livro, consideramos a capacidade de armazenamento de variáveis inteiras ilimitada. Também consideramos que variáveis reais realmente armazenam um número real, e não um arredondamento com ponto flutuante como acontece na prática. A combinação de um conjunto de variáveis é chamada de estrutura. Uma estrutura para pontos no plano pode conter duas variáveis reais, uma para armazenar a coordenada x e outra para armazenar a coordenada y do ponto. Nos referimos a estes atributos de um ponto p como p.x e p.y, respectivamente. Uma seqüência de variáveis de um mesmo tipo, ocupando posições sucessivas da memória, é chamada de vetor. Os elementos de um vetor são referenciados através de um ı́ndice inteiro entre colchetes. O primeiro elemento de um vetor v é referenciado como v[1], e assim por diante. Um vetor possui uma capacidade associada a ele, que representa o número máximo de elementos que o vetor pode armazenar, ou seja, o maior valor de n para o qual v[n] é uma posição válida. Freqüentemente, falamos em vetores ćıclicos. Em um vetor ćıclico com capacidade n, quando ocorre um acesso a posição v[i] com i < 1 ou i > n, este acesso é convertido a um acesso no intervalo válido por meio de adições ou subtrações do valor n. Por exemplo, em um vetor com capacidade 5, é equivalente falarmos em v[2], v[7], v[22] ou v[−3]. Vetores ćıclicos podem ser implementados usando a operação de resto da divisão, por isso, são também chamados de vetores com ı́ndice módulo n. A utilização mais freqüente de vetores é para armazenar listas. Uma lista é um conjunto de elementos listados em determinada ordem. Embora os elementos de uma lista, sempre possuam uma ordem associada a eles, não necessariamente esta ordem possui um significado. Por exemplo, o vetor v = (5, 1, 3, 9, 7) é uma representação válida para o conjunto dos 5 primeiros números ı́mpares. Também é posśıvel forçarmos os elementos do vetor a estar armazenados segundo uma ordem definida. O vetor ordenado crescentemente que armazena os 5 primeiros números ı́mpares é v = (1, 3, 5, 7, 9). 15 2.2. GRAFOS E ÁRVORES 16 Quando vetores são usados como listas, nos referimos ao número de elementos armazenados no vetor v como |v|. O parâmetro |v| pode ser armazenado pelo programa como uma variável inteira separada ou ser definido implicitamente através de um śımbolo especial para marcar o final do vetor. Nos parágrafos a seguir, nos concentraremos na primeira alternativa. Vejamos a complexidade de tempo de algumas operações com listas armazenadas em vetor. Para inserirmos um elemento no final da lista, basta fazermos |v| ← |v|+1 e v[|v|]← x, onde x é o novo elemento. Portanto, essa operação leva tempo Θ(1). Para removermos o último elemento da lista, basta fazermos |v| ← |v|−1, também levando tempo Θ(1). Para buscarmos um elemento podemos precisar percorrer a lista inteira, portanto a busca de um elemento leva no pior caso tempo Θ(|v|). Para removermos um elemento qualquer da lista, é necessário deslocarmos todos os elementos seguintes, levando tempo Θ(|v|). Para inserirmos um elemento em uma posição espećıfica da lista, a situação é equivalente, levando tempo Θ(|v|). Existem dois tipos especiais de listas, que são freqüentemente armazenados em vetores: pilhas e filas. Pilhas e filas possuem apenas duas operações básicas, inserir e remover. A operação de remoção, além de remover o elemento, retorna seu valor. Uma pilha é uma lista onde os elementos são sempre inseridos e removidos no final da lista, chamado de topo da pilha. Uma fila é uma lista onde os elementos são inseridos no final da lista, chamado de fim da fila, e removidos do ińıcio da lista, chamado de ińıcio da fila. Em uma pilha armazenada em um vetor v, inserir(v, x) corresponde a |v| ← |v| + 1 e v[|v|]← x. A função remover(v) corresponde a |v| ← |v| − 1 e retorne v[|v|+ 1]. Para armazenarmos uma fila em um vetor precisamos utilizar um vetor ćıclico. Guardamos dois ı́ndices módulo n, um para indicar o ińıcio e outro para indicar o final da fila. Para inserir um elemento na fila, coloca-se este elemento no final, incrementando o ı́ndice correspondente. Para remover um elemento, basta incrementar o ı́ndice correspondente ao ińıcio da fila. Outra maneira de armazenar listas é usando listas encadeadas. Em uma lista encadeada, cada elemento aponta para o elemento seguinte na lista. Deste modo, é posśıvel realizar operações de inserir e remover em qualquer posição da lista em tempo Θ(1). Outra vantagem das listas encadeadas é que não é necessário definir previamente uma capacidade para a lista, como acon- tecia no vetor. Porém, as listas encadeadas possuem algumas desvantagens. Uma delas é que as constantes multiplicativas da complexidade de tempo ocultas pela notação O são maiores que nos vetores. Outra desvantagem é que não é posśıvel acessar em tempo Θ(1) qualquer elemento da lista, como acontecia no vetor. Com isto, não é posśıvel realizar os métodos de busca binária que serão vistos no caṕıtulo 3. 2.2. Grafos e Árvores Um grafo é uma estrutura combinatória extremamente útil para a modelagem de diversos problemas. Um grafo G é definido como dois conjuntos, V (G) e E(G). Os elementos do con- junto V (G) são chamados de vértices do grafo. Os elementos do conjunto E(G) são pares não ordenados de vértices de V (G), sendo chamados de arestas. Grafos são muito mais fáceis de visualisar quando representados graficamente. Por exemplo, o grafo com V (G) = {a, b, c, d, e} e E(G) = {(a, b), (a, c), (a, e), (b, d), (c, e), (d, e)} está representado na figura 2.1(a). Há outras maneiras de representar este mesmo grafo, como mostra a figura 2.1(b). Outra estrutura útil é chamada de grafo direcionado, ou digrafo (pronuncia-se di-GRA-fo, pois não há acento como na palavra d́ıgrafo). Em um grafo direcionado, o conjunto de arestas é formado por pares ordenados. Deste modo, as arestas possuem direção. Quando representamos um digrafo graficamente, desenhamos as arestas como setas, como mostra a figura 2.1(c). Há duas maneiras muito usadas para representar um grafo ou digrafo no computador. A primeira delas é chamada de matriz de adjacências. A matriz de adjacências de um grafo G com n vértices é uma matriz M binária n × n onde mi,j = 1 se (vi, vj) ∈ E(G) e mi,j = 0 caso contrário. A matriz de adjacências dos grafo G com V (G) = {a, b, c, d, e} e E(G) = {(a, b), (a, c), (a, e), (b, d), (c, e), (d, e)} é: 2.4. LISTA DE PRIORIDADES - HEAP BINÁRIO 19 face externa vértices faces arestas Figura 2.3. Divisão do plano e seus elementos. Consideramos apenas divisões do plano sem buracos, ou seja, subdiviões do plano em que se pode chegar de qualquer vértice a qualquer vértice caminhando apenas pelas arestas. Não é dif́ıcil tratar o caso com buracos, bastando armazenar os buracos em estruturas separadas, ligadas as faces onde os buracos ocorrem. Existem várias estruturas eficientes para armazenar subdivisões do plano. A estrutura que apresentamos aqui chama-se DCEL (doubly connected edge list - lista de arestas duplamente encadeada). O elemento principal da DCEL são as arestas, mais precisamente as semi-arestas. Um vértice tem como atributos um par de coordenadas x, y e um ponteiro para apenas uma semi- aresta que parte dele. Uma face contém apenas um ponteiro para uma semi-aresta adjacente a ela. Uma semi-aresta, por sua vez, possui diversos atributos: seu vértice de origem, sua semi- aresta gêmea, a face adjacente a ela, e duas outras semi-arestas, chamadas de próxima e anterior. As semi-arestas sempre percorrem as faces internas no sentido anti-horário e semi-arestas gêmeas sempre possuem sentidos opostos, comportando-se ao contrário da direção dos carros em vias de mão dupla. Deste modo, a face adjacente a uma semi-aresta está sempre à sua esquerda. A próxima semi-aresta de uma aresta e é a semi-aresta mais a esquerda (com relação a e) dentre as semi-arestas que têm como origem o vértice destino de e. Devido a natureza extremamente geométrica da estrutura DCEL, é mais fácil compreendê-la examinando o exemplo da figura 2.4. Os algoritmos para implementar operações básicas nessa estrutura são relativamente simples. É um excelente exerćıcio escrever o pseudo-código de alguns destes algoritmos. Apresentamos aqui apenas o pseudo-código da operação que listas todos os vértices adjacentes a um vértice v, no sentido horário, na figura 2.5. Uma estrutura DCEL também pode ser usada para representar o contorno de poliedros no espaço tridimensional. 2.4. Lista de Prioridades - Heap Binário Listas de prioridades são estruturas de dados bastante usadas em vários algoritmos. As principais operações suportadas por uma lista de prioridades são as seguintes: • Criar(S): retorna uma lista de prioridades contendo os elementos do conjunto S. • Inserir(H, e): insere elemento e, com prioridade e.prioridade, em H. • Máximo(H): retorna o elemento de maior prioridade de H. • ExtrairMáximo(H): retorna o elemento de maior prioridade de H, removendo-o de H. Também são permitidas operações para alterar a prioridade de um elemento, ou remover um elemento da lista. Porém, para usar essas operações é importante armazenar um ponteiro para o elemento dentro da lista de prioridades, pois a estrutura não permite que a busca de um elemento na lista seja realizada eficientemente. Alternativamente, uma lista de prioridades pode retornar o elemento mı́nimo e não o ele- mento máximo. Nesta sessão, trataremos de uma lista de prioridades que retorna o elemento máximo, mas o outro caso é análogo. 2.4. LISTA DE PRIORIDADES - HEAP BINÁRIO 20 e1 e´1 e2 e´2 e3 e´3 e4 e´4 e5 e´5 e6 e´6 e7 e´7 f1 f2 f3 v1 v2 v3 v4 v5 v6 (a) vertice x y semiaresta v1 0 2 e′1 v2 0 1 e3 v3 1 1 e′6 v4 0.5 0.5 e′5 v5 0 0 e7 v6 1 0 e′7 (b) face semiaresta f1 e1 f2 e3 f3 e ′ 3 (c) semiaresta origem gemea face proxima anterior e1 v2 e ′ 1 f1 e ′ 2 e4 e′1 v1 e1 f2 e3 e2 e2 v3 e ′ 2 f2 e ′ 1 e3 e′2 v1 e2 f1 e ′ 6 e1 e3 v2 e ′ 3 f2 e2 e ′ 1 e′3 v3 e3 f3 e ′ 4 e6 e4 v5 e ′ 4 f1 e1 e ′ 7 e′4 v2 e4 f3 e7 e ′ 3 e5 v6 e ′ 5 f3 e ′ 5 e7 e′5 v4 e5 f3 e6 e5 e6 v6 e ′ 6 f3 e ′ 3 e ′ 5 e′6 v3 e6 f1 e ′ 7 e ′ 2 (d) Figura 2.4. (a) Divisão do plano. (b) Estruturas dos vértices correspondentes. (c) Estruturas das faces correspondentes. (d) Estruturas das semi-arestas corres- pondentes. Para construirmos uma lista de prioridades, usamos uma árvore binária chamada heap. Cada vértice da árvore é associado a um elemento armazenado. Esta árvore deve satisfazer as seguintes propriedades: Ordenação de heap: A prioridade de todo vértice é maior que a prioridade de seus filhos. Balanceamento: Todos os vértices que não possuem exatamente 2 filhos estão nos dois últimos ńıveis da árvore. Um exemplo de heap está representado na figura 2.6(a). A propriedade de ordenação de heap serve para que o elemento máximo possa ser encontrado rapidamente. Em uma árvore com 2.4. LISTA DE PRIORIDADES - HEAP BINÁRIO 21 VertAdjVertHor(vertice v) e← inicio← v.semiaresta Repita Listar e.gemea.origem e← e.gemea.proxima Enquanto e 6= inicio Figura 2.5. Algoritmo que lista todos os vértices adjacentes a um vértice v, no sentido horário. ordenação de heap, o elemento máximo está sempre na raiz. A propriedade de balanceamento serve para garantir que a altura da árvore seja logaritmica, de modo que inserções e remoções sejam realizadas eficientemente, como veremos a seguir. 12 810 29 6 7 53 1 (a) 12 811 29 10 7 53 1 6 (b) Figura 2.6. (a) Exemplo de heap binário. (b) Inserção do elemento 11 no heap da figura (a). A primeira operação que apresentamos é alterar a prioridade de um elemento do heap. Em seguida, usamos esta operação para construir as demais. Vamos dividir a operação de alterar prioridade em duas operações: aumentar prioridade e reduzir prioridade. Para aumentar a prioridade de um elemento, primeiro trocamos o valor desta prioridade, possivelmente violando a ordenação de heap. Em seguida, seguimos trocando a posição do elemento que teve a prioridade aumentada com seu pai, até que a ordenação de heap seja reestabelecida, como ilustra a figura 2.7. 12 810 29 6 7 53 1 12 810 29 6 7 113 1 12 810 211 6 7 93 1 12 811 210 6 7 93 1 Figura 2.7. Aumento da prioridade de um elemento de 5 para 11. Para reduzir a prioridade de um elemento, primeiro trocamos o valor desta prioridade, possivelmente violando a ordenação de heap. Em seguida, seguimos trocando a posição do elemento que teve a prioridade reduzida com seu filho de maior prioridade, até que a ordenação de heap seja reestabelecida, como ilustra a figura 2.8. A complexidade de tempo dessas operações é proporcional à altura da árvore, sendo, por- tanto, Θ(lg n), onde n é o número de elementos armazenados no heap. Para inserirmos um elemento, colocamos uma nova folha na árvore, filha do elemento de ńıvel mais alto que ainda não possuir dois filhos. Esta folha tem, inicialmente, prioridade −∞. Então, aumentamos a prioridade desta folha para o valor desejado, com o procedimento descrito anteriormente. 2.5. ÁRVORES BINÁRIAS DE BUSCA 24 Observações: Neste pseudo-código, consideramos que os elementos são apenas prioridades, sem possuir outros atributos. h: Vetor que armazena o heap. n: Número de elementos de h. p: Prioridade de um elemento. i: Posição de um elemento de h. S: Vetor com n elementos. AlterarPrioridade(h,n,i,p) Se p > h[i] AumentarPrioridade(h,i,p) Senão ReduzirPrioridade(h,n,i,p) AumentarPrioridade(h,i,p) h[i]← p Enquanto i > 1 e h[bi/2c] < h[i] Troca h[i] e h[bi/2c] ReduzirPrioridade(h,n,i,p) h[i]← p Enquanto 2i 6 n Se (h[2i + 1] > n ou h[2i] > h[2i + 1]) e h[2i] > h[i] Troca h[i] e h[2i] Senão se h[2i + 1] 6 n e h[2i + 1] > h[i] Troca h[i] e h[2i + 1] Criar(S,n) h← S Para i de n até 1 ReduzirPrioridade(h,n,i,h[i]) Retorne h Inserir(h,n,p) n← n + 1 AumentarPrioridade(h,n,p) Remover(h,n,i) n← n− 1 AlterarPrioridade(h,n,i,h[n + 1]) Figura 2.11. Pseudo-código das operações de um heap binário em vetor. menores que e.chave e as chaves de todos os elementos na subárvore direita de e são maiores que e.chave. Dois exemplos de árvores binárias de busca estão representados na figura 2.12. Para buscar uma chave x em uma árvore binária de busca, começamos comparando x com a chave da raiz r. Se x.chave = r.chave, já encontramos o elemento desejado e podemos parar a busca. Caso x.chave < r.chave, sabemos que, se existir elemento com chave x, este elemento está na subárvore esquerda de r. Nesse caso, chamamos o procedimento recursivamente para buscar x na subárvore esquerda de r. O caso x.chave > r.chave é análogo. No lugar de fazermos a busca recursivamente na subárvore esquerda de r, o fazemos na subárvore direita de r. Este procedimento segue até encontrarmos o elemento ou tentarmos fazer a busca em uma árvore vazia. Neste último caso, constatamos que a chave procurada não está armazenada na árvore. Este procedimento está exemplificado na figura 2.13(a). 2.5. ÁRVORES BINÁRIAS DE BUSCA 25 31 4510 409 22 47 5 3 12 25 23 30 46 (a) macaco camelo pato búfalo foca gansoanta avestruz tamanduá zebra paca (b) Figura 2.12. (a) Árvore binária de busca com chaves inteiras. (b) Árvore binária de busca com chaves de cadeias de caracteres. 31 4510 409 22 47 5 3 12 25 23 30 46 25<31 25>10 25>22 (a) 31 4510 409 22 47 5 3 12 25 23 30 46 11<31 11>10 11<22 11 11<12 (b) 30 4510 409 22 47 5 3 12 25 23 46 (c) Figura 2.13. (a) Busca de elemento com chave 25 na árvore da figura 2.12(a). (b) Inserção de elemento com chave 11 na árvore da figura 2.12(a). (c) Remoção do elemento de chave 31 na árvore da figura 2.12(a). Para inserirmos um elemento, começamos fazendo uma busca de sua chave. Caso a chave já esteja na árvore, não devemos inseŕı-la, pois todos os elementos devem ter chaves distintas. Caso não esteja, nossa busca terminará em uma subárvore vazia. Podemos colocar o elemento que desejamos inserir nesta posição. Este procedimento está exemplificado na figura 2.13(b). Para removermos um elemento, também começamos fazendo uma busca de sua chave. Caso o elemento seja uma folha, basta removê-lo. Caso tenha apenas um filho, também pode-se remover o elemento desejado diretamente, subindo o filho em um ńıvel. Caso tenha dois filhos, uma alternativa simples é buscar o maior elemento de sua subárvore esquerda, que ou é uma folha, ou possui apenas um filho. Remove-se diretamente este elemento, movendo-o para a posição do elemento que realmente desejamos remover. Este procedimento está exemplificado na figura 2.13(c). A complexidade de tempo dessas operações depende da altura da árvore. Infelizmente, estes métodos de inserção e remoção não garantem que a altura da árvore seja logaŕıtmica. Para um pior caso, imagine que os elementos são inseridos em ordem crescente. Nesse caso, a árvore obtida não passa de uma lista encadeada, pois nenhum elemento possui filho esquerdo. Existem várias maneiras de garantir que a altura de uma árvore binária de busca com n elementos seja O(lg n). Todas elas se baseiam no conceito de rotações, normalmente realizadas nas operações de inserção e remoção. Uma rotação é uma alteração local na topologia da árvore que preserva a propriedade de árvore binária de busca. As duas rotações principais estão apresentadas graficamente na figura 2.14. Alguns exemplos de árvores binárias de busca balanceadas, ou seja, com altura O(lg n) são árvores rubro-negras, árvores AVL, árvores de difusão (splay trees, complexidade amortizada) e treaps (estrutura randomizada). Nenhuma destas estruturas é muito simples e todas estão bem documentadas em livros de estruturas de dados, por isso não entramos em detalhes aqui. EXERCÍCIOS 26 d b b d rotação direita rotação esquerdaA C E A C E Figura 2.14. Rotações direita e esquerda em árvores binárias de busca. 2.6. Resumo e Observações Finais Neste caṕıtulo, fizemos um resumo de diversas estruturas de dados. Partimos das estrutu- ras elementares, chamadas variáveis. Agrupamentos de variáveis são chamados de estruturas. Vetores são uma seqüência de variáveis do mesmo tipo. Uma lista armazena uma seqüência de elementos. Vetores servem para armazenar listas, que também podem ser armazenadas através de listas encadeadas. Dois tipos especiais de listas são chamados de filas e pilhas. Em uma fila, os elementos são sempre inseridos em um extremo e removidos do extremo oposto da lista. Em uma pilha, os elementos são sempre inseridos e removidos no mesmo extremo. Grafos são uma estrutura combinatória muito estudada e com diversas aplicações. Um grafo consiste em um conjunto de vértices e um conjunto de arestas, que são pares de vértices. Grafos podem ser armazenados como matrizes de adjacência ou listas de adjcências, sendo que a última é normalmente prefeŕıvel para grafos com poucas arestas. Uma árvore é um tipo especial de grafo que não possui ciclos. Uma árvore enraizada é uma árvore como um vértice especial chamado de raiz, e serve para representar hierarquias. Uma árvore binária é uma árvore enraizada em que cada vértice possui dois filhos diferentes, chamados de filho direito e filho esquerdo. Uma subdivisão do plano por segmentos pode ser representada eficientemente com uma estrutura DCEL. Esta estrutura tem como elemento principal as semi-arestas. Listas de prioridades são estruturas de dados não triviais extremamente úteis para o de- senvolvimento de algoritmos eficientes. Uma lista de prioridades armazena um conjunto de elementos, sujeito a inserções e remoções, permitindo que o elemento máximo seja determinado rapidamente. A estrutura mais usada para armazenar listas de prioridades é o heap binário, que é uma árvore balanceada onde todo vértice é maior que seus filhos. Uma árvore binária de busca permite que elementos sejam inseridos, removidos, ou encon- trados a partir de uma chave. Para garantir que as operações sejam realizadas eficientemente, entretanto, é preciso usar árvores binárias de busca especiais. Estas árvores, como AVL, rubro- negra etc, não são apresentadas aqui e usam rotações para garantir que a altura da árvore seja logaritmica. Exerćıcios 2.1) Compare vantagens e desvantagens em armazenar uma lista em vetor ou como lista encadeada. 2.2) Seja hn a menor altura posśıvel para uma árvore binária com n vértices. Prove que hn = Θ(lg n). 2.3) Escreva o pseudo-códigos que lista todos os vértices de uma face, armazenada em estru- tura DCEL, no sentido horário. 2.4) Explique porque o método descrito a seguir não deve ser usado para remover um elemento de um heap binário. Inicia-se o procedimento, esvaziando-se o vértice correspondente ao elemento que desejamos remover. Em seguida, determina-se seu maior filho, e move-se 3.2. BUSCA EM VETOR CICLICAMENTE ORDENADO 29 Entrada: v: Vetor de reais em ordem crescente. inicio: Primeiro elemento da partição do vetor. Inicialmente 1. fim: Último elemento da partição do vetor. Inicialmente o tamanho do vetor. x: Valor que está sendo procurado. Sáıda: Índice i tal que v[i] = x, se existir. BuscaBinária(v, inicio, fim, x) Se inicio < fim Retorne “x /∈ v” Se inicio = fim Se v[inicio] = x Retorne inicio Senão Retorne “x /∈ v” meio← b(inicio + fim)/2c Se v[meio] > x Retorne BuscaBinária(v, inicio, meio− 1, x) Se v[meio] < x Retorne BuscaBinária(v, meio + 1, fim, x) Retorne meio Figura 3.1. Solução do Problema 2 O caso base é quando o vetor tem apenas 1 elemento ou nenhum elemento. Caso o vetor não tenha nenhum elemento, claramente não tem elemento com valor x. Caso tenha apenas 1 elemento o algoritmo resolve o problema comparando este elemento com x. ¤ Resta agora analisarmos a complexidade de tempo do algoritmo. Faremos uma prova geral que servirá de base para todos os algoritmos baseados em busca binária. A idéia é que, como a cada passo descartamos uma fração constante dos elementos, a complexidade de tempo é logaŕıtmica. Vamos chamar de T (n) o tempo gasto pelo algoritmo para um vetor de tamanho n. Em um tempo constante, o algoritmo descarta uma fração α < 1 constante (normalmente α = 1/2) dos elementos. Temos então T (n) = T (αn) + 1. Podemos assumir que o tempo constante de cada passo seja 1, pois a notação O ignora constantes multiplicativas. Vamos provar que T (n) = Θ(lg n), supondo que T (αn) = Θ(lg n). Usando indução temos T (n) = T (αn) + 1 = c lg(αn) + 1 = c lg n + c lg α + 1. Se fizermos c = −1/ lg α temos T (n) = c lg n e finalizamos a indução. Com isto temos: Teorema 3.2. O algoritmo que descrevemos tem complexidade de tempo Θ(lg n), onde n é o número de elementos do vetor. 3.2. Busca em vetor ciclicamente ordenado Muitas vezes, falaremos de ı́ndices de vetores módulo n. Com isto queremos dizer que, se v = (v1, . . . , vn) e nos referimos a um elemento vi fora do intervalo, ou seja, i < 1 ou i > n, então estamos nos referindo ao elemento do intervalo obtido somando ou subtraindo n a i quantas 3.3. PONTO EXTREMO DE POLÍGONO CONVEXO 30 vezes for necessário. Por exemplo, em um vetor v = (v1, . . . , v5), quando dizemos v−5, v0 ou v10 estamos nos referindo ao elemento v5. Seja v = (v1, . . . , vn) um vetor de reais com ı́ndices módulo n. Dizemos que v está ciclica- mente ordenado se o número de elementos vi tais que vi 6 vi+1 para i de 1 a n é igual a n− 1. Por exemplo, o vetor (5, 8, 9, 10, 1, 3) está ciclicamente ordenado. Problema 3. Dados um vetor v ciclicamente ordenado, contendo elementos reais e um número real x, determinar a posição i tal que v[i] = x, se existir. Para resolvermos este problema devemos examinar duas posições ao invés de uma. É útil pensarmos no vetor como um ćırculo. Examinamos os elementos vi e vj com i < j de modo que o número de elementos entre vi e vj pelos dois lados do ćırculo seja aproximadamente igual. Caso vi 6 vj , sabemos que se vi 6 x < vj então x só pode estar nas posições de i até j − 1 e se x < vi ou x > vj então x só pode estar nas posições menores que i ou maiores ou iguais a j. Caso vi > vj , sabemos que se x > vi ou x < vj então x está nas posições de i até j − 1 e se vj 6 x < vi então x está nas posições menores ou iguais a j ou maiores que i. Teorema 3.3. O algoritmo que acabamos de descrever resolve corretamente o problema 3. Demonstração. Buscando um elemento com valor x, examinamos dois elementos vi e vj do vetor v = (v1, . . . , vn), com i < j. Caso vi 6 vj o vetor formado pelos elementos de vi à vj está ordenado e x é candidato a estar nas posições de ı́ndice i até j− 1 se e só se vi 6 x < vj . O procedimento é chamado recursivamente para a partição do vetor candidata a conter elemento de valor x. Caso vi > vj o vetor formado pelos elementos após vj e anteriores a vi está ordenado e o argumento é análogo. O caso base é quando o vetor tem apenas 1 elemento ou nenhum elemento. Caso o vetor não tenha nenhum elemento, claramente não tem elemento com valor x. Caso tenha apenas 1 elemento o algoritmo resolve o problema comparando este elemento com x. ¤ Para facilitar a implementação podemos sempre pegar como pi o ponto com o menor ı́ndice i dentro do intervalo, como está ilustrado na figura 3.2. Assim evitamos que a partição do vetor seja descont́ınua na memória. A complexidade de tempo deste algoritmo é Θ(lg n), pelo mesmo prinćıpio do algoritmo da sessão 3.1. 3.3. Ponto extremo de poĺıgono convexo A técnica de busca binária tem várias aplicações em geometria computacional, especialmente quando a entrada é um poĺıgono convexo. Um ponto no plano é representado por um par de coordenadas reais. Representamos um poĺıgono de n vértices como um vetor v = (v1, . . . , vn) contendo n pontos no plano. A posição v1 contém um dos vértices (qualquer um), v2 o próximo vértice no sentido anti-horário e assim por diante. Denotamos por ª (p1, p2, p3) o ângulo positivo p̂1p2p3 medido no sentido anti-horário. Devido a natureza ćıclica dos poĺıgonos, trabalharemos com ı́ndices módulo n, ou seja, se o ı́ndice do vetor for maior do que n ou menor do que 1, devemos somar ou subtrair n até que o ı́ndice esteja neste intervalo. Um poĺıgono é convexo se, para i de 1 à n, o ângulo ª(vi−1, vi, vi+1) for maior que 180◦ (figura 3.3(a)). Note que quando i = 1, ao dizermos i− 1 estamos nos referindo a posição n. Quando i = n, ao dizermos i + 1 estamos nos referindo a posição 1. Existem várias definições equivalentes para poĺıgono convexo. A maioria caracteriza a in- terseção do poĺıgono com uma reta. Uma definição deste tipo é: um poĺıgono é convexo se sua interseção com uma reta ou é nula ou é um ponto ou um segmento de reta. Esta definição con- sidera o poĺıgono cheio, ou seja, o interior do poĺıgono também é considerado parte do poĺıgono. Esta última definição não nos fornece diretamente nenhum algoritmo para verificar se, dado um poĺıgono, ele é convexo. Já a definição do parágrafo anterior nos fornece um algoritmo linear para verificar convexidade. Basta examinarmos todos os ângulos. Dizemos que um vértice vi de um poĺıgono P = (v1, . . . , vn) é extremo na direção de um vetor d se d · vi > d · vj para todo j 6= i. Denotamos por u · v o produto escalar uxvx + uyvy. 3.3. PONTO EXTREMO DE POLÍGONO CONVEXO 31 Entrada: v: Vetor de reais ciclicamente ordenado. inicio: Primeiro elemento da partição do vetor. Inicialmente 1. fim: Último elemento da partição do vetor. Inicialmente o tamanho do vetor. x: Valor que está sendo procurado. Sáıda: Índice i tal que v[i] = x, se existir. BuscaBináriaĆıclica(v, inicio, fim, x) Se inicio < fim Retorne “x /∈ v” Se inicio = fim Se v[inicio] = x Retorne inicio Senão Retorne “x /∈ v” meio← b(inicio + fim + 1)/2c Se v[inicio] 6 v[meio] Se x > v[inicio] e x < v[meio] Retorne BuscaBináriaĆıclica(v, inicio, meio− 1, x) Senão Retorne BuscaBináriaĆıclica(v, meio, fim, x) Senão Se x > v[meio] e x < v[inicio] Retorne BuscaBináriaĆıclica(v, meio, fim, x) Senão Retorne BuscaBináriaĆıclica(v, inicio, meio− 1, x) Figura 3.2. Solução do Problema 3 Uma outra definição mais geométrica é que vi é extremo na direção d se a reta perpendicular a d que passa por vi divide o plano em dois semiplanos tais que todos os pontos do poĺıgono que não estão sobre a reta estão em um mesmo semiplano e o ponto vi + d está no outro semiplano (figura 3.3(b)). Agora podemos definir o problema: Problema 4. Dados um poĺıgono convexo P e um vetor d determinar o vértice de P extremo na direção d. Vamos começar pegando dois vértices quaisquer vi e vj do poĺıgono P = (v1, . . . , vn), com i < j. Podemos usar este par de vértices para decompor P em dois poĺıgonos conve- xos P1 = (vi, vi+1, . . . , vj) e P2 = (v1, v2, . . . , vi, vj , vj+1, . . . , vn). Para usarmos o prinćıpio de busca binária precisamos descobrir qual desses dois poĺıgonos contém o ponto extremo. Primeiro comparamos d ·vi com d ·vj . Vamos considerar inicialmente que d ·vi > d ·vj e depois trataremos do outro caso. Comparamos então d ·vi com d ·vi+1. Caso d ·vi > d ·vi+1 o poĺıgono que contém o ponto extremo é P1 = (vi, vi+1, . . . , vj). Para provarmos este fato vamos considerar a reta r perpendicular a d que passa por vi e os dois semiplanos S e S̄ definidos por ela. Chamamos de S o semiplano que contém vi+1. Os pontos que estão em S não são candidatos a serem extremos, pois o produto escalar de qualquer um desses pontos com d é menor que d · vi. Todos os pontos de P2 estão em S, pois caso contrário r interceptaria o interior de P2 e também tangenciaria P2 no vértice vi. Caso d · vi < d · vi+1 o poĺıgono que contém o ponto extremo é P2, usando o mesmo argumento. Caso d · vi < d · vj , devemos comparar d · vj com d · vj+1. Se d · vj > d · vj+1, EXERCÍCIOS 34 de tempo de pior caso da função BuscaBinária é Θ(lg n), a complexidade total é O(n lg n). Podemos dizer que a complexidade de tempo é Θ(n lg n) pois a busca binária pode levar o tempo de pior caso em todas as chamadas. Em toda esta análise consideramos que a função f pode ser computada em tempo O(1). Com isto temos: Teorema 3.6. O algoritmo da figura 3.5 tem complexidade de tempo de pior caso Θ(n lg n). Note que, caso o vetor de entrada v não estivesse ordenado, podeŕıamos ordená-lo em tempo Θ(n lg n) antes de iniciarmos as buscas binárias. Esta ordenação não alteraria a complexidade assintótica do procedimento completo, que permaneceria Θ(n lg n). Em muitos problemas em que a entrada não está ordenada da maneira que desejamos, vale a pena iniciarmos ordenando a entrada convenientemente. 3.5. Resumo e Observações Finais A técnica de busca binária fornece algoritmos extremamente eficientes para diversos proble- mas. A idéia central é, a cada passo, descartarmos metade (ou alguma outra fração constante) dos elementos da entrada, examinando apenas um número constante de elementos. Isto é posśıvel em casos onde a entrada é fornecida segundo alguma ordenação conveniente. Para buscarmos um elemento em um vetor ordenado, examinamos o elemento central do vetor, e assim podemos determinar qual a metade candidata a conter o elemento procurado. Em vetores ciclicamente ordenados, podemos proceder de forma semelhante, dividindo o vetor. No caso de poĺıgonos convexos, usamos sempre o fato de que, ao unirmos dois vértices quaisquer de um poĺıgono convexo, os dois novos poĺıgonos obtidos também são convexos. Graças a isso, podemos usar a técnica de busca binária para resolver problemas como o ponto extremo de um poĺıgono convexo em uma dada direção. Em muitos problemas, a entrada não é fornecida ordenada. Pode valer a pena ordená-la, para que se possa usar a técnica de busca binária. Devido a alta performance prática dos algoritmos de ordenação e sua complexidade de Θ(n lg n), pode-se pensar em um vetor ordenado como uma estrutura de dados extremamente simples e eficiente. Um caso que não foi estudado aqui, é quando o número de elementos que podem conter a solução é desconhecido ou muito maior que a posição onde se espera encontrar a solução. Uma alternativa eficiente nesses casos é examinar os elementos segundo uma progressão geométrica. Chamamos este procedimento de busca ilimitada. Por exemplo, examinamos inicialmente o elemento v4, em seguida v8, v16 e assim por diante, até descobrirmos que o elemento que procu- ramos tem ı́ndice menor do que o examinado. Procedemos então com a busca binária tradicional. Nesse caso, o algoritmo é senśıvel a sáıda, tendo complexidade de tempo em função do ı́ndice do elemento procurado no vetor. Pode-se usar esta técnica, por exemplo, para encontrar o máximo de uma função. Uma alternativa a busca binária é usarmos interpolação. Imagine que desejamos encontrar a palavra “bola” em um dicionário de 1000 páginas. Certamente não vamos começar examinando a página 500, mas sim uma página próxima do ińıcio, como 100. A busca por interpolação pode ser extremamente eficiente quando o vetor em que a busca é realizada tem estrutura previśıvel, porém, há casos em que a busca por interpolação tem complexidade de tempo linear, e não logaŕıtmica como a busca binária, sendo muito ineficiente. Uma aplicação geral de busca binária é quando desejamos encontrar o maior valor para o qual uma determinada propriedade é válida. Muitas vezes, é mais simples escrever um algoritmo que teste se a propriedade vale para um valor dado. Podemos então fazer uma busca ilimitada para encontrar o menor valor para o qual a propriedade falha. Exerćıcios 3.1) Escreva o pseudo-código do algoritmo de busca binária em vetor sem usar recursão. EXERCÍCIOS 35 3.2) Ache o erro na demostração abaixo, que prova que a complexidade da busca binária é O(lg lg n): Seja T (n) o tempo do algoritmo de busca binária em um vetor com n elementos, no pior caso. Temos: T (n) = T (d(n− 1)/2e) + O(1) T (n) = O(1), n 6 1 Vamos supor, para obter uma prova por indução, que T (i) = O(lg lg n) para i 6 n. Vamos calcular T (n+1). Temos: T (n+1) = T (dn/2e)+O(1) = O(lg lg(dn/2e))+O(1). Como lg lg(dn/2e) ¹ lg lg(n+1) temos T (n+1) = O(lg lg(n+1))+O(1) = O(lg lg(n+1)), finalizando a indução. 3.3) Escreva um algoritmo eficiente que receba como entrada um vetor v = (v1, . . . , vn) de números inteiros e responda se existe vi = i. Analise a complexidade de tempo do seu algoritmo e prove que ele funciona. 3.4) Projete um algoritmo que recebe como entrada um poĺıgono convexo P armazenado em um vetor e dois pontos u e v. O algoritmo deve retornar o vértice pi de P que minimiza ª (u, v, pi). A complexidade de tempo deve ser O(lg |P |). Prove que o seu algoritmo funciona. 3.5) Projete um algoritmo que recebe como entrada um poĺıgono convexo P armazenado em um vetor e um ponto u. O algoritmo deve responder se u está ou não no interior de P em tempo O(lg |P |). 3.6) Dados dois vetores de números reais em ordem crescente, escreva dois algoritmos, um deles baseado em busca binária e o outro não, para dizer se os dois vetores possuem algum elemento em comum. Analise a complexidade dos algoritmos em função de m e n, os tamanhos dos dois vetores. Quando é mais vantajoso usar cada um dos algoritmos? 3.7) Dados uma função real f(x) e um valor α, o problema de achar uma raiz da função consiste em encontrar um valor de x tal que |f(x)| < α. Escreva um algoritmo que resolve o problema usando busca binária caso f(0) < 0 e f(1) > 0. Escreva um algoritmo mais completo que resolva o problema para qualquer função que possua somente uma raiz, ou seja, existe apenas um valor de x tal que f(x) = 0. Nesse último caso, deve-se usar busca binária ilimitada em duas direções simultaneamente, e a complexidade de tempo deve depender do módulo do valor da raiz. 3.8) Neste exerćıcio, o algoritmo que você deve projetar não é para ser usado por um com- putador. Embora a técnica de busca binária não apareça neste problema, o exerćıcio trabalha análise de complexidade e conceitos de busca ilimitada. Imagine que você foi colocado em um corredor com infinitas portas para ambos os lados (pelo menos você não avista final). Você sabe que existe uma porta que leva a sáıda, mas não parece fácil encontrá-la, pois todas as portas que você abriu até então são fraudes, levando a uma parede de tijolos. Escreva um algoritmo que defina como você deve caminhar para examinar as portas, de modo a andar, no total, apenas O(d) metros, onde d é a distância entre sua posição inicial e a porta que leva a sáıda. *3.9) Projete um algoritmo com complexidade de tempo sub-linear (o(n)) ou prove que isto é imposśıvel. A entrada é um poĺıgono convexo P com n vértices armazenado em um vetor e um ponto u. (a) O algoritmo deve retornar o vértice de P mais próximo de u. (b) O algoritmo deve retornar o ponto do interior ou bordo de P mais próximo de u. EXERCÍCIOS 36 *3.10) Modifique o procedimento BuscaBinária substituindo a linha “meio← b(inicio + fim)/2c” por “meio← variável aleatória inteira com distribuição uniforme de inicio a fim”. O algor- timo continua retornando sempre a resposta certa? Calcule a complexidade assintótica de E[T (n)], o valor esperado do tempo do algoritmo para uma entrada de tamanho n. 4.2. ÁRVORE GERADORA MÍNIMA: ALGORITMO DE PRIM 39 fato, ou seja, que o algoritmo realmente encontra uma árvore geradora (fácil) e que esta árvore geradora é mı́nima (bem mais dif́ıcil). Começamos pegando uma aresta que sabemos pertencer a uma árvore geradora mı́nima de G. Que aresta podeŕıamos escolher? Uma opção é a aresta de custo mı́nimo, mas escolheremos uma outra opção. Vamos escolher um vértice v qualquer e pegar a aresta e1 incidente a v que tenha custo mı́nimo. Será que e1 realmente pertence a alguma árvore geradora mı́nima de G? Vamos chamar de T ′ uma árvore geradora mı́nima de G que não contém e1 e usar esta árvore para construir uma árvore geradora mı́nima de G que contém e1. Adicionando e1 a T ′ obtemos um grafo com um único ciclo que, abusando da notação, chamamos de T ′ ∪ {e1}. Qualquer aresta removida deste ciclo faz com que obtenhamos uma árvore geradora, pois quebraremos o único ciclo do grafo. Se removemos uma aresta e′ incidente a v deste ciclo obtemos uma árvore com custo c(T ′ ∪ {e1} − {e′}) = c(T ′) + c(e1) − c(e′). Como e′ também é incidente a v, temos c(e1) 6 c(e′) e c(T ′ ∪ {e1} − {e′}) 6 c(T ′). Portanto existe árvore geradora T ′ ∪ {e1} − {e′} de custo mı́nimo que contém e1. Como podemos obter a próxima aresta? Também existem várias respostas que funcionam para esta questão (ver exerćıcio 4.3, para um outro exemplo). Vamos pegar uma aresta que seja adjacente em exatamente um dos extremos às arestas já escolhidas para a árvore geradora mı́nima e que tenha custo mı́nimo (figuras 4.3(b) e 4.3(c)). Este é o algoritmo de Prim (pseudo- código na figura 4.2), que funciona devido ao teorema que veremos a seguir. Entrada: G: Grafo conexo com custos associados às arestas. Sáıda: T : Árvore geradora ḿınima de G. Prim(G) V (T )← um vértice qualquer de V (G) Enquanto |V (T )| 6= |V (G)| Encontre aresta (u, v) com u ∈ V (T ) e v /∈ V (T ) de custo ḿınimo Adicione v à V (T ) e (u, v) à E(T ) Retorne T Figura 4.2. Solução do Problema 7 Teorema 4.3. Seja T ′ uma árvore geradora mı́nima de G e T uma árvore tal que E(T ) ⊂ E(T ′). Seja e = (v1, v2) uma aresta de G que tenha custo mı́nimo dentre as arestas (v1, v2) tais que v1 ∈ V (T ) e v2 /∈ V (T ). Então existe uma árvore geradora mı́nima de G que contém E(T ) ∪ {e}. Demonstração. Suponha que T ′ seja uma árvore geradora mı́nima de G que não contém e mas contém todas as arestas de T . Caso não exista T ′, o teorema já está provado. Se adicionamos e a T ′ obtemos o grafo T ′ ∪ {e} que contém um único ciclo. Como v1 ∈ V (T ), v2 /∈ V (T ) e T é uma árvore, então existe uma aresta e′ = (v′1, v ′ 2) neste ciclo tal que v ′ 1 ∈ V (T ) e v′2 /∈ V (T ), como ilustra a figura 4.3(a). O custo da árvore obtida a partir de T ′ pela remoção de e′ e adição de e é c(T ′∪{e}−{e′}) = c(T ′)+c(e)−c(e′). Como c(e) 6 c(e′) então c(T ′∪{e}−{e′}) 6 c(T ′). Portanto existe árvore geradora T ′ ∪ {e} − {e′} de custo mı́nimo que contém E(T ) ∪ {e}. ¤ Existem várias maneiras de implementar este algoritmo, usando diferentes estruturas de dados. Cada implementação tem uma complexidade de tempo diferente. A alternativa mais simples não usa nenhuma estrutura de dados sofisticada, usando apenas vetores, como mostra a figura 4.4. Basta olharmos para os loops para vermos que o algoritmo tem complexidade de tempo Θ(n2), onde n é o número de vértices do grafo. Considerando apenas n, isto é o melhor que 4.2. ÁRVORE GERADORA MÍNIMA: ALGORITMO DE PRIM 40 T ee’ v’1 v’2 v2 v1 T’ (a) r 1 5 5 2 6 6 4 3 2 5 1 4 Próxima aresta (b) r 1 5 5 2 6 6 4 3 2 5 1 4 (c) Figura 4.3. (a) Ilustração referente a prova do teorema 4.3. (b) Execução do algoritmo de Prim na 3a iteração. (c) Ávore gerada pelo algoritmo de Prim. Entrada: G: Grafo conexo com custo custo(u, v) associado a toda aresta (u, v). Se (u, v) /∈ E(G), então custo(u, v) =∞. Sáıda: T : Árvore geradora ḿınima de G. PrimVetor(G) V (T )← v ← um vértice qualquer de V (G) Marcar v Para todo vértice u 6= v u.custo← G.custo(u, v) u.vizinho← v Enquanto |V (T )| 6= |V (G)| v ← vértice não marcado com menor custo Adicione v à V (T ) e (u, v) à E(T ) Marcar v Para todo vértice u não marcado Se custo(u, v) < u.custo u.custo← G.custo(u, v) u.vizinho← v Retorne T Figura 4.4. Solução do Problema 7 usando apenas vetores. podemos fazer, pois o número de arestas do grafo pode ser Θ(n2) e todas precisam ser exa- minadas. Na prática, grafos esparços (poucas arestas) são muito mais comuns do que grafos densos. Por isso, seria bom que consegúıssemos expressar a complexidade de tempo não só em função de n, mas também em função do número de arestas m. O algoritmo de Prim pode ser facilmente modificado para ter complexidade de tempo O(m lg n), usando um heap binário. O novo pseudo-código está na figura 4.5. São executadas O(n) inserções, O(n) extrações de mı́nimo e O(m) reduções de custo no heap. Em um heap binário, todas estas operações levam tempo O(lg n), totalizando tempo O(m lg n), pois como G é conexo m > n−1. Na teoria, podemos usar um heap de Fibonacci, onde o tempo amortizado da operação de redução de custo é O(1). Neste caso, a complexidade de tempo do 4.3. COMPACTAÇÃO DE DADOS: ÁRVORES DE HUFFMAN 41 Entrada: G: Grafo conexo com custo custo(u, v) associado a toda aresta (u, v). Se (u, v) /∈ E(G), então custo(u, v) =∞. Sáıda: T : Árvore geradora ḿınima de G. Observações: H: Heap ḿınimo que armazena vértices usando como chave o campo custo. PrimHeap(G) V (T )← v ← um vértice qualquer de V (G) Marcar v Para todo vértice u 6= v u.custo← G.custo(u, v) u.vizinho← v Inserir(H,u) Enquanto |V (T )| 6= |V (G)| v ← ExtrairMı́nimo(H) Adicione v à V (T ) e (u, v) à E(T ) Marcar v Para todo vértice u não marcado e adjacente à v Se custo(u, v) < u.custo ReduzirCusto(H, u, G.custo(u, v)) u.vizinho← v Retorne T Figura 4.5. Solução do Problema 7 usando um heap. algoritmo fica O(n lg n + m). Na prática, porém, as costantes multiplicativas no tempo do heap de Fibonacci tornam-o mais lento do que o heap binário para qualquer grafo tratável. 4.3. Compactação de dados: Árvores de Huffman Vamos estudar agora um problema de compactação de dados. Nós vamos nos concentrar em arquivos de texto, para simplificar os exemplos, mas as técnicas estudadas aqui independem do tipo de arquivo. Para armazenar um arquivo de texto em um computador cada caractere é armazenado em um byte (8 bits). Certamente, nem todos os 28 = 256 caracteres posśıveis são usados. Uma alternativa fácil para reduzir o tamanho do arquivo é verificar se menos de 2k caracteres são usados, usando apenas k bits neste caso, mas isto não compactará praticamente nada. Uma técnica mais inteligente é considerar as freqüências dos caracteres e codificar cada caractere com um número diferente de bits. Vejamos um exemplo. Queremos compactar a palavra “cabana”. As freqüências dos caracteres nesta palavra são f(c) = f(b) = f(n) = 1/6, f(a) = 1/2. Temos 4 caracteres, então podeŕıamos usar 2 bits por caractere, totalizando 12 bits. Outra opção é usar os seguintes códigos: c : 000, b : 001, n : 01, a : 1. Com isto obtemos a palavra compactada 00010011011 com 11 bits. Não parece que ganhamos muito, mas este exemplo é pequeno e contém pouca redundância (tente algo semelhante com a palavra “aaabaaacaaad”). De fato, a compactação de Huffman sozinha não é muito eficiente, mas ela está presente como parte importante de praticamente todos os melhores compactadores usados atualmente. Um ponto importante é como podemos decodificar a mensagem. Primeiro, precisamos saber o código de cada caractere. Depois veremos como fornecer esta informação. Além disso, pre- cisamos ter uma maneira de descobrir quando acaba um caractere e começa outro. Vejamos o 4.3. COMPACTAÇÃO DE DADOS: ÁRVORES DE HUFFMAN 44 cuja freqüência é a soma das freqüências dos dois filhos, na criação de uma árvore maior. Antes disso, provaremos que toda árvore de Huffman é estritamente binária. Lema 4.4. Toda árvore de Huffman é estritamente binária. Demonstração. Por definição a árvore de Huffman é binária. Suponha que um vértice v tenha apenas um filho. Neste caso podemos remover v da árvore, fazendo que o filho de v seja filho do pai de v. A árvore obtida tem custo menor do que uma árvore de Huffman, o que é absurdo. ¤ Lema 4.5. Seja C = {c1, . . . , cn} um alfabeto onde todo caractere ci tem freqüência f(ci) e f(ci) 6 f(ci+1). Neste caso, existe árvore de Huffman onde c1 e c2 são folhas irmãs. Demonstração. Usaremos uma árvore de Huffman T ′ onde c1 e c2 não são folhas irmãs para construir uma árvore de Huffman T onde c1 e c2 são folhas irmãs. Como T ′ é estritamente binária, existem pelo menos duas folhas irmãs no último ńıvel de T ′. Como c1 e c2 são os dois caracteres menos freqüêntes, se colocarmos c1 e c2 nestas duas folhas, e colocarmos os caracteres que estavam nelas nas posições de c1 e c2, obtemos uma árvore T com c(T ) 6 c(T ′). ¤ Lema 4.6. Se TC é uma árvore de Huffman para o alfabeto C = {c1, . . . , cn}, então TC′, obtida acrescentando dois filhos c′1 e c ′ 2 a uma folha ck de TC onde f(ck) = f(c ′ 1) + f(c ′ 2) e f(c′1), f(c ′ 2) 6 f(ci) para 1 6 i 6 n, é uma árvore de Huffman para o alfabeto C−{ck}∪{c′1, c′2}. Demonstração. O custo de TC′ é c(TC′) = c(TC) + f(c′1) + f(c ′ 2), então c(TC) = c(TC′)− f(c′1) − f(c′2). Para obter um absurdo, suponha que T ′C′ seja uma árvore de Huffman de C ′ com c(T ′C′) < c(TC′). Pelo lema 4.5 podemos considerar que c ′ 1 e c ′ 2 são folhas irmãs em T ′ C′ . Removendo estas duas folhas c′1 e c ′ 2 e atribuindo o caractere ck ao pai delas obtemos uma árvore T ′C com c(T ′ C) = c(T ′ C′)− f(c′1)− f(c′2) < c(TC), o que contradiz o fato de c(TC) ser uma árvore de Huffman para C. ¤ Teorema 4.7. O algoritmo gera uma árvore de Huffman para C. Demonstração. O lema 4.5 é a base da indução. O lema 4.6 fornece o passo indutivo. Note que provamos que a árvore é uma árvore de Huffman na ordem contrária a que ela é constrúıda. Começamos provando que a raiz com seus dois filhos é uma árvore de Huffman e vamos descendo na árvore, como mostra a figura 4.8. ¤ Para que o descompactador decodifique um arquivo compactado com o código de Huffman ele precisa ter conhecimento da árvore. Analisaremos 4 alternativas para este problema: 1) Usar uma árvore pré-estabelecida, baseada em freqüências médias de cada caractere. Esta técnica só é viável em arquivos de texto. Ainda assim, de um idioma para outro a freqüência de cada caractere pode variar bastante. 2) Fornecer a árvore de Huffman, direta ou indiretamente, no ińıcio do arquivo. A árvore de Huffman para 256 caracteres pode ser descrita com 256 caracteres mais 511 bits usando percurso em árvore. Outra opção mais simples é informar a frequência de cada caractere e deixar que o descompactador construa a árvore. É necessário cuidado para garantir que a árvore do compactador e do descompactador sejam idênticas. 3) Fornecer a árvore de Huffman, direta ou indiretamente, para cada bloco do arquivo. Esta técnica divide o arquivo em blocos de um tamanho fixo e constrói árvores separadas para cada bloco. A vantagem é que se as freqüências dos caracteres são diferentes ao longo do arquivo, pode-se obter maior compactação. A desvantagem é que várias árvores tem que ser fornecidas, gastando espaço e tempo de processamento. 4) Usar um código adaptativo. Inicia-se com uma árvore em que todo caractere tem a mesma freqüência e, a cada caractere lido, incrementa-se a freqüência deste caractere, atualizando a árvore. Neste caso não é necessário enviar nenhuma árvore, mas não há compactação significativa no ińıcio do arquivo. Não apresentamos aqui algoritmo para fazer esta atualização na árvore eficientemente. 4.4. COMPACTAÇÃO DE DADOS: LZSS 45 4.4. Compactação de dados: LZSS Uma técnica simples que produz bons resultados de compactação é o método chamado LZSS. Este método, completamente diferente do método de Huffman, se baseia no fato de algumas seqüências de caracteres se repetirem ao longo do arquivo. A idéia é, ao invés de escrevermos todos os caracteres do arquivo explicitamente, fazermos referências a seqüências anteriores. Modelaremos formalmente esta idéia a seguir. Os primeiros modelos não fornecem um compactador eficiente, mas ajudam a entender as idéias centrais da técnica. Temos como entrada uma sequência de caracteres (o arquivo descompactado) e queremos ge- rar uma seqüência de simbolos correspondente ao arquivo (o arquivo compactado). Um śımbolo ou é um caracter ou um par (p, l). Temos que incluir no arquivo uma maneira de distinguir entre estes dois tipos de śımbolo, mas só discutiremos este detalhe bem mais tarde. O significado de um par (p, l) é uma referência a posições anteriores do arquivo: os l caracteres iniciados a partir de p caracteres anteriores no arquivo descompactado. Vejamos alguns exemplos: Descompactado1: métodogulosogulosométodo Compactado1: métodoguloso(6,6)(18,6) Descompactado2: bananadadebanana Compactado2: ban(2,3)dade(10,6) Note que em um śımbolo (p, l), p nunca pode referenciar um caractere que ainda não foi codificado, portanto p > 1. Podemos também forçar l > 2, pois preferimos escrever um único caractere explicitamente a referenciá-lo. O descompactador para este arquivo é bem simples e seu pseudo código está na figura 4.9. Neste exemplo trabalhamos com vetores e não arquivos. Entrada: C: Vetor compactado. D: Vetor onde será escrito o arquivo descompactado. Sáıda: Retorna o número de caracteres do arquivo descompactado. DescompactadorLZSS1(C, D) Di← 1 Para Ci de 1 até |C| Se C[Ci] é um caractere D[Di]← C[Ci] Di← Di + 1 Senão Para i de 0 até C[Ci].l − 1 D[Di]← D[C[Ci].l + i] Di← Di + 1 Retorne Di− 1 Figura 4.9. Descompactador LZSS em vetor. Temos alguns problemas no método de compactação que definimos. Um deles é como re- presentarmos no arquivo um par (p, l) já que tanto p quanto l podem ser tão grandes quanto o tamanho do arquivo descompactado. Outro problema é que o descompactador teria que voltar no arquivo várias vezes para encontrar as referências, o que tornaria a descompactação lenta. A solução para estes dois problemas é limitarmos o valor de p e de l e usarmos um buffer circular em memória. Assim nos limitamos a armazenar em memória as últimas posições escritas no arquivo descompactado. Limitaremos p ao valor p∗ (1 6 p 6 p∗) e l ao valor l∗ (2 6 l 6 l∗). O nosso buffer precisa armazenar apenas p∗ caracteres. O descompactador em arquivo usando um buffer circular está ilustrado no pseudo-código da figura 4.10. 4.4. COMPACTAÇÃO DE DADOS: LZSS 46 Entrada: C: Arquivo compactado. D: Arquivo onde será escrito o arquivo descompactado. p∗: Valor máximo de p em uma śımbolo (p, l). Observações: A operação i mod n é definida como: i mod n é o resto da divisão de i por n se i não é diviśıvel por n e i mod n = n se i é diviśıvel por n. DescompactadorLZSS2(C, D, p∗) B ← AlocarVetor(p∗) Bi← 1 Enquanto o arquivo C não tiver chegado ao fim c← LerŚımbolo(C) Se c é um caractere Escrever(D,c) B[Bi]← c Bi← Bi + 1 mod p∗ Senão Para i de 1 até c.l Escrever(D,B[Bi− c.p] mod p∗) B[Bi]← c Bi← Bi + 1 mod p∗ Figura 4.10. Descompactador LZSS em arquivo. Vários arquivos compactados diferentes podem corresponder a um mesmo arquivo compac- tado. Podemos por exemplo listar todos os caracteres explicitamente, não produzindo qualquer compactação. Queremos compactar o máximo posśıvel. Vamos definir o tamanho do arquivo compactado como o número de śımbolos que ele contém. Embora esta medida não seja total- mente fiel a realidade, ela é necessária para nossos resultados teóricos e nos leva a bons resultados práticos (para obtermos realmente o menor arquivo posśıvel, teŕıamos que minimizar a soma dos bits gastos, que dependem do śımbolo ser um caracter ou um par de valores, mas este problema é bem mais dif́ıcil). Problema 9. Dada uma seqüência de caracteres D e dois valores p∗ e l∗, encontrar a seqüência de śımbolos C correspondente a D que contém o menor número de śımbolos com a restrição de que todo śımbolo (p, l) satisfaz 1 6 p 6 p∗ e 1 6 l 6 l∗ O nosso algoritmo guloso é bastante simples. Sempre tentamos gerar o par (p, l) com o maior valor posśıvel de l. Se este valor for 0 ou 1, geramos o caractere explicitamente. Será óbvio que este algoritmo gera o mı́nimo de śımbolos? Vejamos um exemplo de variação do problema onde o método guloso não funciona bem. Uma variação é quando temos um dicionário definido e ou fornecemos o caractere expli- citamente ou uma referência a palavra no dicionário. Por exemplo se o dicionário contém as palavras: p1 = ab, p2 = de e p3 = bcdef , então podemos codificar abcdef como a p3, mas o método guloso codificaria como p1 c p2 f . Visto isso, parece bem razoável que devemos provar que o método guloso gera o mı́nimo de śımbolos no caso do nosso problema. Teorema 4.8. O algoritmo guloso gera uma seqüência de simbolos correspondente a entrada com o número mı́nimo de śımbolos posśıvel. Demonstração. Seja C1, . . . , Cn uma seqüência de śımbolos gerada pelo algoritmo guloso. Suponha, para obter um absurdo, que C ′1, . . . , C ′ n′ seja uma outra seqüência correspondente a EXERCÍCIOS 49 4.7) Um problema natural em grafos é encontrar o caminho mais curto entre pares de vértices. Na versão com pesos nas arestas, o comprimento de um caminho é a soma dos pesos das arestas pertencentes a ele. Escreva um algoritmo guloso que, dados um grafo com pesos nas arestas e um vértice v deste grafo, encontre a distância de v a todos os demais vértices do grafo. Prove que seu algoritmo está correto. Sugestão: seu algoritmo deve ser bastante semelhante ao algoritmo de Prim para árvore geradora mı́nima, mas deve construir a árvore formada pela união dos caminhos mais curtos que partem de v. Este algoritmo é chamado de algoritmo de Dijkstra. 4.8) Um páıs possue moedas de 1, 5, 10, 25 e 50 centavos. Você deve programar uma máquina capaz de dar troco com essas moedas de modo a fornecer sempre o número mı́nimo de moedas, qualquer que seja a quantia. Considere que a máquina possui quantidades ilimitadas de todas essas moedas. Prove que seu algoritmo funciona. O algoritmo continuaria funcionando se a máquina tivesse apenas moedas de 1, 10 e 25 centavos? 4.9) Escreva um algoritmo guloso onde: A entrada é um conjunto de palavras (cadeias de ca- racteres quaisquer) que formam um dicionário D e uma frase f (outra cadeia de caracte- res), onde todo caractere de f está em D. A sáıda é uma seqüência de segmentos de pala- vras que concatenados formam f . Um segmento de palavra é representado por uma tripla (p, ini, fim) onde p é o número da palavra no dicionário D, ini é o número do primeiro caractere do segmento e fim é o número do último caractere do segmento. Por exemplo: D = (camelo, aguia, sapo), f = guloso; sáıda:(2, 2, 3), (1, 5, 6), (3, 1, 1), (1, 6, 6). Claro que o seu algoritmo deve gerar o mı́nimo de triplas posśıvel. Prove que o seu algoritmo resolve o problema com este número mı́nimo de triplas. 4.10) Deseja-se realizar o máximo posśıvel de tarefas de um conjunto de tarefas onde cada tarefa tem um horário de ińıcio e um horário de término. Duas tarefas não podem estar sendo realizadas simultaneamente. Toda tarefa que for realizada deverá iniciar exatamente no seu horário de ińıcio e terminar exatamente no seu horário de término. Escreva um algoritmo guloso que fornece o maior número posśıvel de tarefas que podem ser realizadas. Prove que seu algoritmo funciona. *4.11) O fecho convexo de um conjunto de pontos no espaço é o menor poliedro convexo que contém todos estes pontos. Dado um conjunto de n pontos no espaço tridimensional, escreva um algoritmo para determinar seu fecho convexo em tempo O(nh), onde h é o número de vértices do poliedro do fecho convexo. CAṔıTULO 5 Divisão e Conquista Resolver problemas pequenos é quase sempre mais simples que resolver problemas maiores. É natural dividir um problema grande em sub-problemas menores e resolver cada um dos sub- problemas separadamente. Feito isto, temos que combinar as soluções dos problemas menores para obtermos a solução do problema total. Os algoritmos de divisão e conquista têm, então, três fases: dividir, conquistar e combinar. Na primeira fase, a divisão, o problema é decomposto em dois (ou mais) sub-problemas. Em alguns algoritmos, esta divisão é bastante simples, enquanto em outros, é a parte mais delicada do algoritmo. Na segunda fase, a conquista, resolvemos os sub-problemas. A beleza da técnica reside no fato de que os problemas menores podem ser resolvidos recursivamente, usando o mesmo procedimento de divisão e conquista, até que o tamanho do problema seja tão pequeno que sua solução seja trivial ou possa ser feita mais rapidamente usando algoritmos mais simples. Na terceira fase, a combinação das soluções, temos que unir as soluções dos problemas menores para obtermos uma solução unificada. Este procedimento nem sempre é trivial, e muitas vezes pode ser simplificado se a divisão (primeira fase) for feita de modo inteligente. 5.1. Envelope Superior O envelope superior de um conjunto de retas S no plano cartesiano é a seqüência de segmentos de retas de S com valor y máximo para x variando de −∞ à +∞ (figura 5.1). O nosso problema é: Problema 10. Dado um conjunto S de retas no plano, construa o envelope superior de S. Envelope Inferior Envelope Superior Figura 5.1. Envelope superior e envelope inferior de um conjunto de retas. Nesta sessão, o nosso algoritmo fará a divisão de modo bastante simples, apenas dividimos S em S1 e S2 de mesmo tamanho (ou tamanhos diferindo de no máximo uma unidade, se |S| for ı́mpar). A parte mais delicada do algoritmo consiste em combinar as duas soluções em uma solução unificada. Queremos resolver então o seguinte problema: dados dois envelopes superiores U1 = (U11 , . . . , U 1 |U1|) e U 2 = (U21 , . . . , U 2 |U2|), obter o envelope superior U = (U1, . . . , U|U |) das retas de U1∪U2. Para combinarmos os dois envelopes superiores, usaremos uma técnica chamada de linha de varredura. Nesta técnica, vamos resolvendo o problema da esquerda para a direita. Iniciamos comparando os coeficientes angulares das retas U11 e U 2 1 , as retas que contém os segmentos mais a esquerda nos envelopes superiores U1 e U2. A reta de menor coeficiente angular 50 5.1. ENVELOPE SUPERIOR 51 dentre U11 e U 2 1 será colocada na posição U1. Digamos que esta reta seja U 1 1 . Seguimos então descobrindo qual a primeira reta que intercepta U1, examinando apenas U12 e U 2 1 , e colocamos esta reta na posição U2. Repetimos este procedimento até obtermos todo o envelope superior U . O pseudo-código do algoritmo está na figura 5.2. Entrada: U1: Vetor com retas formando um envelope superior, da esquerda para a direita. U2: Idem, para outro conjunto de retas. Sáıda: U : Envelope superiror de U1 ∪ U2. Observações: ](r): Coeficiente angular da reta r. No caso de acessos além do limite dos vetores de entrada, considere que qualquer reta intercepta uma dada reta antes de uma reta inexistente. CombinaEnvelopes(U1, U2) i← i1 ← i2 ← 1 Se ](U1[1]) < ](U2[1]) U [1]← U1[1] i1 ← i1 + 1 Senão U [1]← U2[1] i2 ← i2 + 1 Enquanto i1 6 |U1| e i2 6 |U2| Se U1[i1] intercepta U [i] antes de U2[i2] i← i + 1 U [i]← U1[i1] i1 ← i1 + 1 Senão i← i + 1 U [i]← U2[i2] i2 ← i2 + 1 Retorne U Figura 5.2. Fase de combinação do problema 10 Com este algoritmo de combinação de dois envelopes superiores conclúıdo, é bastante simples escrever um algoritmo para resolver o problema original. Na primeira fase, dividimos S em S1 e S2 de mesmo tamanho (ou tamanhos diferindo de no máximo uma unidade, se |S| for ı́mpar). Na segunda fase, resolvemos recursivamente o problema para os dois subconjuntos, a não ser que um dos conjuntos tenha apenas uma reta, quando sabemos que o envelope superior é a própria reta. Na terceira fase, combinamos as soluções com o algoritmo que acabamos de ver. Vamos agora analisar a complexidade de tempo de nosso algoritmo. A primeira fase leva tempo constante e a terceira fase leva tempo linear. A complexidade da segunda fase é colocada na forma de recorrência T (n) = 2T (n/2) + n. Para provarmos um limite superior para T (n) por indução, precisamos ter uma estimativa de quanto vale T (n). Vamos imaginar a execução do algoritmo como uma árvore como na figura 5.3. Cada vértice representa uma execução do procedimento e o número indicado nele representa o número de retas na entrada. Os dois filhos de um vértice correspondem às duas chamadas recursivas feitas a partir do vértice pai. O tempo gasto em todas as execuções com 5.3. CONJUNTO INDEPENDENTE DE PESO MÁXIMO EM ÁRVORES 54 Entrada: S: Conjunto de pontos no plano Sáıda: (p, p′): Par de pontos mais próximos PontosMaisPróximos(S) Sx ← ordenação de S segundo o eixo x Sy ← ordenação de S segundo o eixo y Retorne PMPOrdenado(Sx, 1, |S|, Sy) PMPOrdenado(Sx, inicio, fim, Sy) Se fim− inicio 6 4 Retorne a solução do problema obtida comparando todas as distâncias meio← b(inicio + fim)/2c Para i de 1 até |Sy| Se Sy[i].x 6 Sx[meio], então acrescenta Sy[i] ao final de S1 Senão, acrescenta Sy[i] ao final de S2 (p1, p′1)← PMPOrdenado(Sx, inicio, meio, S1) (p2, p′2)← PMPOrdenado(Sx, meio + 1, fim, S2) Se |p1 − p′1| < |p2 − p′2|, então p← p1 e p′ ← p′1 Senão, p← p2 e p′ ← p′2 d← |p− p′| Para i de 1 até |S1| Se Sx[meio + 1].x− S1[i].x < d Acrescenta S1[i] ao final de S′1 Para i de 1 até |S2| Se S1[i].x− Sx[meio].x < d Acrescenta S2[i] ao final de S′2 j2 ← 1 Para i1 de 1 até |S′1| Enquanto S′1[i1].y − S′2[j2].y > d j2 ← j2 + 1 i2 ← j2 Enquanto S′2[i2].y − S′1[i1].y < d Se |S′2[i2]− S′1[i1]| < d p← S′1[i1] e p′ ← S′2[i2] d← |p− p′| i2 ← i2 + 1 Se i2 > |S′2|, então sai do ’enquanto’ Retorne (p, p′) Figura 5.5. Solução do Problema 11 5.3. Conjunto Independente de Peso Máximo em Árvores Um conjunto independente em um grafo, é um subconjunto de seus vértices que não contém nenhum par de vértices que sejam adjacentes. Chama-se de conjunto independente máximo, o maior conjunto independente do grafo (figura 5.6(a)). Na versão com pesos nos vértices, deseja-se maximizar a soma dos pesos dos vértices do conjunto. Este problema é extremamente complexo de ser resolvido, estando na categoria de problemas NP-dif́ıceis, como veremos no caṕıtulo 10. Porém, se nos restringirmos a árvores (grafos sem ciclos), podemos resolver o problema eficientemente usando divisão e conquista. 5.4. MULTIPLICAÇÃO DE MATRIZES: ALGORITMO DE STRASSEN 55 (a) v T1 T2 T3 (b) Figura 5.6. (a) Conjunto independente máximo de uma árvore sem pesos. (b) Árvore dividida em três sub-árvores pela remoção do vértice v. Problema 12. Dado uma árvore T , com pesos nos vértices, encontrar um conjunto inde- pendente de peso máximo de T . Nos outros problemas dessa sessão, nos preocupamos em fazer a divisão de modo balanceado, ou seja, queŕıamos obter sub-problemas de aproximadamente o mesmo tamanho. Neste caso, entretanto, veremos que isto não é necessário. Vamos começar escolhendo um vértice v da árvore T . Com este vértice, é natural dividir a árvore em algumas sub-árvores (figura 5.6(b), pois a remoção de v vai tornar a árvore desconexa (a não ser que v seja uma folha, mas, se for, também não há problema nenhum). Como podemos usar a solução dos problemas para as sub-árvores de modo a obter uma solução para o problema maior? Pensando um pouco sobre isso, você vai notar que não há qualquer maneira óbvia de fazê-lo, pois caso algum vértice adjacente a v em T esteja no conjunto independente máximo de uma das sub-árvores, não será posśıvel acrescentar v ao novo conjunto independente, aproveitando as soluções dos sub-problemas. Para resolver isto, vamos complicar um pouco nosso problema. Nosso novo problema é: dados uma árvore T , com pesos nos vértices, e um vértice v, calcular: (i) um conjunto independente de maior peso dentre os conjuntos independentes que não contém v; (ii) um conjunto independente de peso máximo. Com isto, podemos descrever nosso algoritmo de divisão e conquista. Na primeira iteração, como não é fornecido nenhum vértice v, iniciamos escolhendo um vértice v qualquer. Para cada sub-árvore Ti obtida pela remoção de v, chamamos de vi o vértice de Ti adjacente à v. Calculamos recursivamente os conjuntos independentes máximos de cada sub-árvore Ti, podendo conter e sem poder conter o vértice vi. O conjunto independente máximo C1 de T , com a restrição de não conter v, é, claramente, a união dos conjuntos independentes máximos das sub-árvores obtidas pela remoção de v. Para calcularmos o conjunto independente máximo real de T , constrúımos um outro conjunto independente C2. O conjunto independente C2 é obtido pela união do vértice v aos conjuntos independentes máximos das sub-árvores Ti, que não contém vi. O conjunto independente máximo de T é, então, o conjunto independente de maior peso dentre C1 e C2. O pseudo-código deste algoritmo está na figura 5.7. Provar que a complexidade de tempo do algoritmo é linear no número de vértices é simples e fica como exerćıcio. 5.4. Multiplicação de Matrizes: Algoritmo de Strassen Problema 13. Dadas duas matrizes n× n, A e B, obter a matriz C = A ·B. Uma solução bastante simples é usar a definição de produto de matrizes, que é Cij = n∑ k=1 AikBkj . 5.4. MULTIPLICAÇÃO DE MATRIZES: ALGORITMO DE STRASSEN 56 Entrada: T : Árvore com pesos nos vértices. v: Vértice de T , inicialmente qualquer vértice. Sáıda: (C1, C2), onde: C1: Conjunto independente que não contém v de peso máximo C2: Conjunto independente de peso máximo de T ConjuntoIndependente(T , v) Para cada sub-árvore Ti obtida pela remoção de v de T vi ← vértice de Ti adjacente a v em T (C1i , C 2 i )← ConjuntoIndependente(Ti,vi) C1 ← C1 ∪ C2i C2 ← C1 ∪ C1i C2 ← C1 ∪ {v} Se peso(C2)<peso(C1) C2 ← C1 Retorne (C1,C2) Figura 5.7. Solução do problema 12 Este algoritmo tem complexidade de tempo O(n3), pois para calcularmos cada elemento na matriz C, fazemos um número linear de operações elementares. Como podemos usar divisão e conquista neste problema, ou seja, decompor o problema em sub-problemas menores? Primeiro vamos simplificar um pouco o problema, nos restringindo a matrizes onde n é uma potência de 2. Não perdemos muito com isto, pois caso a largura de nossa matriz não seja uma potência de 2, podemos completá-la com elementos nulos. Sabemos que o produto de duas matrizes 2× 2 é dado por ( A11 A12 A21 A22 ) · ( B11 B12 B21 B22 ) = ( A11B11 + A12B21 A11B12 + A12B22 A21B11 + A22B21 A21B12 + A22B22 ) . Podemos dividir cada uma das nossas matrizes n × n, A e B, em quatro sub-matrizes n/2×n/2, pois consideramos que n é potência de 2. Usamos então a fórmula para multiplicação de matrizes 2 × 2. Assim, teremos que fazer 8 multiplicações de matrizes n/2 × n/2. Estas multiplicações são resolvidas recursivamente. Note que este algoritmo é bem diferente dos outros algoritmos de divisão e conquista que vimos antes. Não estamos apenas dividindo a entrada em conjuntos disjuntos, e resolvendo recursivamente o problema nesses conjuntos. Agora, dividimos cada uma das matrizes da entrada em 4 partes e criamos 8 sub-problemas combinando estas partes. Deste modo, a fase de divisão, onde definimos os sub-problemas a serem resolvidos, tornou-se bem mais elaborada. Para analisarmos a complexidade de tempo deste algoritmo, vamos apenas contar o número de multiplicações elementares realizadas, já que o número de adições e outras operações é uma constante vezes o número de multiplicações. Contamos exatamente este número com a re- corrência T (n) = { 8T (n/2) , se n > 2 8 , se n = 2 . É fácil notar que T (n) = n3, portanto não ganhamos absolutamente nada com nosso al- goritmo de divisão e conquista. Porém, nosso algoritmo agora é fortemente baseado em uma operação bastante simples, a multiplicação de matrizes 2 × 2. Se conseguirmos descobrir uma maneira mais eficiente de multiplicarmos estas matrizes, podemos melhorar nosso algoritmo EXERCÍCIOS 59 5.7) Uma triangulação de um conjunto S de pontos no plano é uma subdivisão de seu fecho convexo em triângulos disjuntos (exceto em seus bordos), onde os vértices dos triângulos são exatamente os pontos de S (figura 5.8(a)). Escreva um algoritmo para computar uma triangulação de um conjunto de pontos no plano. *5.8) Uma triangulação de Delaunay é uma triangulação que satisfaz a propriedade que os ćırculos circunscritos aos triângulos da triangulação não contém nenhum ponto em seus interiores (figura 5.8(b)). Outra definição é que uma aresta pertence a triangulação de Delaunay se e só se existe ćırculo com os dois pontos da aresta no seu bordo e nenhum ponto em seu interior. Escreva um algoritmo baseado em divisão e conquista que, dado um conjunto S de pontos no plano, compute sua triangulação de Delaunay em tempo O(|S| lg |S|). (a) (b) Figura 5.8. (a) Triangulação de um conjunto de pontos. (b) Triangulação de Delaunay de um conjunto de pontos. *5.9) O fecho convexo de um conjunto de pontos no espaço é o menor poliedro convexo que contém todos estes pontos. Dado um conjunto de n pontos no espaço tridimensional, escreva um algoritmo para determinar seu fecho convexo em tempo O(n lg n). Prove que o algoritmo está correto e analise sua complexidade de tempo. CAṔıTULO 6 Programação Dinâmica A técnica de programação dinâmica é uma técnica de decomposição que resolve um problema decompondo-o em subproblemas cujas soluções são armazenadas em uma tabela. 6.1. Ordem de Multiplicação de Matrizes Imagine que você tem que multiplicar três matrizes A, B e C, na mão, usando apenas papel e lápis. Considere que A é uma matriz 10 × 2 (10 linhas e 2 colunas), B é uma matriz 2 × 20 e C é uma matriz 20 × 5. Imagine que o tempo está correndo e quanto mais rápido você resolver o problema, maior será sua nota. O que você faz? Se a sua resposta é: ‘começo a multiplicar imediatamente’, então você provavelmente fez a escolha errada. Vamos contar quantas multiplicações você terá que fazer. Para multiplicar A por B, você fará 10 · 2 · 20 = 400 multiplicações. Em seguida, para multiplicar (AB) por C, você fará 10 · 20 · 5 = 1000 multiplicações. No total, fará 400 + 1000 = 1400 multiplicações. Porém, se você olhar para o problema com um pouco mais de cuidado, poderá notar que vale mais a pena começar multiplicando B por C, fazendo 2 · 20 · 5 = 200 multiplicações. Em seguida, você multiplica A por (BC), fazendo mais 10 · 2 · 5 = 100 multiplicações. No total, você faz 200 + 100 = 300 multiplicações, enquanto quem começou multiplicando as matrizes na ordem fornecida fez 1100 multiplicações a mais! Note que esta escolha da ordem da multiplicação é posśıvel porque a multiplicação de matri- zes, embora não seja comutativa, é associativa. Imagine que um computador tem que multiplicar uma seqüência de n matrizes. Não há dúvida que vale a pena, antes de iniciar a multiplicação, escolher a melhor ordem para fazê-lo. Isto é válido independente do algoritmo usado para fazer a multiplicação em si. Este é o problema estudado nesta sessão. Problema 14. Dada uma seqüência de n matrizes A1, . . . , An, escolher a ordem para mul- tiplicá-las que minimiza o tempo total gasto. O primeiro passo para resolvermos o problema é nos familiarizarmos com ele. Não precisa- mos nos preocupar com o conteúdo das matrizes que desejamos multiplicar, apenas com suas dimensões. Como, para multiplicarmos a matriz A pela matriz B, a largura de A tem que ser igual a altura de B, podemos condensar as dimensões das n matrizes que desejamos multiplicar em um vetor v com n + 1 posições, contendo as dimensões das matrizes, ou seja, Mi, a i-ésima matriz da multiplicação, tem dimensões vi× vi+1. No nosso exemplo do ińıcio da sessão, o vetor seria v = (10, 2, 20, 5). Nosso algoritmo não assumirá nada sobre o tempo gasto para multiplicar duas matrizes. Consideraremos que o tempo gasto para multiplicar uma matriz a× b por outra matriz b × c é f(a, b, c). Esta função será considerada conhecida, e será avaliada pelo nosso algoritmo diversas vezes. Normalmente, porém, considerar f(a, b, c) = abc é uma boa escolha, portanto, usaremos esta definição para os exemplos concretos. Construiremos nossa solução de baixo para cima, ou seja, partiremos de problemas menores até chegarmos ao problema total que desejamos resolver. Vamos criar um vetor bidimensonal T [1 . . . n, 1 . . . n] e preencheremos na posição T [i, j] a melhor maneira de multiplicarmos as ma- trizes de Ai até Aj . Queremos, no final, obter T [1, n], a solução para nosso problema. Para simplificarmos nossa explicação, computaremos apenas o tempo gasto na ordem ótima de mul- tiplicação, e não a maneira expĺıcita de fazê-lo. Porém, não é dif́ıcil usar o mesmo método para 60 6.2. TODOS OS CAMINHOS MAIS CURTOS 61 1 2 3 4 5 1 0 400 300 290 620 2 0 200 230 320 3 0 300 1200 4 0 225 5 0 Tabela 6.1. Tabela T tal que T [i, j] é o custo de multiplicar as matrizes de Mi até Mj , onde Mk é uma matriz vk × vk+1 segundo v = (10, 2, 20, 5, 3, 15). Consideramos o custo de multiplicar uma matriz a×b por uma matriz b×c como sendo f(a, b, c) = abc. obter realmente a maneira como as multiplicações devem ser realizadas. Vamos começar pelos casos triviais. Quando temos apenas uma matriz, não há nada a fazer, portanto T [i, i] = 0, para 1 6 i 6 n. Quando temos apenas duas matrizes para multiplicar, há apenas uma maneira de fazê-lo, portanto T [i, i + 1] = f(vi, vi+1, vi+2), para 1 6 i 6 n − 1. Quando temos três matrizes, A, B, C, podemos multiplicar primeiro AB ou BC. Assim, para minimizarmos o custo, fazemos T [i, i+2] = min(T [i, i+1]+f(vi, vi+2, vi+3), T [i+1, i+2]+f(vi, vi+1, vi+3)). De um modo geral, para multiplicarmos as matrizes de Mi até Mj , podemos, para i 6 k < j, multiplicar primeiro as matrizes de Mi até Mk e também de Mk+1 até Mj e depois multiplicarmos as duas matrizes obtidas. Temos então: T [i, j] = j−1 min k=i (T [i, k] + T [k + 1, j] + f(vi, vk+1, vj+1)). Um exemplo da tabela T para a entrada v = (10, 2, 20, 5, 3, 15) está na tabela 6.1. No exemplo, a função de custo usada foi f(a, b, c) = abc. Preenchemos as células T [i, j] da tabela 6.1 em ordem não decrescente da diferença de subscrito, ou seja, primeiro preenchemos a diagonal principal com as células T [i, i], em seguida a diagonal com as células T [i, i + 1], e assim por diante, até a última diagonal que consiste da célula T [1, n]. Note que para preencher uma célula da T [i, j] tabela, basta consultar células T [i, k] e T [k, j] com k entre i e j. Com isto, é fácil escrever o pseudo-código da figura 6.1. A complexidade de tempo do algoritmo é claramente O(n3), onde n é o número de matrizes a ser multiplicadas. Isto ocorre porque a tabela tem O(n2) posições e, para preenchermos uma posição, precisamos examinar outras O(n) células da tabela. Em muitos casos, uma complexidade de tempo cúbica no tamanho da entrada é inaceitável para propósitos práticos, porém, no caso da ordem de multiplicação de matrizes, esta comple- xidade é perfeitamente aceitável. Afinal, desejamos, após este pré-processamento, realmente multiplicar as matrizes e esta última fase do processo será provavelmente ainda mais demorada. Assim, não é provável que o número de matrizes seja grande a ponto de tornar a utilização de um algoritmo cúbico inviável. 6.2. Todos os caminhos mais curtos Uma outra aplicação da técnica de programação dinâmica é o problema de todos os caminhos mais curtos num grafo direcionado. Problema 15. Dado um grafo direcionado com pesos positivos nas arestas, encontrar para cada par de vértices o caminho mais curto. Neste caso, é dado um grafo direcionado D, definido por dois conjuntos: o conjunto de vértices V (D) = {v1, v2, . . . , vn} e o conjunto de arestas E(D), pares ordenados de vértices em V (D). Também é dada uma matrix W de pesos associados às arestas do grafo direcionado. A diagonal da matrix W é composta de zeros, enquanto que para i 6= j, w(i, j) é o peso da aresta EXERCÍCIOS 64 pesos vezes a distância da chave à raiz (o custo de acessar a chave associada àquele vértice da árvore). Descreva um algoritmo que usa programação dinâmica para resolver este problema da árvore binária de busca ótima. CAṔıTULO 7 Simplificação A técnica de simplificação é, de certa forma, um caso degenerado do paradigma de divisão e conquista. No método de divisão e conquista, quebrava-se um problema em sub-problemas menores e depois combinavam-se as soluções. No método de simplificação, o problema é redu- zido a um único sub-problema menor que é resolvido pelo mesmo método, até que sucessivas simplificações levem a um problema trivial ou pequeno o suficiente para ser resolvido por força bruta. Este paradima também é chamado de podar e buscar. No caso onde o tamanho da entrada sempre diminui por uma fração constante, o método é chamado de dizimar. 7.1. Centro de Árvore A palavra centro tem um significado geométrico muito forte, embora nem sempre preciso. A idéia de centro nos leva a elementos que estejam relativamente próximos de todos os outros elementos. Mesmo em objetos geométricos simples como triângulos, podemos falar em vários tipos de centros, como incentro, circuncentro, baricentro etc. Para definirmos o centro de um grafo, vamos primeiro definir a excentricidade de um vértice do grafo. Dado um grafo G, a excentricidade de um vértice v de G é a maior distância d(v, v′) de v a algum vértice v′. O centro de um grafo é o conjunto de vértices de excentricidade mı́nima, ou seja, o conjunto de vértices cuja distância ao vértice mais distante é mı́nima. No caso de árvores, o centro é sempre um único vértice ou um par de vértices adjacentes, como veremos. As excentricidades dos vértices de uma árvore estão ilustradas na figura 7.1(a). Problema 16. Dada uma árvore T , encontrar seu centro. Caso a árvore tenha apenas 1 ou 2 vértices, é claro que a árvore inteira é seu próprio centro. Estes são os casos triviais para nosso método de simplificação. Mas como podemos obter o centro de árvores maiores? As folhas não fazem parte do centro. Graças ao teorema abaixo, podemos descartá-las. Teorema 7.1. Seja T uma árvore com pelo menos 3 vértices e T ′ a árvore obtida pela remoção de todas as folhas de T . O centro de T é igual ao centro de T ′. Demonstração. Para todo vértice v da árvore, os vértices mais distantes de v são folhas. Os vértices adjacentes aos vértices mais distantes de v tem distância de v igual a distância do vértice mais distante de v menos uma unidade. Portanto, se removermos todas as folhas da árvore, a excentricidade de todos os vértices diminuirá de uma unidade, não alterando o 6 6 4 666 5 5 5 54 43 6 65 5 (a) 4 4 4 43 32 (b) Figura 7.1. (a) Árvore com as excentricidades dos vértices escritas e o centro da árvore destacado. (b) Árvore da figura obtida após a remoção das folhas da árvore da figura (a). 65 7.2. SELEÇÃO DO k-ÉSIMO 66 conjunto de vértices cuja excentricidade é mı́nima. Como a árvore tem pelo menos 3 vértices, o centro não será removido nesse processo. ¤ Nosso algoritmo é, então, bastante simples. A cada iteração removemos todas as folhas da árvore. Quando sobrar apenas 1 ou 2 vértices, retornamos este(s) vértice(s) como o centro. A complexidade de tempo do algoritmo é linear. Primeiro, constrúımos uma lista com todas as folhas. Em seguida, removemos todas as folhas, construindo uma lista das novas folhas criadas nesse processo. Ou seja, ao removermos uma folha f , verificamos se o vértice adjacente a f passa a ter grau 1. Em caso afirmativo, adicionamos o vértice adjacente a f na lista de folhas criadas. Repetimos este procedimento até restarem apenas 1 ou 2 folhas. Como a complexidade de tempo de cada etapa de remoção de folhas é linear no número de folhas removidas e nenhum vértice é removido mais de uma vez, a complexidade de tempo é linear no número de vértices. 7.2. Seleção do k-ésimo Vários algoritmos se baseiam em dividir um conjunto S em dois conjuntos S1 e S2 de apro- ximadamente o mesmo tamanho. Muitas vezes, é útil adicionar a propriedade que os elementos de S1 são menores que os elementos de S2. Porém, para fazermos esta divisão, precisamos de- terminar o elemento mediano de S, ou seja, o elemento de posição b|S|/2c em S ordenada. Para encontrarmos o elemento mediano, uma alternativa é ordenarmos S e, em seguida, pegarmos o elemento de posição b|S|/2c. Esta alternativa leva tempo O(n lg n). Será que podemos fazer melhor? Para resolvermos este problema, vamos primeiro torná-lo um pouco mais geral. Trataremos, então, do problema de determinar o k-ésimo menor elemento de S. Assim, fazendo k = b|S|/2c, obtemos o elemento mediano. Problema 17. Dados um conjunto S e um inteiro k, determinar o k-ésimo menor elemento de S. A solução deste problema usa a técnica de simplificação de modo bastante complexo, por isso, apresentaremos a solução em partes. Inicialmente, vamos supor que temos acesso a uma função pronta de mediana aproximada, com complexidade de tempo linear no tamanho de S. Esta função recebe como entrada um conjunto S e retorna um elemento x ∈ S tal que pelo menos 30% dos elementos de S são menores ou iguais a x e pelo menos 30% dos elementos de S são maiores ou iguais a x. Estamos considerando que S representa um conjunto, portanto não tem elementos repetidos. É fácil adaptar os algoritmos para funcionarem no caso de elementos repetidos. Podemos usar a mediana aproximada de um conjunto para dividir este conjunto em duas partes, S1 e S2, ‘aproximadamente’ de mesmo tamanho, com a propriedade que os elementos de S1 são menores que os elementos de S2. Se desejamos encontrar o k-ésimo menor elemento, sabemos que S1 contém este elemento se e só se |S1| > k. Caso |S1| < k, temos que o k-ésimo menor elemento de S está em S2. Não só isso, como podemos fazer afirmações ainda mais fortes. Caso |S1| > k, então o k-ésimo menor elemento de S é o k-ésimo menor elmento de S1. Caso |S1| < k, então o k-ésimo menor elemento de S é o (k − |S1|)-ésimo elemento de S2. Deste modo, temos o algoritmo da figura 7.2 que encontra o k-ésimo menor elemento de S. Para analirmos sua complexidade, escrevemos a recorrência T (n) = T (7/10n) + n Pode-se provar por indução que T (n) = O(n). Para ganhar mais intuição sobre este limite, note que, na primeira iteração do algoritmo, são examinados n elementos. Na segunda iteração, são examinados no máximo 7/10n elementos. Na i-ésima iteração, são examinados no máximo (7/10)i−1n elementos. Esses valores formam uma progressão geométrica de termo inicial n e razão 7/10, portanto, mesmo que somássemos infinitos termos, o que não é o caso, a soma não excederia n/(1− 7/10) = 10n/3 = O(n). 7.3. PONTE DO FECHO CONVEXO 69 Embora nosso algoritmo de mediana aproximada necessite de |S| ser múltiplo de 5 para garantir a cota de 30%, caso |S| não seja múltiplo de 5, a nossa cota será alterada apenas pela adição de uma constante, não alterando a complexidade de tempo do nosso algoritmo de seleção do k-ésimo menor elemento. O algoritmo visto não é um exemplo t́ıpico de simplificação, pois resolve não um, mas dois sub-problemas em cada chamada. Porém, preferimos colocá-lo nesta sessão porque a motivação do projeto do algoritmo, como foi apresentado aqui, se baseia em uma idéia de simplificação. 7.3. Ponte do Fecho Convexo No exerćıcio 5.6, deve-se escrever um algoritmo que determina o fecho convexo de um con- junto S de n pontos no plano em tempo O(n lg h), onde h é o número de pontos do fecho convexo. Este algoritmo usa uma função que, dados um conjunto S de n pontos no plano e uma reta vertical r, obtem as arestas do fecho convexo de S que interceptam r (figura 7.5(a)), em tempo O(n). Nesta sessão, descreveremos esta função. Problema 18. Dados um conjunto S de n pontos no plano e uma reta vertical r, encontre as arestas do fecho convexo de S que interceptam r. A reta r interceptará duas arestas do fecho convexo, sendo uma do fecho convexo superior e outra do fecho convexo inferior. Nos concentraremos em obter a aresta do fecho convexo superior que intercepta r, também chamada de “ponte”. A obtenção da aresta do fecho convexo inferior que intercepta r é análoga. Também consideraremos que r realmente intercepta o fecho convexo de S, pois isto só não acontece caso todos os pontos de S estejam do mesmo lado de r. raresta do fecho convexo inferior aresta do fecho convexo superior r (a) algumas retas suporte de S (b) Figura 7.5. (a) Ponte do fecho convexo. (b) Algumas retas suporte de S. Desejamos obter a ponte usando um algoritmo de simplificação. Nosso algoritmo procederá eliminando, a cada iteração, vértices que não são candidatos a serem um dos dois vértices da ponte. Começamos agrupando os pontos de S, arbitrariamente, em pares (p1, q1), . . . , (pbn/2c, qbn/2c). Consideramos que, nos pares (pi, qi), p é o ponto mais à esquerda e q o mais à direita. Caso |S| seja ı́mpar, um dos pontos fica sozinho e não concorre a ser descartado na iteração atual. Como podemos fazer para descobrirmos pontos que, com certeza, não são candidatos a serem vértices da ponte? Definimos uma reta suporte de S como uma reta ρ que contém pelo menos um ponto de S e todos os demais pontos de S estão abaixo da reta ρ (figura 7.5(b)). Dada uma inclinação, é fácil determinar a única reta suporte com esta inclinação. Digamos que nos seja fornecida uma reta suporte qualquer. Caso a reta suporte contenha tanto pontos à esquerda da reta vertical r quanto à direita (provavelmente um ponto de cada lado), então a reta suporte contém a ponte e nosso problema está resolvido. Normalmente, porém, isto não acontecerá. Digamos que a reta suporte ρ contém apenas um ou mais pontos de S que estão a direita da reta vertical r. 7.4. RESUMO E OBSERVAÇÕES FINAIS 70 Podeŕıamos rodar esta reta no sentido anti-horário, como um embrulho para presente, até encontrarmos a ponte. Não vamos fazer isto, porque o tempo gasto não seria linear. Mas segue desta observação um teorema important́ıssimo para o nosso algoritmo: Teorema 7.3. Se ρ é uma reta suporte de S que contém apenas pontos à direita de r, então a ponte de S que intercepta r tem coeficiente angular maior que o de ρ. Analogamente, se ρ é uma reta suporte de S que contém apenas pontos à esquerda de r, então a ponte de S que intercepta r tem coeficiente angular menor que o de ρ. Vamos continuar supondo que ρ contém apenas pontos à direita de r. O outro caso é análogo. Digamos que um dos nossos pares de pontos (pi, qi) defina um segmento de coeficiente angular menor que o coeficiente angular de ρ. Neste caso, podemos dizer seguramente que qi, o vértice da direita do par, não é um dos vértices da ponte. Vamos justificar com cuidado este fato, em prinćıpio não muito óbvio. Suponha, por absurdo, que qi seja um vértice da ponte. O coeficiente angular da ponte tem que ser menor ou igual ao coeficiente angular de (pi, qi), pois caso contrário pi estaria acima da reta que contém a ponte. Isto é absurdo, pois sabemos que a ponte tem coeficiente angular maior que ρ, que por sua vez tem coeficiente angular maior que (pi, qi). Deste modo, dada uma reta suporte ρ que contenha apenas pontos a direita de r, podemos descartar os vértices da direita de todos os pares (pi, qi) com coeficientes angulares menores que o de ρ. Analogamente, dada uma reta suporte ρ que contenha apenas pontos à esquerda de r, podemos descartar os vértices da esquerda de todos os pares (pi, qi) com coeficientes angulares maiores que o de ρ. Não falamos até agora sobre como obter a inclinação conveniente para nossa reta suporte. Queremos que tanto o número de segmentos com coeficiente angulares maiores que o da reta suporte quanto com coeficientes angulares menores que o da reta suporte sejam grandes, pois não sabemos, em prinćıpio, se nossa reta suporte conterá pontos à direita ou à esquerda de ρ. Usando o algoritmo da sessão anterior, podemos escolher a inclinação mediana dentre os segmentos (pi, qi). Deste modo, descartaremos um dos pontos de metade dos segmentos, assim descartando 1/4 do total de pontos. Como, a cada iteração, uma fração constante dos pontos é descartada, pelo argumento já apresentado de progressão geométrica, a complexidade de tempo do algoritmo é linear no número de pontos da entrada. O pseudo-código deste algoritmo está na figura 7.7. 1 2 3 4 5 6 7 ρ r ρr 1 2 4 3 5 Figura 7.6. Duas iterações do algoritmo para encontrar a ponte. Segmentos numerados segundo os coeficientes angulares. 7.4. Resumo e Observações Finais A técnica de simplificação consiste em reduzir um problema com uma entrada grande ao mesmo problema com uma entrada menor. A simplificação é um caso particular do paradigma de divisão e conquista, onde só é necessário resolver recursivamente um único problema menor. Quando o problema é pequeno o suficiente, podemos resolvê-lo diretamente. EXERCÍCIOS 71 Entrada: S: Conjunto de pontos no plano. r: Reta vertical que separa os pontos. Sáıda: (p, q): Par de pontos da ponte. Observações: ](p, q): Coeficiente angular do segmento (p, q). Ponte(S,r) R← Conjunto de bn/2c segmentos (p, q) ∈ S com p.x < q.x Cρ ← coeficiente angular mediano dentre os segmentos de R ρ← reta suporte de coeficiente angular Cρ Se ρ contém pontos à direita e à esquerda de r p← ponto de S mais à esquerda sobre ρ q ← ponto de S mais à direita sobre ρ Retorne (p,q) Se ρ contém somente pontos de S à direita de r Para todo (p, q) ∈ R Se ](p, q) 6 Cρ Remova de S o ponto q Retorne Ponte(S,r) Se ρ contém somente pontos de S à esquerda de r Para todo (p, q) ∈ R Se ](p, q) > Cρ Remova de S o ponto p Retorne Ponte(S,r) Figura 7.7. Solução do problema 18 No primeiro problema estudado, desejamos obter o centro de uma árvore. Simplificamos o problema através da remoção de todas as folhas da árvore, o que não altera o centro. Paramos quando a árvore obtida possuir apenas 1 ou 2 vértices, que são seu próprio centro. Em seguida, examinamos o algoritmo para determinar o k-ésimo menor elemento de um conjunto, que engloba o caso particular de determinar o elemento mediano. Neste problema, conseguimos descartar 20% dos elementos a cada iteração do algoritmo. Para fazermos isso, entretanto, precisamos chamar o próprio algoritmo de seleção da mediana recursivamente. Uma ponte do fecho convexo é a aresta do fecho convexo superior que intercepta uma reta vertical r. Consideramos o problema de dados um conjunto de n pontos e uma reta vertical r obter a ponte. Uma maneira trivial de resolver este problema seria determinando o fecho convexo do conjunto de pontos, o que leva tempo Θ(n lg n). Porém, podemos resolvê-lo diretamente, gastando tempo O(n). Para isso, usamos o algoritmo de cálculo da mediana de modo que conseguimos descartar um quarto dos pontos a cada iteração. Exerćıcios 7.1) O maior divisor comum (mdc) de um par de números inteiros é o maior número que divide, sem deixar resto, os dois números do par. O algoritmo de Euclides encontra mdc de dois números inteiros por simplificação. Dados dois inteiros a, b, com a > b, se b divide a, então mdc(a, b) = b. Caso contrário, seja r o resto da divisão de a por b, então mdc(a, b) = mdc(b, r). Prove que este algoritmo funciona corretamente. 8.1. ARRANJO DE RETAS 74 1 2 3 4 5 6 7 8 9 10 (a) r r (b) Figura 8.2. (a) Ordem em que as arestas são examinadas quando uma nova reta (em cinza) é inserida. (b) Vizinhança da reta r. face externa do retangulo, achamos qual aresta do arranjo é interceptada. Então, dividimos esta aresta quebrando-a em um novo vértice. Para descobrirmos qual a próxima aresta do arranjo que deve ser quebrada pelo acréscimo de um novo vértice, percorremos sequencialmente as arestas da face interceptada pela reta. Percorreremos sempre estas arestas no sentido anti-horário, como ilustra a figura 8.2(a). Este procedimento se repete até chegarmos em outro lado do retângulo envoltório. Deste modo, o algoritmo constrói o arranjo de retas usando sucessivas inserções, em qualquer ordem. A primeira vista, o algoritmo não parece muito eficiente. Uma análise superficial da complexidade de tempo do algoritmo indica que, a cada reta inserida, é necessário examinar O(n2) arestas. Deste modo, a complexidade de tempo do algoritmo é O(n3). Felizmente, podemos refinar nossa análise e provar que o algoritmo tem complexidade Θ(n2). Para provarmos este fato, precisamos mostrar que o número de arestas examinadas ao inserir a n-ésima reta no arranjo é O(n), e não apenas O(n2) como é fácil perceber. Definimos a vizinhança de uma reta no arranjo como o conjunto de arestas que pertencem as faces interceptadas por esta reta (figura 8.2(b)). Claramente, só as arestas da vizinhança da reta inserida são candidatas a ser examinadas. O teorema abaixo é chamado de teorema da vizinhança. Teorema 8.1. O número de arestas na vizinhança de uma reta r em um arranjo de n retas tem no máximo 6n arestas. Demonstração. Nossa prova será por indução em n, mas, antes de começarmos a indução, vamos dividir as arestas da vizinhança em dois conjuntos: arestas esquerdas e arestas direitas . Uma aresta esquerda é aquela que limita o bordo esquerdo de uma face da vizinhança (fi- gura 8.3(a)). Uma aresta direita é aquela que limita o bordo direito de uma face da vizinhança. Algumas arestas podem ser ao mesmo tempo esquerdas e direitas, por fazerem parte de duas células diferentes. Essas arestas serão contadas duas vezes. Provaremos que o número de arestas esquerdas na vizinhança não excede 3n, deste modo provando o teorema. Para tornarmos nossa explicação mais clara, vamos considerar que a reta r seja horizontal. Nosso argumento não fará a indução nas retas em qualquer ordem, mas sim da esquerda para a direita segundo as interseções com r. A escolha da ordem em que os elementos são adicionados pode simplificar extremamente uma prova por indução. No caso base com n = 1, temos apenas uma aresta esquerda na vizinhança de r, portanto a hipótese é válida para o caso base. Suponha que um arranjo com n− 1 retas possui no máximo 3(n− 1) arestas na vizinhança esquerda. Provaremos que a inclusão de uma reta ln que intercepta r a direita de todas as demais acrescenta no máximo 3 arestas a vizinhança de r, assim a hipótese vale para n. A primeira aresta esquerda nova que notamos com a inclusão da reta ln é formada pela própria reta ln. Como ln intercepta r a direita de todas as demais retas e estamos contando apenas as arestas esquerdas, esta é a única aresta nova sobre a própria reta ln. 8.2. FECHO CONVEXO: ALGORITMO DE GRAHAM 75 rr (a) rr l1=sinf l2 l3 l4=ssup ln=5 (b) Figura 8.3. (a) Vizinhança com as arestas esquerdas da vizinhança destacadas. (b) Ilustração do argumento indutivo da prova do teorema da vizinhança. Temos que contar mais duas arestas que podem criadas com a inclusão de ln. Estas arestas são formadas devido a ln poder cortar duas arestas esquerdas de vizinhança de r, uma acima e uma abaixo de r, na face extrema direita da vizinhança de r. Precisamos ainda garantir que nenhuma outra aresta esquerda da vizinhança de r é interceptada. Vamos chamar de ssup e sinf as retas que contém as arestas esquerdas interceptadas por ln na face extrema esquerda da vizinhança de r. Estas retas ficam entre ln e pontos de r a direita de ln. Este parágrafo está exemplificado na figura 8.3(b). Como tanto o número de arestas esquerdas da vizinhança quanto o número de arestas direitas da vizinhança (por argumento análogo) é no máximo 3n, o total de arestas da vizinhança não excede 6n. ¤ Como vimos, só as arestas da vizinhança da nova reta adicionada pelo algoritmo incremental são candidatas a serem percorridas nesta adição. Deste modo, a complexidade de tempo de adicionar uma reta em um arranjo com n retas é O(n). Assim, para adicionarmos todas as n retas, a complexidade total de tempo é O(n2). Como o número máximo de vértices (assim como o número de faces e arestas) do arranjo de retas é Θ(n2), então o nosso algoritmo é ótimo. 8.2. Fecho Convexo: Algoritmo de Graham Como vimos na sessão 4.1, o fecho convexo de um conjunto de pontos no plano é o menor poĺıgono convexo que envolve todos os pontos do conjunto. Na sessão 4.1, apresentamos um algoritmo de complexidade O(nh), onde n é o número de pontos da entrada e h é o número de pontos da sáıda, ou seja, os vértices do fecho convexo. No exerćıcio 5.5, pede-se que, usando o paradigma de divisão e conquista, se escreva um algoritmo que determine o fecho convexo em tempo O(n lg n). No exerćıcio 5.6, pedimos um algoritmo de complexidade de tempo O(n lg h), usando a função que encontra uma ponte do fecho convexo em tempo linear vista na sessão 7.3. Usando árvores de decisão algébricas, foi provado que não é posśıvel resolver o problema de fecho convexo em tempo menor que O(n lg h), em função dos parâmetros n e h. Nesta sessão, fazemos o aparentemente imposśıvel: apresentamos um algoritmo que constrói o fecho convexo de um conjunto de pontos no plano em tempo linear. Como fazemos esta mágica? Reposta: modificamos ligeiramente a entrada do nosso problema. A entrada do problema não é mais um conjunto de pontos do plano, mas sim, um conjunto de pontos do plano ordenado segundo o eixo x. Como a complexidade de tempo da ordenação é O(n lg n), caso os pontos não estejam or- denados convenientemente, o nosso algoritmo não leva tempo O(n), mas sim O(n lg n). Mesmo neste caso, o algoritmo que apresentamos é extremamente eficiente na prática, pois os algoritmos de ordenação são muito rápidos e não necessitam de fazer contas com as coordenadas dos pontos (geralmente números de ponto flutuante). Chamamos este algoritmo de algoritmo de Graham (embora o algoritmo originalmente proposto por Graham não use a ordenação segundo o eixo x, mas sim uma ordenação angular). 8.2. FECHO CONVEXO: ALGORITMO DE GRAHAM 76 Problema 20. Dado um conjunto S de n pontos do plano, ordenados segundo o eixo x, determinar seu fecho convexo. Na maioria dos algoritmos para resolver o problema de fecho convexo, a explicação torna-se mais simples quando o fecho convexo é dividido em duas partes: fecho convexo superior e fecho convexo inferior, como ilustra a figura 8.4. Nosso algoritmo determinará apenas o fecho convexo superior. A determinação do fecho convexo inferior é análoga e juntar os dois em um único poĺıgono convexo é trivial. Para simplificarmos a explicação, também não consideraremos o caso em que dois pontos possuem a mesma coordenada x. Fecho Convexo Superior Fecho Convexo Inferior Figura 8.4. Fecho convexo superior e fecho convexo inferior. O fecho convexo superior de um único ponto é o próprio ponto. O fecho convexo superior de um par de pontos é a aresta que une estes pontos. Dado o fecho convexo superior de um conjunto de pontos, como podemos adicionar mais um ponto no conjunto? Caso o ponto adicionado esteja sob o fecho convexo superior, não há nada a ser feito. Caso contrário, temos que descobrir como atualizar o fecho convexo superior. Fazer esta atualização pode não parecer muito simples. Porém, podemos modificar um pouco nosso algoritmo de modo a não precisarmos considerar a inserção de um ponto qualquer. Fazemos isso modificando a ordem com que os pontos são inseridos. Na sessão anterior, o nosso algoritmo incremental acrescentava os elementos da entrada em qualquer ordem. Na grande maioria dos casos, este procedimento não conduz a algoritmos eficientes. Muitas vezes, é preciso descobrir uma ordem conveniente para adicionar os elementos em nossa construção incremental. Nesta sessão, acrescentaremos os pontos da esquerda para a direita. Deste modo, é necessário que a entrada esteja ordenada segundo o eixo x ou, caso contrário, que façamos esta ordenação. Assim, a pergunta que precisamos responder é: Dado o fecho convexo superior de um con- junto de pontos, como podemos adicionar mais um ponto a direita dos demais pontos do con- junto? Certamente o novo ponto adicionado fará parte do fecho convexo superior. Precisamos descobrir a que outro vértice devemos conectá-lo, removendo os vértices intermediários do fecho convexo superior, como ilustra a figura 8.5(a). Para isto, basta percorrermos as arestas do fecho convexo da direita para a esquerda, examinando o ângulo entre o novo ponto e cada aresta. Caso o ângulo seja maior que 180◦, seguimos para a próxima aresta, como ilustra a figura 8.5(b). Pela definição de poĺıgono convexo como um poĺıgono que tem todos os ângulos internos menores que 180◦, o algoritmo funciona corretamente. O pseudo código deste algoritmo está na figura 8.6. Uma análise superficial da complexidade de tempo do algoritmo, mostra que o algoritmo tem complexidade O(n2), pois a cada ponto inserido, podemos examinar no máximo um número linear de pontos. Porém, é posśıvel refinar a análise e mostrar que a complexidade de tempo do algoritmo é bem menor, sendo O(n). Para isto, argumentamos que, ao adicionarmos um ponto, todos os pontos examinados, com exceção do último ponto examinado, são eliminados do fecho convexo, não sendo candidatos a serem examinados novamente. Assim, embora a complexidade de tempo de uma única inserção de um novo ponto seja linear, a soma da complexidade de tempo de todas as inserções também é linear. 8.3. PROGRAMAÇÃO LINEAR COM DUAS VARIÁVEIS 79 (a) C (b) Figura 8.8. (a) Problema de programação linear inviável. (b) Problema de programação linear ilimitado. A outra situação é quando o vértice de máximo v não satisfaz a nova desigualdade. Neste caso, precisamos encontrar o novo vértice ótimo. Para isto, note que certamente uma das duas desigualdades que definem este vértice tem que ser a desigualdade que acabamos de acrescentar. Com isto, podemos limitar nossa busca aos pontos sobre a reta que acabamos de acrescentar, ou seja, temos que resolver um problema de programação linear em apenas uma variável, como o ilustrado na figura 8.9. Este problema pode ser resolvido trivialmente em tempo linear no número de desigualdades. É posśıvel também que, neste procedimento, não encontremos nenhum ponto viável. Neste caso, podemos afirmar que o problema é inviável, pois não há solução que satisfaz a nova restrição ao mesmo tempo que todas as anteriores. 0-5 5 C 10 x>-4 x>-2 x>1 x<7 x<11 Ponto ótimo Figura 8.9. Problema de programação linear com apenas uma variável. Assim, para acrescentarmos uma desigualdade em um problema com i desigualdades a com- plexidade de tempo é O(i). Para acrescentarmos, uma a uma, as n desigualdades, começando com 2 desigualdades, a complexidade de tempo é: n−1∑ i=2 O(i) = O(n2) Desejamos melhorar esta complexidade de tempo para O(n). Como podemos fazer isto? Uma idéia é escolhermos convenientemente a ordem em que as restrições são acrescentadas pelo método incremental. Isto é mais ou menos o que faremos. De fato, escolher esta ordem é um problema bastante complicado, mas podemos lançar mão da probabilidade. Escolhemos uma ordem aleatória e argumentamos que o valor esperado da complexidade de tempo do algoritmo é O(n). Note que este valor esperado depende apenas da ordem aleatória com que acrescentamos as restrições, e não da entrada do problema em si. Esta ordem aleatória será uma distribuição uniforme das permutações das restrições (com exceção das duas restrições iniciais). Este tipo de permutação aleatória pode ser constrúıda com um algorimo semelhante ao da figura 8.10, que gera uma permutação aleatória de um vetor. O pseudo-código do algoritmo completo está na figura 8.11. EXERCÍCIOS 80 Entrada: v: Vetor a ser permutado. n: Tamanho de v. Sáıda: O vetor v será permutado aleatoriamente. Observações: rand(n): número aleatório distribuido uniformemente de 1 até n PermutaçãoAleatória(v, n) Para i decrescendo de n até 2 Troca v[i] com v[rand(i)] Figura 8.10. Algoritmo que permuta aleatoriamente um vetor. Precisamos calcular qual a probabilidade p(i) da solução do problema com as primeiras i restrições (segundo nossa ordem aleatória) ser diferente da solução onde se acrescenta a (i + 1)- ésima restrição. Estas soluções são diferentes se e só se a (i + 1)-ésima restrição é uma das duas restrições que definem o vértice de máximo v. Como estamos falando de uma restrição aleatória em um universo com i + 1 restrições, a probabilidade disto ocorrer é 2/(i + 1). Assim, o valor esperado da complexidade de tempo do nosso algoritmo é n−1∑ i=2 O(1/i)O(i) = n−1∑ i=2 O(1) = O(n) Este algoritmo é bem simples de implementar e bastante eficiente na prática. Algoritmos randomizados como este, onde a complexidade de tempo é uma esperança que independe da entrada, são excelentes alternativas em várias situações. 8.4. Resumo e Observações Finais Neste caṕıtulo, examinamos um paradigma bastante natural para o desenvolvimento de algo- ritmos, chamado de construção incremental. Começamos resolvendo um problema trivialmente pequeno e, então, adicionamos os elementos da entrada um a um, atualizando a solução. O primeiro problema estudado é armazenar um arranjo de retas em uma estrutura DCEL. Neste problema, não nos importamos com a ordem com que os elementos são inseridos. Qualquer que seja ela, a complexidade de tempo do algoritmo é O(n2), devido ao teorema da vizinhança. No problema do fecho convexo, podemos tornar nosso algoritmo mais simples inserindo os pontos da esquerda para a direita. Deste modo, conseguimos um algoritmo que, uma vez tendo os pontos ordenados, determina seu fecho convexo em tempo linear no número de pontos. No problema de programação linear com duas variáveis, ao invés de determinarmos uma boa ordem para inserir os elementos da entrada, preferimos inseri-los segundo uma ordem aleatória. Deste modo, conseguimos uma boa esperança da complexidade de tempo. Note que esta espe- rança independe da entrada, dependendo apenas da permutação aleatória usada pelo algoritmo. Assim, não há entradas ruins que podem fazer com que o algoritmo demore mais que o desejado. Exerćıcios 8.1) Escreva um algoritmo incremental para determinar o maior elemento em um conjunto com n números reais em tempo O(n). 8.2) Escreva um algoritmo para ordenar um conjunto de n números reais usando o paradigma de construção incremental. A complexidade de tempo do seu algoritmo deve ser O(n2). Qual seria a complexidade de tempo do seu algoritmo em uma máquina que pudesse EXERCÍCIOS 81 Entrada: n: Número de desigualdades. A: Matriz n× 2 de números reais. B: Vetor com n números reais. C: Vetor com 2 números reais. Sáıda: X: Vetor com 2 elementos que maximiza CX satisfazendo AX 6 B. ProgLin(n, A, B, C) // Determina duas retas que limitam o problema Para i de 1 até n Se (A[i][1], A[i][2]) está à esquerda de (C[1], C[2]), fazendo um ângulo de até 90◦ v[1]← i Sai do loop Para i de 1 até n Se (A[i][1], A[i][2]) está à direita de (C[1], C[2]), fazendo um ângulo de menos de 90◦ v[2]← i Sai do loop Se v[1] ou v[2] não foi definido Retorne “problema ilimitado” // Acrescenta ı́ndice das demais retas ao vetor j ← 3 Para i de 1 até n Se i 6= v[1] e i 6= v[2] v[j]← i j ← j + 1 // Permuta aleatoriamente o vetor, exceto as 2 primeiras posições PermutaçãoAleatória(v + 2, n− 2) X ← interseção das retas correspondentes as linhas v[1] e v[2] // Ińıcio da construção incremental Para i de 3 até n j ← v[i] Se X viola restrição correspondente a linha j X ← vértice sobre reta da linha j que maximiza CX e satisfaz desigualdades correspondente as linhas com ı́ndices de v[1] até v[i] Se X não existe Retorne “problema inviável” Retorne X Figura 8.11. Solução do problema de programação linear (problema 21). mover um segmento cont́ınuo de dados de uma região da memória para outra em tempo constante, independente do tamanho do segmento? 8.3) Use uma estrutura de dados como, por exemplo, árvores rubro-negras ou AVL para melhorar a complexidade de tempo do algoritmo do exerćıcio anterior para O(n lg n). 8.4) Escreva um algoritmo que, dado um conjunto de retas no plano, decida se 3 ou mais retas do conjunto se interceptam em um mesmo ponto. Sugestão: use o algoritmo para gerar a estrutura DCEL de um arranjo de retas. 8.5) Dado um conjunto S de pontos no plano cartesiano, um ponto p ∈ S é considerado um ponto de máximo se, para todo p′ ∈ S, ou a coordenada x de p é maior que a coordenada 9.1. FLUXO EM REDES 84 das arestas saindo da fonte é igual a soma dos fluxos das arestas que entram no sumidouro. Chamamos este número de valor do fluxo da rede e denotamos o valor do fluxo f por |f |. Um fluxo de uma rede é máximo quando seu valor é máximo dentre todos os fluxos da rede. Um fluxo máximo da rede da figura 9.1(a) está representado na figura 9.1(b). Problema 22. Dada uma rede, determinar seu fluxo máximo. A idéia do método de refinamento de solução é partir de um fluxo inicial e tentar aumentar este fluxo até obter um fluxo máximo. Como podemos fazer isso? Dizemos que uma aresta e está saturada quando f(e) = c(e), ou seja, o fluxo que passa por esta aresta não pode ser aumentado. Se um fluxo em uma rede possui um caminho que leva da origem ao destino tal que nenhuma aresta do caminho esteja saturada, então certamente podemos aumentar este fluxo até saturarmos alguma das arestas desse caminho. Assim, o nosso algoritmo pode, a cada iteração, encontrar um caminho da origem ao destino sem arestas saturadas e aumentar o fluxo. O algoritmo termina quando não houver caminho da origem ao destino sem arestas saturadas. Será que este método leva necessariamente ao fluxo máximo? A resposta é não. Veja na figura 9.2(a) um exemplo de fluxo onde todo o caminho da origem ao destino possui arestas saturadas e na figura 9.2(b) outro fluxo de valor maior para a mesma rede. 1/1 1/1 0/1 0/1 1/1 0/1 0/1 s t (a) 1/1 0/1 1/1 1/1 1/1 1/1 1/1 s t (b) Figura 9.2. (a) Fluxo de valor 1 onde todo o caminho da origem ao destino possui aresta saturada. (b) Fluxo de valor 2 para a mesma rede. A solução para este problema é, no lugar de procurarmos caminhos da origem ao destino na própria rede em questão, procurarmos este caminho na chamada rede residual. Dados uma rede D e um fluxo f , vamos definir a rede residual Df . Os vértices, a origem e o destino de D e Df são os mesmos. Para cada aresta direcionada e = (v1, v2) ∈ E(D), criamos duas arestas e′ = (v1, v2) e e′′ = (v2, v1) na rede residual Df . A capacidade da aresta e′ ∈ E(Df ) é c(e′) = c(e)− f(e). A capacidade da aresta e′′ ∈ E(Df ) é c(e′′) = f(e). Caso alguma dessas arestas tenha capacidade 0, devemos remover a aresta da rede residual. Caso tenhamos arestas direcionadas duplicadas, substitúımos estas arestas por uma única aresta cuja capacidade é a soma das capacidades das arestas removidas. A rede residual do fluxo da figura 9.3(a) está na figura 9.3(b). s t1/6 0/5 2/2 0/4 4/9 3/3 2/24/9 1/2 3/8 1/50/5 2/2 3/3 1/1 2/4 2/2 (a) s t5 6 6 5 3 2 3 15 2 3 1 2 11 5 4 2 2 4 5 4 (b) Figura 9.3. (a) Rede com um fluxo. (b) Rede residual do fluxo da figura (a). Qual o significado da rede residual? A capacidade das arestas da rede residual Df cor- respondem as variações que o fluxo f pode sofrer. Ao procurarmos um caminho da origem 9.1. FLUXO EM REDES 85 ao destino na rede original, que não tivesse arestas saturadas, não nos permit́ıamos reduzir o fluxo por nenhuma aresta. Porém, usando a rede residual Df , podemos colocar um fluxo em uma aresta e no sentido contrário ao fluxo f(e) que passava originalmente por e, deste modo reduzindo o fluxo por esta aresta. Claramente, qualquer caminho da origem ao destino na rede residual Df corresponde a um aumento no valor do fluxo f . Estes caminhos são chamados de caminhos aumentantes. O valor do novo fluxo será acrescido da capacidade da aresta de menor capacidade no caminho aumentante. Deste modo, o algoritmo procede encontrando caminhos na rede residual, aumentando o fluxo e construindo uma nova rede residual, até não existir mais caminho da origem ao destino na rede residual. Este algoritmo é chamado de algoritmo de Ford- Fulkerson. O pseudo-código do algoritmo encontra-se na figura 9.4. Será que este algoritmo realmente encontra o fluxo máximo? A resposta é sim, mas para provarmos este fato temos que definir alguns termos e provar um teorema importante. Entrada: D: Digrafo com capacidades associadas as arestas. s: Vértice origem. Deve ser uma fonte em D. t: Vértice destino. Deve ser um sumidouro em D. Sáıda: f : Fluxo máximo de s para t em D, onde f [e] é o fluxo pela aresta e. FluxoMáximo(D,s,t) f ← fluxo nulo em todas as arestas Enquanto existir caminho p de s para t em Df min← capacidade ḿınima dentre arestas de p Para toda aresta e de p f [e] = f [e] + min Retorne f Figura 9.4. Pseudo-código do algoritmo de Ford-Fulkerson para fluxo máximo em redes. Um corte (S, T ) em uma rede D é uma partição dos vértices de D em dois conjuntos S e T tais que s ∈ S e t ∈ T . O valor de um corte (S, T ) é a soma das capacidades das arestas direcionadas (u, v) tais que u ∈ S e v ∈ T e é denotado por |(S, T )|. Um corte mı́nimo é um corte que tem valor mı́nimo. Teorema 9.1. Em uma rede D, o valor do corte mı́nimo é igual ao valor do fluxo máximo, ou seja, se fmax é um fluxo máximo em D e (Smin, Tmin) é um corte mı́nimo em D, então |fmax| = |(Smin, Tmin)|. Demonstração. Primeiro vamos provar que |fmax| > |(Smin, Tmin)|. Como não existe caminho de s para t na rede residual do fluxo fmax, então todas as arestas de Smin para Tmin estão saturadas, e todas as arestas de Tmin para Smin tem fluxo zero, de modo que |fmax| > |(Smin, Tmin)|. Agora vamos provar que, se f é um fluxo e (S, T ) é um corte, então |f | 6 |(S, T )|. Conse- quentemente, |fmax| 6 |(Smin, Tmin)|. Pela conservação do fluxo, se somarmos o valor de um fluxo f nas arestas de S para T de um corte (S, T ) qualquer, obtemos exatamente |f |. Como este fluxo de S para T não pode ser maior que soma das capacidades das arestas de S para T , que é o valor do corte, a afirmação é verdadeira. ¤ O algoritmo de Ford-Fulkerson pode aumentar sucessivamente o valor do fluxo usando ca- minhos na rede residual. Além disso, pelo teorema acima, caso o algoritmo alcance um fluxo que não consegue mais aumentar, ou seja, não há caminho de s para t na rede residual, então 9.1. FLUXO EM REDES 86 0/1000 s t0/1 0/1000 0/10000/1000 1/1000 s t1/1 0/1000 1/10000/1000 1/1000 s t0/1 1/1000 1/10001/1000 2/1000 s t1/1 1/1000 2/10001/1000 ... 1000 s t1 1000 10001000 999 s t1 1000 9991000 999 s t1 999 999999 998 s t1 999 998999 ... Figura 9.5. Caso ruim do algoritmo de Ford-Fulkerson. Os fluxos estão re- presentados na linha de cima e a rede residual correspondente está representada abaixo. o fluxo obtido é máximo. Porém, precisamos provar que o algoritmo sempre termina em um tempo finito. Teorema 9.2. O algoritmo apresentado leva tempo O(m|fmax|) em uma rede D com m arestas com capacidades inteiras, onde |fmax| é o valor do fluxo máximo em D. Demonstração. Claramente, a rede residual pode ser constrúıda em tempo O(m) a cada iteração. Um caminho de s para t na rede residual pode ser encontrado em tempo O(m) usando busca. Afirmamos que o valor do fluxo f a cada iteração é um número inteiro. Nesse caso, o número de iterações é no máximo |fmax|, já que o valor de f aumenta a cada iteração. Para provarmos que |f | é sempre inteiro, usamos um argumento indutivo. O valor inicial de |f | é 0, portanto inteiro. Como todas as arestas de D tem capacidades inteiras e as capacidades das arestas de Df são obtidas através de diferenças entre capacidades das arestas em D e fluxos de f , as arestas de Df também tem capacidades inteiras. Como |f | é aumentado no valor da capacidade de uma aresta de Df , então |f | é aumentado de um número inteiro, a cada iteração, se mantendo inteiro. ¤ Dependendo dos caminhos escolhidos na rede residual este algoritmo pode ser bastante lento caso |fmax| seja grande. Um exemplo ruim está ilustrado na figura 9.5. Entrada: D: Digrafo com capacidades associadas as arestas. s: Vértice origem. Deve ser uma fonte em D. t: Vértice destino. Deve ser um sumidouro em D. Sáıda: f : Fluxo máximo de s para t em D, onde f [e] é o fluxo pela aresta e. FluxoMáximo(D,s,t) f ← fluxo nulo em todas as arestas Enquanto existir caminho de s para t em Df p← caminho de s a t em Df com número ḿınimo de arestas min← capacidade ḿınima dentre arestas de p Para toda aresta e de p f [e] = f [e] + min Retorne f Figura 9.6. Pseudo-código do algoritmo de Edmonds-Karp para fluxo máximo em redes. CAṔıTULO 10 Problemas NP-Completos Ao longo deste livro, estudamos técnicas para desenvolver algoritmos eficientes para diversos problemas. Porém, existem vários problemas para os quais não é conhecido nenhum algoritmo eficiente. Pergunta-se: até que ponto vale a pena tentar encontrar um algoritmo eficiente para um problema? Afinal, pode ser que tal algoritmo sequer exista. Por isso, é importante conhecer problemas para os quais não existe algoritmo eficiente, de modo a evitar esforços em vão. Neste caṕıtulo, estudamos uma classe de problemas para os quais acredita-se que não é posśıvel obter algoritmos eficientes. Embora ninguém tenha conseguido provar este fato, apre- sentamos evidências que mostram que é pouco provável que exista algoritmo eficiente para resolver qualquer um desses problemas, chamados de problemas NP-Dif́ıceis (um subconjunto dos problemas NP-Dif́ıceis são os problemas NP-Completos). 10.1. Tempo Polinomial no Tamanho da Entrada Ao longo do livro, usamos vários parâmetros da entrada, e até mesmo da sáıda, para ex- pressar a complexidade de tempo dos algoritmos. Quando a entrada é um grafo, usualmente expressamos a complexidade de tempo em função de n e m, os números de vértices e de arestas do grafo. Ao analisarmos o problema de determinar se um número p é primo, seria natural expressar a complexidade em função do valor p. Assim, o algoritmo que testa dividir p por todos os números naturais de 2 até ⌊√ p ⌋ , tem complexidade de tempo O( √ p). Porém, ao com- pararmos a complexidade de tempo de algoritmos para problemas diferentes, não podemos dizer que um algoritmo O( √ p) para testar primalidade é mais eficiente ou menos eficiente que um algoritmo O(n + m) para um problema em grafos. Felizmente, existe uma propriedade natural da entrada de todos os problemas que permite comparar complexidades de tempo de algoritmos para problemas diferentes. O tamanho da entrada de um problema é o número de bits gastos para descrever esta entrada. Para representarmos um número p em uma máquina binária, precisamos de n = O(lg p) bits. A complexidade de tempo do algoritmo que testa primalidade, se descrita em função do tamanho da entrada n, é O(2n). Um algoritmo é dito polinomial se sua complexidade de tempo é limitada por um polinômio no tamanho da entrada. Por exemplo, um algoritmo O(n2), onde n é o tamanho da entrada, é claramente polinomial. Um algoritmo O(n2 lg n) também é polinomial, pois O(n2 lg n) = O(n3). O algoritmo que testa primalidade em tempo Θ(2n) não é polinomial. Denotamos por poli(n) um polinômio qualquer em n. Ao invés de representar os números em notação binária, podemos representá-los em notação unária. Deste modo, um número p gasta O(p) bits para ser representado, e não O(lg p). Um algoritmo é dito pseudo-polinomial, se a sua complexidade de tempo for O(poli(n)), onde n é o tamanho da entrada com todos os números escritos em notação unária. Deste modo, o algoritmo que apresentamos para testar primalidade é pseudo-polinomial, embora não seja polinomial. Neste texto, consideramos que todos os números são escritos em notação binária, a não ser quando dizemos o contrário. Porque é útil separar os algoritmos em polinomiais e não polinomiais? Consideramos que os algoritmos polinomiais são eficientes, tendo complexidade de tempo aceitável para a maioria das aplicações práticas e consideramos que algoritmos não polinomiais não são eficientes, tendo pouca utilidade prática. A realidade é um pouco diferente. De fato um algoritmo O(n8) não é muito interessante na prática. Além disso, existem diversos algoritmos com complexidade 89 10.2. PROBLEMAS DE DECISÃO E REDUÇÕES 90 de tempo até mesmo linear no tamanho da entrada que, devido às grandes constantes ocultas pela notação O, não tem qualquer utilidade prática. Por outro lado, existem algoritmos não polinomiais com excelente desempenho prático, dos quais o mais famoso é o método simplex usado em programação linear. Embora o método simplex tenha complexidade exponencial no pior caso, na maioria dos casos encontrados na prática este método é bastante rápido. Ainda assim, a grande maioria dos algoritmos polinomiais tem boa performance prática e a grande maioria dos algoritmos não polinomiais tem péssima performance prática. É raro en- contrar um algoritmo com complexidade de tempo O(n8). Poucos são os algoritmos polinomiais que tem complexidade de tempo Ω(n4). Até aqui, a separação dos algoritmos em polinomiais e não polinomiais ainda pode parecer arbitrária. Podeŕıamos dividir os algoritmos em algoritmos com complexidade até O(n4) e al- goritmos que não tem complexidade O(n4), por exemplo, e dizer que os primeiros são eficientes enquanto os últimos não são. Mesmo que esta divisão fosse razoável, não conseguiŕıamos desen- volver a teoria com base nela. A facilidade matemática de separar os algortimos em polinomias e não polinomiais ficará clara na próxima sessão. 10.2. Problemas de Decisão e Reduções Um problema de decisão é um problema que possui apenas duas respostas: sim e não. Neste caṕıtulo, nos restringimos a problemas de decisão. Indiretamente, porém, tratamos de outros tipos de problemas. Por exemplo, se não existir algoritmo polinomial que diz se um grafo possui conjunto independente com pelo menos k vértices, então certamente não existe algoritmo polinomial que encontra o maior conjunto independente em um grafo. Afinal, a existência de um algoritmo polinomial para o problema de otimização implicaria em um algoritmo polinomial para o problema de decisão. Outra maneira de entender problemas de decisão é como reconhecimento de linguagens. Todo problema de decisão pode ser visto como, dada uma entrada x, decidir se x ∈ L para uma linguagem espećıfica L. Por exemplo, se L é o conjunto dos números primos, decidir se x é primo é equivalente a decidir se x ∈ L. Por causa dessa correspondência entre problemas de decisão e linguagens, alternamos livremente entre um e outro. Denotamos por Lπ a linguagem correspondente ao problema π, isto é, a linguagem que contém todas as entradas para as quais a resposta do problema π é sim. Denotamos por π(x) a resposta do problema π para a entrada x. Denotamos por A(x) a sáıda do algoritmo A para a entrada x. Dados dois problemas π e π′, dizemos que π reduz polinomialmente a π′ se existe algoritmo polinomial que transforma uma entrada x de π em uma entrada x′ de π′ tal que x ∈ Lπ ↔ x′ ∈ Lπ′ . Em outras palavras, π reduz polinomialmente a π′ se existe algoritmo polinomial T tal que π(x) = π′(T (x)). O tamanho da sáıda T (x) deve ser limitado por um polinômio no tamanho de x. Chamamos o algoritmo T de transformação. Usamos a notação π′ 6P π para dizer que π′ se reduz polinomialmente a π. O seguinte teorema mostra a utilidade das reduções polinomiais. Teorema 10.1. Dados dois problemas π e π′ onde π 6P π′, se existe algoritmo polinomial para resolver π′, então existe algoritmo polinomial para resolver π. Analogamente, se não existe algoritmo polinomial para resolver π então não existe algoritmo polinomial para resolver π′. Demonstração. Provaremos que, se existir algoritmo polinomial para resolver π′, então existe algoritmo polinomial para resolver π. Como π 6P π′, podemos resolver π fazendo uma redução polinomial da entrada de π para a entrada de π′ e, em seguida, rodando o algoritmo polinomial que resolve π′. A primeira etapa, que consiste em executar o algoritmo de trans- formação, leva tempo polinomial. A segunda etapa leva tempo polinomial no tamanho da entrada de π′, que, por sua vez, é um polinomio no tamanho da entrada de π (já que o algoritmo de transformação é polinomial). Como O(poli(poli(n)) = O(poli(n)), o teorema segue. ¤ Além disso, a relação de redutibilidade polinomial é transitiva: Teorema 10.2. Se π 6P π′ e π′ 6P π′′, então π 6P π′′. 10.3. CERTIFICADOS POLINOMIAIS E A CLASSE NP 91 Demonstração. Seja T o algoritmo polinomial que transforma a entrada de π na entrada de π′ e T ′ o algoritmo polinomial que transforma a entrada de π′ na entrada de π′′. O algoritmo T ′(T (x)) é polinomial e reduz π a π′′. ¤ 10.3. Certificados Polinomiais e a Classe NP Um ciclo Hamiltoniano em um grafo é um ciclo que contém todos os vértices do grafo. Considere o problema de decisão a seguir, para o qual não é conhecido nenhum algoritmo polinomial: Problema 23. Dado um grafo G, dizer se G possui ciclo Hamiltoniano. Digamos que uma raça alieńıgena possua poder de computação ilimitado, podendo executar qualquer algoritmo, polinomial ou não, instantaneamente. Nós terráqueos, entretanto, estamos limitados a executar algoritmos polinomiais e possuimos dois grafos G1 e G2, com milhares de vértices cada um, que desejamos saber se possuem ciclo Hamiltoniano. Então, perguntamos aos alieńıgenas se o grafo G1 possui ciclo Hamiltoniano. Recebemos como resposta um sonoro sim. Neste momento, surge uma dúvida: “Será que os alieńıgenas falam a verdade?” Para excla- recer esta dúvida, um terráqueo tem a seguinte idéia: “Peça para eles nos mostrarem o ciclo.” Então, os alieńıgenas fornecem uma seqüência de milhares de vértices que corresponde ao ciclo Hamiltoniano. Com algum trabalho, verificamos que esta seqüência tem todos os vértices do grafo exatamente uma vez e todas as arestas do ciclo de fato existem. Afinal, esta verificação pode ser feita em tempo polinomial. Assim, temos certeza que os alieńıgenas forneceram a resposta certa com relação ao grafo G1. Apresentamos, então, o grafo G2 aos alieńıgenas, que desta vez respondem não. Neste caso, não podemos pedir para os alińıgenas exibirem o ciclo Hamiltoniano que não existe. Ficamos para sempre na dúvida se eles disseram ou não a verdade sobre o grafo G2. Esta história ilustra a classe de problemas chamada de NP, à qual o problema ciclo Ha- miltoniano pertence. Para os problemas na classe NP, existe um certificado polinomial para a resposta sim. Mais formalmente, se π ∈ NP então, para toda entrada x ∈ Lπ existe uma sequência de bits c com |c| = O(poli(|x|), chamada de certificado polinomial, tal que existe algoritmo polinomial que, recebendo como entrada x e c, verifica que x ∈ Lπ. No caso do ciclo Hamiltoniano o certificado polinomial é o próprio ciclo (figura 10.1). No problema de dizer se um número é composto, o certificado polinomial pode ser um fator do número. a b c d e f g j i h Certificado Polinomial: ahgjfidcbe Figura 10.1. Grafo que possui ciclo hamiltoniano com o certificado polinomial. Entretanto, para a resposta não, isto é, quando x /∈ Lπ, não é necessário que exista este certificado. No caso, não temos necessariamente como provar que um grafo não possui ciclo Hamiltoniano. Quando um número é primo, também não parece óbvio que exista certificado polinomial para dizer que o número é primo (embora exista quando o número é composto). De fato, existe um certificado polinomial que diz que um número é primo, mas este certificado não é simples e não entraremos em detalhes aqui. Outra classe de problemas é chamada de CO-NP. Um problema pertece a CO-NP quando existe certificado para a resposta não. Todo problema pertencente a NP possui um problema simétrico em CO-NP. Dizer se um grafo não possui ciclo Hamiltoniano é um problema em CO- NP. Como mencionamos, o problema de dizer se um número é primo, ou, simetricamente, dizer se um número é composto, pertence simultaneamente a NP e a CO-NP, pois possui certificado polinomial tanto para o sim quanto para o não. 10.5. SATISFABILIDADE 94 SAT 3SATCLIQUE CI 12 3 Figura 10.5. Reduções entre problemas NP-Completos, numeradas segundo a ordem com que são apresentadas neste caṕıtulo. 10.5. Satisfabilidade O primeiro problema que foi provado NP-Completo é chamado de satisfabilidade, ou sim- plesmente SAT. Neste problema, é fornecida uma expressão lógica na forma normal conjuntiva e deseja-se saber se a expressão é satisfat́ıvel. A forma normal conjuntiva é formada por um conjunto de cláusulas ou (representado pelo operador ∨) unidas pelo operador e (representado por ∧). Um exemplo de expressão na forma normal conjuntiva é: (a ∨ c ∨ d) ∧ (a ∨ b ∨ c ∨ d) ∧ (b ∨ c) ∧ (a ∨ b ∨ d). Nestas expressões, o literal a representa a negação do literal a, ou seja, a é verdadeiro se e só se a é falso. A expressão é satisfat́ıvel se existir atribuição de valores verdadeiro e falso aos literais de modo que a expressão seja verdadeira. A expressão acima é satisfat́ıvel, podendo ser satisfeita pela atribuição: a = verdadeiro, b = verdadeiro, c = verdadeiro d = falso. Um exemplo mı́nimo de uma expressão na forma normal conjuntiva não satisfat́ıvel é (a)∧(a). Eis o problema SAT: Problema 24. (SAT) Dada uma expressão lógica na forma normal conjuntiva, dizer se a expressão é satisfat́ıvel. O teorema a seguir foi provado por Cook, mas prová-lo foge do escopo deste livro. Nos con- tentamos em justificar que SAT ∈ NP , pois a atribuição de variáveis é um certificado polinomial para a resposta sim. Teorema 10.4. SAT ∈ NPC Uma variação do problema SAT é chamada de 3SAT. Problema 25. (3SAT) Dada uma expressão lógica na forma normal conjuntiva, com no máximo 3 literais por cláusula, dizer se a expressão é satisfat́ıvel. Um exemplo de expressão de 3SAT é: (a ∨ b ∨ d) ∧ (a ∨ c ∨ d) ∧ (b ∨ d) ∧ (b ∨ c ∨ d). Certamente o problema 3SAT não é mais dif́ıcil de resolver que o problema SAT. Afinal, o problema 3SAT é um caso espećıfico do problema SAT. Seria extremamente simples provar que 3SAT 6P SAT, porém queremos provar a direção contrária. Teorema 10.5. 3SAT ∈ NPC Demonstração. Claramente, 3SAT ∈ NP , pois uma atribuição de valores aos literais é um certificado polinomial para o sim. Pelo teorema 10.3, basta provarmos que SAT 6P 3SAT. Podemos transformar uma cláusula C com n > 3 literais em duas cláusulas C1 e C2 com n − 1 e 3 literais, respectivamente, pelo processo que definimos a seguir. A aplicação sucessiva 10.6. CLIQUE E CONJUNTO INDEPENDENTE 95 deste método permite que uma cláusula com um número arbitrariamente grande de literais seja reduzida a várias cláusulas com 3 literais por cláusula. Sejam x1, . . . , xn os literais de uma clásula C = (x1 ∨ . . . ∨ xn) com n > 3 literais. Criamos uma variável adicional y e definimos as duas cláusulas como: C1 = (x1 ∨ . . . ∨ xn−2 ∨ y) e C2 = (xn−1, xn, y). Precisamos provar que a aplicação dessa transformação não altera a satisfabilidade da ex- pressão. Dada uma atribuição de valores às variáveis, caso a cláusula C seja verdadeira, algum literal xi é verdadeiro. Então, ou xi está em C1 ou xi está em C2. Caso xi esteja em C1, podemos satisfazer as duas cláusulas criadas fazendo y = falso. Caso xi esteja em C2, podemos satisfazer as duas cláusulas criadas fazendo y = verdadeiro. Caso a cláusula C seja falsa, não existe literal xi verdadeiro. Neste caso, não importa se y = verdadeiro ou y = falso, uma das duas cláusulas C1 ou C2 não será satisfeita. Deste modo, a expressão inteira não será satisfeita. Claramente esta transformação leva tempo polinomial no tamanho da entrada. ¤ Deste modo, podemos transformar a expressão de SAT: (a ∨ b ∨ c ∨ d ∨ e) ∧ (b ∨ c ∨ d ∨ e) ∧ (a ∨ c) ∧ (a ∨ d ∨ e) na expressão de 3SAT: (a ∨ b ∨ y3) ∧ (c ∨ y1 ∨ y3) ∧ (d ∨ e ∨ y1) ∧ (b ∨ c ∨ y2) ∧ (d ∨ e ∨ y2) ∧ (a ∨ c) ∧ (a ∨ d ∨ e). 10.6. Clique e Conjunto Independente Uma clique em um grafo é um subconjunto de seus vértices cujo subgrafo induzido é com- pleto. Em outras palavras, uma clique em um grafo G é um subconjunto Q ⊆ V (G) tal que, para todo par de vértices distintos v1, v2 ∈ Q, a aresta (v1, v2) ∈ E(G). Um exemplo de clique está na figura 10.6. Problema 26. (CLIQUE) Dados um grafo G e um inteiro k, dizer se G possui clique com pelo menos k vértices. Figura 10.6. Grafo com uma clique de 5 vértices em destaque. Provaremos que CLIQUE é NP-Completo fazendo uma redução polinomial de SAT a CLIQUE. Note que estamos reduzindo problemas que não parecem ter qualquer relação. O problema CLIQUE é um problema de grafos, enquanto o problema SAT é um problema de lógica. Teorema 10.6. CLIQUE ∈ NPC Demonstração. Claramente, CLIQUE ∈ NP , pois a própria clique é um certificado poli- nomial para o sim. Pelo teorema 10.3, basta provarmos que SAT 6P CLIQUE. A nossa transformação é definida da seguinte maneira. Para cada literal xi em cada cláusula c criamos um vértice correspondente xci no grafo. As arestas são colocadas sempre entre vértices de cláusulas distintas, desde que estes vértices não correspondam a um literal e sua negação. Um exemplo desta transformação está na figura 10.7. O valor de k é definido como o número de cláusulas. 10.6. CLIQUE E CONJUNTO INDEPENDENTE 96 x1 1 x2 1 x3 1 x1 2 x2 2 x3 2 x4 2 x1 3 x2 3 x1 4 x2 4 x3 4 a c d a b c d b c a b d k=4 Figura 10.7. Grafo obtido pela redução da expressão (a ∨ c ∨ d) ∧ (a ∨ b ∨ c ∨ d) ∧ (b ∨ c) ∧ (a ∨ b ∨ d). Claramente esta transformação pode ser feita em tempo polinomial no tamanho da entrada, embora este tempo não seja linear, mas sim quadrático. Precisamos provar que o grafo obtido pela transformação possui clique de tamanho pelo menos k se e só se a expressão lógica é satisfat́ıvel. Suponha que o grafo possui uma clique com pelo menos k vértices. Como os vértices prove- nientes da mesma cláusula não possuem arestas entre si, certamente a clique possui um vértice vindo de cada cláusula. Certamente, não há na clique vértices correspondentes a um literal e sua negação, pois estes vértices não possuiriam aresta entre eles. Então, podemos atribuir valor verdadeiro a todos os literais correspondentes aos vértices da clique. Esta atribuição satisfaz a todas as cláusulas, pois tem pelo menos um literal verdadeiro em cada cláusula. Para provar a outra direção, suponha que a expressão lógica é satisfat́ıvel e fixe uma atri- buição de valores que a satisfaça. Então, cada cláusula possui pelo menos um literal verdadeiro. Defina Q como um conjunto de vértices correspondente a um literal verdadeiro de cada cláusula. Por definição, Q possui k vértices, um de cada cláusula. Além disso, como não há em Q vértices correspondentes a um literal e sua negação, então Q é uma clique. ¤ Um conjunto independente em um grafo é um subconjunto de seus vértices tal que não exista aresta entre qualquer par de vértices do subconjunto. O problema abaixo é extremamente semelhante ao problema clique. Problema 27. (CI) Dados um grafo G e um inteiro k, dizer se G possui conjunto indepen- dente com pelo menos k vértices. Podemos provar que CI é NP-Completo fazendo uma redução simples de CLIQUE para CI. Teorema 10.7. CI ∈ NPC Demonstração. Claramente, CI ∈ NP , pois o próprio conjunto independente é um certi- ficado polinomial para o sim. Pelo teorema 10.3, basta provarmos que CLIQUE 6P CI. A transformação polinomial de CLIQUE para CI é bastante simples. Basta mantermos o valor de k inalterado e gerarmos o grafo G como o complemento do grafo G. O conjunto Q é uma clique em G se e só se o conjunto Q é um conjunto independente em G (figura 10.8). Esta redução é claramente polinomial. ¤