Minicurso de Análise de Algoritmos

Minicurso deAnálise de Algoritmos

http://www.ime.usp.br/~pf/livrinho-AA/

Paulo FeofiloffDepartamento de Ciência da Computação

Instituto de Matemática e EstatísticaUniversidade de São Paulo

2 de janeiro de 2013

http://www.ime.usp.br/~pf/livrinho-AA/

2 FEOFILOFF

Sumário

1 Introdução 9

1.1 Problemas e instâncias . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Consumo de tempo de algoritmos . . . . . . . . . . . . . . . . . . . . 10

1.3 Recursão e algoritmos recursivos . . . . . . . . . . . . . . . . . . . . . 11

1.4 Convenções de notação . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Comparação assintótica de funções 13

2.1 Notação O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2 Notação Ômega . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.3 Notação Teta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4 Consumo de tempo de algoritmos . . . . . . . . . . . . . . . . . . . . 15

3 Solução de recorrências 17

3.1 Exemplo 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.2 Exemplo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.3 Exemplo 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.4 Exemplo 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.5 Teorema mestre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4 Ordenação de vetor 25

4.1 Algoritmo Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.2 Divisão e conquista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

5 Segmento de soma máxima 27

5.1 O problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5.2 Primeiro algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

5.3 Segundo algoritmo: divisão e conquista . . . . . . . . . . . . . . . . . 29

5.4 Terceiro algoritmo: programação dinâmica . . . . . . . . . . . . . . . 30

5.5 Observações sobre programação dinâmica . . . . . . . . . . . . . . . . 32

3

4 FEOFILOFF

6 O problema da maioria 33

6.1 O problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

6.2 Um algoritmo linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

7 Multiplicação de números naturais 37

7.1 O problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

7.2 O algoritmo usual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37


7.4 Algoritmo de Karatsuba . . . . . . . . . . . . . . . . . . . . . . . . . . 40

7.5 Detalhes de implementação . . . . . . . . . . . . . . . . . . . . . . . . 41


8 Escalonamento de intervalos 43

8.1 O problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

8.2 A estrutura recursiva do problema . . . . . . . . . . . . . . . . . . . . 44

8.3 Algoritmo de programação dinâmica . . . . . . . . . . . . . . . . . . . 44

9 As linhas de um parágrafo 47

9.1 O problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47


9.3 Um algoritmo de programação dinâmica . . . . . . . . . . . . . . . . 49

10 Mochila de valor máximo 51

10.1 O problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51


10.3 Algoritmo de programação dinâmica . . . . . . . . . . . . . . . . . . . 52

10.4 Instâncias especiais do problema da mochila . . . . . . . . . . . . . . 54

11 Mochila de valor quase máximo 55

11.1 O problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

11.2 Algoritmo de aproximação . . . . . . . . . . . . . . . . . . . . . . . . . 55

11.3 Observações sobre algoritmos de aproximação . . . . . . . . . . . . . 57

12 A cobertura de um grafo 59

12.1 Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

12.2 O problema da cobertura . . . . . . . . . . . . . . . . . . . . . . . . . . 59

12.3 Um algoritmo de aproximação . . . . . . . . . . . . . . . . . . . . . . 60

12.4 Comentários sobre o método primal-dual . . . . . . . . . . . . . . . . 62

12.5 Instâncias especiais do problema . . . . . . . . . . . . . . . . . . . . . 62

ANÁLISE DE ALGORITMOS 5

13 Conjuntos independentes em grafos 63

13.1 O problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

13.2 Algoritmo probabilístico . . . . . . . . . . . . . . . . . . . . . . . . . . 64

13.3 Comentários sobre algoritmos probabilísticos . . . . . . . . . . . . . . 66

14 Busca em largura num grafo 67

14.1 O problema do componente . . . . . . . . . . . . . . . . . . . . . . . . 67

14.2 Busca em largura: versão preliminar . . . . . . . . . . . . . . . . . . . 67

14.3 Busca em largura: versão mais concreta . . . . . . . . . . . . . . . . . 69

15 Busca em profundidade num grafo 71

15.1 Busca em profundidade . . . . . . . . . . . . . . . . . . . . . . . . . . 71

Posfácio 74

Bibliografia 77

Índice remissivo 79

6 FEOFILOFF

Prefácio

A Análise de Algoritmos (veja o verbete Analysis of Algorithms na Wikipedia) é umadisciplina bem-estabelecida, coberta por um bom número de excelentes livros (a maio-ria em inglês). Este livrinho faz uma modesta introdução ao assunto. Depois de tratarbrevemente de alguns pré-requisitos (como notação assintótica e resolução de recorrên-cias), o texto analisa alguns algoritmos clássicos, discute sua eficiência, e chama a aten-ção para as estratégias (divisão e conquista, programação dinâmica, método primal-dual) que levaram à sua concepção.

Este livrinho é uma versão corrigida do minicurso que ministrei nas JAI (Jornadasde Atualização em Informática) de 2009 da SBC (Sociedade Brasileira de Computação),ocorridas em Bento Gonçalves, RS, em julho de 2009. O minicurso foi publicado nolivro organizado por André P. L. F. de Carvalho e Tomasz Kowaltowski [5].

O texto deve muito a Cristina Gomes Fernandes e José Coelho de Pina Jr., ambosdo Departamento de Ciência da Computação do Instituto de Matemática e Estatísticada USP, que contribuíram com material, ideias e valiosas sugestões.

IME–USP, São Paulo, agosto de 2009P. F.

7

http://en.wikipedia.org/wiki/Analysis_of_algorithms

http://csbc2009.inf.ufrgs.br/index.php?option=com_content&task=view&id=26&Itemid=71

http://csbc2009.inf.ufrgs.br/index.php?option=com_content&task=view&id=26&Itemid=71

http://www.sbc.org.br/

8 FEOFILOFF

Capítulo 1

Introdução

A Análise de Algoritmos1 estuda certos problemas computacionais recorrentes, ou seja,problemas que aparecem, sob diversos disfarces, em uma grande variedade de aplica-ções e de contextos. A análise de um algoritmo para um dado problema trata de

1. provar que o algoritmo está correto e2. estimar o tempo que a execução do algoritmo consome.

(A estimativa do espaço de memória usado pelo algoritmo também é importante emmuitos casos.) Dados dois algoritmos para um mesmo problema, a análise permitedecidir qual dos dois é mais eficiente.

Pode-se dizer que a Análise de Algoritmos é uma disciplina de engenharia, poisela procura prever o comportamento de um algoritmo antes que ele seja efetivamenteimplementado e colocado “em produção”.

Num nível mais abstrato, a análise de algoritmos procura identificar aspectos estru-turais comuns a algoritmos diferentes e estudar paradigmas de projeto de algoritmos(como a divisão e conquista, a programação dinâmica, o método primal-dual, etc.)

Este texto é uma breve introdução à Análise de Algoritmos, baseada nos excelenteslivros de Cormen, Leiserson, Rivest e Stein [3], de Brassard e Bratley [2], de Bentley [1],de Kleinberg e Tardos [10] e de Manber [14].

No restante desta introdução, faremos uma rápida revisão de conceitos básicos efixaremos a notação e a terminologia empregadas no texto.

1.1 Problemas e instâncias

Da mesma forma que distinguimos um algoritmo de sua aplicação a uma particular“entrada”, convém distinguir problemas de suas instâncias. Todo problema computa-cional é uma coleção de instâncias.2 Cada instância do problema é definida por umparticular conjunto de dados.

1 A expressão foi cunhada por D. E. Knuth [12].2 A palavra instância é um neologismo importado do inglês. Ela está sendo empregada aqui no sentido

de exemplo, espécime, amostra, ilustração.

9

10 FEOFILOFF

Considere, por exemplo, o problema de encontrar a média dos elementos de umvetor A[1 . . n] de números. Uma das instâncias deste problema consiste em encontrara média dos elementos do vetor (876,−145, 323, 112, 221).

Em discussões informais, é aceitável dizer “problema” quando “instância do pro-blema” seria mais correto. Em geral, entretanto, é importante manter clara a distinçãoentre os dois conceitos.

O tamanho de uma instância de um problema é a quantidade de dados necessáriapara descrever a instância. O tamanho de uma instância é descrito, em geral, por umsó número natural, mas às vezes é conveniente usar dois ou até mais números. A ideiade tamanho permite dizer que uma instância é menor ou maior que outra.

No problema da média citado acima, por exemplo, é razoável dizer que o tamanhoda instância (876,−145, 323, 112, 221) é 5 e, em geral, que o tamanho de uma instân-cia A[1 . . n] é n. (Dependendo das circunstâncias, entretanto, pode ser mais apropri-ado adotar o número total de dígitos decimais de A[1 . . n] como tamanho da instância.Nesse caso, a instância (876,−145, 323, 112, 221) terá tamanho 15 ou, se o leitor assimpreferir, 16.)

1.2 Consumo de tempo de algoritmos

Dizemos que um algoritmo resolve um problema se, ao receber a descrição de umainstância do problema, devolve uma solução da instância (ou informa que a instâncianão tem solução). Para cada instância do problema, o algoritmo consome uma quanti-dade de tempo diferente. Digamos que o algoritmo consome T (I) unidades de tempopara processar a instância I . A relação entre T (I) e o tamanho de I dá uma medida daeficiência do algoritmo.

Em geral, um problema tem muitas instâncias diferentes de um mesmo tamanho.Isto exige a introdução dos conceitos de “pior caso” e “melhor caso”. Dado um algo-ritmo A para o problema e um número natural n, seja T ∗(n) o máximo de T (I) paratodas as instâncias I de tamanho n do problema. Dizemos que

T ∗ mede o consumo de tempo de A no pior caso.

De modo análogo, seja T∗(n) o mínimo de T (I) para todas as instância I de tamanho n.Dizemos que T∗ mede o consumo de A no melhor caso.

Por exemplo, um algoritmo pode consumir 200n unidades de tempo no melhorcaso e 10n2 + 100n unidades no pior. (Estou ignorando os valores pequenos de n, paraos quais 200n é maior que 10n2 + 100n.)

Nas nossas análises, suporemos quase sempre (o Capítulo 7 é uma exceção) queuma execução de cada linha de pseudocódigo consome uma quantidade de tempo quenão depende do tamanho da instância submetida ao algoritmo. (Para isso, será neces-sário descrever os algoritmos de maneira suficientemente detalhada.) Em particular,suporemos quase sempre que o consumo de tempo das operações aritméticas (adição,multiplicação, comparação, atribuição, etc.) não depende do tamanho dos númerosenvolvidos.


1.3 Recursão e algoritmos recursivos

Muitos problemas computacionais têm a seguinte propriedade: cada solução de umainstância do problema contém soluções de instâncias menores do mesmo problema.Dizemos que tais problemas têm estrutura recursiva. Para resolver um problema dessetipo, aplique o seguinte método: se a instância dada é pequena, resolva-a diretamente(use força bruta se necessário); se a instância é grande,

1. reduza-a a uma instância menor,2. encontre uma solução S da instância menor,3. use S para construir uma solução da instância original.

A aplicação desse método produz um algoritmo recursivo.Para provar que um algoritmo recursivo está correto, basta fazer uma indução ma-

temática no tamanho das instâncias. Antes de empreender a prova, é essencial colocarno papel, de maneira precisa e completa, a relação entre o que o algoritmo recebe eo que devolve.

Exemplo 1: soma dos elementos positivos de um vetor. O seguinte algoritmorecursivo recebe um vetor A[1 . . n] de números inteiros, com n ≥ 0, e devolve a somados elementos positivos do vetor:3

SOMAPOSITIVOS (A, n)1 se n = 02 então devolva 03 senão s← SOMAPOSITIVOS (A, n− 1)4 se A[n] > 05 então devolva s + A[n]6 senão devolva s

A prova da correção do algoritmo é uma indução em n. Se n = 0, é evidente queo algoritmo dá a resposta correta. Agora tome n ≥ 1. Podemos supor, por hipótese deindução, que SOMAPOSITIVOS com argumentos A e n − 1 produz o resultado prome-tido. Portanto, no início da linha 4, s é a soma dos elementos positivos de A[1 . . n−1].A partir de s, as linhas 4 a 6 calculam corretamente a soma dos elementos positivos deA[1 . . n].

Exemplo 2: logaritmo truncado. O piso de um número não negativo x é o úniconúmero natural i tal que i ≤ x < i + 1. O piso de x é denotado por bxc. bxc

Para todo número natural n ≥ 1, o piso do logaritmo de n na base 2, denotado por lgn

blg nc, é o único número natural k tal que 2k ≤ n < 2k+1.O seguinte algoritmo recursivo recebe um número natural n ≥ 1 e devolve blg nc:

3 Usaremos a excelente notação do livro de Cormen et al. [3] para descrever algoritmos.

12 FEOFILOFF

PISODELOG (n)1 se n = 12 então devolva 03 senão devolva PISODELOG (bn/2c) + 1

Prova da correção do algoritmo: Se n = 1, é evidente que o algoritmo devolve ovalor correto de blg nc. Agora tome n ≥ 2 e seja k o número blg nc. Queremos mostrarque o algoritmo devolve k.

Como 2k ≤ n < 2k+1, temos 2k−1 ≤ n/2 < 2k. Como 2k−1 é um número natural,temos 2k−1 ≤ bn/2c < 2k e portanto blgbn/2cc = k − 1. Como bn/2c < n, podemossupor, por hipótese de indução, que o valor da expressão PISODELOG (bn/2c) é k − 1.Portanto, o algoritmo devolve k − 1 + 1 = k, como queríamos provar.

1.4 Convenções de notação

Para concluir esta introdução, estabelecemos algumas convenções de notação. Denota-remos por N o conjunto 0, 1, 2, 3, . . . dos números naturais (que coincide com o dosNinteiros não negativos). O conjunto N − 0 será denotado por N>. O conjunto dosN>

números reais será denotado por R. O conjunto dos reais não negativos e o dos reaisRestritamente positivos serão denotados por R≥ e por R> respectivamente.R≥

R>

Como já dissemos acima, o piso de um número x em R≥ é o único número i em Ntal que i ≤ x < i+ 1. O teto de x é o único número j em N tal que j− 1 < x ≤ j. O pisoe o teto de x são denotados por bxc e dxe respectivamente.dxe

Denotaremos por lg n o logaritmo de um número n na base 2. Portanto, lg n =log2 n.

Capítulo 2

Comparação assintótica de funções

É desejável exprimir o consumo de tempo de um algoritmo de uma maneira que nãodependa da linguagem de programação, nem dos detalhes de implementação, nem docomputador empregado. Para tornar isto possível, é preciso introduzir um modo gros-seiro de comparar funções. (Estou me referindo às funções — no sentido matemático dapalavra — que exprimem a dependência entre o consumo de tempo de um algoritmo eo tamanho de sua “entrada”.)

Essa comparação grosseira só leva em conta a “velocidade de crescimento” dasfunções. Assim, ela despreza fatores multiplicativos (pois a função 2n2, por exemplo,cresce tão rápido quanto 10n2) e despreza valores pequenos do argumento (a funçãon2 cresce mais rápido que 100n, embora n2 seja menor que 100n quando n é pequeno).Dizemos que esta maneira de comparar funções é assintótica.

Há três tipos de comparação assintótica: uma com sabor de “≤”, outra com saborde “≥”, e uma terceira com sabor de “=”.

2.1 Notação O

Dadas funções F e G de N em R≥, dizemos que F está em O(G) se existem c e n0 em N>

tais queF (n) ≤ c ·G(n)

para todo n ≥ n0. A mesma coisa pode ser dita assim: existe c em N> tal que F (n) ≤c ·G(n) para todo n suficientemente grande. Em lugar de “F está em O(G)”, podemosdizer “F é O(G)”, “F ∈ O(G)” e até “F = O(G)”.

Exemplo 1: 100n está em O(n2), pois 100n ≤ n · n = n2 para todo n ≥ 100.

Exemplo 2: 2n3+100n está em O(n3). De fato, para todo n ≥ 1 temos 2n3+100n ≤2n3 + 100n3 ≤ 102n3. Eis outra maneira de provar que 2n3 + 100n está em O(n3): paratodo n ≥ 100 tem-se 2n3 + 100n ≤ 2n3 + n · n · n = 3n3.

Exemplo 3: n1.5 está em O(n2), pois n1.5 ≤ n0.5n1.5 = n2 para todo n ≥ 1.

Exemplo 4: n2/10 não está em O(n). Eis uma prova deste fato. Tome qualquer c

13

14 FEOFILOFF

em N>. Para todo n > 10c temos n2/10 = n · n/10 > 10c · n/10 = cn. Logo, não éverdade que n2/10 ≤ cn para todo n suficientemente grande.

Exemplo 5: 2n está em O(2n). De fato, 2n ≤ 2n para todo n ≥ 1, como provaremospor indução em n. Prova: Se n = 1, a afirmação é verdadeira pois 2 · 1 = 21. Agoratome n ≥ 2 e suponha, a título de hipótese de indução, que 2(n − 1) ≤ 2n−1. Então2n ≤ 2(n + n − 2) = 2(n − 1) + 2(n − 1) ≤ 2n−1 + 2n−1 = 2n, como queríamosdemonstrar.

A seguinte regra da soma é útil: se F e F ′ estão ambas em O(G) então F + F ′

também está em O(G). Eis uma prova da regra. Por hipótese, existem números ce n0 tais que F (n) ≤ cG(n) para todo n ≥ n0. Analogamente, existem c′ e n′0 taisque F ′(n) ≤ c′G(n) para todo n ≥ n′0. Então, para todo n ≥ max(n0, n

′0), tem-se

F (n) + F ′(n) ≤ (c + c′)G(n).

Exemplo 6: Como 2n3 e 100n estão ambas em O(n3), a função 2n3 + 100n tambémestá em O(n3).

Nossa definição da notação O foi formulada para funções de N em R≥, mas ela podeser estendida, da maneira óbvia, a funções que não estão definidas ou são negativaspara valores pequenos do argumento.

Exemplo 7: Embora n2 − 100n não esteja em R≥ quando n < 100, podemos dizerque n2 − 100n é O(n2), pois n2 − 100n ≤ n2 para todo n ≥ 100.

Exemplo 8: Embora lg n não esteja definida quando n = 0, podemos dizer que lg nestá em O(n). De fato, se tomarmos o logaritmo da desigualdade n ≤ 2n do Exemplo 5,veremos que lg n ≤ n para todo n ≥ 1.

Exemplo 9: n lg n está em O(n2). Segue imediatamente do Exemplo 8.

Exercícios

2.1 Critique a afirmação “n2 − 100n está em O(n2) para todo n ≥ 100”.

2.2 Mostre que lg n está em O(n0.5).

2.2 Notação Ômega

Dadas funções F e G de N em R≥, dizemos que F está em Ω(G) se existe c em N> talque

F (n) ≥ 1

c·G(n)

para todo n suficientemente grande. É claro que Ω é “inversa” de O, ou seja, umafunção F está em Ω(G) se e somente se G está em O(F ).

Exemplo 10: n3 + 100n está em Ω(n3), pois n3 + 100n ≥ n3 para todo n.

A definição da notação Ω pode ser estendida, da maneira óbvia, a funções F ou Gque estão definidas e são não negativas apenas para valores grandes de n.


Exemplo 11: n2− 2n é Ω(n2). De fato, temos 2n ≤ 12n

2 para todo n ≥ 4 e portanton2 − 2n ≥ n2 − 1

2n2 = 1

2n2.

Exemplo 12: n lg n está em Ω(n). De fato, para todo n ≥ 2 tem-se lg n ≥ 1 eportanto n lg n ≥ n.

Exemplo 13: 100n não está em Ω(n2). Tome qualquer c em N>. Para todo n >100c, tem-se 100 < 1

cn e portanto 100n < 1cn

2.

Exemplo 14: n não é Ω(2n). Basta mostrar que para qualquer c em N> tem-sen < 1

c2n para todo n suficientemente grande. Como todo c é menor que alguma po-tência de 2, basta mostrar que, para qualquer k em N>, tem-se n ≤ 2−k2n para todo nsuficientemente grande. Especificamente, mostraremos que n ≤ 2n−k para todo n ≥ 2k.

A prova é por indução em n. Se n = 2k, temos k ≤ 2k−1 conforme o Exemplo 5com k no papel de n, e portanto n = 2k ≤ 2 · 2k−1 = 2k = 22k−k = 2n−k. Agora tomen ≥ 2k + 1 e suponha, a título de hipótese de indução, que n − 1 ≤ 2n−1−k. Entãon ≤ n + n − 2 = n − 1 + n − 1 = 2 · (n − 1) ≤ 2 · 2n−1−k = 2n−k, como queríamosdemonstrar.

Exercícios

2.3 Mostre que 2n−1 está em Ω(2n).

2.4 Mostre que lg n não é Ω(n).

2.3 Notação Teta

Dizemos que F está em Θ(G) se F está em O(G) e também em Ω(G), ou seja, se existemc e c′ em N> tais que

1

c·G(n) ≤ F (n) ≤ c′ ·G(n)

para todo n suficientemente grande. Se F está em Θ(G), diremos que F é proporcionala G, ainda que isto seja um tanto incorreto.

Exemplo 15: Para qualquer a em R> e qualquer b em R, a função an2 + bn estáem Θ(n2).

Exercício

2.5 Mostre que n(n + 1)/2 e n(n− 1)/2 estão em Θ(n2).

2.4 Consumo de tempo de algoritmos

Seja A um algoritmo para um problema cujas instâncias têm tamanho n. Se a funçãoque mede o consumo de tempo deA no pior caso está em O(n2), por exemplo, podemos

16 FEOFILOFF

usar expressões como

“A consome O(n2) unidades de tempo no pior caso”

e “A consome tempo O(n2) no pior caso”. Podemos usar expressões semelhantes comΩ ou Θ no lugar de O e “melhor caso” no lugar de “pior caso”.

(Se A consome tempo O(n2) no pior caso, também consome O(n2) em qualquercaso. Analogamente, se consome Ω(n2) no melhor caso, também consome Ω(n2) emqualquer caso. Mas não podemos dispensar a cláusula “no pior caso” em uma afirma-ção como “A consome tempo Ω(n2) no pior caso”.)

Linear, linearítmico, quadrático. Um algoritmo é linear se consome tempo Θ(n)no pior caso. É fácil entender o comportamento de um tal algoritmo: quando o tama-nho da “entrada” dobra, o algorimo consome duas vezes mais tempo; quando o tama-nho é multiplicado por uma constante c, o consumo de tempo também é multiplicadopor c. Algoritmos lineares são considerados muito rápidos.

Um algoritmo é linearítmico (ou ene-log-ene) se consome tempo Θ(n lg n) no piorcaso. Se o tamanho da “entrada” dobra, o consumo dobra e é acrescido de 2n; se o ta-manho é multiplicado por uma constante c, o consumo é multiplicado por c e acrescidode um pouco mais que cn.

Um algoritmo é quadrático se consome tempo Θ(n2) no pior caso. Se o tamanhoda “entrada” dobra, o consumo quadruplica; se o tamanho é multiplicado por umaconstante c, o consumo é multiplicado por c2.

Polinomial e exponencial. Um algoritmo é polinomial se consome tempo O(nk)no pior caso, sendo k um número natural. Por exemplo, é polinomial qualquer algo-ritmo que consome O(n100) unidades de tempo. Apesar desse exemplo, algoritmospolinomiais são considerados rápidos.

Um algoritmo é exponencial se consome tempo Ω(an) no pior caso, sendo a umnúmero real maior que 1. Por exemplo, é exponencial qualquer algoritmo que consomeΩ(1.1n) unidades de tempo. Se n é multiplicado por 10, por exemplo, o consumo detempo de um tal algoritmo é elevado à potência 10. Algoritmos exponenciais não sãopolinomiais.

Exercício

2.6 Suponha que dois algoritmos, A e B, resolvem um mesmo problema. Suponha que o ta-manho das instâncias do problema é medido por um parâmetro n. Em quais dos seguintescasos podemos afirmar que A é mais rápido que B? Caso 1: A consome tempo O(lg n) nopior caso e B consome tempo O(n3) no pior caso. Caso 2: A consome O(n2 lg n) unida-des de tempo no pior caso e B consome Ω(n2) unidades de tempo no pior caso. Caso 3:No pior caso, A consome O(n2) unidades de tempo e B consome Ω(n2 lg n) unidades detempo.

Capítulo 3

Solução de recorrências

A habilidade de resolver recorrências é importante para a análise do consumo de tempode algoritmos recursivos. Uma recorrência é uma fórmula que define uma função,digamos F , em termos dela mesma. Mais precisamente, define F (n) em termos deF (n− 1), F (n− 2), F (n− 3), etc.

Uma solução de uma recorrência é uma fórmula que exprime F (n) diretamente emtermos de n. Para as aplicações à análise de algoritmos, uma fórmula exata para F (n)não é necessária: basta mostrar que F está em Θ(G) para alguma função G definidaexplicitamente em termos de n.

3.1 Exemplo 1

Seja F uma função de N em R>. Suponha que F (1) = 1 e F satisfaz a recorrência

F (n) = 2F (n− 1) + 1 (3.1)

para todo n ≥ 2. Eis alguns valores da função: F (2) = 3, F (3) = 7, F (4) = 15. É fácil“desenrolar” a recorrência:

F (n) = 2F (n− 1) + 1

= 2(2F (n− 2) + 1) + 1

= 4F (n− 2) + 3

= · · ·= 2jF (n− j) + 2j − 1

= 2n−1F (1) + 2n−1 − 1 .

Concluímos assim queF (n) = 2n − 1 (3.2)

para todo n ≥ 1. (Não temos informações sobre o valor de F (0).) Portanto, F estáem Θ(2n).

17

18 FEOFILOFF

Exercícios

3.1 Confira a fórmula (3.2) por indução em n.

3.2 Sejam a, b e n0 três números naturais e suponha que F (n0) = a e F (n) = 2F (n − 1) + bpara todo n > n0. Mostre que F está em Θ(2n).

3.2 Exemplo 2

Suponha que uma função F de N em R> satisfaz a seguinte recorrência:

F (n) = F (n− 1) + n (3.3)

para todo n ≥ 2. Suponha ainda que F (1) = 1. Teremos, em particular, F (2) = F (1) +2 = 3 e F (3) = F (2) + 3 = 6.

A recorrência pode ser facilmente “desenrolada”: F (n) = F (n−1) +n = F (n−2) +(n−1)+n = · · · = F (1)+2+3+ · · ·+(n−1)+n = 1+2+3+· · ·+(n−1)+n. Concluímosassim que

F (n) = 12(n2 + n) (3.4)

para todo n ≥ 1. (Não temos informações sobre o valor de F (0).) Portanto, F estáem Θ(n2).

Recorrências semelhantes. O valor de F (1) tem pouca influência sobre o resul-tado. Se tivéssemos F (1) = 10, por exemplo, a fórmula (3.4) seria substituída porF (n) = 1

2(n2 + n) + 9, e esta função também está em Θ(n2).O ponto a partir do qual (3.3) começa a valer também tem pouca influência sobre a

solução da recorrência. Se (3.3) valesse apenas a partir de n = 5, por exemplo, teríamosF (n) = 1

2(n2 + n) + F (4)− 10 no lugar de (3.4), e esta função também está em Θ(n2).

Exercícios

3.3 Confira (3.4) por indução em n.

3.4 Suponha que F satisfaz a recorrência F (n) = F (n− 1) + 3n+ 2 para n = 2, 3, 4, . . . Mostreque se F (1) = 1 então F (n) = 3n2/2 + 7n/2 − 4 para todo n ≥ 2. Conclua que F estáem Θ(n2).

3.5 Sejam a, b e c três números naturais e suponha que F satisfaz as seguintes condições:F (n0) = a e F (n) = F (n− 1) + bn + c para todo n > n0. Mostre que F está em Θ(n2).

3.6 Suponha que F (n) = F (n − 1) + 7 para n = 2, 3, 4, . . . Mostre que se F (1) = 1 entãoF (n) = 7n− 6 para todo n ≥ 1. Conclua que F está em Θ(n).

3.3 Exemplo 3

Seja F uma função que leva N em R>. Suponha que F satisfaz a recorrência

F (n) = 2F (bn/2c) + n (3.5)


para todo n ≥ 2. (Não faz sentido trocar “bn/2c” por “n/2” pois n/2 não está em Nquando n é ímpar.) Suponha ainda que F (1) = 1 (e portanto F (2) = 4, F (3) = 5, etc.)

É mais fácil entender (3.5) quando n é uma potência de 2, pois nesse caso bn/2c sereduz a n/2. Se n = 2j , temos

F (2j) = 2F (2j−1) + 2j

= 22F (2j−2) + 212j−1 + 2j

= 23F (2j−3) + 222j−2 + 212j−1 + 2j

= 2jF (20) + 2j−121 + · · ·+ 222j−2 + 212j−1 + 202j

= 2j20 + 2j−121 + · · ·+ 222j−2 + 212j−1 + 202j

= (j + 1)2j

= j2j + 2j . (3.6)

Para ter certeza, podemos conferir esta fórmula por indução em j. Se j = 1, temosF (2j) = 4 = (j + 1)2j . Agora tome j ≥ 2. De acordo com (3.5), F (2j) = 2F (2j−1) + 2j .Por hipótese de indução, F (2j−1) = 2j−1j. Logo, F (2j) = 2 ·2j−1j+2j = 2jj+2j , comoqueríamos mostrar.

Como 2j = n, a expressão (3.6) pode ser reescrita assim:

F (n) = n lg n + n (3.7)

quando n é potência de 2. Embora esta fórmula só se aplique às potências de 2, po-demos usá-la para obter cotas superior e inferior válidas para todo n suficientementegrande. O primeiro passo nessa direção é verificar que F é crescente, ou seja, que

F (n) < F (n + 1) (3.8)

para todo n ≥ 1. A prova é uma indução em n. Se n = 1, temos F (n) = 1 < 4 =F (n + 1). Agora tome n ≥ 2. Se n é par então F (n) < F (n) + 1 = 2F (n2 ) + n + 1 =2F (bn+1

2 c)+n+1 = F (n+1), em virtude de (3.5). Agora suponha n ímpar. Por hipótesede indução, F (n−12 ) ≤ F (n−12 + 1) = F (n+1

2 ). Logo, por (3.5),

F (n) = 2F (n−12 ) + n ≤ 2F (n+12 ) + n < 2F (n+1

2 ) + n + 1 = F (n + 1) .

Mostramos assim que F é crescente.Agora podemos calcular uma boa cota superior para F a partir de (3.7). Mostrare-

mos queF (n) ≤ 6n lg n (3.9)

para todo n ≥ 2. Tome o único j em N tal que 2j ≤ n < 2j+1. Em virtude de (3.8),F (n) < F (2j+1). Em virtude de (3.6), F (2j+1) = (j + 2)2j+1 ≤ 3j2j+1 = 6j2j . Comoj ≤ lg n, temos 6j2j ≤ 6n lg n.

Uma boa cota inferior para F também pode ser calculada a partir de (3.7): mostra-remos que

F (n) ≥ 12n lg n (3.10)

20 FEOFILOFF

para todo n ≥ 2. Tome o único j em N tal que 2j ≤ n < 2j+1. Em virtude de (3.8)e (3.6), temos F (n) ≥ F (2j) = (j + 1)2j = 1

2(j + 1)2j+1. Como lg n < j + 1, temos12(j + 1)2j+1 > 1

2n lg n.De (3.9) e (3.10), concluímos que F está em Θ(n lg n).

Recorrências semelhantes. O ponto n0 a partir do qual a recorrência (3.5) começaa valer, bem como os valores de F (1), F (2), . . . , F (n0 − 1), têm pouca influência so-bre a solução da recorrência: quaisquer que sejam esses valores iniciais, F estará emΘ(n lg n). Se (3.5) vale apenas para n ≥ 3, por exemplo, teremos n lg n + F (2)−2

2 n nolugar de (3.7).

A parcela n na expressão 2F (bn/2c)+n também pode ser ligeiramente alterada semque F saia de Θ(n lg n). Assim, quaisquer que sejam c > 0 e d, se F (n) = 2F (bn/2c) +cn + d então F está em Θ(n lg n).

Finalmente, podemos trocar “2F (bn/2c)” por “2F (dn/2e)” ou até mesmo por“F (bn/2c) + F (dn/2e)” sem que F saia de Θ(n lg n).

Mas o fator 2 que multiplica “F (bn/2c)” é crítico: se este fator for alterado, a funçãoF deixará de pertencer a Θ(n lg n).

Exercícios

3.7 Suponha que um função F de N em R> satisfaz a recorrência F (n) = F (bn/2c) + 1 paratodo n ≥ 2. Mostre que F está em Θ(lg n).

3.8 Seja F uma função de N em R> tal que F (n) = 2F (bn/2c) + 1 para todo n ≥ 2. Mostre queF está em Θ(n).

3.9 Seja F um função de N em R> tal que F (n) = 4F (bn/2c) + n quando n ≥ 2. Mostre queF está em Θ(n2). Sugestão: mostre que 1

4n2 ≤ F (n) ≤ 8n2 para todo n suficientemente

grande.

3.4 Exemplo 4

Seja F um função de N em R>. Suponha que

F (n) = 3F (bn/2c) + n (3.11)

para todo n ≥ 2. Suponha ainda que F (1) = 1. Para começar a entender o comporta-mento de F , considere os valores de n que são potências de 2. Quando n = 2j , temos

F (2j) = 3F (2j−1) + 2j

= 32F (2j−2) + 312j−1 + 2j

= 33F (2j−3) + 322j−2 + 312j−1 + 2j

= 3jF (20) + 3j−121 + · · ·+ 322j−2 + 312j−1 + 302j

= 3j20 + 3j−121 + · · ·+ 322j−2 + 312j−1 + 302j


= 2j((3/2)j + (3/2)j−1 + · · ·+ (3/2)2 + (3/2)1 + (3/2)0

)= 2j

(3/2)j+1 − 1

3/2− 1

= 2j+1((3/2)j+1 − 1

)= 3j+1 − 2j+1 . (3.12)

Observe que 3j = (2lg 3)j = (2j)lg 3 = nlg 3. (A título de curiosidade, lg 3 fica entre 1.584e 1.585.) Portanto, a fórmula (3.12) pode ser reescrita assim:

F (n) = 3nlg 3 − 2n

para toda potência n de 2. Embora esta fórmula só valha para as potências de 2, po-demos usá-la para obter cotas superior e inferior válidas para todo n suficientementegrande. A primeira providência nessa direção é certificar-se de que F é crescente:

F (n) < F (n + 1)

para todo n ≥ 1. A prova é análoga à de (3.8). Agora estamos em condições de calcularuma boa cota superior para F :

F (n) ≤ 9nlg 3 (3.13)

para todo n ≥ 1. Tome j em N tal que 2j ≤ n < 2j+1. Como F é crescente, (3.12) garanteque F (n) < F (2j+1) = 3j+2 − 2j+2 ≤ 3j+2 = 9 · (2j)lg 3 ≤ 9nlg 3, como queríamosmostrar. Também podemos calcular uma boa cota inferior:

F (n) ≥ 13n

lg 3 (3.14)

para todo n ≥ 1. Tome j em N tal que 2j ≤ n < 2j+1. Como F é crescente, (3.12) garanteque F (n) ≥ F (2j) = 3j+1−2j+1 = 3j +2 ·3j−2 ·2j ≥ 3j = 1

33j+1 = 13(2j+1)lg 3 > 1

3nlg 3,

como queríamos demonstrar.As relações (3.13) e (3.14) mostram que F está em Θ(nlg 3).

Recorrências semelhantes. Se (3.11) valesse apenas quando n ≥ n0, a função Fcontinuaria em Θ(nlg 3) quaisquer que fossem os valores de F (bn0/2c), F (bn0/2c + 1),. . . , F (n0 − 1).

Além disso, F continuará em Θ(nlg 3) se (3.11) for substituída por F (n) =3F (bn/2c) + cn + d, quaisquer que sejam c > 0 e d. Também continuará em Θ(nlg 3) se“3F (bn/2c)” for trocado por “2F (bn/2c) + F (dn/2e)” ou até mesmo por “2F (bn/2c) +F (dn/2e+ 1)”.

Exercício

3.10 Confira a formula (3.12) por indução em j.

22 FEOFILOFF

3.5 Teorema mestre

O seguinte teorema dá a solução de muitas recorrências semelhantes às das Seções 3.3e 3.4. Sejam a, k e c números em N>, N e R> respectivamente. Seja F uma função de Nem R> tal que

F (n) = aF(n

2

)+ cnk (3.15)

para n = 21, 22, 23, . . . Suponha ainda que F é assintoticamente não decrescente, ouseja, que existe n1 tal que F (n) ≤ F (n + 1) para todo n ≥ n1. Nessas condições,

se lg a > k então F está em Θ(nlg a), (3.16)se lg a = k então F está em Θ(nk lg n), (3.17)se lg a < k então F está em Θ(nk). (3.18)

(Recorrências como (3.15) aparecem na análise de algoritmos baseados na estraté-gia da divisão e conquista: dada uma instância de tamanho n, divida a instância em apartes de tamanho n/2, resolva essas subinstâncias, e combine as soluções em tempolimitado por cnk.)

Generalização. O teorema pode ser generalizado como segue. Sejam a ≥ 1, b ≥ 2,k ≥ 0 e n0 ≥ 1 números em N e seja c um número em R>. Seja F é uma função de Nem R> tal que

F (n) = aF(nb

)+ cnk (3.19)

para n = n0b1, n0b

2, n0b3, . . . Suponha ainda que F é assintoticamente não decrescente.

Nessas condições,

se lg a/ lg b > k então F está em Θ(nlg a/ lg b), (3.20)se lg a/ lg b = k então F está em Θ(nk lg n), (3.21)se lg a/ lg b < k então F está em Θ(nk). (3.22)

A prova deste teorema pode ser encontrada na Seção 4.7 do livro de Brassard eBratley [2] e na Seção 4.4 do livro de Cormen et al. [3].

Exemplo A. Seja c um número em R> e seja F uma função de N em R> tal queF (n) = F (bn/2c) + 2F (dn/2e) + cn para todo n ≥ 2. Nessas condições, F é não decres-cente e portanto (3.16) garante que F está em Θ(nlg 3). (Compare com o resultado daSeção 3.4.)

Exemplo B. Sejam a e k números em N tais que a > 2k e seja c um número em R>.Seja F é uma função de N em R> tal que F (n) = aF

(bn/2c

)+ cnk para todo n ≥ 1.

Nessas condições, F é não decrescente e portanto (3.16) garante que F está em Θ(nlg a).


Notas bibliográficas

Este capítulo foi baseada na Seção 4.7 do livro de Brassard e Bratley [2]. Veja também overbete Master theorem na Wikipedia.

http://en.wikipedia.org/wiki/Master_theorem

24 FEOFILOFF

Capítulo 4

Ordenação de vetor

Um vetor A[p . . r] é crescente se A[p] ≤ A[p + 1] ≤ · · · ≤ A[r]. A tarefa de colocarum vetor em ordem crescente é um dos problemas computacionais mais conhecidos ebem-estudados.

Problema da Ordenação: Rearranjar um vetor A[p . . r] em ordem crescente.

4.1 Algoritmo Mergesort

O seguinte algoritmo é uma solução eficiente do Problema da Ordenação:

MERGESORT (A, p, r)1 se p < r2 então q ← b(p + r)/2c3 MERGESORT (A, p, q)4 MERGESORT (A, q+1, r)5 INTERCALA (A, p, q, r)

A rotina INTERCALA rearranja o vetor A[p . . r] em ordem crescente supondo que ossubvetores A[p . . q] e A[q+1 . . r] são ambos crescentes.

O algoritmo está correto. Adote o número n := r − p + 1 como tamanho da ins-tância (A, p, r) do problema. Se n ≤ 1, o vetor tem no máximo 1 elemento e portantonão fazer nada é a ação correta. Suponha agora que n ≥ 2. Nas linhas 3 e 4, o algo-ritmo é aplicado a instâncias do problema que têm tamanho estritamente menor que n(tamanho dn/2e na linha 3 e tamanho bn/2c na linha 4). Assim, podemos supor, porhipótese de indução, que no início da linha 5 os vetores A[p . . q] e A[q+1 . . r] estão emordem crescente. Graças à ação de INTERCALA, A[p . . r] estará em ordem crescente nofim da linha 5.

25

26 FEOFILOFF

p q q+1 r

111 333 555 555 777 888 222 444 777 999 999

Figura 4.1: Vetor A no início da linha 5 do algoritmo.

Consumo de tempo. Seja T (n) o tempo que o algoritmo consome, no pior caso,para processar uma instância de tamanho n. Então

T (n) = T (dn/2e) + T (bn/2c) + n .

As parcelas T (dn2 e) e T (bn2 c) correspondem às linhas 3 e 4. A parcela n representa oconsumo de tempo da linha 5, uma vez que o algoritmo INTERCALA pode ser imple-mentado de maneira a consumir tempo proporcional a n. (Veja o Exercício 4.1 abaixo.)Como vimos nas Seções 3.3 e 3.5, a função T está em

Θ(n lg n) .

O consumo de tempo do algoritmo no melhor caso também está em Θ(n lg n).

Exercício

4.1 Descreva em pseudocódigo o algoritmo INTERCALA mencionado acima. Mostre que oconsumo de tempo do algoritmo é Θ(n).

4.2 Divisão e conquista

O algoritmo MERGESORT emprega a estratégia da divisão e conquista: a instância origi-nal do problema é dividida em duas instâncias menores, essas instâncias são resolvidasrecursivamente, e as soluções são combinadas para produzir uma solução da instânciaoriginal.

O segredo do sucesso está no fato de que o processo de divisão (que está na linha 2,nesse caso) e o processo da combinação (que acontece na linha 5) consomem poucotempo.

A estratégia da divisão e conquista rende algoritmos eficientes para muitos proble-mas. Veremos exemplos nos capítulos seguintes.

Capítulo 5

Segmento de soma máxima

Imagine uma grandeza que evolui com o tempo, aumentando ou diminuindo uma vezpor dia, de maneira irregular. Dado o registro das variações diárias desta grandezaao longo de um ano, queremos encontrar um intervalo de tempo em que a variaçãoacumulada tenha sido máxima. Este capítulo, inspirado no livro de Bentley [1], estudatrês algoritmos para o problema. Cada algoritmo é mais eficiente que o anterior; cadaalgoritmo usa uma estratégia diferente.

5.1 O problema

Um segmento de um vetor A[p . . r] é qualquer subvetor da forma A[i . . k], com p ≤ i ≤k ≤ r. A condição i ≤ k garante que o segmento não é vazio.1 A soma de um segmentoA[i . . k] é o número A[i] + A[i + 1] + · · ·+ A[k].

A solidez de um vetor A[p . . r] é a soma de um segmento de soma máxima. (Otermo “solidez” é apenas uma conveniência local e não será usado fora deste capítulo.)

Problema do Segmento de Soma Máxima: Calcular a solidez de um vetorA[p . . r] de números inteiros.

Se o vetor não tem elementos negativos, sua solidez é a soma de todos os elementos.Por outro lado, se todos os elementos são negativos então a solidez do vetor é o valorde seu elemento menos negativo.

20 −30 15 −10 30 −20 −30 30

Figura 5.1: A cor mais clara destaca um segmento de soma máxima.A solidez do vetor é 35.

1 Teria sido mais “limpo” e natural aceitar segmentos vazios. Mas a discussão fica ligeiramente maissimples se nos limitarmos aos segmentos não vazios.

27

28 FEOFILOFF

5.2 Primeiro algoritmo

Se aplicarmos cegamente a definição de solidez, teremos que examinar todos os paresordenados (i, j) tais que p ≤ i ≤ j ≤ r. Esse algoritmo consumiria Θ(n3) unidades detempo. Mas é possivel fazer algo mais eficiente:

SOLIDEZI (A, p, r)

1 x← A[r]2 para q ← r − 1 decrescendo até p faça3 s← 04 para j ← q até r faça5 s← s + A[j]6 se s > x então x← s7 devolva x

O algoritmo está correto. A cada passagem pela linha 2, imediatamente antes dacomparação de q com p,

x é a solidez do vetor A[q+1 . . r].

Este invariante mostra que o algoritmo está correto, pois na última passagem pela li-nha 2 teremos q = p− 1 e então x será a solidez do A[p . . r].

Consumo de tempo. Adote n := r− p+ 1 como medida do tamanho da instânciaA[p . . r] do nosso problema. O consumo de tempo do algoritmo será medido em relaçãoa n.

Podemos supor que uma execução de qualquer das linhas do algoritmo consomeuma quantidade de tempo que não depende de n. Para cada valor fixo de q, o bloco delinhas 5-6 é repetido r − q + 1 vezes. Como q decresce de r − 1 até p, o número total derepetições do bloco de linhas 5-6 é

r−1∑q=p

(r − q + 1) = n + (n− 1) + · · ·+ 3 + 2 = 12(n2 + n− 2) .

Portanto, o consumo de tempo está em Θ(n2), tanto no pior quanto no melhor caso.O algoritmo é ineficiente porque a soma de cada segmento é recalculada muitas ve-

zes. Por exemplo, a soma de A[10 . . r] é refeita durante o cálculo das somas de A[9 . . r],A[8 . . r], etc. O algoritmo da próxima seção procura remediar esta ineficiência.

Exercícios

5.1 Modifique o algoritmo SOLIDEZI de modo que ele devolva um par (i, k) de índices tal quea soma A[i] + · · ·+ A[k] é a solidez de A[p . . r].

5.2 Escreva um algoritmo análogo a SOLIDEZI para tratar da variante do problema que admitesegmentos vazios. Nessa variante, um segmento A[i . . k] é vazio se i = k + 1. A soma deum segmento vazio é 0.


5.3 Segundo algoritmo: divisão e conquista

Nosso segundo algoritmo usa a estratégia da divisão e conquista (veja a Seção 4.2),que consiste em dividir a instância dada ao meio, resolver cada uma das metades efinalmente juntar as duas soluções. O algoritmo devolve a solidez do vetor A[p . . r]supondo p ≤ r:

SOLIDEZII (A, p, r)

1 se p = r2 então devolva A[p]3 senão q ← b(p + r)/2c4 x′ ← SOLIDEZII (A, p, q)5 x′′ ← SOLIDEZII (A, q + 1, r)6 y′ ← s← A[q]7 para i← q − 1 decrescendo até p faça8 s← A[i] + s9 se s > y′ então y′ ← s

10 y′′ ← s← A[q + 1]11 para j ← q + 2 até r faça12 s← s + A[j]13 se s > y′′ então y′′ ← s14 x← max (x′, y′ + y′′, x′′)15 devolva x

O algoritmo está correto. Seja n := r − p + 1 o número de elementos do vetorA[p . . r]. Se n = 1, é claro que a resposta do algoritmo está correta. Suponha agora quen ≥ 2. Depois da linha 4, por hipótese de indução, x′ é a solidez de A[p . . q]. Depois dalinha 5, x′′ é a solidez de A[q+1 . . r]. Depois do bloco de linhas 6-13, y′ + y′′ é a maiorsoma da forma A[i] + · · ·+ A[j] com i ≤ q < j. (Veja o Exercício 5.3.)

Em suma, y′ + y′′ cuida dos segmentos que contêm A[q] e A[q+1], enquanto x′ e x′′

cuidam de todos os demais segmentos. Concluímos assim que o número x calculadona linha 14 é a solidez de A[p . . r].

p q q+1 r

20 −30 15 −10 30 −20 −30 30

Figura 5.2: Início da linha 14 do algoritmo SOLIDEZII.Nesse ponto, x′ = 20, x′′ = 30, y′ = 5 e y′′ = 30.

Consumo de tempo. Seja T (n) o consumo de tempo do algoritmo no pior casoquando aplicado a um vetor de tamanho n. O bloco de linhas 6 a 13 examina todos os

30 FEOFILOFF

elementos de A[p . . r] e portanto consome tempo proporcional a n. Temos então

T (n) = T (dn/2e) + T (bn/2c) + n .

A parcela T (dn/2e) descreve o consumo da linha 4 e a parcela T (bn/2c) descreve o con-sumo da linha 5. Esta recorrência já foi discutida nas Seções 3.3 e 3.5, onde mostramosque T está em

Θ(n lg n) .

O algoritmo SOLIDEZII é mais eficiente que SOLIDEZI pois n lg n é O(n2) enquanton2 não é O(n lg n). Mas SOLIDEZII tem suas próprias ineficiências, pois refaz algunscálculos diversas vezes (por exemplo, a soma de A[i . . q] nas linhas 6-9 já foi calculadadurante a execução da linha 4). A próxima seção procura eliminar estas ineficiências.

Exercício

5.3 Prove que depois do bloco de linhas 6-13 do algoritmo SOLIDEZII, y′ + y′′ é a maior somadentre todas as que têm a forma A[i] + · · ·+ A[j] com i ≤ q < j.

5.4 Terceiro algoritmo: programação dinâmica

Nosso terceiro algoritmo usa a técnica da programação dinâmica, que consiste em ar-mazenar os resultados de cálculos intermediários numa tabela para evitar que eles se-jam repetidos.

Mas a técnica não pode ser aplicada diretamente ao nosso problema. Será precisotratar do seguinte problema auxiliar, que restringe a atenção aos segmentos terminaisdo vetor: dado um vetor A[p . . r], encontrar a maior soma da forma

A[i] + · · ·+ A[r] ,

com p ≤ i ≤ r. Para facilitar a discussão, diremos que a maior soma desta forma éa firmeza do vetor A[p . . r]. A solidez do vetor é o máximo das firmezas de A[p . . r],A[p . . r−1], A[p . . r−2], etc.

A firmeza do vetor tem uma propriedade recursiva que a solidez não tem. Suponhaque A[i]+· · ·+A[r] é a firmeza de A[p . . r]. Se i ≤ r−1 então A[i]+· · ·+A[r−1] é a firmezade A[p . . r−1]. (De fato, se A[p . . r−1] tivesse firmeza maior então existiria h ≤ r− 1 talque A[h] + · · · + A[r−1] > A[i] + · · · + A[r−1] e portanto teríamos A[h] + · · · + A[r] >A[i] + · · ·+ A[r], o que é impossível.)

Se denotarmos a firmeza de A[p . . q] por F [q], podemos resumir a propriedade re-cursiva por meio de uma recorrência: para qualquer vetor A[p . . r],

F [r] = max(F [r−1] + A[r] , A[r]

). (5.1)

Em outras palavras, F [r] = F [r− 1] +A[r] e menos que F [r− 1] seja negativo, caso emque F [r] = A[r].

A recorrência (5.1) serve de base para o seguinte algoritmo, que calcula a solidezde A[p . . r] supondo p ≤ r:


SOLIDEZIII (A, p, r)

1 F [p]← A[p]2 para q ← p + 1 até r faça3 se F [q − 1] > 04 então F [q]← F [q−1] + A[q]5 senão F [q]← A[q]6 x← F [p]7 para q ← p + 1 até r faça8 se F [q] > x então x← F [q]9 devolva x

O algoritmo está correto. A cada passagem pela linha 2, imediatamente antes queq seja comparado com r, F [q − 1] é a firmeza de A[p . . q−1]. Mais que isso,

F [j] é a firmeza de A[p . . j] (5.2)

para j = q−1, q−2, . . . , p+1, p. Logo, no início da linha 6, o fato (5.2) vale para j = p,p + 1, . . . , r.

O bloco de linhas 6-8 escolhe a maior das firmezas. Portanto, no fim do algoritmo,x é a solidez de A[p . . r].

Consumo de tempo. O algoritmo consome tempo proporcional ao número deelementos n := r − p + 1 do vetor. O consumo de tempo do algoritmo está em

Θ(n)

e o algoritmo é, portanto, linear.

p r

A 20 −30 15 −10 30 −20 −30 30

F 20 −10 15 5 35 15 −15 30

Figura 5.3: Vetores A e F no fim da execução do algoritmo SOLIDEZIII.

Exercícios

5.4 Os dois processos iterativos de SOLIDEZIII podem ser fundidos num só, evitando-se assimo uso do vetor F [p . . r]. Uma variável f pode fazer o papel de um elemento genérico dovetor F . Implemente essa ideia.

5.5 Suponha dada uma matriz A[1 . . n, 1 . . n] de números inteiros (nem todos não negativos).Encontrar uma submatriz quadrada de A que tenha soma máxima. (Veja o livro de Ben-tley [1, p.84].)

32 FEOFILOFF

5.5 Observações sobre programação dinâmica

O algoritmo SOLIDEZIII é um exemplo de programação dinâmica.2 A técnica só seaplica a problemas dotados de estrutura recursiva: qualquer solução de uma instânciadeve conter soluções de instâncias menores. Assim, o ponto de partida de qualqueralgoritmo de programação dinâmica é uma recorrência.

A característica distintiva da programação dinâmica é a tabela que armazena as so-luções das várias subinstâncias da instância original. (No nosso caso, trata-se da tabelaF [p . . r].) O consumo de tempo do algoritmo é, em geral, proporcional ao tamanho databela.

Os Capítulos 8, 9 e 10 exibem outros exemplos de programação dinâmica.


Este capítulo foi baseado no livro de Bentley [1].

2 Aqui, a palavra programação não tem relação direta com programação de computadores. Ela significaplanejamento e refere-se à construção da tabela que armazena os resultados intermediários usados paracalcular a solução do problema.

Capítulo 6

O problema da maioria

Imagine uma eleição com muitos candidatos e muitos eleitores. Como é possível deter-minar, em tempo proporcional ao número de eleitores, se algum dos candidatos obtevea maioria1 dos votos?

6.1 O problema

Seja A[1 . . n] um vetor de números naturais. Para qualquer número x, a cardinalidadedo conjunto i : 1 ≤ i ≤ n, A[i] = x é o número de ocorrências de x em A[1 . . n].Diremos que x é um valor majoritário de A[1 . . n] se o número de ocorrências de xem A[1 . . n] é maior que n/2. Assim, um valor majoritário ocorre exatamente 1

2(n + y)vezes, sendo y um número natural não nulo que é par se n é par e ímpar de n é impar.

Problema da Maioria: Encontrar um valor majoritário em um dado vetorA[1 . . n].

Nem todo vetor tem um valor majoritário. Mas se um valor majoritário existe, eleé único.

Poderíamos ordenar o vetor A[1 . . n], contar o número de ocorrências de cada ele-mento, e verificar se alguma dessas contagens supera n/2. A ordenação do vetor con-some Ω(n lg n) unidades de tempo se usarmos o algoritmo MERGESORT (veja o Capí-tulo 4).2 As contagens no vetor ordenado consomem Ω(n). Portanto, o algoritmo todoconsumirá Ω(n lg n) unidades de tempo. À primeira vista, parece ímpossível resolvero problema em menos tempo.3 Mas existe um algoritmo que consome apenas O(n)unidades de tempo, como mostraremos a seguir.

1 A popular expressão “metade dos votos mais um” é incorreta pois a metade de um número ímparnão é um número inteiro.

2 Sabe-se que todo algoritmo baseado em comparações consome Ω(n lgn) unidades tempo.3 Se o número de possíveis valores de A[1 . . n] fosse pequeno, conhecido a priori e independente de n,

poderíamos usar um algoritmo do tipo bucket sort, que consome O(n) unidades de tempo.

33

34 FEOFILOFF

44 33 11 22 33 22 22 33 22 22 22 22

Figura 6.1: Este vetor tem um valor majoritário?

6.2 Um algoritmo linear

Um algoritmo eficiente para o problema começa com a seguinte observação: se A[1 . . n]tem um valor majoritário e se A[n − 1] 6= A[n] então A[1 . . n−2] também tem um va-lor majoritário. (A observação se aplica igualmente a quaisquer dois elementos: seA[i] 6= A[j] e A tem um valor majoritário então o vetor que se obtém pela eliminaçãodas posições i e j também tem um valor majoritário.) Embora a intuição aceite estaobservação como verdadeira, sua demonstração exige algum cuidado (veja a prova dacorreção do algoritmo abaixo).

A recíproca da observação não é verdadeira. Por exemplo, (2, 5, 5, 1, 3) não temvalor majoritário, mas se retirarmos os dois últimos elementos então 5 passará a serum valor majoritário.

Eis outra observação simples mas importante: para qualquer k no intervalo 1 . . n,um número x é valor majoritário de A[1 . . n] se e somente se x é majoritário emA[1 . . k−1] ou em A[k . . n] ou em ambos. (É possível, entretanto, que A[1 . . k−1] eA[k . . n] tenham valores majoritários sem que A[1 . . n] tenha um valor majoritário.)

Usaremos as duas observações para obter um bom candidato a valor majoritário.Um bom candidato é um número x com a seguinte propriedade: se o vetor tem umvalor majoritário então x é esse valor. É fácil verificar se um bom candidato é, de fato,majoritário: basta percorrer o vetor e contar o número de ocorrências do candidato. Adificuldade está em obter um bom candidato em tempo O(n).

O seguinte algoritmo recebe um vetor A[1 . . n] de números naturais, com n ≥ 1,e devolve um valor majoritário se tal existir. Se o vetor não tem valor majoritário,devolve −1 (note que o vetor não tem elementos negativos):

MAJORITÁRIO (A, n)

1 x← A[1]2 y ← 13 para m← 2 até n faça4 se y ≥ 15 então se A[m] = x6 então y ← y + 17 senão y ← y − 18 senão x← A[m]9 y ← 1


10 c← 011 para m← 1 até n faça12 se A[m] = x13 então c← c + 114 se c > n/215 então devolva x16 senão devolva −1

O algoritmo está correto. A cada passagem pela linha 3, imediatamente antes dacomparação de m com n, temos os seguintes invariantes:

i. y ≥ 0 eii. existe k no intervalo 1 . .m−1 tal que A[1 . . k−1] não tem valor majoritário

e x ocorre exatamente 12 (m− k + y) vezes em A[k . .m−1].

(Note que m − k é o número de elementos de A[k . .m−1].) A validade de i é óbvia.A validade de ii pode ser verificada como segue. No início da primeira iteração, oinvariante ii vale com k = 1. Suponha agora que ii vale no início de uma iteraçãoqualquer. Seja k um índice com as propriedades asseguradas por ii. Se y ≥ 1 entãoo invariante vale no início da próxima iteração com o mesmo k da iteração corrente,quer A[m] seja igual a x, quer seja diferente. Suponha agora que y = 0. Como onúmero de ocorrências de x em A[k . .m] é exatamente 1

2 (m− k), o vetor A[k . .m] nãotem valor majoritário. Como A[1 . . k−1] também não tem valor majoritário, A[1 . .m]não tem valor majoritário. Assim, no início da próxima iteração, o invariante ii valerácom k = m− 1.

Na última passagem pela linha 3 temos m = n + 1 e portanto existe k no intervalo1 . . n tal que A[1 . . k−1] não tem valor majoritário e x ocorre exatamente 1

2 (n−k+1+y)vezes em A[k . . n]. Suponha agora que A[1 . . n] tem um valor majoritário a. ComoA[1 . . k−1] não tem valor majoritário, a é majoritário em A[k . . n]. Portanto, a = x ey ≥ 1. Concluímos assim que, no começo da linha 10,

x é um bom candidato.

As linhas 10 a 13 verificam se x é de fato majoritário.

Consumo de tempo. É razoável supor que o consumo de tempo de uma execu-ção de qualquer das linhas do algoritmo é constante, ou seja, não depende de n. Assim,podemos estimar o consumo de tempo total contando o número de execuções das di-versas linhas.

O bloco de linhas 4-9 é executado n− 1 vezes. O bloco de linhas 12-13 é executadon vezes. As linhas 1 e 2 e o bloco de linhas 14-16 é executado uma só vez. Portanto, oconsumo de tempo total do algoritmo está em

Θ(n)

(tanto no melhor quanto no pior caso). O algoritmo é linear.

36 FEOFILOFF

Como se vê, a análise do consumo de tempo do algoritmo é muito simples. Adificuldade do problema está em inventar um algoritmo que seja mais rápido que oalgoritmo óbvio.


Este capítulo foi baseado nos livros de Bentley [1] e Manber [14].

Capítulo 7

Multiplicação de números naturais

Quanto tempo é necessário para multiplicar dois números naturais? Se os números têmm e n dígitos respectivamente, o algoritmo usual consome tempo proporcional a mn.No caso m = n, o consumo de tempo é, portanto, proporcional a n2.

É difícil imaginar um algoritmo mais rápido que o usual se m e n forem pequenos(menores que duas ou três centenas, digamos). Mas existe um algoritmo que é bemmais rápido quando m e n são grandes (como acontece em criptografia, por exemplo).

7.1 O problema

Usaremos notação decimal para representar números naturais. (Poderíamos igual-mente bem usar notação binária, ou notação base 232, por exemplo.) Diremos que umdígito é qualquer número menor que 10. Diremos que um número natural u tem ndígitos1 se u < 10n. Com esta convenção, podemos nos restringir, sem perder genera-lidade, ao caso em que os dois multiplicandos têm o mesmo número de dígitos:

Problema da Multiplicação: Dados números naturais u e v com n dígitos cada,calcular o produto u · v.

Você deve imaginar que cada número natural é representado por um vetor de dígi-tos. Mas nossa discussão será conduzida num nível de abstração alto, sem manipulaçãoexplícita desse vetor. (Veja a Seção 7.5.)

7.2 O algoritmo usual

Preliminarmente, considere a operação de adição. Sejam u e v dois números naturaiscom n dígitos cada. A soma u+v tem n+1 dígitos e o algoritmo usual de adição calculau + v em tempo proporcional a n.

Considere agora o algoritmo usual de multiplicação de dois números u e v com n

1 Teria sido melhor dizer “tem no máximo n dígitos”.

37

38 FEOFILOFF

dígitos cada. O algoritmo tem dois passos. O primeiro passo calcula todos os n produ-tos de u por um dígito de v (cada um desses produtos tem n + 1 dígitos). O segundopasso do algoritmo desloca para a esquerda, de um número apropriado de casas, cadaum dos n produtos obtidos no primeiro passo e soma os n números resultantes. Oproduto u · v tem 2n dígitos.

O primeiro passo do algoritmo consome tempo proporcional a n2. O segundo passotambém consome tempo proporcional a n2. Assim, o consumo de tempo do algoritmousual de multiplicação está em Θ(n2).

9 9 9 9 A7 7 7 7 B

6 9 9 9 3 C6 9 9 9 3 D

6 9 9 9 3 E6 9 9 9 3 F

7 7 7 6 2 2 2 3 G

Figura 7.1: Algoritmo usual de multiplicação de dois números naturais. Aqui es-tamos multiplicando 9999 por 7777 para obter o produto 77762223. A linha C é oresultado da multiplicação da linha A pelo dígito menos significativo da linha B. Aslinhas D, E e F são definidas de maneira semelhante. A linha G é o resultado da somadas linhas C a F.

Exercício

7.1 Descreva o algoritmo usual de adição em pseudocódigo. O algoritmo deve receber núme-ros u e v com n dígitos cada e devolver a soma u + v.

7.2 Descreva algoritmo usual de multiplicação em pseudocódigo. O algoritmo deve recebernúmeros u e v com n dígitos cada e devolver o produto u · v.


Sejam u e v dois números com n dígitos cada. Suponha, por enquanto, que n é par. Sejap o número formado pelos n/2 primeiros dígitos de u e seja q o número formado pelosn/2 últimos dígitos de u. Assim,

u = p · 10n/2 + q .

Defina r e s analogamente para v, de modo que v = r · 10n/2 + s. Teremos então

u · v = p · r · 10n + (p · s + q · r) · 10n/2 + q · s . (7.1)

Esta expressão reduz a multiplicação de dois números com n dígitos cada a quatromultiplicações (a saber, p por r, p por s, q por r e q por s) de números com n/2 dígitos


cada.2

Se n for uma potência de 2, o truque pode ser aplicado recursivamente a cada umadas quatro multiplicações menores. O resultado é o seguinte algoritmo recursivo, querecebe números naturais u e v com n dígitos cada e devolve o produto u · v:

RASCUNHO (u, v, n)

1 se n = 12 então devolva u · v3 senão m← n/24 p← bu/10mc5 q ← u mod 10m

6 r ← bv/10mc7 s← v mod 10m

8 pr ← RASCUNHO (p, r, m)9 qs ← RASCUNHO (q, s, m)

10 ps ← RASCUNHO (p, s, m)11 qr ← RASCUNHO (q, r, m)12 x← pr · 102m + (ps + qr) · 10m + qs13 devolva x

O algoritmo está correto. É claro que o algoritmo produz o resultado corretose n = 1. Suponha agora que n ≥ 2. Como m < n, podemos supor, por hipótesede indução, que a linha 8 produz o resultado correto, ou seja, que pr = p · r. Analoga-mente, podemos supor que qs = q · s, ps = p · s e qr = q · r no início da linha 12. Alinha 12 não faz mais que implementar (7.1). Portanto, x = u · v.

Consumo de tempo. As linhas 4 a 7 envolvem apenas o deslocamento de casasdecimais, podendo portanto ser executadas em não mais que n unidades de tempo. Asmultiplicações por 102m e 10m na linha 12 também consomem no máximo n unidadesde tempo, pois podem ser executadas com um mero deslocamento de casas decimais.As adições na linha 12 consomem tempo proporcional ao número de dígitos de x, iguala 2n.

Portanto, se denotarmos por T (n) o consumo de tempo do algoritmo no pior caso,teremos

T (n) = 4T (n/2) + n . (7.2)

As quatro parcelas T (n/2) se referem às linhas 8 a 11 e a parcela n se refere ao consumodas demais linhas. Segue daí que T está em Θ(n2), como já vimos no Exercício 3.9.Assim, o algoritmo RASCUNHO não é mais eficiente que o algoritmo usual de multipli-cação.

2 Minha calculadora de bolso não é capaz de exibir/armazenar números que tenham mais que n dí-gitos. Para calcular o produto de dois números com n dígitos cada, posso recorrer à equação (7.1): uso amáquina para calcular os quatro produtos e depois uso lápis e papel para fazer as três adições.

40 FEOFILOFF

99998888 u77776666 v

9999 p8888 q

7777 r6666 s

77762223 pr59247408 qs

135775310 ps + qr

7777580112347408 x

Figura 7.2: Multiplicação de u por v calculada pelo algoritmo RASCUNHO. Nesteexemplo temos n = 8. O resultado da operação é x.

7.4 Algoritmo de Karatsuba

Para tornar o algoritmo da seção anterior muito mais rápido, basta observar que os trêsnúmeros de que precisamos do lado direito de (7.1) — a saber, p · r, (p · s+ q · r) e q · s —podem ser obtidos com apenas três multiplicações. De fato,

p · s + q · r = y − p · r − q · s ,

sendo y = (p + q) · (r + s). Assim, a equação (7.1) pode ser substituída por

u · v = p · r · 10n + (y − p · r − q · s) · 10n/2 + q · s . (7.3)

(É bem verdade que (7.3) envolve duas adições e duas subtrações adicionais, mas essasoperações consomem muito menos tempo que as multiplicações.) Se n não é par, bastatrocar n/2 por dn/2e: teremos u = p · 10dn/2e + q e v = r · 10dn/2e + s e portanto

u · v = p · r · 102dn/2e + (y − p · r − q · s) · 10dn/2e + q · s .

Segue daí o seguinte algoritmo de Karatsuba, que recebe números naturais u e v comn dígitos cada e devolve o produto u · v:

KARATSUBA (u, v, n)

1 se n ≤ 32 então devolva u · v3 senão m← dn/2e4 p← bu/10mc5 q ← u mod 10m

6 r ← bv/10mc7 s← v mod 10m

8 pr ← KARATSUBA (p, r, m)9 qs ← KARATSUBA (q, s, m)

10 y ← KARATSUBA (p + q, r + s, m+1)11 x← pr · 102m + (y − pr − qs) · 10m + qs12 devolva x


O algoritmo está correto. A prova da correção do algoritmo é análoga à provada correção do algoritmo RASCUNHO. As instâncias em que n vale 1, 2 ou 3 devem sertratadas na base da recursão porque o algoritmo é aplicado, na linha 10, a uma instânciade tamanho dn/2e+ 1, e este número só é menor que n quando n > 3.

Consumo de tempo. Seja T (n) o consumo de tempo do algoritmo KARATSUBA

no pior caso. Então

T (n) = 2T (dn/2e) + T (dn/2e+ 1) + n . (7.4)

As duas parcelas T (dn/2e) e a parcela T (dn/2e+1) se referem às linhas 8, 9 e 10 respec-tivamente. A parcela n representa o consumo de tempo das demais linhas.

Como sugerimos na Seção 3.5, a função T está na mesma classe assintótica que afunção T ′ que satisfaz a recorrência T ′(n) = 3T ′(bn/2c)+n. De acordo com a Seção 3.4,T ′ está em Θ(nlg 3). Portanto

T está em Θ(nlg 3) . (7.5)

Como lg 3 < 1.6, o algoritmo KARATSUBA é mais rápido que o algoritmo usual. (Ob-serve que nlg 3 é apenas um pouco maior que n

√n.) Mas, em virtude da constante

multiplicativa escondida sob a notação Θ, esta superioridade só se manifesta quandon é maior que algumas centenas.

999988888 u077766666 v

07769223 pr5925807408 qs

98887 p + q67443 r + s

6669235941 y735659310 y − pr − qs

077765801856807408 x

Figura 7.3: Multiplicação de u por v calculada pelo algoritmo KARATSUBA. O resul-tado da operação é x. Se u e v tivessem n dígitos cada, pr e qs teriam n+1 dígitos cada,y teria n + 2 (mais precisamente, só n + 1) dígitos e x teria 2n dígitos.

7.5 Detalhes de implementação

Para implementar os algoritmos que discutimos acima, é preciso representar cada nú-mero por um vetor de dígitos, ou seja, um vetor U [1 . . n] cujos componentes pertencemao conjunto 0, 1, . . . , 9. Um tal vetor representa o número natural U [n] · 10n−1 +U [n−1] · 10n−2 + · · ·+ U [2] · 10 + U [1].

O algoritmo KARATSUBA recebe os vetores U [1 . . n] e V [1 . . n] que representam u ev respectivamente e devolve o vetor X[1 . . 2n] que representa x. Nas linhas 4 e 5, p érepresentado por U [m+1 . . n] e q é representado por U [1 . .m]. A implementação das

42 FEOFILOFF

9 8 7 6 5 4 3 2 1

9 9 9 9 8 8 8 8 8

Figura 7.4: Vetor U [1 . . 9] que representa o número 999988888.

linhas 6 e 7 é análoga. Nas linhas 8 e 9, pr é representado por um vetor PR[1 . . 2m] e qsé representado por um vetor QS [1 . . 2m].

Na linha 10, para calcular p + q basta submeter U [m+1 . . n] e U [1 . .m] ao algo-ritmo usual de adição, que produz um vetor A[1 . .m+1]. Algo análogo vale para asubexpressão r + s. O número y é representado por um vetor Y [1 . . 2m+1].

Na linha 11, o valor de y − pr − qs é calculado pelo algoritmo usual de subtração(não é preciso cuidar de números negativos pois y − pr − qs ≥ 0). Para calcular ovalor da expressão pr · 102m + (y − pr − qs) · 10m + qs , basta concatenar os vetoresPR[1 . . 2m] e QS [1 . . 2m] que representam pr e qs respectivamente e somar o resultadocom y − pr − qs (deslocado de m posições) usando o algoritmo usual de adição.


O algoritmo KARATSUBA é um bom exemplo de aplicação da estratégia de divisão econquista, que já encontramos nos Capítulos 4 e 5. O segredo do sucesso da estratégianeste caso está no fato de que o processo de divisão da instância original (linhas 3 a 7 doalgoritmo) e o processo de combinação das soluções das instâncias menores (linha 11)consomem relativamente pouco tempo.


Este capítulo foi baseada na Seção 7.1 do livro de Brassard e Bratley [2]. O assuntotambém é discutido nos livros de Knuth [11], Dasgupta, Papadimitriou e Vazirani [4] eKleinberg e Tardos [10].

O algoritmo KARATSUBA foi publicado em 1962 pelos matemáticos russos AnatoliiKaratsuba e Yurii Ofman. Veja o verbetes Multiplication algorithm e Karatsuba algorithmna Wikipedia.

http://en.wikipedia.org/wiki/Karatsuba-Ofman_algorithm

http://en.wikipedia.org/wiki/Karatsuba_algorithm

Capítulo 8

Escalonamento de intervalos

Imagine que vários eventos querem usar um certo centro de convenções. Cada eventogostaria de usar o centro durante o intervalo de tempo que começa numa data a etermina numa data b. Dois eventos são considerados compatíveis se os seus intervalosde tempo são disjuntos. Cada evento tem um certo valor e a administração do centroprecisa selecionar um conjunto de eventos mutuamente compatíveis que tenha o maiorvalor total possível.

8.1 O problema

Sejam a1, a2, . . . , an e b1, b2, . . . , bn números naturais tais que ai ≤ bi para cada i.Cada índice i representa o intervalo que tem origem ai e término bi, ou seja, o conjuntoai, ai+1, . . . , bi−1, bi.

Dois intervalos distintos i e j são compatíveis se bi < aj ou bj < ai. Um conjuntode intervalos é viável se seus elementos são compatíveis dois a dois.

A cada intervalo i está associado um número natural vi que representa o valordo intervalo. O valor de um conjunto S de intervalos é o número v(S) :=

∑i∈S vi.

Um conjunto viável S tem valor máximo se v(S) ≥ v(S′) para todo conjunto S′ deintervalos que seja viável.

Problema dos Intervalos Compatíveis de Valor Máximo: Dados números natu-rais a1, . . . , an, b1, . . . , bn e v1, . . . , vn tais que ai ≤ bi para cada i, encontrar umsubconjunto viável de 1, . . . , n que tenha valor máximo.

A primeira ideia que vem à mente é a de um algoritmo “guloso”1 que escolhe osintervalos em ordem decrescente de valor. Mas isso não resolve o problema.

1 Um algoritmo guloso constrói uma solução escolhendo, a cada passo, o objeto mais “saboroso” deacordo com algum critério estabelecido a priori.

43

44 FEOFILOFF

Exercício

8.1 Coloque os intervalos em ordem decrescente de valor, ou seja, suponha que v1 ≥ v2 ≥· · · ≥ vn. Agora considere o seguinte algoritmo. A m-ésima iteração do algoritmo começacom um subconjunto viável S de 1, . . . ,m−1. Se S∪m for viável, comece nova iteraçãocom S ∪ m no lugar de S. Senão, comece nova iteração sem alterar S. Mostre que estealgoritmo guloso. não resolve o problema.

8.2 A estrutura recursiva do problema

Adote a abreviatura svvm para a expressão “subconjunto viável de valor máximo”e seja S um svvm do conjunto de intervalos 1, . . . , n. Se S não contém n então Stambém é um svvm de 1, . . . , n − 1. Se S contém n então S − n é um svvm doconjunto de todos os intervalos que são compatíveis com n.

Podemos resumir esta propriedade dizendo que o problema tem estrutura recur-siva: qualquer solução de uma instância do problema contém soluções de instânciasmenores.

Para simplificar a descrição do conjunto de intervalos compatíveis com n, convémsupor que os intervalos estão em ordem crescente de términos, ou seja, que

b1 ≤ b2 ≤ · · · ≤ bn . (8.1)

Sob esta hipótese, o conjunto dos intervalos compatíveis com n é simplesmente1, . . . , j, sendo j o maior índice tal que bj < an.

Se denotarmos por X(n) o valor de um svvm de 1, . . . , n, a estrutura recursivado problema garante que

X(n) = max(X(n− 1) , X(j) + vn

), (8.2)

sendo j o maior índice tal que bj < an. Se tal j não existe então (8.2) se reduz a

X(n) = max(X(n− 1) , vn

).

Esta recorrência pode ser facilmente transformada em um algoritmo recursivo. Mas oalgoritmo é muito ineficiente, pois resolve cada subinstância repetidas vezes.

Exercício

8.2 Escreva um algoritmo recursivo baseado em (8.2). Mostre que o consumo de tempo doalgoritmo no pior caso está em Ω(2n). (Sugestão: Considere um conjunto com n intervaloscompatíveis dois a dois, todos com valor 1. Mostre que o tempo T (n) que o algoritmoconsome para processar o conjunto satisfaz a recorrência T (n) = T (n− 1) + T (n− 1) + 1.)

8.3 Algoritmo de programação dinâmica

Para tirar bom proveito da recorrência (8.2), é preciso recorrer à técnica da programaçãodinâmica (veja a Seção 5.5), que consiste em guardar as soluções das subinstâncias


numa tabela à medida que elas forem sendo resolvidas. Com isso, cada subinstânciaserá resolvida uma só vez.

O seguinte algoritmo recebe n intervalos que satisfazem (8.1) e devolve o valor deum svvm de 1, . . . , n:

INTERVALOSCOMPATÍVEIS (a1, . . . , an, b1, . . . , bn, v1, . . . , vn)1 X[0]← 02 para m← 1 até n faça3 j ← m− 14 enquanto j ≥ 1 e bj ≥ am faça5 j ← j − 16 se X[m− 1] > X[j] + vm7 então X[m]← X[m− 1]8 senão X[m]← X[j] + vm9 devolva X[n]

(Não é difícil extrair da tabela X um svvm de 1, . . . , n.)

O algoritmo está correto. Na linha 2, imediatamente antes da comparação de mcom n,

X[m−1] é o valor de um svvm de 1, . . . ,m−1,X[m−2] é o valor de um svvm de 1, . . . ,m−2, . . . ,X[1] é o valor de um svvm de 1.

Este invariante certamente vale no início da primeira iteração, quando m = 1. Supo-nha agora que ele vale no início de uma iteração qualquer. Para mostrar que continuavalendo no início da iteração seguinte, observe que, no começo da linha 6, 1, . . . , jé o conjunto dos intervalos compatíveis com m. Assim, o valor atribuído a X[m] naslinhas 7 e 8 está de acordo com a recorrência (8.2) e portanto X[m] é o valor de umsvvm de 1, . . . ,m.

Na última passagem pela linha 2 temos m = n + 1 e portanto X[n] é o valor de umsvvm de 1, . . . , n. Assim, o algoritmo cumpre o que prometeu.

Consumo de tempo. Uma execução de qualquer linha do algoritmo INTERVA-LOSCOMPATÍVEIS consome uma quantidade de tempo que não depende de n. Logo, oconsumo de tempo total do algoritmo pode ser medido contando o número de execu-ções das diversas linhas.

Para cada valor fixo de m, a linha 5 é executada no máximo m− 1 vezes. Como mvaria de 1 a n e

∑nm=1(m − 1) = 1

2(n2 − n), a linha 5 é executada menos que n2 vezes.Todas as demais linhas são executadas no máximo n − 1 vezes. Logo, o consumo detempo total do algoritmo está em

O(n2)

no pior caso. Uma análise um pouco mais cuidadosa mostra que o consumo está emΘ(n2) no pior caso.

46 FEOFILOFF

Não levamos em conta ainda o pré-processamento que rearranja os intervalos emordem crescente de término. Como esse pré-processamento pode ser feito em tempoO(n lg n) (veja o Capítulo 4) e n lg n está em O(n2), o consumo de tempo total é Θ(n2).(Mas veja o Exercício 8.3.)

Exercícios

8.3 Mostre que o algoritmo INTERVALOSCOMPATÍVEIS pode ser implementado de modo a con-sumir apenas O(n) unidades de tempo. Sugestão: construa uma tabela auxiliar que pro-duza, em tempo constante, efeito equivalente ao das linhas 4-5.

8.4 Escreva um algoritmo de pós-processamento que extraia da tabela X[1 . . n] produzida peloalgoritmo INTERVALOSCOMPATÍVEIS um svvm de 1, . . . , n. O seu algoritmo deve con-sumir O(n) unidades de tempo.


O problema dos intervalos valorados é discutido no livro de Kleinberg e Tardos [10]. Overbete Interval scheduling na Wikipedia trata do escalonamento de intervalos.

http://en.wikipedia.org/wiki/Interval_scheduling

Capítulo 9

As linhas de um parágrafo

Um parágrafo de texto é uma sequência de palavras, sendo cada palavra uma sequên-cia de caracteres. Queremos imprimir um parágrafo em uma ou mais linhas consecuti-vas de uma folha de papel de tal modo que cada linha tenha no máximo L caracteres.As palavras do parágrafo não devem ser quebradas entre linhas e cada duas palavrasconsecutivas numa linha devem ser separadas por um espaço.

Para que a margem direita fique razoavelmente uniforme, queremos distribuir aspalavras pelas linhas de modo a minimizar a soma dos cubos dos espaços em brancoque sobram no fim de todas as linhas exceto a última.

9.1 O problema

Para simplificar a discussão do problema, convém numerar as palavras do parágrafoem ordem inversa e confundir as palavras com os seus comprimentos. Diremos, pois,que um parágrafo é uma sequência cn, cn−1, . . . , c2, c1 de números naturais. Diremostambém que cada ci é uma palavra: cn é a primeira palavra do parágrafo e c1 é a última.

Um trecho de um parágrafo cn, cn−1, . . . , c1 é qualquer sequência da formacm, cm−1, . . . , ck com n ≥ m ≥ k ≥ 1. Este trecho será denotado por (m, k). O compri-mento do trecho (m, k) é o número

c(m, k) := cm + 1 + cm−1 + 1 + · · ·+ 1 + ck .

Os próximos conceitos envolvem um número natural L que chamaremos capacidadede uma linha. Um trecho (m, k) é curto se c(m, k) ≤ L. O defeito de um trecho curto(m, k) é o número

(L− c(m, k))3 .

Uma L-decomposição do parágrafo cn, cn−1, . . . , c1 é uma subdivisão do parágrafo emtrechos curtos. Mais precisamente, uma L-decomposição é uma sequência

(n, kq), (kq − 1, kq−1), (kq−1 − 1, kq−2), . . . , (k2 − 1, k1) (k1 − 1, 1)

de trechos curtos em que n ≥ kq > kq−1 > · · · > k2 > k1 > 1. O defeito de umadecomposição é a soma dos defeitos de todos os trechos da decomposição exceto oúltimo. Uma decomposição é ótima se tem defeito mínimo.

47

48 FEOFILOFF

Aaaa bb cccc d eee ff gggg iiijj kkk. Llll mmm nn ooooo-----ppppp qq r sss ttt uu.

Aaaa bb cccc d eee ff gggg----iii jj kkk. Llll mmm nn ooooo-ppppp qq r sss ttt uu.

Figura 9.1: Duas decomposições do mesmo parágrafo. As linhas têm capaci-dade L = 30 e os caracteres “-” representam os espaços em branco que contri-buem para o defeito. O defeito da primeira decomposição é 03 + 53 = 125 e o dasegunda é 43 + 13 = 65.

ccc bbb cccaaa bbb--ccc

Figura 9.2: À direita temos uma decomposição ótima de um parágrafo c3, c2, c1. Acapacidade das linhas é L = 9. Os caracteres “-” representam os espaços em brancoque contribuem para o defeito. No centro, temos uma decomposição ótima do pará-grafo c2, c1. À esquerda, uma decomposição ótima do parágrafo c1.

Problema da Decomposição de um Parágrafo: Dado um parágrafo cn, cn−1, . . . ,c1 e um número natural L, encontrar uma L-decomposição ótima do parágrafo.

É claro que as instâncias do problema em que ci > L para algum i não têm solução.

Exercícios

9.1 Tente explicar por que a definição de defeito usa a terceira potência e não a primeira ou asegunda.

9.2 Considere a seguinte heurística “gulosa”: preencha a primeira linha até onde for possível,depois preencha o máximo possível da segunda linha, e assim por diante. Mostre que estaheurística não resolve o problema.

9.3 Suponha que ci = 1 para i = n, . . . , 1. Mostre que o defeito de uma decomposição ótima éno máximo b2n/Lc.


O problema da decomposição de parágrafos tem caráter recursivo, como passamosa mostrar. Suponha que (n, k) é o primeiro trecho de uma decomposição ótima do


parágrafo cn, cn−1, . . . , c1. Se k ≥ 2 então

a correspondente decomposição de ck−1, ck−2, . . . , c1 é ótima.

Eis a prova desta propriedade: Seja x o defeito da decomposição de ck−1, . . . , c1 indu-zida pela decomposição ótima de cn, . . . , c1. Suponha agora, por um momento, que oparágrafo ck−1, . . . , c1 tem uma decomposição com defeito menor que x. Então a com-binação desta decomposição com o trecho (n, k) é uma decomposição de cn, . . . , c1 quetem defeito menor que o mínimo, o que é impossível.

A propriedade recursiva pode ser representada por uma relação de recorrência.Seja X(n) o defeito de uma decomposição ótima do parágrafo cn, cn−1, . . . , c1. Se otrecho (n, 1) é curto então X(n) = 0. Caso contrário,

X(n) = minc(n,k)≤L

((L− c(n, k))3 + X(k−1)

), (9.1)

sendo o mínimo tomado sobre todos os trechos curtos da forma (n, k).A recorrência poderia ser transformada facilmente num algoritmo recursivo. Mas

o cálculo do min em (9.1) levaria o algoritmo a resolver as mesmas subinstâncias váriasvezes, o que é muito ineficiente.

9.3 Um algoritmo de programação dinâmica

Para usar a recorrência (9.1) de maneira eficiente, basta interpretar X como uma ta-bela X[1 . . n] e calcular X[n], depois X[n−1], e assim por diante. Esta é a técnica daprogramação dinâmica. O seguinte algoritmo implementa esta ideia. Ele devolve o de-feito mínimo de um parágrafo cn, cn−1, . . . , c1 supondo n ≥ 1, linhas de capacidade Le ci ≤ L para todo i:

DEFEITOMÍNIMO (cn, . . . , c1, L)1 para m← 1 até n faça2 X[m]←∞3 k ← m4 s← cm5 enquanto k > 1 e s ≤ L faça6 X ′ ← (L− s)3 + X[k−1]7 se X ′ < X[m] então X[m]← X ′

8 k ← k − 19 s← s + 1 + ck

10 se s ≤ L então X[m]← 011 devolva X[n]

(Não é difícil modificar o algoritmo de modo que ele produza uma decomposiçãoótima e não apenas o seu defeito.)

No início de cada iteração do bloco de linhas 6-9, o valor da variável s é c(m, k). Asprimeiras execuções do processo iterativo descrito nas linhas 5-9 terminam tipicamente

50 FEOFILOFF

com k = 1 e (m, k) é o único trecho da decomposição. As execuções subsequentes domesmo bloco terminam com k ≥ 2 e portanto com s > L.

O algoritmo está correto. Na linha 1, imediatamente antes da comparação de mcom n, temos o seguinte invariante:

X[m− 1] é o defeito mínimo do parágrafo cm−1, . . . , c1 ,X[m− 2] é o defeito mínimo do parágrafo cm−2, . . . , c1 ,

. . . ,X[1] é o defeito mínimo do parágrafo c1 .

Este invariante vale vacuamente na primeira passagem pela linha 1. Suponha agoraque o invariante vale no início de uma iteração qualquer. A propriedade continuavalendo no início da iteração seguinte, pois o bloco de linhas 2-10 calcula o defeito deuma decomposição ótima de parágrafo cm, cm−1, . . . , c1 usando a recorrência (9.1).

No fim do processo iterativo temos m = n + 1 e portanto X[n] é o defeito mínimodo parágrafo cn, . . . , c1.

Consumo de tempo. Adote n como tamanho da instância (cn, . . . , c1, L) do pro-blema. Podemos supor que uma execução de qualquer linha do código consome umaquantidade de tempo que não depende de n. Assim, o consumo de tempo é determi-nado pelo número de execuções das várias linhas.

Para cada valor fixo de m, o bloco de linhas 6-9 é executado no máximo m − 1vezes. Como m assume os valores 1, 2, . . . , n, o número total de execuções do bloco delinhas 6-9 não passa de 1

2n(n− 1). Portanto, o algoritmo consome

Θ(n2)

unidades de tempo no pior caso. No melhor caso (que acontece, por exemplo, quandoci ≥ dL/2e para cada i), o algoritmo consome Θ(n) unidades de tempo.

Exercício

9.4 Modifique o algoritmo DEFEITOMÍNIMO para que ele devolva a descrição 〈kq, kq−1, . . . , k1〉de uma decomposição ótima do parágrafo cn, . . . , c1 e não apenas o defeito da decomposi-ção.


O problema que discutimos neste capítulo é proposto como exercício nos livros de Cor-men et al. [3], Parberry [17] e Parberry e Gasarch [18].

Capítulo 10

Mochila de valor máximo

Suponha dado um conjunto de objetos e uma mochila. Cada objeto tem um certo pesoe um certo valor. Queremos escolher um conjunto de objetos que tenha o maior valorpossível sem ultrapassar a capacidade (ou seja, o limite de peso) da mochila. Estecélebre problema aparece em muitos contextos e faz parte de muitos problemas maiselaborados.

10.1 O problema

Suponha dados números naturais p1, . . . , pn e v1, . . . , vn. Diremos que pi é o peso e vi é ovalor de i. Para qualquer subconjunto S de 1, 2, . . . , n, sejam p(S) e v(S) os números∑

i∈S pi e∑

i∈S vi respectivamente. Diremos que p(S) é o peso e v(S) é o valor de S.Em relação a um número natural c, um subconjunto S de 1, . . . , n é viável se

p(S) ≤ c. Um subconjunto viável S∗ de 1, . . . , n é ótimo se v(S∗) ≥ v(S) para todoconjunto viável S.

Problema da Mochila: Dados números naturais p1, . . . , pn, c, v1, . . . , vn, encon-trar um subconjunto ótimo de 1, . . . , n.

Uma solução da instância (n, p, c, v) do problema é qualquer subconjunto ótimode 1, . . . , n. Poderíamos ser tentados a encontrar uma solução examinando todos ossubconjuntos 1, . . . , n. Mas esse algoritmo é inviável, pois consome tempo Ω(2n).


Seja S uma solução da instância (n, p, c, v). Temos duas possibilidades, conforme nesteja ou não em S. Se n /∈ S então S também é um solução da instância (n− 1, p, c, v).Se n ∈ S então S − n é solução de (n− 1, p, c− pn, v).

Podemos resumir isso dizendo que o problema tem estrutura recursiva: toda solu-ção de uma instância do problema contém soluções de instâncias menores.

Se denotarmos por X(n, c) o valor de um solução de (n, p, c, v), a estrutura recur-

51

52 FEOFILOFF

siva do problema pode ser representada pela seguinte recorrência:

X(n, c) = max(X(n− 1, c) , X(n− 1, c− pn) + vn

). (10.1)

O segundo termo de max só faz sentido se c− pn ≥ 0, e portanto

X(n, c) = X(n− 1, c) (10.2)

quando pn > c.Poderíamos calcular X(n, c) recursivamente. Mas o algoritmo resultante é muito

ineficiente, pois resolve cada subinstância um grande número de vezes.

Exercício

10.1 Escreva um algoritmo recursivo baseado na recorrência (10.1-10.2). Calcule o consumo detempo do seu algoritmo no pior caso. (Sugestão: para cada n, tome a instância em quec = n e pi = vi = 1 para cada i. Mostre que o consumo de tempo T (n) para essa família deinstâncias satisfaz a recorrência T (n) = 2T (n− 1) + 1.)

10.3 Algoritmo de programação dinâmica

Para obter um algoritmo eficiente a partir da recorrência (10.1-10.2), é preciso armaze-nar as soluções das subinstâncias numa tabela à medida que elas forem sendo obtidas,evitando assim que elas sejam recalculadas. Esta é a técnica da programação dinâmica,que já encontramos em capítulos anteriores.

Como c e todos os pi são números naturais, podemos tratar X como uma tabelacom linhas indexadas por 0 . . n e colunas indexadas por 0 . . c. Para cada i entre 0 e ne cada b entre 0 e c, a casa X[i, b] da tabela será o valor de uma solução da instância(i, p, b, v). As casas da tabela X precisam ser preenchidas na ordem certa, de modoque toda vez que uma casa for requisitada o seu valor já tenha sido calculado.

O algoritmo abaixo recebe uma instância (n, p, c, v) do problema e devolve o valorde uma solução da instância:1

MOCHILAPD (n, p, c, v)

1 para b← 0 até c faça2 X[0, b]← 03 para j ← 1 até n faça4 x← X[j − 1, b]5 se b− pj ≥ 06 então y ← X[j − 1, b− pj ] + vj7 se x < y então x← y8 X[j, b]← x9 devolva X[n, c]

1 É fácil extrair da tabela X um subconjunto viável de 1, . . . , n que tenha valor X[n, c]. Veja o Exer-cício 10.4.


p4213

v500400300450

0 1 2 3 4 50 0 0 0 0 0 01 0 0 0 0 500 5002 0 0 400 400 500 5003 0 300 400 700 700 8004 0 300 400 700 750 850

Figura 10.1: Uma instância do Problema da Mochila com n = 4 e c = 5. Afigura mostra a tabela X[0 . . n, 0 . . c] calculada pelo algoritmo MOCHILAPD.

O algoritmo está correto. A cada passagem pela linha 1, imediatamente antes dascomparação de b com c, as b primeiras colunas da tabela estão corretas, ou seja,

X[i, a] é o valor de uma solução da instância (i, p, a, v) (10.3)

para todo i no intervalo 0 . . n e todo a no intervalo 0 . . b−1. Para provar este invariante,basta entender o processo iterativo nas linhas 3 a 8. No início de cada iteração desseprocesso,

X[i, b] é o valor de uma solução da instância (i, p, b, v) (10.4)

para todo i no intervalo 0 . . j−1. Se o invariante (10.4) vale no início de uma iteração,ele continua valendo no início da iteração seguinte em virtude da recorrência (10.1-10.2). Isto prova que (10.3) de fato vale a cada passagem pela linha 1.

Na última passagem pela linha 1 temos b = c + 1 e portanto (10.3) garante queX[n, c] é o valor de uma solução da instância (n, p, c, v).

Consumo de tempo. É razoável supor que uma execução de qualquer das linhasdo código consome uma quantidade de tempo que não depende de n nem de c. Por-tanto, basta contar o número de execuções das diversas linhas.

Para cada valor fixo de b, o bloco de linhas 4-8 é executado n vezes. Como b variade 0 a c, o número total de execuções do bloco de linhas 4-8 é (c + 1)n. As demais linhassão executadas no máximo c+1 vezes. Esta discussão mostra que o algoritmo consome

Θ(nc)

unidades de tempo. (Poderíamos ter chegado à mesma conclusão observando que oconsumo de tempo do algoritmo é proporcional ao número de casas da tabela X .)

O consumo de tempo de MOCHILAPD é muito sensível às variações de c. Ima-gine, por exemplo, que c e os elementos de p são todos multiplicados por 100. Comoisto constitui uma mera mudança de escala, a nova instância do problema é concei-tualmente idêntica à original. No entanto, nosso algoritmo consumirá 100 vezes maistempo para resolver a nova instância.

54 FEOFILOFF

Observações sobre o consumo de tempo. Ao dizer que o consumo de tempo doalgoritmo é Θ(nc), estamos implicitamente adotando o par de números (n, c) comotamanho da instância (n, p, c, v). No entanto, é mais razoável dizer que o tamanho dainstância é (n, dlg ce), pois c pode ser escrito com apenas dlg ce bits. É mais razoável,portanto, dizer que o algoritmo consome

Θ(n2lg c)

unidades de tempo. Isto torna claro que o consumo de tempo cresce explosivamentecom lg c.

Gostaríamos de ter um algoritmo cujo consumo de tempo não dependesse do valorde c, um algoritmo cujo consumo de tempo estivesse em O(n2), ou O(n10), ou O(n100).(Um tal algoritmo seria considerado “fortemente polinomial”.) Acredita-se, porém,que um tal algoritmo não existe.2

Exercícios

10.2 É verdade que X[i, 0] = 0 para todo i depois da execução do algoritmo MOCHILAPD?

10.3 Por que nosso enunciado do problema inclui instâncias em que c vale 0? Por que incluiinstâncias com objetos de peso nulo?

10.4 Mostre como extrair da tabela X[0 . . n, 0 . . c] produzida pelo algoritmo MOCHILAPD umsubconjunto ótimo de 1, . . . , n.

10.5 Faça uma mudança de escala para transformar o conjunto 0, 1, . . . , c no conjunto denúmeros racionais entre 0 e n. Aplique o mesmo fator de escala aos pesos pi. O algoritmoMOCHILAPD pode ser aplicado a essa nova instância do problema?

10.4 Instâncias especiais do problema da mochila

Algumas coleções de instâncias do Problema da Mochila têm especial interesse prático.Se vi = pi para todo i, temos o célebre Problema Subset Sum, que pode ser apresentadoassim: imagine que você emitiu cheques de valores v1, . . . , vn durante o mês; se o bancodebitou um total de c na sua conta no fim do mês, quais podem ter sido os chequesdebitados?

Considere agora as instâncias do Problema da Mochila em que vi = 1 para todo i.(Você pode imaginar que p1, . . . , pn são os tamanhos de n arquivos digitais. Quantosdesses arquivos cabem num pen drive de capacidade c?) Esta coleção de instânciaspode ser resolvida por um algoritmo “guloso” óbvio que é muito mais eficiente queMOCHILAPD.


O problema da mochila é discutido na Seção 16.2 do livro de Cormen et al. [3] e naSeção 8.4 do livro de Brassard e Bratley [2], por exemplo.

2 O Problema da Mochila é NP-difícil. Veja o livro de Cormen et al. [3].

Capítulo 11

Mochila de valor quase máximo

O algoritmo de programação dinâmica para o Problema da Mochila (veja o Capítulo 10)é lento. Dada a dificuldade de encontrar um algoritmo mais rápido,1 faz sentido re-duzir nossas exigências e procurar por uma solução quase ótima. Um tal algoritmodeve calcular um conjunto viável de valor maior que uma fração predeterminada (di-gamos 50%) do valor máximo.

11.1 O problema

Convém repetir algumas das definições da Seção 10.1. Dados números naturaisp1, . . . , pn, c e v1, . . . , vn, diremos que pi é o peso e vi é o valor de i. Para qualquersubconjunto S de 1, . . . , n, denotaremos por p(S) a soma

∑i∈S pi e diremos que S é

viável se p(S) ≤ c. O valor de S é o número v(S) :=∑

i∈S vi. Um conjunto viável S∗ éótimo se v(S∗) ≥ v(S) para todo conjunto viável S.

Problema da Mochila: Dados números naturais p1, . . . , pn, c, v1, . . . , vn, encon-trar um subconjunto viável ótimo de 1, . . . , n.

Todo objeto de peso maior que c pode ser ignorado e qualquer objeto de peso nulopode ser incluído em todos os conjuntos viáveis. Suporemos então, daqui em diante,que

1 ≤ pi ≤ c (11.1)

para todo i.

11.2 Algoritmo de aproximação

O algoritmo que descreveremos a seguir tem caráter “guloso” e dá preferência aos obje-tos de maior valor específico. O valor específico de um objeto i é o número vi/pi. Parasimplificar a descrição do algoritmo, suporemos que os objetos são dados em ordem

1 O problema é NP-difícil. Veja o livro de Cormen et al. [3].

55

56 FEOFILOFF

decrescente de valor específico, ou seja, que

v1p1≥ v2

p2≥ · · · ≥ vn

pn. (11.2)

Nosso algoritmo recebe uma instância do problema que satisfaz as condições (11.1)e (11.2) e devolve um subconjunto viável X de 1, . . . , n tal que

v(X) ≥ 12v(S∗) ,

sendo S∗ é um subconjunto viável ótimo:

MOCHILAQUASEÓTIMA (n, p, c, v)

1 X ← ∅2 s← x← 03 k ← 14 enquanto k ≤ n e s + pk ≤ c faça5 X ← X ∪ k6 s← s + pk7 x← x + vk8 k ← k + 19 se k > n ou x ≥ vk

10 então devolva X11 senão devolva k

O bloco de linhas 4 a 8 determina o maior k tal que p1 + · · · + pk−1 ≤ c. No inícioda linha 9, X = 1, . . . , k−1, s = p(X) e x = v(X).

O algoritmo está correto. No início da linha 9, é claro que X é viável. Se k > nentão X = 1, . . . , n e o algoritmo adota X como solução. Nesse caso, é evidente quev(X) ≥ 1

2 v(S) para todo conjunto viável S, como prometido.Suponha agora que k ≤ n no início da linha 9. Graças à hipótese (11.1), o conjunto

k é viável e o algoritmo adota como solução o mais valioso dentre X e k. Restamostrar que

max (v(X), vk) ≥ 12 v(S)

para todo conjunto viável S. O primeiro passo da demonstração consiste na seguinteobservação:

max (v(X), vk) ≥ 12(v(X) + vk) = 1

2 v(R) ,

sendo R := X ∪ k. O segundo passo mostra que v(R) > v(S) qualquer que seja o


conjunto viável S:

v(R)− v(S) = v(R− S)− v(S −R)

=∑

i∈R−Svi −

∑i∈S−R

vi

=∑

i∈R−S

vipi

pi −∑

i∈S−R

vipi

pi

≥ vkpk

p(R− S) − vkpk

p(S −R) (11.3)

=vkpk

(p(R)− p(S)

)>

vkpk

(c− c

)(11.4)

= 0 .

A relação (11.3) vale porque vi/pi ≥ vk/pk para todo i em R e vi/pi ≤ vk/pk para todo ino complemento de R. Já (11.4) vale porque p(R) > c e p(S) ≤ c.

Consumo de tempo. Adote n (poderia igualmente ter adotado 2n + 1) como me-dida do tamanho da instância (n, p, c, v) do problema. Uma execução de qualquerdas linhas do algoritmo consome uma quantidade de tempo que não depende de n. Obloco de linhas 5-8 é executado no máximo n vezes. Assim, o algoritmo todo consome

Θ(n)

unidades de tempo, tanto no pior quanto no melhor caso. O algoritmo propriamentedito é, portanto, linear.

O pré-processamento necessário para fazer valer (11.1) e (11.2) pode ser feito emtempo Θ(n lg n) (veja o Capítulo 4). Portanto, o consumo de tempo do processo todo é

Θ(n lg n) .

Exercício

11.1 Construa uma instância do Problema da Mochila para a qual o algoritmo devolve k nalinha 11.

11.3 Observações sobre algoritmos de aproximação

Um algoritmo rápido cujo resultado é uma fração predeterminadada solução ótimaé conhecido como algoritmo de aproximação. O resultado do algoritmo MOCHILA-QUASEÓTIMA, por exemplo, é melhor que 50% do ótimo. Esse fator de aproximaçãopode parecer grosseiro, mas é suficiente para algumas aplicações que precisam de umalgoritmo muito rápido.

58 FEOFILOFF

Outros algoritmos de aproximação para o Problema da Mochila têm fator de apro-ximação bem melhor que 50%. O algoritmo de Ibarra e Kim (veja o livro de Fernan-des et al. [8], por exemplo) garante um fator de aproximação tão próximo de 100%quanto o usuário desejar. Como seria de se esperar, o consumo de tempo do algoritmoé tanto maior quanto maior o fator de aproximação solicitado. O algoritmo de Ibarra eKim é baseado numa variante de MOCHILAPD em que os papéis de p e v são trocados.(Veja o Exercício 10.5.)


Algoritmos de aproximação para o Problema da Mochila são discutidos na Seção 13.2do livro de Brassard e Bratley [2].

Capítulo 12

A cobertura de um grafo

Imagine um conjunto de salas interligadas por túneis. Um guarda postado numa salaé capaz de vigiar todos os túneis que convergem sobre a sala. Queremos determinar onúmero mínimo de guardas suficiente para vigiar todos os túneis.

Se houver um custo associado com cada sala (este é o custo de manter um guardana sala), queremos determinar o conjunto mais barato de guardas capaz de mantertodos os túneis sob vigilância.

12.1 Grafos

Um grafo é um par (V,A) de conjuntos tal que A ⊆(V2

). Cada elemento de A é, por-

tanto, um par não ordenado de elementos de V . Os elementos de V são chamadosvértices e os de A são chamados arestas.

Uma aresta i, j é usualmente denotada por ij. Os vértices i e j são as pontasdesta aresta.

12.2 O problema da cobertura

Uma cobertura de um grafo é um conjunto X de vértices que contém pelo menos umadas pontas de cada aresta. Se cada vértice i tem um custo ci, o custo de uma coberturaX é o número c(X) :=

∑i∈X ci.

Problema da Cobertura: Dado um grafo cujos vértices têm custos em N, encon-trar uma cobertura de custo mínimo.

Poderíamos resolver o problema examinando todos os subconjuntos do conjuntode vértices, mas um tal algoritmo é explosivamente lento: seu consumo de tempocresce exponencialmente com o número de vértices. Infelizmente, acredita-se quenão existem algoritmos substancialmente mais rápidos para o problema, nem mesmoquando todos os vértices têm custo unitário.1

1 O Problema da Cobertura é NP-difícil. Veja o livro de Cormen et al. [3].

59

60 FEOFILOFF

Faz sentido, portanto, procurar por um bom algoritmo de aproximação, um algo-ritmo rápido que encontre uma cobertura cujo custo seja limitado por um múltiplopredeterminado do ótimo. (Veja a Seção 11.3.)

rrr rrrrr rrrFigura 12.1: Uma instância do Problema da Cobertura. Encontre umacobertura mínima, supondo que todos os vértices têm custo 1.

Exercício

12.1 Seja (V,A) um grafo. Ignore os custos dos vértices do grafo. Uma cobertura X desse grafoé mínima se não existe uma cobertura X ′ tal que |X ′| < |X|. Uma cobertura X é minimalse não existe uma cobertura X ′ tal que X ′ ⊂ X . Mostre que uma cobertura minimal podeser arbitrariamente maior que uma cobertura mínima.

12.3 Um algoritmo de aproximação

O seguinte algoritmo recebe um grafo (V,A) e um número natural ci para cada vértice ie devolve uma cobertura X tal que c(X) ≤ 2 · c(X∗), sendo X∗ uma cobertura de customínimo:

COBERTURABARATA (V, A, c)

1 para cada i em V faça2 xi ← 03 para cada ij em A faça4 yij ← 05 para cada pq em A faça6 e← min (cp − xp , cq − xq)7 ypq ← ypq + e8 xp ← xp + e9 xq ← xq + e

10 X ← ∅11 para cada i em V faça12 se xi = ci então X ← X ∪ i13 devolva X

O algoritmo atribui números naturais y às arestas. Você pode imaginar que ypq éa quantia que a aresta pq paga a cada uma de suas pontas para convencer uma delasa fazer parte da cobertura. Um vértice p aceita participar da cobertura se

∑q ypq ≥ cp,

sendo a soma feita sobre todas as arestas que têm ponta p. A regra do jogo é nuncapagar mais que o necessário. Portanto,

∑q ypq ≤ cp para todo vértice p.


O algoritmo está correto. No início de cada iteração do bloco de linhas 6-9, temosos seguintes invariantes:

i. xi =∑

j yij para todo i em V ,ii. xi ≤ ci para todo i em V ,

iii. para toda aresta ij já examinada tem-se xi = ci ou xj = cj .

Estas propriedades são obviamente verdadeiras no início da primeira iteração. Noinício de cada iteração subsequente, o invariante i continua valendo, pois ypq, xp e xqsão acrescidos da mesma quantidade e. O invariante ii continua valendo, pois e ≤cp − xp e e ≤ cq − xq. O invariante iii continua valendo, pois e = cp − xp ou e = cq − xq.

Os invariantes i e ii têm a seguinte consequência: no início de cada iteração dobloco de linhas 6-9, temos ∑

ij∈Ayij ≤ c(Z) (12.1)

para qualquer cobertura Z. Para mostrar isso, basta observar que∑

ij∈A yij ≤∑i∈Z∑

j yij =∑

i∈Z xi ≤∑

i∈Z ci. A primeira desigualdade vale porque toda arestatem pelo menos uma de suas pontas em Z. A igualdade seguinte vale em virtude doinvariante i. A última desigualdade decorre do invariante ii.

Agora observe que no fim do bloco de linhas 10-12 temos

c(X) ≤ 2∑

ij∈Ayij . (12.2)

De fato, como xi = ci para todo i em X , temos∑

i∈X ci =∑

i∈X xi =∑

i∈X∑

j yij ≤2∑

ij∈A yij . A segunda igualdade vale em virtude do invariante i. A última desigual-dade é verdadeira pois cada aresta tem no máximo duas pontas em X .

Segue de (12.2) e (12.1) que, depois do bloco de linhas 10-12, para qualquer cober-tura Z,

c(X) ≤ 2 c(Z) .

Isto vale, em particular, se Z é uma cobertura de custo mínimo. Como X é uma cober-tura (em virtude do invariante iii), o algoritmo cumpre o que prometeu.

O fator de aproximação 2 pode parecer ser grosseiro, mas o fato é que ninguémdescobriu ainda um algoritmo eficiente com fator de aproximação 1.9 por exemplo.

Consumo de tempo. Podemos supor que o grafo é dado da maneira mais cruapossível: os vértices são 1, 2, . . . , n e as arestas são listadas em ordem arbitrária.

Seja m o número de arestas do grafo e adote o par (n,m) como tamanho de umainstância do problema. Podemos supor que uma execução de qualquer das linhas doalgoritmo consome tempo que não depende de n nem de m. A linha 2 é executada nvezes. A linha 4 é executada m vezes. A linha 12 é executada n vezes. O bloco delinhas 6-9 é repetido m vezes. Assim, o consumo de tempo total do algoritmo está em

Θ(n + m) ,

tanto no pior quanto no melhor caso. O algoritmo é, portanto, linear.

62 FEOFILOFF

12.4 Comentários sobre o método primal-dual

O algoritmo COBERTURABARATA é o resultado da aplicação do método primal-dual deconcepção de algoritmos. O primeiro passo do método (omitido acima) é escrever umprograma linear que represente o problema. As variáveis duais do programa linear sãoas variáveis y do nosso algoritmo. A relação (12.1) é uma manifestação da dualidadede programação linear. (Veja o meu material [6] sobre o assunto.)

Os algoritmos do tipo primal-dual têm um certo caráter “guloso”. No algoritmoCOBERTURABARATA, por exemplo, as arestas são examinadas em ordem arbitrária e aslinhas 8-9 do algoritmo aumentam o valor de xp e xq — o que torna mais provável ainclusão de p e q em X — o máximo possível sem se preocupar com o objetivo globalde minimizar o custo da cobertura X .

Exercício

12.2 Considere as instâncias do Problema da Cobertura em que todos os vértices têm o mesmocusto. Dê um algoritmo de aproximação para essas instâncias que seja mais simples queCOBERTURABARATA. O seu algoritmo deve produzir uma cobertura de tamanho não su-perior ao dobro do ótimo.

12.5 Instâncias especiais do problema

Um grafo é bipartido se seu conjunto de vértices admite uma bipartição (U,W ) tal quetoda aresta tem uma ponta em U e outra em W . (Portanto, U e W são coberturas.)

Existe um algoritmo muito elegante e eficiente para o Problema da Cobertura res-trito a grafos bipartidos. (Veja a Seção 22.4 do livro de Sedgewick [19], por exemplo.)O algoritmo consome Θ(nm) unidades de tempo no pior caso, sendo n o número devértices e m o número de arestas do grafo.


Este capítulo foi baseado no livro de Kleinberg e Tardos [10].

Capítulo 13

Conjuntos independentes em grafos

Considere a relação amigo–de entre os usuários de um site de relacionamentos. Quere-mos encontrar um conjunto máximo de usuários que sejam amigos dois a dois.

Um problema da mesma natureza (mas computacionalmente mais fácil) já foi estu-dado no Capítulo 8: encontrar um conjunto máximo de intervalos dois a dois compatí-veis.

13.1 O problema

Um conjunto I de vértices de um grafo é independente se seus elementos são dois adois não vizinhos, ou seja, se nenhuma aresta do grafo tem ambas as pontas em I . Umconjunto independente I é máximo se não existe um conjunto independente I ′ tal que|I ′| > |I|.

Problema do Conjunto Independente: Encontrar um conjunto independentemáximo num grafo dado.

Conjuntos independentes são os complementos das coberturas (veja o Capítulo 12).De fato, em qualquer grafo (V,A), se I é um conjunto independente então V − I é umacobertura. Reciprocamente, se C é uma cobertura então V −C é um conjunto indepen-dente. Portanto, encontrar um conjunto independente máximo é computacionalmenteequivalente a encontrar uma cobertura mínima. Não se conhecem bons algoritmospara esses problemas.

Apesar da relação de complementaridade, algoritmos de aproximação para o Pro-blema da Cobertura (como o que discutimos na Seção 12.3) não podem ser convertidosem algoritmos de aproximação para o Problema do Conjunto Independente. De fato,se uma cobertura mínima num grafo de n vértices tiver apenas 100 vértices e se nossoalgoritmo de aproximação obtiver uma cobertura com 199 vértices, o correspondenteconjunto independente terá n − 199 vértices. Mas este número não é menor que umapercentagem fixa do tamanho de um conjunto independente máximo.

63

64 FEOFILOFF

Discutiremos a seguir um algoritmo probabilístico muito simples, que fornece umconjunto independente de tamanho esperado razoavelmente grande, embora modesto.

Exercício

13.1 Mostre que o problema dos intervalos compatíveis discutido no Capítulo 8 é um casoespecial (ou seja, uma coleção de instâncias) do problema do conjunto independente.

13.2 Um conjunto independente I em um grafo é maximal se não existe um conjunto indepen-dente I ′ no grafo tal que I ′ ⊃ I . Mostre que um conjunto independente maximal pode serarbitrariamente menor que um conjunto independente máximo.

13.2 Algoritmo probabilístico

Convém lembrar que todo grafo com n vértices tem entre 0 e(n2

)arestas. Portanto, se

m é o número de arestas então 0 ≤ 2m ≤ n2−n. O algoritmo que discutiremos a seguirproduz um conjunto independente I cujo tamanho esperado é

n2/4m .

O resultado é intuitivamente razoável: quanto mais denso o grafo, ou seja, quanto maispróximo m de n2, menor o tamanho esperado de I .

m n/2 n 2n 10n n√n/4 n2/4 (n2 − n)/2

n2/4m n/2 n/4 n/8 n/40√n 1 n/(2n− 2)

Figura 13.1: Comparação entre o número m de arestas e o tamanho esperadodo conjunto independente produzido pelo algoritmo CONJINDEPENDENTE.

O algoritmo recebe um grafo com vértices 1, 2, . . . , n e conjunto A de arestas edevolve um conjunto independente I tal que

• |I| ≥ n/2 se m ≤ n/2 e• E[|I|] ≥ n2/4m se m > n/2,

sendo m := |A|. A expressão E[x] denota o valor esperado de x.


CONJINDEPENDENTE (n, A)

1 para i← 1 até n faça2 X[i]← 13 m← |A|4 se 2m > n5 então para i← 1 até n faça6 r ← RANDOM (2m− 1)7 se r < 2m− n8 então X[i]← 09 para cada ij em A faça

10 se X[i] = 1 e X[j] = 111 então X[i]← 012 devolva X[1 . . n]

O conjunto independente que o algoritmo devolve é representado pelo vetor bo-oleano X indexado pelos vértices: i pertence ao conjunto independente se e somentese X[i] = 1.

A rotina RANDOM é um gerador de números aleatórios. Com argumento U , elaproduz um número natural uniformemente distribuído no conjunto 0, 1, 2 . . . , U. (Émuito difícil obter números verdadeiramente aleatórios, mas existem bons algoritmospara gerar números pseudoaleatórios.)

O algoritmo está correto. O algoritmo tem duas fases. Na primeira fase (linhas 1-8), o algoritmo elimina vértices até que sobre um conjunto W . Se m ≤ n/2, W é oconjunto de todos os vértices. Caso contrário, os vértices são eliminados com proba-bilidade 1 − n/2m, ou seja, permanecem em W na proporção de n em cada 2m. (Sem = 10n, por exemplo, sobra 1 vértice em cada 20. Se m = 1

2n√n, sobra 1 em cada

√n.

Se m = n2/4, sobram cerca de 2 vértices apenas.)É fácil determinar o tamanho esperado de W uma vez que cada um dos n vértices

fica em W com probabilidade n/2m. Se w := |W | então

E[w] = nn

2m=

n2

2m.

Considere agora o conjunto B das arestas que têm ambas as pontas em W . Como ografo tem m arestas e a probabilidade de uma ponta de aresta ficar em W é n/2m,temos

E[b] = m( n

2m

)2=

n2

4m,

sendo b := |B|.Na segunda fase (linhas 9-11), o algoritmo elimina vértices de W de modo que

o conjunto restante I seja independente. Esta segunda fase do algoritmo remove nomáximo b vértices e portanto o tamanho esperado de I é

E[|I|] ≥ E[w]− E[b] =n2

2m− n2

4m=

n2

4m.

66 FEOFILOFF

Se executarmos o algoritmo um bom número de vezes e escolhermos o maior dosconjuntos independentes que resultar, temos uma boa chance de obter um conjuntoindependente de tamanho não menor que n2/4m.

Consumo de tempo. O algoritmo é linear. É razoável supor que cada execuçãoda rotina RANDOM consome tempo independente de n e de m. Assim, o algoritmoconsome

Θ(n + m)

unidades de tempo, sendo Θ(n) unidades na primeira fase e Θ(m) unidades na se-gunda.

13.3 Comentários sobre algoritmos probabilísticos

Diz-se que um algoritmo é probabilístico ou aleatorizado se usa números aleatórios.Cada execução de um tal algoritmo dá uma resposta diferente e o algoritmo prometeque o valor esperado da resposta é suficientemente bom. Em geral, o algoritmo é exe-cutado muitas vezes e o usuário escolhe a melhor das respostas.

Alguns algoritmos (não é o caso do algoritmo CONJINDEPENDENTE acima) prome-tem também que a resposta fornecida está próxima do valor esperado com alta proba-bilidade.

Os algoritmos probabilísticos ignoram, em geral, a estrutura e as peculiaridades dainstância que estão resolvendo. Mesmo assim, surpreendentemente, muitos algoritmosprobabilísticos produzem resultados bastante úteis.


O algoritmo deste capítulo é descrito, por exemplo, no livro de Mitzenmacher e Up-fal [15]. Sobre algoritmos aleatorizados em geral, veja o verbete Randomized algorithmna Wikipedia.

http://en.wikipedia.org/wiki/Randomized_algorithm

Capítulo 14

Busca em largura num grafo

Considere a relação amigo–de entre os usuários de uma rede social. Digamos que doisusuários A e B estão ligados se existe uma sucessão de amigos que leva de A a B.

Suponha que queremos determinar todos os usuários ligados a um dado usuário.A melhor maneira de resolver esse problema é fazer uma busca num grafo (veja aSeção 12.1).

14.1 O problema do componente

Um caminho em um grafo é qualquer sequência (i1, i2, . . . , iq) de vértices tal que cadaip é vizinho de ip−1 para todo p ≥ 2. Dizemos que um vértice está ligado a outro seexiste um caminho que começa no primeiro e termina no segundo. O conjunto de todosos vértices ligados a um vértice v é o componente (do grafo) que contém v.

Problema do Componente: Dado um vértice v de um grafo, encontrar o con-junto de todos os vértices ligados a v.

Este é um dos mais básicos e corriqueiros problemas sobre grafos.

14.2 Busca em largura: versão preliminar

Usaremos a estratégia da “busca em largura” para resolver o problema. Começaremospor escrever uma versão preliminar do algoritmo, em alto nível de abstração.

Dizemos que dois vértices i e j são vizinhos se ij é uma aresta. A vizinhança deum vértice i é o conjunto de todos os vizinhos de i e será denotada por Z(i).

O seguinte algoritmo recebe um vértice v de um grafo representado por seu con-junto V de vértices e suas vizinhanças Z(i), i ∈ V , e devolve o conjunto de todos osvértices ligados a v.

67

68 FEOFILOFF

COMPONENTEPRELIM (V, Z, v)

1 P ← ∅2 C ← v3 enquanto C 6= ∅ faça4 seja i um elemento de C5 para cada j em Z(i) faça6 se j /∈ C ∪ P7 então C ← C ∪ j8 C ← C − i9 P ← P ∪ i

10 devolva P

Você pode imaginar que os vértices em P são pretos, os vértices em C são cinza etodos os demais são brancos. Um vértice é branco enquanto não tiver sido visitado. Aoser visitado, o vértice fica cinza e assim permanece enquanto todos os seus vizinhosnão tiverem sido visitados. Quando todos os vizinhos forem visitados, o vértice ficapreto.

O algoritmo está correto. Considere o processo iterativo no bloco de linhas 3-9.A cada passagem pela linha 3, imediatamente antes da comparação de C com ∅, temosos seguintes invariantes:

i. P ∩ C = ∅,ii. v ∈ P ∪ C,

iii. todo vértice em P ∪ C está ligado a v eiv. toda aresta com uma ponta em P tem a outra ponta em P ∪ C.

É evidente que estas propriedades valem no início da primeira iteração. Suponha agoraque elas valem no início de uma iteração qualquer. É claro que i e ii continuam valendono início da próxima iteração. No caso do invariante iii, basta verificar que os vérticesacrescentados a P ∪ C durante esta iteração estão todos ligados a v. Para isso, é sufici-ente observar que i está ligado a v (invariante iii) e portanto todos os vértices em Z(i)também estão ligados a v.

Finalmente, considere o invariante iv. Por um lado, o único vértice acrescentado aP durante a iteração corrente é i. Por outro lado, ao final da iteração, todos os vizinhosde i estão em P ∪ C. Assim, o invariante iv continua válido no início da próximaiteração.

No fim do processo iterativo, C está vazio. De acordo com os invariantes ii e iv,todos os vértices de qualquer caminho que começa em v estão em P . Reciprocamente,todo vértice em P está ligado a v, de acordo com invariante iii. Portanto, P é o conjuntode vértices ligados a v. Assim, ao devolver P , o algoritmo cumpre o que prometeu.

Consumo de tempo. Não há como discutir o consumo de tempo do algoritmode maneira precisa, pois não especificamos estruturas de dados que representem asvizinhanças Z(i) e os conjuntos P e C.


Podemos garantir, entretanto, que a execução do algoritmo termina depois de nãomais que |V | iterações do bloco de linhas 4-9. De fato, no decorrer da execução doalgoritmo, cada vértice entra em C (linha 7) no máximo uma vez, faz o papel de i nalinha 4 no máximo uma vez, é transferido de C para P (linhas 8 e 9) e portanto nuncamais entra em C. Assim, o número de iterações não passa de |V |.

Exercícios

14.1 Um grafo é conexo se seus vértices estão ligados dois a dois. Escreva um algoritmo quedecida se um grafo é conexo.

14.2 Escreva um algoritmo que calcule o número de componentes de um grafo.

14.3 Busca em largura: versão mais concreta

Podemos tratar agora de uma versão mais concreta do algoritmo COMPONENTEPRE-LIM, que adota estruturas de dados apropriadas para representar os vários conjuntosde vértices.

Suponha que os vértices do grafo são 1, 2, . . . , n. As vizinhanças dos vértices serãorepresentadas por uma matriz Z com linhas indexadas pelos vértices e colunas indexa-das por 1, 2, . . . , n− 1. Os vizinhos de um vértice i serão

Z[i, 1], Z[i, 2], . . . , Z[i, g[i]] ,

onde g[i] é o grau de i, ou seja, o número de vizinhos de i. (Na prática, usam-se listasencadeadas para representar essas vizinhanças.) Observe que cada aresta ij apareceexatamente duas vezes nesta representação: uma vez na linha i da matriz Z e outra vezna linha j.

Os conjuntos P e C da seção anterior serão representados por um vetor cor inde-xado pelos vértices: cor [i] valerá 2 se i ∈ P , valerá 1 se i ∈ C e valerá 0 nos demaiscasos. O conjunto C terá também uma segunda representação: seus elementos ficarãoarmazenados num vetor F [a . . b], que funcionará como uma fila com início a e fim b.Isso permitirá implementar de maneira eficiente o teste “C 6= ∅” na linha 3 de COMPO-NENTEPRELIM, bem como a escolha de i em C na linha 4.

O algoritmo recebe um grafo com vértices 1, 2, . . . , n, representado por seu vetor degraus g e sua matriz de vizinhos Z e recebe um vértice v. O algoritmo devolve um vetorcor [1 . . n] que representa o conjunto de vértices ligados a v (os vértices do componentesão os que têm cor 2).

70 FEOFILOFF

COMPONENTE (n, g, Z, v)

1 para i← 1 até n faça2 cor [i]← 03 cor [v]← 14 a← b← 15 F [b]← v6 enquanto a ≤ b faça7 i← F [a]8 para h← 1 até g[i] faça9 j ← Z[i, h]

10 se cor [j] = 011 então cor [j]← 112 b← b + 113 F [b]← j14 cor [i]← 215 a← a + 116 devolva cor [1 . . n]

O algoritmo COMPONENTE está correto pois o código não faz mais que implemen-tar o algoritmo COMPONENTEPRELIM, que já discutimos.

Consumo de tempo. Seja m o número de arestas do grafo. (Em termos dos pa-râmetros do algoritmo, m é 1

2

∑ni=1 g[i].) Adotaremos o par (n,m) como medida do

tamanho de uma instância do problema.Podemos supor que uma execução de qualquer das linhas do algoritmo consome

uma quantidade de tempo que não depende de n nem de m. A linha 7 é executada nvezes no pior caso, pois cada vértice do grafo faz o papel de i na linha 7 uma só vez aolongo da execução do algoritmo. (Segue daí, em particular, que b ≤ n.) Para cada valorfixo de i, o bloco de linhas 9-13 é executado g[i] vezes. Segue dessas duas observaçõesque, no pior caso, o processo iterativo nas linhas 6-15 consome tempo proporcional àsoma

n∑i=1

g[i] ,

que vale 2m. O consumo desse processo iterativo está, portanto, em Θ(m) no pior caso.Como o consumo de tempo das linhas 1-5 está em Θ(n), o consumo de tempo total

do algoritmo está emΘ(n + m)

no pior caso. (No melhor caso, o vértice v não tem vizinhos e portanto o algoritmoconsome apenas Θ(n) unidades de tempo.)

Exercício

14.3 Escreva um algoritmo que calcule um caminho de comprimento mínimo dentre os queligam dois vértices dados de um grafo. (O comprimento de um caminho é o número dearestas do caminho.)

Capítulo 15

Busca em profundidade num grafo

Este capítulo trata de um segundo algoritmo para o problema estudado no capítuloanterior.

Problema do Componente: Dado um vértice v de um grafo, encontrar o con-junto de todos os vértices ligados a v.

O algoritmo que discutiremos a seguir usa a estratégia da “busca em profundi-dade”. A importância do algoritmo transcende em muito o problema do componente.O algoritmo serve de modelo para soluções eficientes de vários problemas mais com-plexos, como o de calcular os componentes biconexos de um grafo, por exemplo.

15.1 Busca em profundidade

O seguinte algoritmo recebe um vértice v de um grafo e devolve o conjunto de todos osvértices ligados a v. O conjunto de vértices do grafo é 1, . . . , n e o conjunto de arestasé representado pelas vizinhanças Z(p), já definidas na Seção 14.2.

COMPONENTE (n, Z, v)

1 para p← 1 até n faça2 cor [p]← 03 BUSCAEMPROFUNDIDADE (v)4 devolva cor [1 . . n]

O vetor cor , indexado pelo vértices, representa a solução: um vértice p está ligadoa v se e somente se cor [p] = 2.

O algoritmo COMPONENTE é apenas uma “casca” que repassa o serviço para arotina recursiva BUSCAEMPROFUNDIDADE. Do ponto de vista desta rotina, o grafo e ovetor cor são variáveis globais (a rotina pode, portanto, consultar e alterar o valor dasvariáveis).

71

72 FEOFILOFF

BUSCAEMPROFUNDIDADE (p)

5 cor [p]← 26 para cada q em Z(p) faça7 se cor [q] = 08 então BUSCAEMPROFUNDIDADE (q)

O vetor cor só tem dois valores: 0 e 2. Diremos que um vértice p é branco secor [p] = 0 e preto se cor [p] = 2. Diremos também que um caminho (veja Seção 14.1) ébranco se todos os seus vértices são brancos. A rotina BUSCAEMPROFUNDIDADE pintade preto alguns dos vértices que eram brancos. Assim, um caminho que era brancoquando a rotina foi invocada pode deixar de ser branco durante a execução da rotina.

Podemos dizer agora o que a rotina BUSCAEMPROFUNDIDADE faz. Ela recebe umvértice branco p — que é vizinho de um vértice preto a menos que seja igual a v — epinta de preto todos os vértices que estejam ligados a p por um caminho branco. (Arotina não altera as cores dos demais vértices.)

Agora que deixamos claro o problema que a rotina BUSCAEMPROFUNDIDADE re-solve, é importante adotar uma boa definição de tamanho das instâncias desse pro-blema. O número de vértices e arestas do grafo não dá uma boa medida do tamanhoda instância, pois a rotina ignora boa parte do grafo. É bem mais apropriado dizer queo tamanho da instância é o número ∑

x∈Xg(x) , (15.1)

onde X é o conjunto dos vértices ligados a p por caminhos brancos e g(x) := |Z(x)| é ograu do vértice x.

A rotina está correta. A prova da correção da rotina BUSCAEMPROFUNDIDADE éuma indução no tamanho da instância. Se o tamanho for 0, o vértice p não tem vizinhos.Se o tamanho for 1, o único vértice em Z(p) é preto. Em qualquer desses casos, a rotinacumpre o que prometeu.

Suponha agora que o tamanho da instância é maior que 1. Seja B o conjunto devértices brancos no início da execução da rotina e seja X o conjunto dos vértices ligadosa p em B. Queremos mostrar que no fim do processo iterativo descrito nas linhas 6-8 oconjunto dos vértices brancos é B −X .

Sejam q1, q2, . . . , qk os elementos de Z(p) na ordem em que eles serão examinadosna linha 6. Para j = 1, 2, . . . , k, seja Yj o conjunto dos vértices ligados a qj em B − p.É claro que X = p ∪ Y1 ∪ · · · ∪ Yk.

Se Yi ∩ Yj 6= ∅ então Yi = Yj . De fato, se Yi e Yj têm um vértice em comum entãoexiste um caminho em B−p com origem qi e término em Yj . Portanto também existeum caminho em B−p de qi a qj , donde qj ∈ Yi. Segue daí que Yj ⊆ Yi. Um raciocínioanálogo mostra que Yi ⊆ Yj .

O processo iterativo descrito nas linhas 6-8 pode ser reescrito como

6 para j ← 1 até k faça7 se cor [qj ] = 08 então BUSCAEMPROFUNDIDADE (qj)


e isso permite formular o seguinte invariante: a cada passagem pela linha 6,

o conjunto dos vértices brancos é B −(p ∪ Y1 ∪ · · · ∪ Yj−1

). (15.2)

Esta propriedade certamente vale no início da primeira iteração. Suponha agora queela vale no início de uma iteração qualquer. Se tivermos Yj = Yi para algum i entre 1e j−1 então, no início desta iteração, todos os vértices em Yj já são pretos e a linha 8 nãoé executada. Caso contrário, Yj é disjunto de Y1∪ · · ·∪Yj−1 e portanto todos os vérticesem Yj estão ligados a qj por caminhos em B−

(p∪Y1∪ · · · ∪Yj−1

). Como

∑y∈Yj

g(y)

é menor que∑

x∈X g(x), podemos supor, por hipótese de indução, que a invocação deBUSCAEMPROFUNDIDADE na linha 8 com argumento qj produz o resultado prometido.Assim, no fim desta iteração, o conjunto dos vértices brancos é B−

(p∪Y1∪· · ·∪Yj

).

Isto prova que (15.2) continua valendo no início da próxima iteração.No fim do processo iterativo, o invariante (15.2) garante que o conjunto de vértices

brancos é B −(p)∪ Y1 ∪ · · · ∪ Yk

), ou seja, B −X . Logo, BUSCAEMPROFUNDIDADE

cumpre o que prometeu.

Consumo de tempo. A análise da correção da rotina BUSCAEMPROFUNDIDADE

permite concluir que o consumo de tempo da rotina é proporcional ao tamanho,∑x∈X g(x), da instância. Em particular, o consumo de tempo da linha 3 de COM-

PONENTE não passa de∑

x∈V g(x). Como esta soma é igual ao dobro do número dearestas do grafo, m, podemos dizer que a linha 3 de COMPONENTE consome

O(m)

unidades de tempo. No pior caso, o consumo é Θ(m).Se levarmos em conta o consumo de tempo das linhas 1-2 de COMPONENTE, tere-

mos um consumo total deΘ(n + m)

unidades de tempo no pior caso.

Exercício

15.1 Escreva e analise uma versão não recursiva do algoritmo BUSCAEMPROFUNDIDADE.

74 FEOFILOFF

Posfácio

O texto fez uma modesta introdução à Análise de Algoritmos usando material dosexcelentes livros citados na bibliografia. Embora tenha tratado apenas de problemase algoritmos muito simples, espero que este minicurso possa guiar o leitor que queiraanalisar os seus próprios algoritmos.

O tratamento de algoritmos probabilísticos foi muito superficial e muitos outrosassuntos ficaram de fora por falta de espaço. Assim, não foi possível discutir a análisede tipos abstratos de dados, como filas de prioridades e estruturas union/find. A análiseamortizada (muito útil para estimar o consumo de tempo dos algoritmos de fluxo emredes, por exemplo) foi igualmente ignorada. Finalmente, não foi possível mencionara teoria da complexidade de problemas e a questão P=NP.

75

Bibliografia

[1] J.L. Bentley. Programming Pearls. ACM Press, second edition, 2000. 9, 27, 31, 32, 36

[2] G. Brassard and P. Bratley. Fundamentals of Algorithmics. Prentice Hall, 1996. 9, 22,23, 42, 54, 58

[3] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms.MIT Press and McGraw-Hill, second edition, 2001. 9, 11, 22, 50, 54, 55, 59

[4] S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. Algorithms. McGraw-Hill,2006. 42

[5] A.C.P.L. de Carvalho and T. Kowaltowski, editors. Atualizações em Informática 2009.SBC (Soc. Bras. de Computação). PUC-Rio, 2009. ISBN 978-85-87926-54-8. 7

[6] P. Feofiloff. Algoritmos de Programação Linear. Internet http://www.ime.usp.br/~pf/prog-lin/, 1999. 206 páginas. 62

[7] P. Feofiloff. Análise de Algoritmos. Internet http://www.ime.usp.br/~pf/analise_de_algoritmos/, 2011.

[8] C.G. Fernandes, F.K. Miyazawa, M. Cerioli, and P. Feofiloff, editors. Uma Introdu-ção Sucinta a Algoritmos de Aproximação. XXIII Colóquio Brasileiro de Matemática.IMPA (Instituto de Matemática Pura e Aplicada), Rio de Janeiro, 2001. Internethttp://www.ime.usp.br/~cris/aprox/. 58

[9] J. Hromkovic. Algorithmics for Hard Problems: Introduction to Combinatorial Opti-mization, Randomization, Approximation, and Heuristics. Springer, second edition,2004.

[10] J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley, 2005. 9, 42, 46, 62

[11] D.E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Program-ming. Addison-Wesley, third edition, 1997. 42

[12] D.E. Knuth. Selected Papers on Analysis of Algorithms. CSLI Lecture Notes, no. 102.Center for the Study of Language and Information (CSLI), Stanford, CA, 2000. 9

[13] D.E. Knuth. The Art of Computer Programming. Addison-Wesley, ca. 1973. Severalvolumes.

77

http://www.ime.usp.br/~pf/prog-lin/

http://www.ime.usp.br/~pf/prog-lin/

http://www.ime.usp.br/~pf/analise_de_algoritmos/

http://www.ime.usp.br/~pf/analise_de_algoritmos/

http://www.ime.usp.br/~cris/aprox/

[14] U. Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.9, 36

[15] M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithmsand Probabilistic Analysis. Cambridge University Press, 2005. 66

[16] R. Neapolitan and K. Naimipour. Foundations of Algorithms. Jones and Bartlett,second edition, 1998.

[17] I. Parberry. Problems on Algorithms. Prentice Hall, 1995. 50

[18] I. Parberry and W. Gasarch. Problems on Algorithms. Internet: http://www.eng.unt.edu/ian/books/free/, second edition, 2002. 50

[19] R. Sedgewick. Algorithms in C, Part5: Graph Algorithms. Addison-Wesley, thirdedition, 2000. 62

[20] J.L. Szwarcfiter and L. Markenzon. Estruturas de Dados e seus Algoritmos. LivrosTécnicos e Científicos, second edition, 1994.

[21] N. Ziviani. Projeto de Algoritmos (com implementações em Pascal e C). Thomson,second edition, 2004.

http://www.eng.unt.edu/ian/books/free/

http://www.eng.unt.edu/ian/books/free/

Índice remissivo

bxc, 11, 12dxe, 12lg n, 11Ω( ), 14Θ( ), 15N, 12N>, 12R, 12R≥, 12R>, 12

algoritmo, 9aleatorizado, 66correto, 9de aproximação, 57de Karatsuba, 40ene-log-ene, 16exponencial, 16guloso, 43, 44, 54linear, 16inearítmico, 16Mergesort, 25polinomial, 16primal-dual, 62probabilístico, 66quadrático, 16recursivo, 11, 25, 39, 44, 49, 52, 71

análise assintótica, 13aproximação (algoritmo de), 57aresta (de grafo), 59assintoticamente não decrescente, 22assintótico, 13

Bentley, 9, 27, 31, 32, 36BFS, 67Brassard, 9, 22, 23, 42, 54, 58Bratley, 9, 22, 23, 42, 54, 58breadth-first search, 67bucket sort, 33busca

em largura, 67em profundidade, 71

caminho (em grafo), 67cobertura (de grafo), 59compatíveis (intervalos), 43componente (de grafo), 67conexo (grafo), 69conjunto independente (em grafo), 63consumo de tempo, 10Cormen, 9, 11, 22, 50, 54, 55, 59correção (de algoritmo), 9crescente, 25

Dasgupta, 42depth-first search, 71DFS, 71dígito, 37dígitos (número de), 37divisão e conquista, 22, 26, 29, 42

eficiência, 10estrutura recursiva

de um problema, 11, 32, 44, 48, 51

firmeza (de vetor), 30fortemente polinomial, 54

Gasarch, 50grafo, 59

bipartido, 62conexo, 69

grau de vértice, 69guloso (algoritmo), 43, 44, 54

indução matemática, 11, 14, 18, 25instância de problema, 9intercalação de vetores, 25, 26intervalo, 43invariante, 28, 31, 35, 49, 50, 53, 61, 68, 73

79

80 FEOFILOFF

Karatsuba, 40Kleinberg, 9, 42, 46, 62Knuth, 9, 42

Leiserson, 9lg n, 12log, 11

maioria, 33majoritário, 33Manber, 9, 36maximal, 64melhor caso, 10Mergesort, 25minimal, 60mínimo, 60Mitzenmacher, 66mochila

de valor máximo, 51de valor quase máximo, 55

multiplicação de números, 37

N, 12N>, 12não decrescente, 22notação

O grande, 13Ômega grande, 14Teta grande, 15

NP-difícil, 54, 55, 59número de dígitos, 37números

naturais, 12reais, 12

O( ), 13Ω( ), 14O grande, 13Ômega (Ω) grande, 14Ofman, 42

palavra, 47Papadimitriou, 42parágrafo, 47Parberry, 50pen drive, 54pior caso, 10piso de logaritmo, 11piso de número, 11, 12pontas (de aresta), 59primal-dual, 62problema, 9

programação dinâmica, 30, 32, 44, 49, 52programação linear, 62proporcional, 15prova por

contradição, 13, 15indução matemática, 11, 14, 18, 25

R, 12R≥, 12R>, 12recorrência, 17recursão, 11recursivo (algoritmo), 11, 25, 39, 44, 49, 52, 71Rivest, 9

Sedgewick, 62segmento (de vetor), 27solidez (de vetor), 27Stein, 9suficientemente grande, 13svvm, 44

Θ( ), 15tamanho de instância, 10Tardos, 9, 42, 46, 62tem n dígitos, 37tempo (consumo de), 10teorema mestre, 22Teta (Θ) grande, 15teto de número, 12

unidade de tempo, 10, 16Upfal, 66

valor específico, 55valor majoritário, 33Vazirani, 42vértice (de grafo), 59vetor crescente, 25viável, 43, 51, 55vizinhos (vértices), 67

Documents

Minicurso de Análise de Algoritmos