Guia Completo de Programação Competitiva
Guia Completo de Programação Competitiva
com
Antti Laaksonen
Prefácio ix
I Técnicas básicas 1
1 Introdução 3
1.1 Linguagens de programação ......................... 3
1.2 Entrada e saída . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Trabalhando com números . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Código de encurtamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Concursos e recursos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Complexidade de tempo 17
2.1 Regras de cálculo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Classes de complexidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Estimativa de eficiência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Soma máxima do subarray . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Classificação 25
3.1 Teoria da classificação . ... 25
3.2 Classificação em C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Busca binária . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4 Estruturas de dados 35
4.1 Matrizes dinâmicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2 Estruturas de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.3 Estruturas de mapas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.4 Iteradores e intervalos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.5 Outras estruturas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.6 Comparação com a classificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5 Pesquisa completa 47
5.1 Gerando subconjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.2 Gerando permutações . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.3 Retrocesso . ... 50
5.4 Podando a pesquisa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.5 Encontre-se no meio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
iii
6 Algoritmos gananciosos 57
6.1 Problema da moeda . ... 57
6.2 Agendamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6.3 Tarefas e prazos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.4 Minimização de somas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.5 Compressão de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
7 Programação dinâmica 65
7.1 Problema da moeda . ... 65
7.2 Maior subsequência crescente . . . . . . . . . . . . . . . . . . . . . . . 70
7.3 Caminhos em uma grade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
7.4 Problemas com a mochila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.5 Editar distância . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
7.6 Contagem de ladrilhos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
8 Análise amortizada 77
8.1 Método dos dois ponteiros ........................... 77
8.2 Elementos menores mais próximos . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
8.3 Janela deslizante mínima . . . . . . . . . . . . . . . . . . . . . . . . . . 81
9 Consultas de intervalo 83
9.1 Consultas de matriz estática ............................ 84
9.2 Árvore indexada binária ............................ 86
9.3 Árvore de segmentos . ... 89
9.4 Técnicas adicionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
Manipulação de 10 bits 95
10.1 Representação de bits ............................. 95
10.2 Operações de bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
10.3 Representando conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
10.4 Otimizações de bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
10.5 Programação dinâmica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4
13 Caminhos mais curtos 123
13.1 Algoritmo de Bellman–Ford ......................... 123
13.2 Algoritmo de Dijkstra. . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
13.3 Algoritmo de Floyd–Warshall . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
você
III Tópicos avançados 195
21 Teoria dos números 197
21.1 Primos e fatores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
21.2 Aritmética modular ............................ 201
21.3 Resolução de equações ............................. 204
21.4 Outros resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
22 Combinatória 207
22.1 Coeficientes binomiais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
22.2 Números catalães . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
22.3 Inclusão-exclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
22.4 Lema de Burnside . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
22.5 Fórmula de Cayley .............................. 215
23 Matrizes 217
23.1 Operações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
23.2 Recorrências lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
23.3 Gráficos e matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
24 Probabilidade 225
24.1 Cálculo ................................. 225
24.2 Eventos . ... 226
24.3 Variáveis aleatórias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
24.4 Cadeias de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
24.5 Algoritmos aleatórios . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
nós
29 Geometria 265
29.1 Números complexos ............................. 266
29.2 Pontos e retas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
29.3 Área do polígono . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
29.4 Funções de distância . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
Bibliografia 281
vii
viii
Prefácio
O propósito deste livro é dar a você uma introdução completa à programação competitiva. É
assumido que você já conhece os conceitos básicos de programação, mas não é necessário
nenhum conhecimento prévio em programação competitiva.
O livro é especialmente destinado a estudantes que querem aprender algoritmos e
possivelmente participar da Olimpíada Internacional de Informática (IOI) ou do Concurso
Internacional de Programação Universitária (ICPC). Claro, o livro também é adequado para
qualquer outra pessoa interessada em programação competitiva.
Leva muito tempo para se tornar um bom programador competitivo, mas também é
uma oportunidade de aprender muito. Você pode ter certeza de que obterá uma boa
compreensão geral de algoritmos se passar um tempo lendo o livro, resolvendo problemas
e participando de concursos.
O livro está em desenvolvimento contínuo. Você sempre pode enviar feedback sobre o
livro paraahslaaks@[Link] .
ix
x
Parte I
Técnicas básicas
1
Capítulo 1
Introdução
Linguagens de programação
3
inteiros grandes. Ainda assim, a maioria dos problemas em concursos de programação são definidos de forma que
usar uma linguagem de programação específica não seja uma vantagem injusta.
Todos os programas de exemplo neste livro são escritos em C++, e as estruturas de dados e
algoritmos da biblioteca padrão são frequentemente usados. Os programas seguem o padrão C++11,
que pode ser usado na maioria dos concursos hoje em dia. Se você ainda não sabe programar em C++,
agora é um bom momento para começar a aprender.
# incluir<bits/stdc++.h>
usando namespacepadrão;
Inteiroprincipal() {
// a solução vem aqui
}
Entrada e saída
Na maioria dos concursos, fluxos padrão são usados para ler a entrada e escrever a
saída. Em C++, os fluxos padrão sãocinzapara entrada ecortepara saída. Além disso, as
funções Cescaneareimprimirfpode ser usado.
A entrada para o programa geralmente consiste em números e strings que são separados
por espaços e quebras de linha. Eles podem ser lidos a partir docinzatransmitir da seguinte
forma:
Inteiroum, b;
sequência x;
cin >> a >> b >> x;
4
Esse tipo de código sempre funciona, assumindo que haja pelo menos um espaço ou
quebra de linha entre cada elemento na entrada. Por exemplo, o código acima pode ler
ambas as entradas a seguir:
123 456
macaco
ios::sync_with_stdio(0);
[Link](0);
Inteiroum, b;
escanear("%d %d", &a, &b);
corda s;
obter linha(cin, s);
enquanto(cin >> x) {
// código
}
Este loop lê elementos da entrada um após o outro, até que não haja mais dados
disponíveis na entrada.
5
Em alguns sistemas de concurso, arquivos são usados para entrada e saída. Uma solução
fácil para isso é escrever o código como de costume usando fluxos padrão, mas adicionar as
seguintes linhas ao início do código:
Inteiros
O tipo inteiro mais usado em programação competitiva éem,que é um tipo de 32 bits com
um intervalo de valores de−231. . . 231−1 ou cerca de−2·109. . . 2·109. Se o tipo Inteironão é
suficiente, o tipo de 64 bitslongo longopode ser usado. Tem uma faixa de valor de
− 263. . . 263−1 ou cerca de−9·1018. . . 9·1018.
O código a seguir define umlongo longovariável:
Inteiroum = 123456789;
longo longob = a*a;
cout << b <<"\n";// -1757895751
Aritmética modular
Nós denotamos porxmodeuo restante quandoxé dividido poreu. Por exemplo, 17
mod 5=2, porque 17=3·5+2.
Às vezes, a resposta para um problema é um número muito grande, mas é o suficiente
para produzi-lo ”móduloeu”, ou seja, o resto quando a resposta é dividida poreu(para
6
exemplo, “módulo 109+7”). A ideia é que mesmo que a resposta real seja muito
grande, basta usar os tiposInteiroelongo longo.
Uma propriedade importante do resto é que, além da adição, subtração e
multiplicação, o resto pode ser obtido antes da operação:
Dessa forma, podemos pegar o restante após cada operação e os números nunca
ficarão muito grandes.
Por exemplo, o código a seguir calculanão!, o fatorial denão, móduloeu:
longo longox = 1;
para(Inteiroeu = 2; eu <= n; eu++) {
x = (x*i)%m;
}
cout << x%m <<"\n";
x = x%m;
se(x < 0) x += m;
imprimirf("%.9f\n", x);
Uma dificuldade ao usar números de ponto flutuante é que alguns números não podem ser
representados com precisão como números de ponto flutuante, e haverá erros de
arredondamento. Por exemplo, o resultado do código a seguir é surpreendente:
dobrox = 0,3*3+0,1;
imprimirf("%.20f\n", x);// 0,999999999999999988898
7
Devido a um erro de arredondamento, o valor dexé um pouco menor que 1, enquanto o
valor correto seria 1.
É arriscado comparar números de ponto flutuante com o operador ==, porque é
possível que os valores sejam iguais, mas não são devido a erros de precisão. Uma
maneira melhor de comparar números de ponto flutuante é assumir que dois números
são iguais se a diferença entre eles for menor quee, ondeeé um número pequeno.
Observe que, embora os números de ponto flutuante sejam imprecisos, os inteiros até um certo
limite ainda podem ser representados com precisão. Por exemplo, usandodobro,é possível
representar com precisão todos os números inteiros cujo valor absoluto é no máximo 253.
Código de encurtamento
Código curto é ideal em programação competitiva, porque os programas devem ser escritos o
mais rápido possível. Por causa disso, programadores competitivos geralmente definem nomes
mais curtos para tipos de dados e outras partes do código.
Nomes de tipos
Usando o comandotipo definidoé possível dar um nome mais curto a um tipo de dado. Por
exemplo, o nomelongo longoé longo, então podemos definir um nome mais curtotodos:
ll a = 123456789; ll b =
987654321; cout <<
a*b <<"\n";
O comandotipo definidotambém pode ser usado com tipos mais complexos. Por
exemplo, o código a seguir fornece o nomenóspara um vetor de inteiros e o nomepipara
um par que contém dois inteiros.
8
Macros
Outra maneira de encurtar o código é definirmacros. Uma macro significa que certas
strings no código serão alteradas antes da compilação. Em C++, as macros são definidas
usando o #definirpalavra-chave.
Por exemplo, podemos definir as seguintes macros:
# definirF primeiro
# definirS segundo
# definirPB push_back
# definirMP fazer_par
v.push_back(criar_par(y1,x1));
v.push_back(criar_par(y2,x2)); Inteirod
= v[i].primeiro+v[i].segundo;
[Link](MP(y1,x1));
[Link](MP(y2,x2));
Inteirod = v[i].F+v[i].S;
Uma macro também pode ter parâmetros que tornam possível encurtar loops
e outras estruturas. Por exemplo, podemos definir a seguinte macro:
REP(i,1,n) {
pesquisar(i);
}
Às vezes, macros causam bugs que podem ser difíceis de detectar. Por exemplo,
considere a seguinte macro que calcula o quadrado de um número:
# definirQuadrado(a) a*a
9
corresponde ao código
# definirSQ(a) (a)*(a)
Agora o código
corresponde ao código
Matemática
A matemática desempenha um papel importante na programação competitiva, e não é
possível se tornar um programador competitivo de sucesso sem ter boas habilidades
matemáticas. Esta seção discute alguns conceitos e fórmulas matemáticas importantes
que são necessários mais adiante no livro.
Fórmulas de soma
∑
não
xo=1o+2o+3o+. . .+nãoo,
x=1
ondeoé um inteiro positivo, tem uma fórmula de forma fechada que é um polinômio
de grauk+1. Por exemplo1,
∑
não não(n+1)
x =1+2+3+. . .+n =
x=1 2
e
∑
não não(n+1)(2n+1)
x2 =12+22+32+. . .+não2= .
x=1 6
3, 7, 11, 15
1Existe até uma fórmula geral para tais somas, chamadaFórmula de Faulhaber, mas é muito complexo
para ser apresentado aqui.
10
é uma progressão aritmética com constante 4. A soma de uma progressão aritmética
pode ser calculada usando a fórmula
não(um + b)
︸um+·︷·︷·+b︸=
2
nãonúmeros
3, 6, 12, 24
S = a+ak+ak2+···+b.
Multiplicando ambos os lados poro, nós temos
kS = ak+ak2+ah3+···+livro de bolso,
e resolver a equação
kS −S = bk−a
produz a fórmula.
Um caso especial de uma soma de uma progressão geométrica é a fórmula
1+2+4+8+. . .+2n−1=2não−1.
UMsoma harmônicaé uma soma da forma
não1
∑ 1 1 1
=1+ + + ...+ .
x=1x 2 3 não
Um limite superior para uma soma harmônica é log2(não)+1. Ou seja, podemos modificar
cada termo 1/opara queotorna-se a potência de dois mais próxima que não excedeo. Por
exemplo, quandon =6, podemos estimar a soma da seguinte forma:
11111 11111
1+ + + + + ≤1+ + + + +.
23456 22444
Este limite superior consiste em log2(não)+1 partes (1, 2·1/2, 4·1/4, etc.), e o valor de cada
parte é no máximo 1.
11
Teoria dos conjuntos
X ={2, 4, 7}
4∈Xe 5∉X.
;, {2}, {4}, {7}, {2, 4}, {2, 7}, {4, 7} e {2, 4, 7}.
Alguns conjuntos usados com frequência sãoN (números naturais),Z (inteiros),P (números
racionais) eR (números reais). O conjuntoNãopode ser definido de duas maneiras, dependendo
da situação: ouNão={0, 1, 2, . . .} ouNão={1, 2, 3, ...}.
Também podemos construir um conjunto usando uma regra da forma
{e(não) :não∈S},
X ={2não:não∈Z}
12
Lógica
O valor de uma expressão lógica éverdadeiro(1) oufalso(0). Os operadores lógicos
mais importantes são¬(negação),∧(conjunção),∨(disjunção),⇒ (implicação) e⇔(
equivalência). A tabela a seguir mostra os significados desses operadores:
Sobre¬UM¬BA∧BA∨BA⇒BA⇔B
0 0 1 1 0 0 1 1
0 1 1 0 0 1 1 0
1 0 0 1 0 1 0 0
1 1 0 0 1 1 1 1
significa que para cada elementoxno conjunto, há um elementoeno conjunto tal queeé menor
quex. Isso é verdadeiro no conjunto dos números inteiros, mas falso no conjunto dos números
naturais.
Usando a notação descrita acima, podemos expressar muitos tipos de proposições
lógicas. Por exemplo,
significa que se um númeroxé maior que 1 e não é um número primo, então existem
númerosumebque são maiores que 1 e cujo produto éx. Esta proposição é verdadeira
no conjunto dos inteiros.
Funções
A funçãobxcarredonda o númeroxaté um inteiro, e a funçãoexe arredonda o
númeroxaté um inteiro. Por exemplo,
13
Ofatorialnão! pode ser definido
∏
não
x =1·2·3·. . .·não
x=1
ou recursivamente
0! = 1
não!= não·(n−1)!
ONúmeros de Fibonaccisurgem em muitas situações, Eles podem ser definidos
recursivamente, como segue:
e(0) = 0
e(1) = 1
e(não) = e(n−1)+e(n−2)
Existe também uma fórmula de forma fechada para calcular os números de Fibonacci, que às
vezes é chamadaFórmula de Binet:
p p
(1+5)não−(1− 5)não
e(não)= p .
2não5
Logaritmos
Ologaritmode um númeroxé denotado logo(x), ondeoé a base do logaritmo. De
acordo com a definição, logo(x)=umexatamente quandooum= x.
Uma propriedade útil dos logaritmos é que logo(x) é igual ao número de vezes que
temos que dividirxporoantes de chegarmos ao número 1. Por exemplo, log2(32)=5 porque
são necessárias 5 divisões por 2:
32→16→8→4→2→1
Logaritmos são frequentemente usados na análise de algoritmos, porque muitos
algoritmos eficientes reduzem algo pela metade a cada passo. Portanto, podemos estimar a
eficiência de tais algoritmos usando logaritmos.
O logaritmo de um produto é
registroo(sobre)=registroo(um)+registroo(b),
e consequentemente,
registroo(xnão)=não·registroo(x).
14
e usando isso, é possível calcular logaritmos para qualquer base se houver uma maneira de
calcular logaritmos para alguma base fixa.
Ologaritmo naturalem(x) de um númeroxé um logaritmo cuja base é e≈
2.71828. Outra propriedade dos logaritmos é que o número de dígitos de um
inteiroxna basebébregistrob(x)+1c. Por exemplo, a representação de 123 na base 2
é 1111011 ebregistro2(123)+1c =7.
Concursos e recursos
IOI
A Olimpíada Internacional de Informática (IOI) é uma competição anual de
programação para alunos do ensino médio. Cada país pode enviar uma equipe de
quatro alunos para a competição. Geralmente, há cerca de 300 participantes de 80
países.
O IOI consiste em duas competições de cinco horas de duração. Em ambas as competições, os
participantes são solicitados a resolver três tarefas de algoritmo de várias dificuldades. As tarefas são
divididas em subtarefas, cada uma das quais tem uma pontuação atribuída. Mesmo que os
competidores sejam divididos em equipes, eles competem como indivíduos.
O programa IOI [41] regula os tópicos que podem aparecer nas tarefas IOI.
Quase todos os tópicos do programa IOI são abordados neste livro.
Os participantes do IOI são selecionados por meio de concursos nacionais. Antes do
IOI, muitos concursos regionais são organizados, como a Baltic Olympiad in
Informatics (BOI), a Central European Olympiad in Informatics (CEOI) e a Asia-Pacific
Informatics Olympiad (APIO).
Alguns países organizam concursos de prática online para futuros participantes do IOI,
como a Competição Aberta Croata em Informática [11] e a Olimpíada de Computação dos
EUA [68]. Além disso, uma grande coleção de problemas de concursos poloneses está
disponível online [60].
CIPC
O International Collegiate Programming Contest (ICPC) é um concurso anual de
programação para estudantes universitários. Cada equipe no concurso consiste em três
estudantes e, diferentemente do IOI, os estudantes trabalham juntos; há apenas um
computador disponível para cada equipe.
O ICPC consiste em várias etapas e, finalmente, as melhores equipes são convidadas para as
Finais Mundiais. Embora haja dezenas de milhares de participantes na competição, há apenas
um pequeno número2de vagas finais disponíveis, então, mesmo avançar para as finais é uma
grande conquista em algumas regiões.
Em cada concurso do ICPC, as equipes têm cinco horas de tempo para resolver cerca de dez problemas
de algoritmo. Uma solução para um problema é aceita somente se resolver todos os casos de teste de forma
eficiente. Durante o concurso, os competidores podem visualizar os resultados de outros
2O número exato de vagas finais varia de ano para ano; em 2017, houve 133 vagas finais.
15
equipes, mas na última hora o placar fica congelado e não é possível ver os
resultados dos últimos envios.
Os tópicos que podem aparecer no ICPC não são tão bem especificados quanto aqueles
no IOI. Em todo caso, está claro que mais conhecimento é necessário no ICPC,
especialmente mais habilidades matemáticas.
Concursos online
Também há muitos concursos online abertos para todos. No momento, o site de
concurso mais ativo é o Codeforces, que organiza concursos semanalmente. No
Codeforces, os participantes são divididos em duas divisões: iniciantes competem na
Div2 e programadores mais experientes na Div1. Outros sites de concurso incluem
AtCoder, CS Academy, HackerRank e Topcoder.
Algumas empresas organizam concursos online com finais presenciais. Exemplos de tais
concursos são Facebook Hacker Cup, Google Code Jam e [Link]. Claro, as empresas
também usam esses concursos para recrutamento: ter um bom desempenho em um concurso é
uma boa maneira de provar suas habilidades.
Livros
Já existem alguns livros (além deste livro) que focam em programação competitiva
e resolução de problemas algorítmicos:
Os dois primeiros livros são destinados a iniciantes, enquanto o último livro contém
material avançado.
Claro, livros de algoritmos gerais também são adequados para programadores competitivos.
Alguns livros populares são:
16
Capítulo 2
Complexidade de tempo
Regras de cálculo
A complexidade temporal de um algoritmo é denotadaO(···)onde os três pontos
representam alguma função. Normalmente, a variávelnãodenota o tamanho da entrada.
Por exemplo, se a entrada for uma matriz de números,nãoserá o tamanho da matriz e, se a
entrada for uma string,nãoserá o comprimento da string.
Laços
Um motivo comum pelo qual um algoritmo é lento é que ele contém muitos loops que passam
pela entrada. Quanto mais loops aninhados o algoritmo contém, mais lento ele é. Se houvero
loops aninhados, a complexidade de tempo éO(nãoo).
Por exemplo, a complexidade de tempo do código a seguir éO(não):
17
Ordem de grandeza
Uma complexidade de tempo não nos diz o número exato de vezes que o código dentro de
um loop é executado, mas apenas mostra a ordem de magnitude. Nos exemplos a seguir, o
código dentro do loop é executado 3não,n+5 eenão/2evezes, mas a complexidade temporal
de cada código éO(não).
para(Inteiroeu = 1; eu <= n; eu += 2) {
// código
}
Fases
Se o algoritmo consiste em fases consecutivas, a complexidade de tempo total é a
maior complexidade de tempo de uma única fase. A razão para isso é que a fase mais
lenta é geralmente o gargalo do código.
Por exemplo, o código a seguir consiste em três fases com complexidades de tempo O(não),
O(não2) eO(não). Assim, a complexidade de tempo total éO(não2).
18
Várias variáveis
Às vezes, a complexidade de tempo depende de vários fatores. Neste caso, a fórmula de
complexidade de tempo contém várias variáveis.
Por exemplo, a complexidade de tempo do código a seguir éO(nm):
Recursão
A complexidade de tempo de uma função recursiva depende do número de vezes que a
função é chamada e da complexidade de tempo de uma única chamada. A complexidade de
tempo total é o produto desses valores.
Por exemplo, considere a seguinte função:
vazioe(Inteiron) {
se(n == 1)retornar;
f(n-1);
}
vaziog(Inteiron) {
se(n == 1)retornar;
g(n-1);
g(n-1);
}
Neste caso, cada chamada de função gera duas outras chamadas, exceto paran =1. Vamos ver o
que acontece quandogé chamado com parâmetronão. A tabela a seguir mostra as chamadas de
função produzidas por esta única chamada:
g(1) 2n−1
1+2+4+···+2n−1=2não−1=O(2não).
19
Classes de complexidade
O(registronão) Umlogarítmicoalgoritmo geralmente reduz pela metade o tamanho da entrada em cada etapa. O
o tempo de execução de tal algoritmo é logarítmico, porque log2nãoé igual ao
número de vezesnãodeve ser dividido por 2 para obter 1.
p
O(não) Umalgoritmo de raiz quadradaé mais lento queO(registronão) mas mais rápido queO(não).
p p p
Uma propriedade especial das raízes quadradas é quen não, então a raiz quadradanão
= n/ fica, em certo sentido, no meio da entrada.
O(não) Umlinearo algoritmo passa pela entrada um número constante de vezes. Este
geralmente é a melhor complexidade de tempo possível, porque geralmente é necessário
acessar cada elemento de entrada pelo menos uma vez antes de relatar a resposta.
O(nãoregistronão) Essa complexidade de tempo geralmente indica que o algoritmo classifica a entrada,
porque a complexidade de tempo dos algoritmos de classificação eficientes éO(nãoregistronão
). Outra possibilidade é que o algoritmo utilize uma estrutura de dados onde cada operação
levaO(registronão) tempo.
O(2não) Essa complexidade de tempo geralmente indica que o algoritmo itera por meio de
todos os subconjuntos dos elementos de entrada. Por exemplo, os subconjuntos de {1, 2, 3}
são;, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3} e {1, 2, 3}.
O(não!) Essa complexidade de tempo geralmente indica que o algoritmo itera por meio de
todas as permutações dos elementos de entrada. Por exemplo, as permutações de
{1, 2, 3} são (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) e (3, 2, 1).
20
Estimando a eficiência
Ao calcular a complexidade de tempo de um algoritmo, é possível verificar, antes de
implementar o algoritmo, se ele é eficiente o suficiente para o problema. O ponto de
partida para estimativas é o fato de que um computador moderno pode executar algumas
centenas de milhões de operações em um segundo.
Por exemplo, suponha que o limite de tempo para um problema é de um segundo e o
tamanho da entrada én =105. Se a complexidade do tempo forO(não2), o algoritmo executará
cerca de (105)2=1010operações. Isso deve levar pelo menos algumas dezenas de segundos, então
o algoritmo parece ser muito lento para resolver o problema.
Por outro lado, dado o tamanho da entrada, podemos tentaradivinhara complexidade de
tempo necessária do algoritmo que resolve o problema. A tabela a seguir contém algumas
estimativas úteis assumindo um limite de tempo de um segundo.
Muitas vezes, há vários algoritmos possíveis para resolver um problema, de modo que suas
complexidades de tempo são diferentes. Esta seção discute um problema clássico que tem uma
abordagem diretaO(não3) solução. No entanto, ao projetar um algoritmo melhor, é possível
resolver o problema emO(não2) tempo e até mesmo emO(não) tempo.
Dada uma matriz denãonúmeros, nossa tarefa é calcular ossoma máxima do
subarray, ou seja, a maior soma possível de uma sequência de valores consecutivos na
matriz2. O problema é interessante quando pode haver valores negativos no array. Por
exemplo, no array
−1 2 4 −3 5 2 −5 2
21
o seguinte subarray produz a soma máxima 10:
−1 2 4 −3 5 2 −5 2
Algoritmo 1
Uma maneira direta de resolver o problema é percorrer todos os subarrays
possíveis, calcular a soma dos valores em cada subarray e manter a soma máxima.
O código a seguir implementa esse algoritmo:
Inteiromelhor = 0;
para(Inteiroa = 0; a < n; a++) {
para(Inteirob = a; b < n; b++) {
Inteirosoma = 0;
para(Inteirok = a; k <= b; k++) {
soma += array[k];
}
melhor = max(melhor,soma);
}
}
cout << melhor <<"\n";
Algoritmo 2
É fácil tornar o Algoritmo 1 mais eficiente removendo um loop dele. Isso é possível
calculando a soma ao mesmo tempo em que a extremidade direita do subarray se
move. O resultado é o seguinte código:
Inteiromelhor = 0;
para(Inteiroa = 0; a < n; a++) {
Inteirosoma = 0;
para(Inteirob = a; b < n; b++) {
soma += array[b];
melhor = max(melhor,soma);
}
}
cout << melhor <<"\n";
22
Algoritmo 3
Surpreendentemente, é possível resolver o problema emO(não) tempo3, o que significa
que apenas um loop é suficiente. A ideia é calcular, para cada posição do array, a soma
máxima de um subarray que termina naquela posição. Depois disso, a resposta para o
problema é o máximo dessas somas.
Considere o subproblema de encontrar o subarray de soma máxima que termina na
posiçãoo. Existem duas possibilidades:
O algoritmo contém apenas um loop que passa pela entrada, então a complexidade de tempo éO(
não). Essa também é a melhor complexidade de tempo possível, porque qualquer algoritmo para o
problema precisa examinar todos os elementos da matriz pelo menos uma vez.
Comparação de eficiência
É interessante estudar o quão eficientes os algoritmos são na prática. A tabela a seguir
mostra os tempos de execução dos algoritmos acima para diferentes valores denão em um
computador moderno.
Em cada teste, a entrada foi gerada aleatoriamente. O tempo necessário para ler a
entrada não foi medido.
3Em [8], este algoritmo de tempo linear é atribuído a JB Kadane, e o algoritmo é algumas vezes chamado
Algoritmo de Kadane.
23
A comparação mostra que todos os algoritmos são eficientes quando o tamanho da entrada
é pequeno, mas entradas maiores trazem diferenças notáveis nos tempos de execução dos
algoritmos. O algoritmo 1 se torna lento quandon =104, e o Algoritmo 2 se torna lento quandon
=105. Somente o Algoritmo 3 é capaz de processar até mesmo as maiores entradas
instantaneamente.
24
Capítulo 3
Classificação
Teoria da classificação
1 3 8 2 9 2 5 6
1 2 2 3 5 6 8 9
O(não2)algoritmos
Algoritmos simples para classificar uma matriz funcionam emO(não2) tempo. Tais algoritmos são
curtos e geralmente consistem em dois loops aninhados. Um famosoO(não2) classificação de tempo
25
algoritmo éclassificação por bolhasonde os elementos “borbulham” na matriz de acordo com
seus valores.
A classificação por bolhas consiste emnãorodadas. Em cada rodada, o algoritmo itera
pelos elementos do array. Sempre que dois elementos consecutivos são encontrados que
não estão na ordem correta, o algoritmo os troca. O algoritmo pode ser implementado da
seguinte forma:
1 3 8 2 9 2 5 6
1 3 2 8 9 2 5 6
1 3 2 8 2 9 5 6
1 3 2 8 2 5 9 6
1 3 2 8 2 5 6 9
Inversões
A classificação por bolhas é um exemplo de um algoritmo de classificação que sempre troca
consecutivo elementos na matriz. Acontece que a complexidade de tempo de tal algoritmo é
semprepelo menosO(não2), porque no pior dos casos,O(não2) swaps são necessários para
classificar a matriz.
Um conceito útil ao analisar algoritmos de classificação é uminversão: um par de elementos
de matriz (variedade[um],variedade[b]) tal queum < bevariedade[um]>variedade[b], ou seja, os
elementos estão na ordem errada. Por exemplo, o array
26
1 2 2 6 3 5 9 8
tem três inversões: (6, 3), (6, 5) e (9, 8). O número de inversões indica quanto
trabalho é necessário para ordenar o array. Um array é completamente ordenado
quando não há inversões. Por outro lado, se os elementos do array estiverem na
ordem inversa, o número de inversões é o maior possível:
não(n−1)
1+2+···+(n−1)= =O(não2)
2
Trocar um par de elementos consecutivos que estão na ordem errada remove
exatamente uma inversão do array. Portanto, se um algoritmo de classificação só pode
trocar elementos consecutivos, cada troca remove no máximo uma inversão, e a
complexidade de tempo do algoritmo é de pelo menosO(não2).
O(nãoregistronão)algoritmos
É possível classificar uma matriz de forma eficiente emO(nãoregistronão) tempo usando algoritmos
que não se limitam a trocar elementos consecutivos. Um desses algoritmos émesclar classificação1,
que é baseado em recursão.
A classificação por mesclagem classifica uma submatrizvariedade[um. . .b] do seguinte modo:
Merge sort é um algoritmo eficiente, porque ele reduz pela metade o tamanho do subarray
em cada etapa. A recursão consiste emO(registronão) níveis, e o processamento de cada nível
levaO(não) tempo. Mesclando os subarraysvariedade[um. . .o] evariedade[o +1. . .b] é possível
em tempo linear, porque eles já estão classificados.
Por exemplo, considere classificar a seguinte matriz:
1 3 6 2 8 2 5 9
1 3 6 2 8 2 5 9
1 2 3 6 2 5 8 9
1De acordo com [47], o merge sort foi inventado por J. von Neumann em 1945.
27
Por fim, o algoritmo mescla as submatrizes classificadas e cria a matriz
classificada final:
1 2 2 3 5 6 8 9
É possível classificar uma matriz mais rápido do que emO(nãoregistronão) tempo? Acontece que
isso énãopossível quando nos restringimos a algoritmos de classificação baseados na
comparação de elementos de matriz.
O limite inferior para a complexidade de tempo pode ser provado considerando a
classificação como um processo em que cada comparação de dois elementos fornece mais
informações sobre o conteúdo do array. O processo cria a seguinte árvore:
x < y?
x < y? x < y?
Aqui "x < y?” significa que alguns elementosxeesão comparados. Sex < y, o processo
continua para a esquerda e, caso contrário, para a direita. Os resultados do processo são as
maneiras possíveis de classificar a matriz, um total denão! maneiras. Por esta razão, a altura da
árvore deve ser de pelo menos
registro2(não!)=registro2(1)+registro2(2)+···+registro2(não).
Obtemos um limite inferior para esta soma escolhendo o últimonão/2 elementos e alterando o
valor de cada elemento para log2(não/2). Isso produz uma estimativa
registro2(não!)≥(não/2)·registro2(não/2),
28
Por exemplo, a matriz
1 3 6 9 9 3 5 9
1 2 3 4 5 6 7 8 9
1 0 2 0 1 1 0 0 3
Classificação em C++
Quase nunca é uma boa ideia usar um algoritmo de classificação caseiro em um concurso,
porque há boas implementações disponíveis em linguagens de programação. Por exemplo,
a biblioteca padrão C++ contém a funçãoorganizarque pode ser facilmente usado para
classificar matrizes e outras estruturas de dados.
Há muitos benefícios em usar uma função de biblioteca. Primeiro, economiza
tempo porque não há necessidade de implementar a função. Segundo, a
implementação da biblioteca é certamente correta e eficiente: não é provável que uma
função de classificação caseira seja melhor.
Nesta seção veremos como usar o C++organizarfunção. O código a seguir
classifica um vetor em ordem crescente:
vetor<Inteiro> v = {4,2,5,3,5,8,3};
classificar([Link](),[Link]());
classificar([Link](),[Link]());
29
O código a seguir classifica a stringe:
corda s ="macaco";
classificar([Link](), [Link]());
Classificar uma string significa que os caracteres da string são classificados. Por
exemplo, a string ”monkey” se torna ”ekmnoy”.
Operadores de comparação
vetor<par<Inteiro,Inteiro>> v;
v.push_back({1,5});
v.push_back({2,3});
v.push_back({1,2});
classificar([Link](), [Link]());
Depois disso, a ordem dos pares é (1, 2), (1, 5) e (2, 3).
De forma semelhante, tuplas (tupla)são classificados principalmente pelo primeiro elemento,
secundariamente pelo segundo elemento, etc.2:
vetor<tupla<Inteiro,Inteiro,Inteiro
>> v; v.push_back({2,1,4});
v.push_back({1,5,3});
v.push_back({2,1,3});
classificar([Link](), [Link]());
Depois disso, a ordem das tuplas é (1, 5, 3), (2, 1, 3) e (2, 1, 4).
2Observe que em alguns compiladores mais antigos, a funçãofazer_tuplatem que ser usado para criar
30
coordenada x e secundariamente pela coordenada y.
estruturaP {
Inteirox, e;
operador bool<(constanteP &p) {
se(x != px)retornarx < px; senão
retorney < py;
}
};
Funções de comparação
Também é possível dar uma resposta externafunção de comparaçãopara oorganizarfunção como
uma função de retorno de chamada. Por exemplo, a seguinte função de comparaçãocompclassifica
strings principalmente por comprimento e secundariamente por ordem alfabética:
boolcomp(string a, string b) {
se([Link]() != [Link]())[Link]() < [Link]();
retornarum < b;
}
Pesquisa binária
31
Método 1
A maneira usual de implementar a busca binária se assemelha a procurar uma palavra em um
dicionário. A busca mantém uma região ativa no array, que inicialmente contém todos os
elementos do array. Então, uma série de etapas é realizada, cada uma das quais reduz pela
metade o tamanho da região.
Em cada etapa, a busca verifica o elemento do meio da região ativa. Se o
elemento do meio for o elemento alvo, a busca termina. Caso contrário, a busca
continua recursivamente para a metade esquerda ou direita da região,
dependendo do valor do elemento do meio.
A ideia acima pode ser implementada da seguinte forma:
Inteiroa = 0, b = n-1;
enquanto(a <= b) {
Inteirok = (a+b)/2; se
(matriz[k] == x) {
// x encontrado no índice k
}
se(matriz[k] > x) b = k-1;
outroa = k+1;
}
Nesta implementação, a região ativa éum. . .b, e inicialmente a região é 0. . .n−1. O algoritmo
reduz pela metade o tamanho da região em cada etapa, de modo que a complexidade do tempo
éO(registronão).
Método 2
Um método alternativo para implementar a busca binária é baseado em uma maneira
eficiente de iterar pelos elementos do array. A ideia é fazer saltos e diminuir a
velocidade quando nos aproximamos do elemento alvo.
A busca percorre a matriz da esquerda para a direita, e o comprimento do salto inicial é
não/2. A cada passo, o comprimento do salto será reduzido pela metade: primeironão/4,
entãonão/8, não/16, etc., até que finalmente o comprimento seja 1. Após os saltos, o
elemento alvo foi encontrado ou sabemos que ele não aparece na matriz.
O código a seguir implementa a ideia acima:
Inteirok = 0;
para(Inteirob = n/2; b >= 1; b /= 2) {
enquanto(k+b < n && matriz[k+b] <= x) k += b;
}
se(matriz[k] == x) {
// x encontrado no índice k
}
32
Funções C++
A biblioteca padrão C++ contém as seguintes funções que são baseadas em busca
binária e funcionam em tempo logarítmico:
autok = limite_inferior(matriz,matriz+n,x)-matriz;
se(k < n && matriz[k] == x) {
// x encontrado no índice k
}
Inteirox = -1;
para(Inteirob = z; b >= 1; b /= 2) {
enquanto(!ok(x+b)) x += b;
}
Inteirok = x+1;
33
A busca encontra o maior valor dexpara qualOK(x) é[Link], o próximo valork = x+1
é o menor valor possível para o qualOK(o) éverdadeiro.O comprimento inicial do saltopor
tem que ser grande o suficiente, por exemplo algum valor para o qual sabemos de
antemão queOK(por) éverdadeiro.
O algoritmo chama a funçãoOKO(registropor) vezes, então a complexidade total do tempo
depende da funçã[Link] exemplo, se a função funciona emO(não) tempo, a complexidade
total do tempo éO(nãoregistropor).
• e(x)>e(x+1) quandox≥o.
A ideia é usar a busca binária para encontrar o maior valor dexpara qual e(x)<e(
x+1). Isto implica quek = x+1 porquee(x+1)>e(x+2). O código a seguir implementa a
pesquisa:
Inteirox = -1;
para(Inteirob = z; b >= 1; b /= 2) {
enquanto(f(x+b) < f(x+b+1)) x += b;
}
Inteirok = x+1;
Note que, diferentemente da busca binária comum, aqui não é permitido que
valores consecutivos da função sejam iguais. Neste caso, não seria possível saber
como continuar a busca.
34
Capítulo 4
Estruturas de dados
Matrizes dinâmicas
vetor<Inteiro> v;
v.push_back(3);// [3]
v.push_back(2);// [3,2]
v.push_back(5);// [3,2,5]
35
Uma maneira mais curta de iterar por um vetor é a seguinte:
para(autox : v) {
corte << x <<"\n";
}
vetor<Inteiro> v;
v.push_back(5);
v.push_back(2);
cout << [Link]() <<"\n";// 2
v.pop_back();
cout << [Link]() <<"\n";// 5
vetor<Inteiro> v = {2,4,2,5,1};
cadeia de caracteres a =
"chapéu"; sequência b = a+a;
cout << b <<"\n";// chapéu chapéu
b[5] ='você';
cout << b <<"\n";// chapéus
sequência c = [Link](3,4); cout <<
c <<"\n";// tiva
36
Estruturas de conjuntos
UMdefiniré uma estrutura de dados que mantém uma coleção de elementos. As operações
básicas de conjuntos são inserção, busca e remoção de elementos.
A biblioteca padrão C++ contém duas implementações de conjunto: A estrutura definiré
baseado em uma árvore binária balanceada e suas operações funcionam emO(registronão)
tempo. A estruturaconjunto_desordenadousa hashing e suas operações funcionam emO(1)
tempo em média.
A escolha de qual implementação de conjunto usar é muitas vezes uma questão de
gosto. O benefício dodefinirestrutura é que ela mantém a ordem dos elementos e fornece
funções que não estão disponíveis emconjunto_não_ordenado.Por outro lado,
conjunto_desordenadopode ser mais eficiente.
O código a seguir cria um conjunto que contém inteiros e mostra algumas das
operações. A funçãoinseriradiciona um elemento ao conjunto, a funçãocontar
retorna o número de ocorrências de um elemento no conjunto e a função apagar
remove um elemento do conjunto.
conjunto<Inteiro> s;
[Link](3);
[Link](2);
[Link](5);
cout << [Link](3) <<"\n";// 1 cout
<< [Link](4) <<"\n";// 0
[Link](3);
[Link](4);
cout << [Link](3) <<"\n";// 0 cout
<< [Link](4) <<"\n";// 1
Um conjunto pode ser usado principalmente como um vetor, mas não é possível
acessar os elementos usando a notação []. O código a seguir cria um conjunto, imprime o
número de elementos nele e, em seguida, itera por todos os elementos:
conjunto<Inteiro> s = {2,5,6,8};
cout << [Link]() <<"\n";// 4
para(autox : s) {
corte << x <<"\n";
}
Uma propriedade importante dos conjuntos é que todos os seus elementos são
distinto. Assim, a funçãocontarsempre retorna 0 (o elemento não está no conjunto) ou
1 (o elemento está no conjunto) e a funçãoinserirnunca adiciona um elemento ao
conjunto se ele já estiver lá. O código a seguir ilustra isso:
conjunto<Inteiro> s;
[Link](5);
[Link](5);
[Link](5);
cout << [Link](5) <<"\n";// 1
37
C++ também contém as estruturasmulticonjuntoemulticonjunto_desordenadoque de outra
forma funcionam comodefinireconjunto_desordenadomas eles podem conter múltiplas instâncias de
um elemento. Por exemplo, no código a seguir, todas as três instâncias do número 5 são adicionadas a
um multiset:
multiconjunto<Inteiro
> s; [Link](5);
[Link](5);
[Link](5);
cout << [Link](5) <<"\n";// 3
[Link](5);
cout << [Link](5) <<"\n";// 0
Muitas vezes, apenas uma instância deve ser removida, o que pode ser feito da seguinte maneira:
[Link]([Link](5));
cout << [Link](5) <<"\n";// 2
Estruturas de mapas
mapa<sequência de
caracteres,Inteiro> m; m[
"macaco"] = 4; m["banana"] =
3; m["cravo"] = 9;
corte << m["banana"] <<"\n";// 3
Se o valor de uma chave for solicitado, mas o mapa não contiver, a chave será
automaticamente adicionada ao mapa com um valor padrão. Por exemplo, no código a
seguir, a chave ”aybabtu” com valor 0 é adicionada ao mapa.
mapa<sequência de caracteres,Inteiro> m;
38
A funçãocontarverifica se uma chave existe em um mapa:
se([Link]("Aybabtu")) {
// chave existe
}
para(autox : m) {
cout << [Link] <<" "<< [Link] <<"\n";
}
Iteradores e intervalos
Muitas funções na biblioteca padrão C++ operam com iteradores. Umiterador é uma
variável que aponta para um elemento em uma estrutura de dados.
Os iteradores frequentemente usadoscomeçarefimdefine um intervalo que contém todos os
elementos em uma estrutura de dados. O iteradorcomeçaraponta para o primeiro elemento na
estrutura de dados e o iteradorfimaponta para a posiçãodepoiso último elemento. A situação se
parece com o seguinte:
Iteradores são usados em funções de biblioteca padrão C++ que recebem um intervalo de elementos
em uma estrutura de dados. Normalmente, queremos processar todos os elementos em uma
estrutura de dados, então os iteradorescomeçarefimsão fornecidos para a função.
Por exemplo, o código a seguir classifica um vetor usando a funçãoorganizar,então
inverte a ordem dos elementos usando a funçãoreverter,e finalmente embaralha a ordem
dos elementos usando a funçãoembaralhamento aleatório.
Essas funções também podem ser usadas com um array comum. Nesse caso, as
funções recebem ponteiros para o array em vez de iteradores:
39
ordenar(a, a+n);
reverter(a, a+n);
random_shuffle(a, a+n);
Definir iteradores
Iteradores são frequentemente usados para acessar elementos de um conjunto. O código a seguir cria um
iteradoristoque aponta para o menor elemento em um conjunto:
conjunto<Inteiro>::iterador it = [Link]();
autoisto = [Link]();
O elemento para o qual um iterador aponta pode ser acessado usando o símbolo *. Por
exemplo, o código a seguir imprime o primeiro elemento no conjunto:
autoisto = [Link]();
cout << *isto <<"\n";
Os iteradores podem ser movidos usando os operadores ++ (para frente) e -- (para trás), o
que significa que o iterador se move para o próximo ou anterior elemento no conjunto.
O código a seguir imprime todos os elementos em ordem crescente:
autoisto = [Link](x); se
(ele == [Link]()) {
// x não foi encontrado
}
40
Por exemplo, o código a seguir encontra o elemento mais próximo dex:
autoisto = s.lower_bound(x);
se(ele == [Link]()) {
cout << *isso <<"\n"; }
senão se(ele == [Link]()) {
isto--;
cout << *isso <<"\n"; }
outro{
Inteiroa = *isso; isso--;
Inteirob = *isso;
se(xb < ax) cout << b <<"\n"; outro
cout << a <<"\n";
}
O código assume que o conjunto não está vazio e percorre todos os casos possíveis
usando um [Link], o iterador aponta para o menor elemento cujo valor é
pelo menosx. Seistoé igual acomeçar,o elemento correspondente é o mais próximo dex. Se
istoé igual afim,o maior elemento do conjunto é o mais próximo dex. Se nenhum dos casos
anteriores for válido, o elemento mais próximo dexé o elemento que corresponde aistoou o
elemento anterior.
Outras estruturas
Conjunto de bits
conjunto de bits<10> s;
s[1] = 1;
s[3] = 1;
s[4] = 1;
s[7] = 1;
corte << s[4] <<"\n";// 1 corte
<< s[5] <<"\n";// 0
O benefício de usar bitsets é que eles exigem menos memória do que arrays comuns,
porque cada elemento em um bitset usa apenas um bit de memória. Por exemplo, senãobits são
armazenados em umInteiromatriz, 32nãobits de memória serão usados, mas um conjunto de
bits correspondente requer apenasnãobits de memória. Além disso, os valores de um bitset
podem ser manipulados eficientemente usando operadores de bit, o que torna possível otimizar
algoritmos usando conjuntos de bit.
O código a seguir mostra outra maneira de criar o bitset acima:
41
A funçãocontarretorna o número de uns no bitset:
Deque
UMdequeé um array dinâmico cujo tamanho pode ser alterado eficientemente em ambas as
extremidades do array. Como um vetor, um deque fornece as funçõesempurrar_para_tráse
pop_back, mas também inclui as funçõesempurrar_frenteepop_frontque não estão disponíveis
em um vetor.
Um deque pode ser usado da seguinte maneira:
deque<Inteiro> e;
d.push_back(5);// [5]
d.push_back(2);// [5,2]
d.push_front(3);// [3,5,2]
d.pop_back();// [3,5]
d.pop_front();// [5]
Pilha
UMpilhaé uma estrutura de dados que fornece doisO(1) operações de tempo:
adicionar um elemento ao topo e remover um elemento do topo. Só é possível acessar
o elemento do topo de uma pilha.
O código a seguir mostra como uma pilha pode ser usada:
pilha<Inteiro> s;
[Link](3);
[Link](2);
[Link](5);
cout << [Link]();// 5
[Link]();
cout << [Link]();// 2
42
Fila
UMfilatambém fornece doisO(1) operações de tempo: adicionar um elemento ao
final da fila e remover o primeiro elemento da fila. Só é possível acessar o primeiro
e o último elemento de uma fila.
O código a seguir mostra como uma fila pode ser usada:
fila<Inteiro> q;
[Link](3);
[Link](2);
[Link](5);
cout << [Link]();// 3
[Link]();
cout << [Link]();// 2
Fila de prioridade
prioridade_fila<Inteiro> q;
[Link](3);
[Link](5);
[Link](7);
[Link](2);
cout << [Link]() <<"\n";// 7
[Link]();
cout << [Link]() <<"\n";// 5
[Link]();
[Link](6);
cout << [Link]() <<"\n";// 6
[Link]();
Se quisermos criar uma fila de prioridades que suporte encontrar e remover o menor
elemento, podemos fazer isso da seguinte maneira:
prioridade_fila<Inteiro,vetor<Inteiro>,maior<Inteiro>> q;
43
Estruturas de dados baseadas em políticas
Og++compilador também suporta algumas estruturas de dados que não fazem parte da biblioteca
padrão C++. Essas estruturas são chamadasbaseado em políticasestruturas de dados. Para usar essas
estruturas, as seguintes linhas devem ser adicionadas ao código:
# incluir<ext/pb_ds/assoc_container.hpp>
usando namespace__gnu_pbds;
tipo definidoárvore<Inteiro,tipo_nulo,menos<Inteiro>,rb_tree_tag,
atualização_de_nó_estatística_de_ordem_de_árvore> conjunto_indexado;
conjunto_indexado s;
[Link](2);
[Link](3);
[Link](7);
[Link](9);
A especialidade deste conjunto é que temos acesso aos índices que os elementos teriam em
um array ordenado. A funçãoencontrar_por_ordemretorna um iterador para o elemento em
uma determinada posição:
44
para ambas as listas. Por exemplo, para as listas
Algoritmo 1
Construímos um conjunto de elementos que aparecem emUM, e depois disso, iteramos
pelos elementos deBe verificar se cada elemento também pertence aUM. Isso é eficiente
porque os elementos deUMestão em um conjunto. Usando odefinirestrutura, a
complexidade de tempo do algoritmo éO(nãoregistronão).
Algoritmo 2
Não é necessário manter um conjunto ordenado, então, em vez dedefinirestrutura também
podemos usar oconjunto_desordenadoestrutura. Esta é uma maneira fácil de tornar o
algoritmo mais eficiente, porque só precisamos alterar a estrutura de dados subjacente. A
complexidade de tempo do novo algoritmo éO(não).
Algoritmo 3
Em vez de estruturas de dados, podemos usar a classificação. Primeiro, classificamos as duas listasUM
e B. Depois disso, iteramos por ambas as listas ao mesmo tempo e encontramos os elementos
comuns. A complexidade de tempo da classificação éO(nãoregistronão), e o resto do algoritmo
funciona emO(não) tempo, então a complexidade total do tempo éO(nãoregistronão).
Comparação de eficiência
A tabela a seguir mostra a eficiência dos algoritmos acima quandonãovaria e os
elementos das listas são inteiros aleatórios entre 1 . . . 109:
Os algoritmos 1 e 2 são iguais, exceto que eles usam estruturas de conjuntos diferentes.
Neste problema, esta escolha tem um efeito importante no tempo de execução, porque o
Algoritmo 2 é 4–5 vezes mais rápido que o Algoritmo 1.
No entanto, o algoritmo mais eficiente é o Algoritmo 3, que usa classificação. Ele usa apenas
metade do tempo em comparação ao Algoritmo 2. Curiosamente, a complexidade de tempo do
Algoritmo 1 e do Algoritmo 3 éO(nãoregistronão), mas apesar disso, o Algoritmo 3 é dez vezes
mais rápido. Isso pode ser explicado pelo fato de que a classificação é uma
45
procedimento simples e é feito apenas uma vez no início do Algoritmo 3, e o resto
do algoritmo funciona em tempo linear. Por outro lado, o Algoritmo 1 mantém
uma árvore binária balanceada complexa durante todo o algoritmo.
46
Capítulo 5
Pesquisa completa
Pesquisa completaé um método geral que pode ser usado para resolver quase
qualquer problema de algoritmo. A ideia é gerar todas as soluções possíveis para o
problema usando força bruta e, então, selecionar a melhor solução ou contar o
número de soluções, dependendo do problema.
A busca completa é uma boa técnica se houver tempo suficiente para passar por
todas as soluções, porque a busca geralmente é fácil de implementar e sempre dá a
resposta correta. Se a busca completa for muito lenta, outras técnicas, como
algoritmos gulosos ou programação dinâmica, podem ser necessárias.
Gerando subconjuntos
Método 1
Uma maneira elegante de percorrer todos os subconjuntos de um conjunto é usar recursão.
A seguinte funçãoprocurargera os subconjuntos do conjunto {0, 1, . . . ,n −1}. A função
mantém um vetorsubconjuntoque conterá os elementos de cada subconjunto. A busca
começa quando a função é chamada com parâmetro 0.
vazioprocurar(Inteirok) {
se(k == n) {
// subconjunto do processo
}outro{
pesquisar(k+1);
subconjunto.push_back(k);
pesquisar(k+1);
subconjunto.pop_back();
}
}
47
Quando a funçãoprocuraré chamado com parâmetroo, ele decide se deve incluir o
elementoono subconjunto ou não, e em ambos os casos, então chama a si mesmo com
o parâmetroo +1 No entanto, sek = n, a função percebe que todos os elementos foram
processados e um subconjunto foi gerado.
A árvore a seguir ilustra as chamadas de função quandon =3. Podemos sempre
escolher o ramo esquerdo (onão está incluído no subconjunto) ou o ramo direito (oestá
incluído no subconjunto).
procurar(0)
procurar(1) procurar(1)
procurar(3)procurar(3)procurar(3)procurar(3)procurar(3)procurar(3)procurar(3)procurar(3)
Método 2
Outra maneira de gerar subconjuntos é com base na representação de bits de inteiros. Cada
subconjunto de um conjunto denãoelementos podem ser representados como uma sequência
denãobits, que corresponde a um número inteiro entre 0 . . . 2não−1. Os bits na sequência
indicam quais elementos estão incluídos no subconjunto.
A convenção usual é que o último bit corresponde ao elemento 0, o segundo último bit
corresponde ao elemento 1, e assim por diante. Por exemplo, a representação de bit de 25
é 11001, que corresponde ao subconjunto {0, 3, 4}.
O código a seguir percorre os subconjuntos de um conjunto denãoelementos
48
Gerando permutações
A seguir, consideramos o problema de gerar todas as permutações de um conjunto denão
elementos. Por exemplo, as permutações de {0, 1, 2} são (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0),
(2, 0, 1) e (2, 1, 0). Novamente, há duas abordagens: podemos usar recursão ou percorrer as
permutações iterativamente.
Método 1
Assim como subconjuntos, permutações podem ser geradas usando recursão. A
seguinte funçãoprocurarpassa pelas permutações do conjunto {0, 1, . . . ,n −1}. A
função constrói um vetorpermutaçãoque contém a permutação, e a busca começa
quando a função é chamada sem parâmetros.
vazioprocurar() {
se(permutaçã[Link]() == n) {
// permutação de processo
}outro{
para(Inteiroeu = 0; eu < n; eu++) {
se(escolhido[i])continuar;
escolhido[i] =verdadeiro;
permutação.push_back(i);
pesquisa();
escolhido[i] =falso;
permutação.pop_back();
}
}
}
Método 2
Outro método para gerar permutações é começar com a permutação {0, 1, . . . ,n −
1} e repetidamente usar uma função que constrói a próxima permutação em
ordem crescente. A biblioteca padrão C++ contém a função próxima_permutação
que pode ser usado para isso:
49
Retrocedendo
UMretrocedendoo algoritmo começa com uma solução vazia e estende a solução passo a
passo. A busca recursivamente percorre todas as diferentes maneiras de como uma
solução pode ser construída.
Como exemplo, considere o problema de calcular o número de maneirasnão rainhas podem
ser colocadas em umnão×nãotabuleiro de xadrez para que nenhuma das duas rainhas se
ataquem. Por exemplo, quandon =4, existem duas soluções possíveis:
Pq Pq
Pq Pq
Pq Pq
Pq Pq
O problema pode ser resolvido usando o backtracking, colocando rainhas no tabuleiro linha
por linha. Mais precisamente, exatamente uma rainha será colocada em cada linha para que
nenhuma rainha ataque nenhuma das rainhas colocadas antes. Uma solução foi encontrada
quando todasnãorainhas foram colocadas no tabuleiro.
Por exemplo, quandon =4, algumas soluções parciais geradas pelo algoritmo de
retrocesso são as seguintes:
Pq Pq Pq Pq
Pq Pq Pq Pq
Pq Pq Pq Pq
No nível mais baixo, as três primeiras configurações são ilegais, porque as rainhas
atacam umas às outras. No entanto, a quarta configuração é válida e pode ser estendida
para uma solução completa colocando mais duas rainhas no tabuleiro. Há apenas uma
maneira de colocar as duas rainhas restantes.
O algoritmo pode ser implementado da seguinte forma:
50
vazioprocurar(Inteiroe) {
se(e == n) {
contar++;
retornar;
}
para(Inteirox = 0; x < n; x++) {
se(coluna[x] || diag1[x+y] || diag2[x-y+n-1])continuar;
coluna[x] = diag1[x+y] = diag2[x-y+n-1] = 1;
pesquisar(y+1);
coluna[x] = diag1[x+y] = diag2[x-y+n-1] = 0;
}
}
0 1 2 3 0 1 2 3 3 4 5 6
0 1 2 3 1 2 3 4 2 3 4 5
0 1 2 3 2 3 4 5 1 2 3 4
0 1 2 3 3 4 5 6 0 1 2 3
Podando a pesquisa
Muitas vezes podemos otimizar o backtracking podando a árvore de busca. A ideia é
adicionar "inteligência" ao algoritmo para que ele perceba o mais rápido possível se
uma solução parcial não puder ser estendida para uma solução completa. Essas
otimizações podem ter um efeito tremendo na eficiência da busca.
1Não há nenhuma maneira conhecida de calcular com eficiência valores maiores deq(não). O recorde
atual é q(27)=234907967154122528, calculado em 2016 [55].
51
Vamos considerar o problema de calcular o número de caminhos em umnão×não grade do
canto superior esquerdo para o canto inferior direito de modo que o caminho visite cada
quadrado exatamente uma vez. Por exemplo, em um 7×7 grade, há 111712 desses caminhos.
Um dos caminhos é o seguinte:
Nós nos concentramos nos 7×7 caso, porque seu nível de dificuldade é apropriado
para nossas necessidades. Começamos com um algoritmo de backtracking direto e,
então, o otimizamos passo a passo usando observações de como a busca pode ser
podada. Após cada otimização, medimos o tempo de execução do algoritmo e o
número de chamadas recursivas, para que possamos ver claramente o efeito de cada
otimização na eficiência da busca.
Algoritmo básico
A primeira versão do algoritmo não contém nenhuma otimização. Simplesmente usamos
backtracking para gerar todos os caminhos possíveis do canto superior esquerdo para o
canto inferior direito e contamos o número de tais caminhos.
Otimização 1
Em qualquer solução, primeiro nos movemos um passo para baixo ou para a direita. Sempre há
dois caminhos que são simétricos em relação à diagonal da grade após o primeiro passo. Por
exemplo, os seguintes caminhos são simétricos:
Portanto, podemos decidir que sempre primeiro movemos um passo para baixo (ou para a direita) e,
finalmente, multiplicamos o número de soluções por dois.
52
Otimização 2
Se o caminho atingir o quadrado inferior direito antes de ter visitado todos os outros
quadrados da grade, fica claro que não será possível completar a solução. Um exemplo
disso é o seguinte caminho:
Otimização 3
Se o caminho tocar uma parede e puder virar para a esquerda ou para a direita, a grade se divide em
duas partes que contêm quadrados não visitados. Por exemplo, na seguinte situação, o caminho pode
virar para a esquerda ou para a direita:
Neste caso, não podemos mais visitar todos os quadrados, então podemos encerrar a
busca. Esta otimização é muito útil:
Otimização 4
A ideia da Otimização 3 pode ser generalizada: se o caminho não puder continuar
para a frente, mas pode virar para a esquerda ou para a direita, a grade se divide em duas partes que
contêm quadrados não visitados. Por exemplo, considere o seguinte caminho:
53
É claro que não podemos mais visitar todos os quadrados, então podemos encerrar a
busca. Após essa otimização, a busca é muito eficiente:
Agora é um bom momento para parar de otimizar o algoritmo e ver o que alcançamos.
O tempo de execução do algoritmo original era de 483 segundos, e agora, após as
otimizações, o tempo de execução é de apenas 0,6 segundos. Assim, o algoritmo se
tornou quase 1000 vezes mais rápido após as otimizações.
Este é um fenômeno comum em backtracking, porque a árvore de busca é geralmente
grande e mesmo observações simples podem efetivamente podar a busca. Especialmente úteis
são as otimizações que ocorrem durante os primeiros passos do algoritmo, ou seja, no topo da
árvore de busca.
Encontre-se no meio
Encontre-se no meioé uma técnica onde o espaço de busca é dividido em duas partes de
tamanho aproximadamente igual. Uma busca separada é realizada para ambas as partes e,
finalmente, os resultados das buscas são combinados.
A técnica pode ser usada se houver uma maneira eficiente de combinar os resultados das
pesquisas. Em tal situação, as duas pesquisas podem exigir menos tempo do que uma pesquisa
grande. Normalmente, podemos transformar um fator de 2nãoem um fator de 2não/2usando a
técnica de encontro no meio.
Como exemplo, considere um problema em que nos é dada uma lista denão
números e um númerox, e queremos descobrir se é possível escolher alguns números
da lista para que sua soma sejax. Por exemplo, dada a lista [2, 4, 5, 9] e x =15, podemos
escolher os números [2, 4, 9] para obter 2+4+9=15. No entanto, sex =10 para a mesma
lista, não é possível formar a soma.
Um algoritmo simples para o problema é percorrer todos os subconjuntos dos
elementos e verificar se a soma de algum dos subconjuntos éx. O tempo de execução de tal
algoritmo éO(2não), porque existem 2nãosubconjuntos. No entanto, usando o meet no
técnica intermediária, podemos alcançar uma eficiência maiorO(2não/2) algoritmo de tempo2 [Link]ção
queO(2não) eO(2não/2) são complexidades diferentes porque 2não/2é igual a 2não.
54
A ideia é dividir a lista em duas listasUMeBde modo que ambas as listas contenham
cerca de metade dos números. A primeira pesquisa gera todos os subconjuntos deUMe
armazena suas somas em uma listaSUM. Correspondentemente, a segunda pesquisa cria
uma listaSBde B. Depois disso, basta verificar se é possível escolher um elemento entreSUM
e outro elemento deSBde modo que sua soma sejax. Isso é possível exatamente
quando há uma maneira de formar a somaxusando os números da lista original.
Por exemplo, suponha que a lista seja [2, 4, 5, 9] ex =15. Primeiro, dividimos a
lista emUm =[2, 4] eB =[5, 9]. Depois disso, criamos listasSUM=[0, 2, 4, 6] eSB=[0, 5,
9, 14]. Neste caso, a somax =15 é possível formar, porqueSUM
contém a soma 6,SBcontém a soma 9 e 6+9=15. Isso corresponde à solução [2, 4,
9].
Podemos implementar o algoritmo de modo que sua complexidade de tempo sejaO(2não/2).
Primeiro, geramosclassificadolistasSUMeSB, o que pode ser feito emO(2não/2) tempo usando uma
técnica de mesclagem. Depois disso, como as listas estão classificadas, podemos fazer check-inO(2não/2
) tempo se a somaxpode ser criado a partir deSUMeSB.
55
56
Capítulo 6
Algoritmos gananciosos
en =520, precisamos de pelo menos quatro moedas. A solução ótima é selecionar moedas
200+200+100+20 cuja soma é 520.
Algoritmo ganancioso
Um algoritmo ganancioso simples para o problema sempre seleciona a maior moeda possível, até que
a quantia necessária de dinheiro tenha sido construída. Este algoritmo funciona no caso de exemplo,
porque primeiro selecionamos duas moedas de 200 centavos, depois uma moeda de 100 centavos e,
finalmente, uma moeda de 20 centavos. Mas este algoritmo sempre funciona?
Acontece que se as moedas forem moedas de euro, o algoritmo gananciososempre
funciona, ou seja, sempre produz uma solução com o menor número possível de moedas. A
correção do algoritmo pode ser mostrada como segue:
Primeiro, cada moeda 1, 5, 10, 50 e 100 aparece no máximo uma vez em uma solução
ótima, porque se a solução contivesse duas dessas moedas, poderíamos substituir
57
eles por uma moeda e obter uma solução melhor. Por exemplo, se a solução contivesse
moedas 5+5, poderíamos substituí-los pela moeda 10.
Da mesma forma, as moedas 2 e 20 aparecem no máximo duas vezes em uma solução
ótima, porque poderíamos substituir as moedas 2+2+2 por moedas 5+1 e moedas 20+20+20 por
moedas 50+10. Além disso, uma solução ótima não pode conter moedas 2+2+1 ou 20+20+10,
porque poderíamos substituí-las pelas moedas 5 e 50.
Usando essas observações, podemos mostrar para cada moedaxque não é possível
construir de forma otimizada uma somaxou qualquer quantia maior usando apenas
moedas menores quex. Por exemplo, sex =100, a maior soma ótima usando as moedas
menores é 50+20+20+5+2+2=99. Assim, o algoritmo ganancioso que sempre seleciona a
maior moeda produz a solução ótima.
Este exemplo mostra que pode ser difícil argumentar que um algoritmo ganancioso
funciona, mesmo que o algoritmo em si seja simples.
Caso geral
No caso geral, o conjunto de moedas pode conter quaisquer moedas e o algoritmo ganancioso
nãonecessariamente produzem uma solução ótima.
Podemos provar que um algoritmo guloso não funciona mostrando um
contraexemplo onde o algoritmo dá uma resposta errada. Neste problema, podemos
facilmente encontrar um contraexemplo: se as moedas são {1, 3, 4} e a soma alvo é 6, o
algoritmo guloso produz a solução 4+1+1 enquanto a solução ótima é 3+3.
Não se sabe se o problema geral da moeda pode ser resolvido usando algum algoritmo
ganancioso1. No entanto, como veremos no Capítulo 7, em alguns casos, o problema geral pode
ser resolvido eficientemente usando um algoritmo de programação dinâmica que sempre
fornece a resposta correta.
Agendamento
Neste caso o número máximo de eventos é dois. Por exemplo, podemos selecionar eventos
BeEdo seguinte modo:
1No entanto, é possívelverificarem tempo polinomial se o algoritmo ganancioso apresentado neste capítulo funcionar
para um determinado conjunto de moedas [53].
58
UM
B
C
E
É possível inventar vários algoritmos gananciosos para o problema, mas qual deles
funciona em todos os casos?
Algoritmo 1
A primeira ideia é selecionar comocurtoeventos quanto possível. No caso de exemplo, este
algoritmo seleciona os seguintes eventos:
UM
B
C
E
Entretanto, selecionar eventos curtos nem sempre é uma estratégia correta. Por
exemplo, o algoritmo falha no seguinte caso:
Se selecionarmos o evento curto, podemos selecionar apenas um evento. No entanto, seria possível
selecionar ambos os eventos longos.
Algoritmo 2
Outra ideia é sempre selecionar o próximo evento possível quecomeçacomocedo
possível. Este algoritmo seleciona os seguintes eventos:
UM
B
C
E
Se selecionarmos o primeiro evento, não será possível selecionar nenhum outro evento. No
entanto, seria possível selecionar os outros dois eventos.
59
Algoritmo 3
A terceira ideia é sempre selecionar o próximo evento possível queterminacomocedo
possível. Este algoritmo seleciona os seguintes eventos:
UM
B
C
E
Acontece que esse algoritmosempreproduz uma solução ótima. A razão para isso é
que é sempre uma escolha ótima selecionar primeiro um evento que termine o mais
cedo possível. Depois disso, é uma escolha ótima selecionar o próximo evento usando
a mesma estratégia, etc., até que não possamos selecionar mais eventos.
Uma maneira de argumentar que o algoritmo funciona é considerar o que acontece se primeiro
selecionarmos um evento que termina mais tarde do que o evento que termina o mais cedo possível. Agora,
teremos no máximo um número igual de escolhas sobre como podemos selecionar o próximo evento.
Portanto, selecionar um evento que termina mais tarde nunca pode produzir uma solução melhor, e o
algoritmo ganancioso está correto.
Tarefas e prazos
Vamos agora considerar um problema em que nos é dadonãotarefas com durações e
prazos e nossa tarefa é escolher uma ordem para executar as tarefas. Para cada tarefa,
ganhamosd - xpontos ondeeé o prazo da tarefa exé o momento em que terminamos a
tarefa. Qual é a maior pontuação total possível que podemos obter?
Por exemplo, suponha que as tarefas sejam as seguintes:
0 5 10
C B UM E
60
Traduzido do Inglês para o Português - [Link]
X E
um b
E X
b um
Minimizando somas
|um1−x|c+|um2−x|c+···+|umnão− x|c.
Casoc =1
Neste caso, devemos minimizar a soma
|um1−x|+|um2−x|+···+|umnão− x|.
|1−2|+|2−2|+|9−2|+|2−2|+|6−2| =12.
No caso geral, a melhor escolha paraxé omedianados números, ou seja, o número do meio
após a classificação. Por exemplo, a lista [1, 2, 9, 2, 6] se torna [1, 2, 2, 6, 9] após a
classificação, então a mediana é 2.
A mediana é uma escolha ótima, porque sexé menor que a mediana, a soma se
torna menor ao aumentarx, e sexé maior que a mediana, a soma se torna menor
ao diminuirx. Portanto, a solução ótima é quexé a mediana. Senãoé par e há duas
medianas, ambas as medianas e todos os valores entre elas são escolhas ótimas.
Casoc =2
Neste caso, devemos minimizar a soma
(um1−x)2+(um2−x)2+···+(umnão- x)2.
61
Por exemplo, se os números forem [1, 2, 9, 2, 6], a melhor solução é selecionarx =4
que produz a soma
(1−4)2+(2−4)2+(9−4)2+(2−4)2+(6−4)2=46.
A última parte não depende dex, então podemos ignorá-lo. As partes restantes
formam uma funçãonx2−2xsondes = um1+um2+···+umnão. Esta é uma parábola com
abertura para cima e raízesx =0 ex =2e/não, e o valor mínimo é a média das raízesx = s/
não, ou seja, a média dos númerosum1,um2, . . . ,umnão.
Compressão de dados
personagem palavra-código
UM 00
B 01
C 10
E 11
Este é umcomprimento constantecódigo que significa que o comprimento de cada palavra-código é
o mesmo. Por exemplo, podemos comprimir a stringAABACDACAdo seguinte modo:
000001001011001000
personagem palavra-código
UM 0
B 110
C 10
E 111
Um código ótimo produz uma string comprimida que é tão curta quanto possível.
Neste caso, a string comprimida usando o código ótimo é
001100101110100,
62
então são necessários apenas 15 bits em vez de 18 bits. Assim, graças a um código melhor, foi
possível economizar 3 bits na string comprimida.
Exigimos que nenhuma palavra-código seja um prefixo de outra palavra-código. Por
exemplo, não é permitido que um código contenha ambas as palavras-código 10 e 1011. O
motivo para isso é que queremos ser capazes de gerar a string original a partir da string
compactada. Se uma palavra-código pudesse ser um prefixo de outra palavra-código, isso
nem sempre seria possível. Por exemplo, o código a seguir énãoválido:
personagem palavra-código
UM 10
B 11
C 1011
E 111
Usando este código, não seria possível saber se a string comprimida 1011
corresponde à stringSobreou a cordaC.
Codificação Huffman
5 1 2 1
UM B C E
2
0 1
5 2 1 1
UM C B E
2DA Huffman descobriu esse método ao resolver uma tarefa de curso universitário e publicou
o algoritmo em 1952 [40].
63
Depois disso, os nós com peso 2 são combinados:
4
0 1
2 2
0 1
C
5 1 1
UM B E
9
0 1
5 4
0 1
UM
2 2
0 1
C
1 1
B E
Agora todos os nós estão na árvore, então o código está pronto. As seguintes palavras-código
podem ser lidas da árvore:
personagem palavra-código
UM 0
B 110
C 10
E 111
64
Capítulo 7
Programação dinâmica
Primeiro, veremos como a programação dinâmica pode ser usada para encontrar uma
solução ótima e, depois, usaremos a mesma ideia para contar as soluções.
Entender a programação dinâmica é um marco na carreira de todo programador
competitivo. Embora a ideia básica seja simples, o desafio é como aplicar a programação
dinâmica a diferentes problemas. Este capítulo apresenta um conjunto de problemas
clássicos que são um bom ponto de partida.
65
Formulação recursiva
A ideia na programação dinâmica é formular o problema recursivamente para que a
solução do problema possa ser calculada a partir de soluções para subproblemas menores.
No problema da moeda, um problema recursivo natural é o seguinte: qual é o menor
número de moedas necessário para formar uma somax?
Deixarresolver(x) denotam o número mínimo de moedas necessárias para uma
somax. Os valores da função dependem dos valores das moedas. Por exemplo, se
moedas={1, 3, 4}, os primeiros valores da função são os seguintes:
resolver(0) = 0
resolver(1) = 1
resolver(2) = 2
resolver(3) = 1
resolver(4) = 1
resolver(5) = 2
resolver(6) = 2
resolver(7) = 2
resolver(8) = 2
resolver(9) = 3
resolver(10) = 3
Por exemplo,resolver(10)=3, porque são necessárias pelo menos 3 moedas para formar
a soma 10. A solução ótima é 3+3+4=10.
A propriedade essencial deresolveré que seus valores podem ser recursivamente
calculados a partir de seus valores menores. A ideia é focar nosimprimeiromoeda que
escolhemos para a soma. Por exemplo, no cenário acima, a primeira moeda pode ser 1,
3 ou 4. Se primeiro escolhermos a moeda 1, a tarefa restante é formar a soma 9 usando
o número mínimo de moedas, que é um subproblema do problema original. Claro, o
mesmo se aplica às moedas 3 e 4. Assim, podemos usar a seguinte fórmula recursiva
para calcular o número mínimo de moedas:
resolver(x)=mínimo(resolver(x−1)+1,
resolver(x−3)+1,
resolver(x−4)+1).
O caso base da recursão éresolver(0)=0, porque nenhuma moeda é necessária para formar
uma soma vazia. Por exemplo,
resolver(10)=resolver(7)+1=resolver(4)+2=resolver(0)+3=3.
Agora estamos prontos para fornecer uma função recursiva geral que calcula o
número mínimo de moedas necessárias para formar uma somax:
-
--∞ x <0
resolver(x)= 0 x =0
---
mínimoc∈moedasresolver(x−c)+1 x >0
Primeiro, sex <0, o valor é∞, porque é impossível formar uma soma negativa de
dinheiro. Então, sex =0, o valor é 0, porque nenhuma moeda é necessária para formar um
66
soma vazia. Finalmente, sex >0, a variávelcpassa por todas as possibilidades de como
escolher a primeira moeda da soma.
Uma vez encontrada uma função recursiva que resolva o problema, podemos
implementar diretamente uma solução em C++ (a constanteINFdenota infinito):
Inteiroresolver(Inteirox) {
se(x < 0)retornarINF; se
(x == 0)retornar0; Inteiro
melhor = INF;
para(autoc : moedas) {
melhor = min(melhor, resolver(xc)+1);
}
retornarmelhor;
}
Ainda assim, essa função não é eficiente, porque pode haver um número exponencial
de maneiras de construir a soma. No entanto, a seguir veremos como tornar a função
eficiente usando uma técnica chamada memoização.
Usando memorização
A ideia da programação dinâmica é usarmemorizaçãopara calcular eficientemente
valores de uma função recursiva. Isso significa que os valores da função são
armazenados em um array após calculá-los. Para cada parâmetro, o valor da função é
calculado recursivamente apenas uma vez, e depois disso, o valor pode ser recuperado
diretamente do array.
Neste problema, usamos matrizes
boolpronto[N];
Inteirovalor[N];
Inteiroresolver(Inteirox) {
se(x < 0)retornarINF; se
(x == 0)retornar0;
se(pronto[x])retornarvalor[x];
Inteiromelhor = INF;
para(autoc : moedas) {
melhor = min(melhor, resolver(xc)+1);
}
valor[x] = melhor;
pronto[x] =verdadeiro;
retornarmelhor;
}
67
A função manipula os casos basex <0 ex =0 como anteriormente. Então a
função verifica depreparar[x] seresolver(x) já foi armazenado emvalor[x], e se for,
a função o retorna diretamente. Caso contrário, a função calcula o valor de
resolver(x) recursivamente e armazena-o emvalor[x].
Esta função funciona de forma eficiente, porque a resposta para cada parâmetroxé
calculado recursivamente apenas uma vez. Após um valor deresolver(x) foi armazenado em
valor[x], ele pode ser recuperado eficientemente sempre que a função for chamada
novamente com o parâmetroxA complexidade temporal do algoritmo éO(nk), ondenãoé a
soma alvo eoé o número de moedas.
Note que também podemositerativamenteconstruir a matrizvalorusando um loop que
simplesmente calcula todos os valores deresolverpara parâmetros 0 . . .não:
valor[0] = 0;
para(Inteirox = 1; x <= n; x++) {
valor[x] = INF;
para(autoc : moedas) {
se(xc >= 0) {
valor[x] = min(valor[x], valor[xc]+1);
}
}
}
Na verdade, a maioria dos programadores competitivos prefere essa implementação, porque ela
é mais curta e tem fatores constantes mais baixos. De agora em diante, também usamos
implementações iterativas em nossos exemplos. Ainda assim, geralmente é mais fácil pensar em
soluções de programação dinâmica em termos de funções recursivas.
Inteiroprimeiro[N];
valor[0] = 0;
para(Inteirox = 1; x <= n; x++) {
valor[x] = INF;
para(autoc : moedas) {
se(xc >= 0 && valor[xc]+1 < valor[x]) {
valor[x] = valor[xc]+1;
primeiro[x] = c;
}
}
}
68
Depois disso, o código a seguir pode ser usado para imprimir as moedas que aparecem em uma
solução ótima para a somanão:
enquanto(n > 0) {
cout << primeiro[n] <<"\n"; n
-= primeiro[n];
}
• 1+1+1+1+1 • 3+1+1
• 1+1+3 • 1+4
• 1+3+1 • 4+1
resolver(x)=resolver(x−1)+
resolver(x−3)+
resolver(x−4).
Sex <0, o valor é 0, porque não há soluções. Sex =0, o valor é 1, porque só há uma
maneira de formar uma soma vazia. Caso contrário, calculamos a soma de todos os
valores da formaresolver(x−c) ondecestá emmoedas.
O código a seguir constrói uma matrizcontartal quecontar[x] é igual ao valor
deresolver(x) para 0≤x≤não:
contagem[0] = 1;
para(Inteirox = 1; x <= n; x++) {
para(autoc : moedas) {
se(xc >= 0) {
contagem[x] += contagem[xc];
}
}
}
69
Muitas vezes o número de soluções é tão grande que não é necessário calcular o
número exato, mas é suficiente para dar a resposta móduloeuonde, por exemplo, m =
109+7. Isso pode ser feito alterando o código para que todos os cálculos sejam feitos
em móduloeu. No código acima, basta adicionar a linha
contagem[x] %= m;
depois da linha
contagem[x] += contagem[xc];
0 1 2 3 4 5 6 7
6 2 5 1 7 4 8 3
comprimento(0) = 1
comprimento(1) = 1
comprimento(2) = 2
comprimento(3) = 1
comprimento(4) = 3
comprimento(5) = 2
comprimento(6) = 4
comprimento(7) = 2
Por exemplo,comprimento(6)=4, porque a maior subsequência crescente que termina
na posição 6 consiste em 4 elementos.
70
Para calcular um valor decomprimento(o), devemos encontrar uma posiçãoeu < kpara qual
variedade[eu]<variedade[o] ecomprimento(eu) é o maior possível. Então sabemos que
comprimento(o)=comprimento(eu)+1, porque esta é uma forma ótima de adicionarvariedade[o]
para uma subsequência. No entanto, se não houver tal posiçãoeu, entãocomprimento(o)=1, o que
significa que a subsequência contém apenasvariedade[o].
Como todos os valores da função podem ser calculados a partir de seus valores menores,
podemos usar programação dinâmica. No código a seguir, os valores da função serão
armazenados em um arraycomprimento.
Este código funciona emO(não2) tempo, porque consiste em dois loops aninhados. No entanto, também
é possível implementar o cálculo de programação dinâmica de forma mais eficiente emO(nãoregistronão)
tempo. Você consegue encontrar uma maneira de fazer isso?
Nosso próximo problema é encontrar um caminho do canto superior esquerdo para o canto inferior
direito de umnão×nãograde, de modo que só nos movamos para baixo e para a direita. Cada
quadrado contém um inteiro positivo, e o caminho deve ser construído de modo que a soma dos
valores ao longo do caminho seja a maior possível.
A imagem a seguir mostra um caminho ótimo em uma grade:
3 7 9 2 7
9 8 3 5 5
1 7 9 8 5
3 8 6 4 10
6 3 9 7 8
A soma dos valores no caminho é 67, e esta é a maior soma possível em um caminho
do canto superior esquerdo ao canto inferior direito.
Suponha que as linhas e colunas da grade sejam numeradas de 1 anão, e valor[e][x
] é igual ao valor do quadrado (e,x). Deixarsoma(e,x) denotam a soma máxima em um
caminho do canto superior esquerdo até o quadrado (e,x). Agorasoma(não,não) nos
diz a soma máxima do canto superior esquerdo ao canto inferior direito. Por exemplo,
na grade acima,soma(5, 5)=67.
Podemos calcular recursivamente as somas da seguinte forma:
soma(e,x)=máx(soma(e,x−1),soma(e−1,x))+valor[e][x]
71
A fórmula recursiva é baseada na observação de que um caminho que termina no
quadrado (e,x) pode vir do quadrado (e,x−1) ou quadrado (e−1,x):
↓
→
Inteirosoma[N][N];
0 1 2 3 4 5 6 7 8 9 10 11 12
XX XXXXXXXXX XX
Neste caso, todas as somas entre 0. . . 12 são possíveis, exceto 2 e 10. Por
exemplo, a soma 7 é possível porque podemos selecionar os pesos [1, 3, 3].
Para resolver o problema, focamos em subproblemas onde usamos apenas o primeiroo
pesos para construir somas. Deixepossível(x,o)=verdadeiro se pudermos construir uma
somax usando o primeiroopesos e outrospossível(x,o)=falso. Os valores da função podem
ser recursivamente calculados como segue:
possível(x,o)=possível(x-wo,k−1)∨possível(x,k−1)
72
A fórmula é baseada no fato de que podemos usar ou não o pesoco
na soma. Se usarmosco, a tarefa restante é formar a somax-wousando o primeirok
−1 pesos, e se não usarmosco, a tarefa restante é formar a soma xusando o
primeirok−1 pesos. Como casos base,
{
verdadeiro x =0
possível(x, 0)=
falso x6=0
o\x0 1 2 3 4 5 6 7 8 9 10 11 12
0 X
1 X X
2 X X X X
3 X X X X XX
4 XX XXXXXXXXX X X
No entanto, aqui está uma implementação melhor que usa apenas uma matriz
unidimensionalpossível[x] que indica se podemos construir um subconjunto com somax. O
truque é atualizar a matriz da direita para a esquerda para cada novo peso:
possível[0] =verdadeiro;
para(Inteirok = 1; k <= n; k++) {
para(Inteirox = W; x >= 0; x--) {
se(possível[x]) possível[x+w[k]] =verdadeiro;
}
}
Note que a ideia geral apresentada aqui pode ser usada em muitos problemas de
mochila. Por exemplo, se nos são dados objetos com pesos e valores, podemos determinar
para cada soma de pesos a soma máxima de valores de um subconjunto.
73
Editar distância
distância(um,b)=mínimo(distância(um,b-1)+1,
distância(uma−1,b)+1, distância(uma−1,
b-1)+custo(um,b)).
FILME
0 1 2 3 4 5
eu 1 1 2 3 4 5
O 2 2 1 2 3 4
V 3 3 2 1 2 3
E 4 4 3 2 2 2
1A distância recebeu o nome de VI Levenshtein, que a estudou em conexão com códigos binários.
[49].
74
O canto inferior direito da tabela nos diz que a distância de edição entre AMORe
FILMEé 2. A tabela também mostra como construir a sequência mais curta de
operações de edição. Neste caso, o caminho é o seguinte:
FILME
0 1 2 3 4 5
eu 1 1 2 3 4 5
O 2 2 1 2 3 4
V 3 3 2 1 2 3
E 4 4 3 2 2 2
Contando ladrilhos
Às vezes, os estados de uma solução de programação dinâmica são mais complexos do que
combinações fixas de números. Como exemplo, considere o problema de calcular o número
de maneiras distintas de preencher umnão×eugrade usando 1×2 e 2×1 tamanho de
ladrilhos. Por exemplo, uma solução válida para o 4×7 grade é
• você@UMvocê@UMvocê
• para@UMtuut
• @Um@Umttu
• @Um@Um@Umpara
75
Uma solução é válida se a linha 1 não contiver o caracterepara, linhanãonão contém o
caracterevocê, e todas as linhas consecutivas sãocompatível. Por exemplo, as linhaspara@UM
tuute @Um@Umttusão compatíveis, enquanto as linhasvocê@UMvocê@UMvocê e @
Um@Um@Umparanão são compatíveis.
Como uma linha consiste emeucaracteres e há quatro opções para cada caractere,
o número de linhas distintas é no máximo 4eu. Assim, a complexidade temporal da
solução éO(não42eu) porque podemos passar peloO(4eu) estados possíveis para cada
linha e, para cada estado, existemO(4eu) estados possíveis para a linha anterior. Na
prática, é uma boa ideia girar a grade para que o lado mais curto tenha comprimento
eu, porque o fator 42eudomina a complexidade do tempo.
É possível tornar a solução mais eficiente usando uma representação mais
compacta para as linhas. Acontece que é suficiente saber quais colunas da linha
anterior contêm o quadrado superior de um ladrilho vertical. Assim, podemos
representar uma linha usando apenas caracteresvocêe -, onde - é uma combinação de
caracterespara, @ [Link] esta representação, existem apenas 2eulinhas distintas
e a complexidade do tempo éO(não22eu).
Como nota final, há também uma fórmula direta surpreendente para calcular o número
de ladrilhos2:
∏ /2∏eeu/2e
enão πa πb
4·(porque2 + porque 2 )
um=1b=1 n+1 mais1
Esta fórmula é muito eficiente, pois calcula o número de ladrilhos emO(nm) tempo,
mas como a resposta é um produto de números reais, um problema ao usar a fórmula
é como armazenar os resultados intermediários com precisão.
2Surpreendentemente, esta fórmula foi descoberta em 1961 por duas equipes de pesquisa [43, 67] que trabalharam de forma
independente.
76
Capítulo 8
Análise amortizada
Nométodo dos dois ponteiros, dois ponteiros são usados para iterar pelos valores do array.
Ambos os ponteiros podem se mover para uma direção apenas, o que garante que o algoritmo
funcione eficientemente. Em seguida, discutimos dois problemas que podem ser resolvidos
usando o método dos dois ponteiros.
Soma de submatriz
Como primeiro exemplo, considere um problema em que nos é dado um conjunto denão
inteiros positivos e uma soma alvox, e queremos encontrar uma submatriz cuja soma sejax
ou relatar que não existe tal submatriz.
Por exemplo, a matriz
1 3 2 5 1 1 2 3
1 3 2 5 1 1 2 3
Este problema pode ser resolvido emO(não) tempo usando o método dos dois ponteiros. A
ideia é manter ponteiros que apontam para o primeiro e o último valor de um subarray. Em cada
turno, o ponteiro esquerdo move-se um passo para a direita, e o ponteiro direito move-se para a
direita enquanto a soma do subarray resultante for no máximox. Se a soma se tornar
exatamentex, uma solução foi encontrada.
77
Como exemplo, considere a seguinte matriz e uma soma de destinox =8:
1 3 2 5 1 1 2 3
1 3 2 5 1 1 2 3
1 3 2 5 1 1 2 3
1 3 2 5 1 1 2 3
Problema 2SUM
Outro problema que pode ser resolvido usando o método dos dois ponteiros é o seguinte
problema, também conhecido comoProblema 2SUM:dado um conjunto denãonúmeros e uma
soma alvox, encontre dois valores de matriz tais que sua soma sejax, ou relatar que tais valores
não existem.
Para resolver o problema, primeiro classificamos os valores do array em ordem crescente.
Depois disso, iteramos pelo array usando dois ponteiros. O ponteiro esquerdo começa no
primeiro valor e se move um passo para a direita em cada volta. O ponteiro direito começa no
último valor e sempre se move para a esquerda até que a soma dos valores esquerdo e direito
seja no máximox. Se a soma for exatamentex, uma solução foi encontrada.
Por exemplo, considere a seguinte matriz e uma soma de destinox =12:
1 4 5 6 7 9 9 10
As posições iniciais dos ponteiros são as seguintes. A soma dos valores é 1+10=
11 que é menor quex.
78
1 4 5 6 7 9 9 10
Então o ponteiro esquerdo move um passo para a direita. O ponteiro direito move
três passos para a esquerda, e a soma se torna 4+7=11.
1 4 5 6 7 9 9 10
Depois disso, o ponteiro esquerdo move-se um passo para a direita novamente. O ponteiro
direito não se move, e uma solução 5+7=12 foi encontrado.
1 4 5 6 7 9 9 10
1Durante muito tempo, pensou-se que resolver o problema 3SUM seria mais eficiente do que emO(não2)
o tempo não seria possível. No entanto, em 2014, descobriu-se [30] que não é esse o caso.
79
1 3 4 2 5 3 4 2
1 3 4 2 5 3 4 2
1 3 4
1 3 4 2 5 3 4 2
1 2
Então, o elemento 5 é maior que o elemento 2, então ele será adicionado à pilha, e
seu elemento menor mais próximo é 2:
1 3 4 2 5 3 4 2
1 2 5
1 3 4 2 5 3 4 2
1 2 3 4
Por fim, todos os elementos, exceto 1, são removidos da pilha e o último elemento
2 é adicionado à pilha:
1 3 4 2 5 3 4 2
1 2
80
Janela de correr mínima
UMjanela deslizanteé um subarray de tamanho constante que se move da
esquerda para a direita através do array. Em cada posição da janela, queremos
calcular algumas informações sobre os elementos dentro da janela. Nesta seção,
focamos no problema de manter ojanela deslizante mínima, o que significa que
devemos relatar o menor valor dentro de cada janela.
O mínimo da janela deslizante pode ser calculado usando uma ideia semelhante à
que usamos para calcular os elementos menores mais próximos. Mantemos uma fila
onde cada elemento é maior que o elemento anterior, e o primeiro elemento sempre
corresponde ao elemento mínimo dentro da janela. Após cada movimentação da
janela, removemos elementos do final da fila até que o último elemento da fila seja
menor que o novo elemento da janela, ou a fila fique vazia. Também removemos o
primeiro elemento da fila se ele não estiver mais dentro da janela. Finalmente,
adicionamos o novo elemento da janela ao final da fila.
Como exemplo, considere a seguinte matriz:
2 1 4 5 3 4 1 2
2 1 4 5 3 4 1 2
1 4 5
2 1 4 5 3 4 1 2
1 3
2 1 4 5 3 4 1 2
3 4
2 1 4 5 3 4 1 2
81
Finalmente a janela alcança sua última posição. O elemento 2 é adicionado à
fila, mas o menor valor dentro da janela ainda é 1.
2 1 4 5 3 4 1 2
1 2
Como cada elemento da matriz é adicionado à fila exatamente uma vez e removido da
fila no máximo uma vez, o algoritmo funciona emO(não) tempo.
82
Capítulo 9
Consultas de intervalo
Neste capítulo, discutimos estruturas de dados que nos permitem processar consultas de intervalo de
forma eficiente. Em umconsulta de intervalo, nossa tarefa é calcular um valor com base em um
subarray de um array. Consultas de intervalo típicas são:
0 1 2 3 4 5 6 7
1 3 8 4 6 1 3 4
Inteirosoma(Inteiroum,Inteirob) {
Inteiros = 0;
para(Inteiroeu = a; eu <= b; i++) {
s += matriz[i];
}
retornare;
}
Esta função funciona emO(não) tempo, ondenãoé o tamanho do array. Assim, podemos
processarqconsultas emO(não) tempo usando a função. No entanto, se ambosnãoeq são
grandes, essa abordagem é lenta. Felizmente, descobriu-se que há maneiras de processar
consultas de intervalo de forma muito mais eficiente.
83
Consultas de matriz estática
Primeiro, focamos em uma situação em que a matriz éestático, ou seja, os valores do array
nunca são atualizados entre as consultas. Neste caso, basta construir uma estrutura de dados
estática que nos diga a resposta para qualquer consulta possível.
Consultas de soma
0 1 2 3 4 5 6 7
1 3 4 8 6 1 4 2
0 1 2 3 4 5 6 7
1 4 8 16 22 23 27 29
Como a matriz de soma de prefixo contém todos os valores desomaq(0,o), podemos calcular qualquer valor
desomaq(um,b) emO(1) tempo da seguinte forma:
somaq(um,b)=somaq(0,b)−somaq(0,uma−1)
0 1 2 3 4 5 6 7
1 3 4 8 6 1 4 2
Nesse casosomaq(3, 6)=8+6+1+4=19. Esta soma pode ser calculada a partir de dois valores da
matriz de soma de prefixos:
0 1 2 3 4 5 6 7
1 4 8 16 22 23 27 29
84
A imagem a seguir ilustra a ideia:
E C
B UM
S(UM)-S(B)-S(C)+S(E),
ondeS(X) denota a soma dos valores em uma submatriz retangular do canto superior
esquerdo até a posição deX.
Consultas mínimas
Consultas mínimas são mais difíceis de processar do que consultas de soma. Ainda assim, há uma maneira
bastante simplesO(nãoregistronão) método de pré-processamento de tempo após o qual podemos
responder a qualquer consulta mínima emO(1) tempo1. Observe que, como as consultas mínimas e máximas
podem ser processadas de forma semelhante, podemos nos concentrar nas consultas mínimas.
A ideia é pré-calcular todos os valores de minq(um,b) ondeb −a+1 (o comprimento do
intervalo) é uma potência de dois. Por exemplo, para a matriz
0 1 2 3 4 5 6 7
1 3 4 8 6 1 4 2
0 0 1 0 1 1 0 3 1
1 1 3 1 2 3 1 4 3
2 2 4 2 3 4 2 5 1
3 3 8 3 4 6 3 6 1
4 4 6 4 5 1 4 7 1
5 5 1 5 6 1 0 7 1
6 6 4 6 7 2
7 7 2
mínimoq(um,b)=mínimo(mínimoq(um,a+w−1),mínimoq(a+w,b)),
1Esta técnica foi introduzida em [7] e às vezes chamada demesa esparsamétodo. Existem também
técnicas mais sofisticadas [22] onde o tempo de pré-processamento é apenasO(não), mas tais
algoritmos não são necessários na programação competitiva.
85
ondeb-a+1 é uma potência de dois eem =(b-a+1)/2. O cálculo de todos esses valores levaO(não
registronão) tempo.
Depois disso, qualquer valor demínimoq(um,b) pode ser calculado emO(1) tempo como um
mínimo de dois valores pré-calculados. Sejaoseja a maior potência de dois que não exceda b-a+1.
Podemos calcular o valor demínimoq(um,b) usando a fórmula
Na fórmula acima, o intervalo [um,b] é representado como a união dos intervalos [um,
uma+ k−1] e [b− k+1,b], ambos de comprimentoo.
Como exemplo, considere o intervalo [1, 6]:
0 1 2 3 4 5 6 7
1 3 4 8 6 1 4 2
0 1 2 3 4 5 6 7
1 3 4 8 6 1 4 2
0 1 2 3 4 5 6 7
1 3 4 8 6 1 4 2
UMárvore indexada bináriaou umÁrvore Fenwick2pode ser visto como uma variante dinâmica de uma
matriz de soma de prefixo. Ele suporta doisO(registronão) operações de tempo em uma matriz:
processamento de uma consulta de soma de intervalo e atualização de um valor.
A vantagem de uma árvore indexada binária é que ela nos permite atualizar eficientemente
valores de array entre consultas de soma. Isso não seria possível usando um array de soma de prefixo,
porque após cada atualização, seria necessário construir todo o array de soma de prefixo novamente
emO(não) tempo.
Estrutura
Mesmo que o nome da estrutura seja um índice binárioárvore, é geralmente representado como
um array. Nesta seção, assumimos que todos os arrays são one-indexed, porque isso torna a
implementação mais fácil.
Deixarp(o) denotam a maior potência de dois que divideo. Armazenamos uma árvore
indexada binária como uma matrizárvoretal que
árvore[o]=somaq(k−p(o)+1,o),
2A estrutura de árvore indexada binária foi apresentada por PM Fenwick em 1994 [21].
86
ou seja, cada posiçãoocontém a soma dos valores em um intervalo da matriz original
cujo comprimento ép(o) e que termina na posiçãoo. Por exemplo, desdep(6)=2, árvore[
6] contém o valor desomaq(5, 6).
Por exemplo, considere a seguinte matriz:
1 2 3 4 5 6 7 8
1 3 4 8 6 1 4 2
1 2 3 4 5 6 7 8
1 4 4 16 6 7 4 29
A imagem a seguir mostra mais claramente como cada valor na árvore indexada binária
corresponde a um intervalo na matriz original:
1 2 3 4 5 6 7 8
1 4 4 16 6 7 4 29
Usando uma árvore indexada binária, qualquer valor desomaq(1,o) pode ser calculado em O
(registronão) tempo, porque um intervalo [1,o] pode sempre ser dividido emO(registronão) intervalos
cujas somas são armazenadas na árvore.
Por exemplo, o intervalo [1, 7] consiste nos seguintes intervalos:
1 2 3 4 5 6 7 8
1 4 4 16 6 7 4 29
Para calcular o valor desomaq(um,b) ondeum >1, podemos usar o mesmo truque que
usamos com matrizes de soma de prefixos:
somaq(um,b)=somaq(1,b)−somaq(1,uma−1).
87
Como podemos calcular ambossomaq(1,b) esomaq(1,uma−1) emO(registronão) tempo, a complexidade total
do tempo éO(registronão).
Então, após atualizar um valor no array original, vários valores na árvore indexada
binária devem ser atualizados. Por exemplo, se o valor na posição 3 mudar, as somas
dos seguintes intervalos mudam:
1 2 3 4 5 6 7 8
1 4 4 16 6 7 4 29
Implementação
As operações de uma árvore indexada binária podem ser implementadas eficientemente usando
operações de bits. O fato essencial necessário é que podemos calcular qualquer valor dep(o) usando a
fórmula
p(o)=o&−o.
A função a seguir calcula o valor desomaq(1,o):
Inteirosoma(Inteirok) {
Inteiros = 0;
enquanto(k >= 1) {
s += árvore[k];
k -= k&-k;
}
retornare;
}
vazioadicionar(Inteirook,Inteirox) {
enquanto(k <= n) {
árvore[k] += x;
k += k&-k;
}
}
88
Árvore de segmentos
UMárvore de segmento3é uma estrutura de dados que suporta duas operações: processar uma
consulta de intervalo e atualizar um valor de matriz. As árvores de segmento podem suportar
consultas de soma, consultas de mínimo e máximo e muitas outras consultas para que ambas as
operações funcionem emO(registronão) tempo.
Comparado a uma árvore indexada binária, a vantagem de uma árvore de segmento é que ela é
uma estrutura de dados mais geral. Enquanto árvores indexadas binárias suportam apenas consultas
de soma4, árvores de segmento também suportam outras consultas. Por outro lado, uma árvore de
segmento requer mais memória e é um pouco mais difícil de implementar.
Estrutura
Uma árvore de segmentos é uma árvore binária tal que os nós no nível inferior da árvore
correspondem aos elementos da matriz, e os outros nós contêm informações necessárias
para processar consultas de intervalo.
Nesta seção, assumimos que o tamanho do array é uma potência de dois e a indexação
baseada em zero é usada, porque é conveniente construir uma árvore de segmento para tal
array. Se o tamanho do array não for uma potência de dois, podemos sempre acrescentar
elementos extras a ele.
Primeiro, discutiremos árvores de segmento que suportam consultas de soma. Como
exemplo, considere o seguinte array:
0 1 2 3 4 5 6 7
5 8 6 3 2 7 2 6
39
22 17
13 9 9 8
5 8 6 3 2 7 2 6
3A implementação bottom-up neste capítulo corresponde à de [62]. Estruturas semelhantes foram usadas no
final da década de 1970 para resolver problemas geométricos [9].
4Na verdade, usandodoisárvores indexadas binárias é possível suportar consultas mínimas [16], mas isso é mais
complicado do que usar uma árvore de segmentos.
89
Acontece que qualquer intervalo [um,b] pode ser dividido emO(registronão) intervalos cujos
valores são armazenados em nós de árvore. Por exemplo, considere o intervalo [2,7]:
0 1 2 3 4 5 6 7
5 8 6 3 2 7 2 6
39
22 17
13 9 9 8
5 8 6 3 2 7 2 6
39
22 17
13 9 9 8
5 8 6 3 2 7 2 6
O caminho de baixo para cima sempre consiste emO(registronão) nós, então cada
atualização mudaO(registronão) nós na árvore.
Implementação
Armazenamos uma árvore de segmentos como uma matriz de 2nãoelementos ondenãoé o tamanho
do array original e uma potência de dois. Os nós da árvore são armazenados de cima para baixo:
90
árvore[1] é o nó superior,árvore[2] eárvore[3] são seus filhos, e assim por diante.
Finalmente, os valores deárvore[não] paraárvore[2n−1] correspondem aos valores da
matriz original no nível inferior da árvore.
Por exemplo, a árvore de segmentos
39
22 17
13 9 9 8
5 8 6 3 2 7 2 6
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
39 22 17 13 9 9 8 5 8 6 3 2 7 2 6
Inteirosoma(Inteiroum,Inteirob) {
um += n; b += n;
Inteiros = 0;
enquanto(a <= b) {
se(a%2 == 1) s += árvore[a++]; se
(b%2 == 0) s += árvore[b--]; a /=
2; b /= 2;
}
retornare;
}
A função mantém um intervalo que é inicialmente [um+ n,b+n]. Então, a cada passo, o
intervalo é movido um nível mais alto na árvore e, antes disso, os valores dos nós que
não pertencem ao intervalo mais alto são adicionados à soma.
A função a seguir aumenta o valor da matriz na posiçãooporx:
vazioadicionar(Inteirook,Inteirox) {
k += n;
árvore[k] += x;
para(k /= 2; k >= 1; k /= 2) {
árvore[k] = árvore[2*k]+árvore[2*k+1];
}
}
91
Primeiro, a função atualiza o valor no nível inferior da árvore. Depois disso, a
função atualiza os valores de todos os nós internos da árvore, até atingir o nó
superior da árvore.
Ambas as funções acima funcionam emO(registronão) tempo, porque uma árvore de
segmento denão elementos consistem emO(registronão) níveis, e as funções sobem um nível na
árvore a cada passo.
Outras consultas
Árvores de segmento podem suportar todas as consultas de intervalo onde é possível dividir um
intervalo em duas partes, calcular a resposta separadamente para ambas as partes e então
combinar as respostas de forma eficiente. Exemplos dessas consultas são mínimo e máximo,
máximo divisor comum e operações de bit and, or e xor.
Por exemplo, a seguinte árvore de segmentos suporta consultas mínimas:
3 1
5 3 1 2
5 8 6 3 1 7 2 6
3 1
5 3 1 2
5 8 6 3 1 7 2 6
92
Técnicas adicionais
Compressão de índice
Uma limitação em estruturas de dados que são construídas sobre um array é que os
elementos são indexados usando inteiros consecutivos. Dificuldades surgem quando
índices grandes são necessários. Por exemplo, se desejarmos usar o índice 109, a matriz
deve conter 109elementos que exigiriam muita memória.
No entanto, muitas vezes podemos contornar essa limitação usandocompressão de índice,
onde os índices originais são substituídos pelos índices 1, 2, 3, etc. Isso pode ser feito se
soubermos todos os índices necessários durante o algoritmo de antemão.
A ideia é substituir cada índice originalxcomc(x) ondecé uma função que comprime
os índices. Exigimos que a ordem dos índices não mude, então seum < b, entãoc(um)<c(
b). Isso nos permite realizar consultas convenientemente, mesmo que os índices
estejam compactados.
Por exemplo, se os índices originais forem 555, 109e 8, os novos índices são:
c(8) = 1
c(555) = 2
c(109) = 3
Atualizações de alcance
0 1 2 3 4 5 6 7
3 3 1 1 1 5 2 2
93
0 1 2 3 4 5 6 7
3 5 −2 0 0 −1 −3 0
De forma mais geral, para aumentar os valores no intervalo [um,b] porx, aumentamos o
valor na posiçãoumporxe diminuir o valor na posiçãob+1 porx. Assim, é necessário apenas
atualizar valores únicos e processar consultas de soma, para que possamos usar uma árvore
indexada binária ou uma árvore de segmentos.
Um problema mais difícil é suportar consultas de intervalo e atualizações de
intervalo. No Capítulo 28, veremos que até isso é possível.
94
Capítulo 10
Manipulação de bits
Representação de bits
000000000000000000000000101011
Os bits na representação são indexados da direita para a esquerda. Para converter uma
representação de bitsbo···b2b1b0em um número, podemos usar a fórmula
bo2o+. . .+b222+b121+b020.
Por exemplo,
1·25+1·23+1·21+1·20=43.
A representação de bits de um número éassinadoounão assinado. Normalmente, uma
representação assinada é usada, o que significa que números negativos e positivos podem
ser representados. Uma variável assinada denãobits podem conter qualquer número inteiro
entre−2n−1e 2n−1−1. Por exemplo, oInteirotipo em C++ é um tipo assinado, então umInteiro
variável pode conter qualquer inteiro entre−231e 231−1.
O primeiro bit em uma representação assinada é o sinal do número (0 para
números não negativos e 1 para números negativos), e o restanten−1 bit contém a
magnitude do nú[Link] de doisé usado, o que significa que o
número oposto de um número é calculado primeiro invertendo todos os bits do
número e depois aumentando o número em um.
Por exemplo, a representação de bits doInteironúmero−43 é
1111111111111111111111111010101.
95
Em uma representação sem sinal, apenas números não negativos podem ser usados,
mas o limite superior para os valores é maior. Uma variável sem sinal denãobits podem
conter qualquer número inteiro entre 0 e 2não−1. Por exemplo, em C++, umint sem sinal
variável pode conter qualquer número inteiro entre 0 e 232−1.
Há uma conexão entre as representações: um número assinado−x é igual a um
número sem sinal 2não- x. Por exemplo, o código a seguir mostra que o número
assinadox = −43 é igual ao número sem sinale =232−43:
Inteirox = -43;
int sem sinaly = x; corte << x <<"\n";
// -43 cout << e <<"\n";//
4294967253
Inteirox = 2147483647
corte << x <<"\n";// 2147483647 x+
+;
corte << x <<"\n";// -2147483648
Inicialmente, o valor dexé 231−1. Este é o maior valor que pode ser armazenado em um
Inteirovariável, então o próximo número depois de 231−1 é−231.
Operações de bits
E operação
Oeoperaçãox&eproduz um número que tem um bit em posições onde ambosxee
tem um bit. Por exemplo, 22 e 26 = 18, porque
10110 (22)
& 11010 (26)
= 10010 (18)
Usando a operação and, podemos verificar se um númeroxé mesmo porquex&1 = 0 sex
é par, ex&1 = 1 sexé estranho. De forma mais geral,xé divisível por 2oexatamente quandox
& (2o−1) = 0.
Ou operação
Oouoperaçãox|eproduz um número que tem um bit em posições onde pelo
menos um dexeetem um bit. Por exemplo, 22 | 26 = 30, porque
10110 (22)
| 11010 (26)
= 11110 (30)
96
Operação Xor
Oxoroperaçãox^eproduz um número que tem um bit em posições onde
exatamente um dexeetem um bit. Por exemplo, 22 ^ 26 = 12, porque
10110 (22)
^ 11010 (26)
= 01100 (12)
Não operação
Onãooperação ~xproduz um número onde todos os bits dexforam invertidas. A
fórmula ~x = −x−1 contém, por exemplo, ~29= −30.
O resultado da operação not no nível de bit depende do comprimento da
representação de bit, porque a operação inverte todos os bits. Por exemplo, se os
números forem de 32 bitsInteironúmeros, o resultado é o seguinte:
x= 29 00000000000000000000000011101
~x=−30 1111111111111111111111111100010
Mudanças de bits
Aplicações
Um número da forma 1<<otem um bit em posiçãooe todos os outros bits são zero, então
podemos usar esses números para acessar bits únicos de números. Em particular, o oo bit
de um número é exatamente um quandox& (1<<o) não é zero. O código a seguir imprime a
representação de bits de umInteironúmerox:
97
Funções adicionais
O compilador g++ fornece as seguintes funções para contagem de bits:
Inteirox = 5328;//000000000000000001010011010000
cout << __builtin_clz(x) <<"\n";// 19 cout <<
__builtin_ctz(x) <<"\n";// 4 cout <<
__builtin_popcount(x) <<"\n";// 5 cout <<
__paridade_construída(x) <<"\n";// 1
Representando conjuntos
Cada subconjunto de um conjunto {0, 1, 2, . . . ,n−1} pode ser representado como umnãobit inteiro
cujos bits indicam quais elementos pertencem ao subconjunto. Esta é uma maneira eficiente de
representar conjuntos, porque cada elemento requer apenas um bit de memória, e as operações de
conjunto podem ser implementadas como operações de bit.
Por exemplo, uma vez queInteiroé um tipo de 32 bits, umInteironúmero pode representar qualquer
subconjunto do conjunto {0, 1, 2, . . . , 31}. A representação de bits do conjunto {1, 3, 4, 8} é
000000000000000000000100011010,
Definir implementação
O código a seguir declara umInteirovariávelxque pode conter um subconjunto de {0, 1,
2, . . . ,31}. Depois disso, o código adiciona os elementos 1, 3, 4 e 8 ao conjunto e imprime o
tamanho do conjunto.
Inteirox = 0;
x |= (1<<1);
x |= (1<<3);
x |= (1<<4);
x |= (1<<8);
cout << __builtin_popcount(x) <<"\n";// 4
98
Então, o código a seguir imprime todos os elementos que pertencem ao conjunto:
Operações de conjunto
Inteirox = (1<<1)|(1<<3)|(1<<4)|(1<<8);
Inteiroy = (1<<3)|(1<<6)|(1<<8)|(1<<9);
Inteiroz = x|y;
cout << __builtin_popcount(z) <<"\n";// 6
Inteirob = 0;
fazer{
// subconjunto do processo
b }enquanto(b=(bx)&x);
99
Otimizações de bits
Muitos algoritmos podem ser otimizados usando operações de bits. Tais otimizações
não alteram a complexidade de tempo do algoritmo, mas podem ter um grande
impacto no tempo de execução real do código. Nesta seção, discutimos exemplos de
tais situações.
Distâncias de Hamming
ODistância de Hammingpresunto(um,b) entre duas cordasumebde comprimento
igual é o número de posições onde as strings diferem. Por exemplo,
presunto(01101, 11001)=2.
Considere o seguinte problema: Dada uma lista denãosequências de bits, cada uma
com comprimentoo, calcule a distância mínima de Hamming entre duas strings na lista. Por
exemplo, a resposta para [00111, 01101, 11110] é 2, porque
• presunto(00111, 01101)=2,
• presunto(00111, 11110)=3, e
• presunto(01101, 11110)=3.
Uma maneira simples de resolver o problema é percorrer todos os pares de strings e
calcular suas distâncias de Hamming, o que produz umO(não2o) algoritmo de tempo. A
seguinte função pode ser usada para calcular distâncias:
Inteirohamming(sequência a, sequência b) {
Inteirod = 0;
para(Inteiroeu = 0; eu < k; eu++) {
se(a[i] != b[i]) d++;
}
retornare;
}
Inteiropresunto(Inteiroum,Inteirob) {
retornar__contagem_populacional_construída(a^b);
Na função acima, a operação xor constrói uma sequência de bits que possui um bit em
posições ondeumebdiferem. Então, o número de bits é calculado usando o __
contagem_pop_incorporadafunção.
Para comparar as implementações, geramos uma lista de 10000 sequências de bits
aleatórias de comprimento 30. Usando a primeira abordagem, a busca levou 13,5 segundos e,
após a otimização de bits, levou apenas 0,5 segundos. Assim, o código otimizado de bits foi
quase 30 vezes mais rápido do que o código original.
100
Contagem de sub-redes
Inteirocontagem = 0;
para(Inteiroeu = 0; eu < n; eu++) {
se(cor[a][i] == 1 && cor[b][i] == 1) contagem++;
}
Inteirocontagem = 0;
para(Inteiroeu = 0; eu <= n/N; eu++) {
contagem += __builtin_popcount(cor[a][i]&cor[b][i]);
}
101
Programação dinâmica
Operações de bit fornecem uma maneira eficiente e conveniente de implementar algoritmos de
programação dinâmica cujos estados contêm subconjuntos de elementos, porque tais estados
podem ser armazenados como inteiros. Em seguida, discutimos exemplos de combinação de
operações de bit e programação dinâmica.
Seleção ótima
Como primeiro exemplo, considere o seguinte problema: São-nos dados os preços deo
produtos acimanãodias, e queremos comprar cada produto exatamente uma vez. No
entanto, podemos comprar no máximo um produto por dia. Qual é o preço total
mínimo? Por exemplo, considere o seguinte cenário (k =3 en =8):
01234567
produto 0 6 9 5 2 8 9 1 6
produto 1 8 2 6 2 7 5 7 2
produto 2 5 3 9 7 3 5 1 4
01234567
produto 0 6 9 5 2 8 9 1 6
produto 1 8 2 6 2 7 5 7 2
produto 2 5 3 9 7 3 5 1 4
total(S,e)=mínimo(total(S,e −1),
mínimo(total(S\x,e −1)+preço[x][e]))
x∈S
Isso significa que não compramos nenhum produto no diaeou compre um produto
x que pertence aS. No último caso, removemosxdeSe adicione o preço dex ao
preço total.
O próximo passo é calcular os valores da função usando programação dinâmica.
Para armazenar os valores da função, declaramos um array
Inteirototal[1<<K][N];
102
ondeEeNãosão constantes adequadamente grandes. A primeira dimensão do array corresponde
a uma representação de bits de um subconjunto.
Primeiro, os casos em qued =0 pode ser processado da seguinte forma:
De permutações a subconjuntos
Usando programação dinâmica, muitas vezes é possível mudar uma iteração sobre
permutações em uma iteração sobre subconjuntos1. O benefício disso é quenão!, o
número de permutações é muito maior que 2não, o número de subconjuntos. Por
exemplo, sen =20, entãonão!≈2.4·1018e 2não≈106. Assim, para certos valores denão,
podemos percorrer eficientemente os subconjuntos, mas não as permutações.
Como exemplo, considere o seguinte problema: Existe um elevador com peso
máximox, enãopessoas com pesos conhecidos que querem ir do térreo ao último
andar. Qual é o número mínimo de viagens necessárias se as pessoas entrarem no
elevador em uma ordem ótima?
Por exemplo, suponha quex =10,n =5 e os pesos são os seguintes:
pessoa peso
0 2
1 3
2 3
3 5
4 6
Nesse caso, o número mínimo de viagens é 2. Uma ordem ótima é {0, 2, 3, 1, 4},
que divide as pessoas em duas viagens: primeiro {0, 2, 3} (peso total 10) e depois
{1, 4} (peso total 9).
103
O problema pode ser facilmente resolvido emO(não!não) tempo testando todas as
permutações possíveis denãopessoas. No entanto, podemos usar programação dinâmica para
obter uma maneira mais eficienteO(2nãonão) algoritmo de tempo. A ideia é calcular para cada
subconjunto de pessoas dois valores: o número mínimo de viagens necessárias e o peso mínimo
das pessoas que viajam no último grupo.
Deixarpeso[p] denota o peso da pessoap. Definimos duas funções:passeios(S)
é o número mínimo de viagens para um subconjuntoS, edurar(S) é o peso mínimo
da última viagem. Por exemplo, no cenário acima
porque os passeios ótimos são {1, 4} e {3}, e o segundo passeio tem peso 5. Claro,
nosso objetivo final é calcular o valor depasseios({0 . . .n−1}).
Podemos calcular os valores das funções recursivamente e então aplicar programação
dinâmica. A ideia é passar por todas as pessoas que pertencem aSe escolher de forma otimizada
a última pessoapque entra no elevador. Cada uma dessas escolhas produz um subproblema para
um subconjunto menor de pessoas. Sedurar(S\p)+peso[p]≤x, podemos adicionarppara o último
passeio. Caso contrário, temos que reservar um novo passeio que inicialmente contém apenasp.
par<Inteiro,Inteiro> melhor[1<<N];
que contém para cada subconjuntoSum par (passeios(S),durar(S)). Definimos o valor para um grupo
vazio da seguinte forma:
melhor[0] = {1,0};
104
Observe que o loop acima garante que para quaisquer dois subconjuntosS1eS2tal queS
1⊂S2, nós processamosS1antesS2. Assim, os valores de programação dinâmica são
calculados na ordem correta.
Contando subconjuntos
Nosso último problema neste capítulo é o seguinte: SejaX ={0 . . .n−1}, e cada
subconjunto S⊂Xé atribuído um inteirovalor[S]. Nossa tarefa é calcular para cadaS
∑
soma(S)= valor[UM],
UM⊂S
• valor[;]=3 • valor[{2}]=5
soma(S)=parcial(S,n−1).
parcial(S,−1)=valor[S],
porque neste caso nenhum elemento pode ser removido deS. Então, no caso geral
podemos usar a seguinte recorrência:
{
parcial(S,k−1) o∉S
parcial(S,o)=
parcial(S,k−1)+parcial(S\ {o},k−1) o∈S
105
Aqui nos concentramos no elementoo. Seo∈S, temos duas opções: podemos
manteroemSou removê-lo deS.
Existe uma maneira particularmente inteligente de implementar o cálculo de somas.
Podemos declarar um array
Inteirosoma[1<<N];
Este código calcula os valores deparcial(S,o) parak =0 . . .n−1 para a matrizsoma. Desde
parcial(S,o) é sempre baseado emparcial(S,k-1), podemos reutilizar o array soma,o que
produz uma implementação muito eficiente.
106
Parte II
Algoritmos de grafos
107
Capítulo 11
Terminologia de gráfico
1 2
3 4
1 2
3 4
109
Conectividade
Um gráfico éconectadose houver um caminho entre quaisquer dois nós. Por exemplo,
o seguinte gráfico é conectado:
1 2
3 4
1 2
3 4
1 2 4 5
3 6 7
1 2
3 4
Um gráfico édirigidose as arestas puderem ser percorridas em apenas uma direção. Por Para
exemplo, o seguinte gráfico é direcionado:
1 2
3 4
110
Pesos de borda
Em umponderadográfico, cada aresta recebe umapeso. Os pesos são frequentemente
interpretados como comprimentos de aresta. Por exemplo, o gráfico a seguir é ponderado:
5
1 2 7
1 6 5
3 4 3
7
Vizinhos e graus
Dois nós sãovizinhosouadjacentese houver uma aresta entre eles. O graude um
nó é o número de seus vizinhos. Por exemplo, no gráfico a seguir, os vizinhos do
nó 2 são 1, 4 e 5, então seu grau é 3.
1 2
3 4
1 2
3 4
111
Colorações
Em umcoloraçãode um gráfico, cada nó recebe uma cor para que nenhum nó adjacente
tenha a mesma cor.
Um gráfico ébipartidose é possível colori-lo usando duas cores. Acontece que
um grafo é bipartido exatamente quando não contém um ciclo com um número
ímpar de arestas. Por exemplo, o grafo
1 2 3
4 5 6
1 2 3
4 5 6
No entanto, o gráfico
1 2 3
4 5 6
não é bipartido, porque não é possível colorir o seguinte ciclo de três nós usando
duas cores:
1 2 3
4 5 6
Simplicidade
Um gráfico ésimplesse nenhuma aresta começa e termina no mesmo nó, e não há arestas
múltiplas entre dois nós. Frequentemente assumimos que os gráficos são simples. Por
exemplo, o gráfico a seguir énãosimples:
1 2 3
4 5 6
112
Representação gráfica
Há várias maneiras de representar gráficos em algoritmos. A escolha de uma estrutura
de dados depende do tamanho do gráfico e da maneira como o algoritmo o processa.
A seguir, passaremos por três representações comuns.
vetor<Inteiro> adj[N];
A constanteNãoé escolhido para que todas as listas de adjacência possam ser armazenadas. Por
exemplo, o gráfico
1 2 3
adj[1].push_back(2);
adj[2].push_back(3);
adj[2].push_back(4);
adj[3].push_back(4);
adj[4].push_back(1);
Se o gráfico não for direcionado, ele pode ser armazenado de maneira semelhante, mas cada aresta é
adicionada em ambas as direções.
Para um gráfico ponderado, a estrutura pode ser estendida da seguinte forma:
vetor<par<Inteiro,Inteiro>> adj[N];
5 7
1 2 3
2 6 5
113
pode ser armazenado da seguinte forma:
adj[1].push_back({2,5});
adj[2].push_back({3,7});
adj[2].push_back({4,6});
adj[3].push_back({4,5});
adj[4].push_back({1,2});
para(autovocê : adj[s]) {
// nó do processo u
}
Ummatriz de adjacênciaé uma matriz bidimensional que indica quais arestas o grafo
contém. Podemos verificar eficientemente a partir de uma matriz de adjacência se há uma
aresta entre dois nós. A matriz pode ser armazenada como uma matriz
Inteiroadj[N][N];
1 2 3
1234
1 0 1 0 0
2 0 0 1 1
3 0 0 0 1
4 1 0 0 0
114
5 7
1 2 3
2 6 5
1234
1 0 5 0 0
2 0 0 7 6
3 0 0 0 5
4 2 0 0 0
Umlista de arestascontém todas as arestas de um gráfico em alguma ordem. Esta é uma maneira
conveniente de representar um gráfico se o algoritmo processar todas as arestas do gráfico e não for
necessário encontrar arestas que comecem em um nó dado.
A lista de arestas pode ser armazenada em um vetor
vetor<par<Inteiro,Inteiro>> bordas;
onde cada par (um,b) denota que há uma aresta do nóumpara nób. Assim, o
gráfico
1 2 3
bordas.push_back({1,2});
bordas.push_back({2,3});
bordas.push_back({2,4});
bordas.push_back({3,4});
bordas.push_back({4,1});
115
vetor<tupla<Inteiro,Inteiro,Inteiro>> bordas;
Cada elemento nesta lista tem o formato (um,b,c), o que significa que há uma
aresta do nóumpara nóbcom pesoc. Por exemplo, o gráfico
5 7
1 2 3
2 6 5
bordas.push_back({1,2,5});
bordas.push_back({2,3,7});
bordas.push_back({2,4,6});
bordas.push_back({3,4,5});
bordas.push_back({4,1,2});
1Em alguns compiladores mais antigos, a funçãofazer_tupladeve ser usado em vez das chaves (por
exemplo,fazer_tupla(1,2,5)em vez de {(1,2,5}).
116
Capítulo 12
Travessia de gráfico
Busca em profundidade
Exemplo
Vamos considerar como a busca em profundidade processa o seguinte gráfico:
1 2
4 5
1 2
4 5
117
Depois disso, os nós 3 e 5 serão visitados:
1 2
4 5
1 2
4 5
Implementação
A busca em profundidade pode ser convenientemente implementada usando recursão. A
seguinte funçãodfsinicia uma busca em profundidade em um nó dado. A função assume
que o gráfico é armazenado como listas de adjacência em uma matriz
vetor<Inteiro> adj[N];
boolvisitou[N];
que mantém o controle dos nós visitados. Inicialmente, cada valor da matriz éfalso,e
quando a busca chega ao nóe, o valor devisitado[e] torna-severdadeiro.A função pode
ser implementada da seguinte forma:
vaziodfs(Inteiroe) {
se(visitado[s])retornar;
visitado[s] =verdadeiro; //
nó do processo s para(auto
você: adj[s]) {
dfs(você);
}
}
118
Busca em largura
Busca em largura(BFS) visita os nós em ordem crescente de distância do nó inicial.
Assim, podemos calcular a distância do nó inicial para todos os outros nós usando
a busca em largura. No entanto, a busca em largura é mais difícil de implementar
do que a busca em profundidade.
A busca em largura percorre os nós um nível após o outro. Primeiro, a busca
explora os nós cuja distância do nó inicial é 1, depois os nós cuja distância é 2, e
assim por diante. Esse processo continua até que todos os nós tenham sido
visitados.
Exemplo
Vamos considerar como a busca em largura processa o seguinte gráfico:
1 2 3
4 5 6
Suponha que a busca comece no nó 1. Primeiro, processamos todos os nós que podem ser alcançados
a partir do nó 1 usando uma única aresta:
1 2 3
4 5 6
1 2 3
4 5 6
1 2 3
4 5 6
119
Agora calculamos as distâncias do nó inicial para todos os nós do gráfico. As
distâncias são as seguintes:
nó distância
1 0
2 1
3 2
4 1
5 2
6 3
Implementação
A busca em largura é mais difícil de implementar do que a busca em profundidade,
porque o algoritmo visita nós em diferentes partes do gráfico. Uma implementação
típica é baseada em uma fila que contém nós. A cada passo, o próximo nó na fila
será processado.
O código a seguir pressupõe que o gráfico é armazenado como listas de adjacência e
mantém as seguintes estruturas de dados:
fila<Inteiro> q;
boolvisitou[N];
Inteirodistância[N];
visitou[x] =verdadeiro;
distância[x] = 0;
[Link](x);
enquanto(![Link]()) {
Inteiros = [Link](); [Link](); //
nó do processo s para(auto
você : adj[s]) {
se(visitou[u])continuar;
visitou[u] =verdadeiro;
distância[u] = distância[s]+1;
[Link](u);
}
}
120
Aplicações
Usando os algoritmos de travessia de grafos, podemos verificar muitas propriedades de grafos.
Normalmente, tanto a busca em profundidade quanto a busca em largura podem ser usadas,
mas, na prática, a busca em profundidade é uma escolha melhor, porque é mais fácil de
implementar. Nas aplicações a seguir, assumiremos que o grafo é não direcionado.
Verificação de conectividade
Um grafo é conectado se houver um caminho entre quaisquer dois nós do grafo. Assim,
podemos verificar se um grafo é conectado começando em um nó arbitrário e descobrindo se
podemos alcançar todos os outros nós.
Por exemplo, no gráfico
1 2
4 5
1 2
4 5
Como a busca não visitou todos os nós, podemos concluir que o grafo não é conectado.
De forma semelhante, também podemos encontrar todos os componentes conectados de
um grafo iterando pelos nós e sempre iniciando uma nova busca em profundidade se o nó
atual ainda não pertencer a nenhum componente.
Encontrando ciclos
1 2
4 5
121
1 2
4 5
Verificação de bipartição
Um grafo é bipartido se seus nós podem ser coloridos usando duas cores de modo que não haja
nós adjacentes com a mesma cor. É surpreendentemente fácil verificar se um grafo é bipartido
usando algoritmos de travessia de grafos.
A ideia é colorir o nó inicial de azul, todos os seus vizinhos de vermelho, todos os
seus vizinhos de azul, e assim por diante. Se em algum ponto da busca notarmos que
dois nós adjacentes têm a mesma cor, isso significa que o grafo não é bipartido. Caso
contrário, o grafo é bipartido e uma coloração foi encontrada.
Por exemplo, o gráfico
1 2
4 5
1 2
4 5
Notamos que a cor de ambos os nós 2 e 5 é vermelha, enquanto eles são nós
adjacentes no gráfico. Assim, o gráfico não é bipartido.
Esse algoritmo sempre funciona, porque quando há apenas duas cores
disponíveis, a cor do nó inicial em um componente determina as cores de todos os
outros nós no componente. Não faz diferença se o nó inicial é vermelho ou azul.
Observe que, no caso geral, é difícil descobrir se os nós em um gráfico podem ser
coloridos usandoocores para que nenhum nó adjacente tenha a mesma cor. Mesmo
quandok =3, nenhum algoritmo eficiente é conhecido, mas o problema é NP-difícil.
122
Capítulo 13
Encontrar um caminho mais curto entre dois nós de um gráfico é um problema importante que
tem muitas aplicações práticas. Por exemplo, um problema natural relacionado a uma rede
rodoviária é calcular o menor comprimento possível de uma rota entre duas cidades, dados os
comprimentos das estradas.
Em um grafo não ponderado, o comprimento de um caminho é igual ao número de suas arestas,
e podemos simplesmente usar a busca em largura para encontrar um caminho mais curto. No
entanto, neste capítulo, focamos em grafos ponderados, onde algoritmos mais sofisticados são
necessários para encontrar caminhos mais curtos.
Algoritmo Bellman–Ford
OAlgoritmo Bellman–Ford1encontra os caminhos mais curtos de um nó inicial para todos
os nós do gráfico. O algoritmo pode processar todos os tipos de gráficos, desde que o
gráfico não contenha um ciclo com comprimento negativo. Se o gráfico contiver um ciclo
negativo, o algoritmo pode detectar isso.
O algoritmo mantém o controle das distâncias do nó inicial para todos os nós do
gráfico. Inicialmente, a distância para o nó inicial é 0 e a distância para todos os outros
nós é infinita. O algoritmo reduz as distâncias encontrando arestas que encurtam os
caminhos até que não seja possível reduzir nenhuma distância.
Exemplo
Vamos considerar como o algoritmo Bellman-Ford funciona no gráfico a seguir:
0 5 ∞
1 2 2
7
3 3 6
∞
3 4 2
∞ 1 ∞
123
Cada nó do gráfico recebe uma distância. Inicialmente, a distância até o nó inicial é
0, e a distância até todos os outros nós é infinita.
O algoritmo busca por arestas que reduzem distâncias. Primeiro, todas as arestas do nó
1 reduzem distâncias:
0 5 5
1 2 2
7
3 3 5
∞
3 4 2
3 1 7
0 5 5
1 2 2
7
3 3 5
7
3 4 2
3 1 4
0 5 5
1 2 2
7
3 3 5
6
3 4 2
3 1 4
Depois disso, nenhuma aresta pode reduzir qualquer distância. Isso significa que
as distâncias são finais, e calculamos com sucesso as distâncias mais curtas do nó
inicial para todos os nós do gráfico.
Por exemplo, a menor distância 3 do nó 1 ao nó 5 corresponde ao seguinte
caminho:
0 5 5
1 2 2
7
3 3 5
6
3 4 2
3 1 4
124
Implementação
A seguinte implementação do algoritmo Bellman-Ford determina as distâncias
mais curtas de um nóxpara todos os nós do gráfico. O código assume que o
gráfico é armazenado como uma lista de arestasbordasque consiste em tuplas da
forma (um,b,c), o que significa que há uma aresta do nóumpara nóbcom pesoc.
O algoritmo consiste emn−1 rodadas, e em cada rodada o algoritmo percorre
todas as arestas do gráfico e tenta reduzir as distâncias. O algoritmo constrói uma
matrizdistânciaque conterá as distâncias dexpara todos os nós do gráfico. A
constanteINFdenota uma distância infinita.
Ciclos negativos
O algoritmo de Bellman–Ford também pode ser usado para verificar se o gráfico contém um
ciclo com comprimento negativo. Por exemplo, o gráfico
3 2 1
1 2 4
5 3 −7
125
Algoritmo SPFA
OAlgoritmo SPFA(”Shortest Path Faster Algorithm”) [20] é uma variante do algoritmo
Bellman–Ford, que é frequentemente mais eficiente do que o algoritmo original. O
algoritmo SPFA não passa por todas as arestas em cada rodada, mas, em vez disso, escolhe
as arestas a serem examinadas de uma forma mais inteligente.
O algoritmo mantém uma fila de nós que podem ser usados para reduzir as
distâncias. Primeiro, o algoritmo adiciona o nó inicialxpara a fila. Então, o algoritmo
sempre processa o primeiro nó na fila, e quando uma aresta um→breduz uma
distância, nóbé adicionado à fila.
A eficiência do algoritmo SPFA depende da estrutura do gráfico: o algoritmo é
frequentemente eficiente, mas sua pior complexidade de tempo ainda éO(nm) e é
possível criar entradas que tornam o algoritmo tão lento quanto o algoritmo
Bellman-Ford original.
Algoritmo de Dijkstra
Exemplo
Vamos considerar como o algoritmo de Dijkstra funciona no gráfico a seguir quando o
nó inicial é o nó 1:
∞ 6 ∞
3 4 2
2 9 5
∞
2 1 1
∞ 5 0
2EW Dijkstra publicou o algoritmo em 1959 [14]; no entanto, seu artigo original não menciona
como implementar o algoritmo de forma eficiente.
126
Quando um nó é selecionado, o algoritmo percorre todas as arestas que
começam no nó e reduz as distâncias usando-as:
∞ 6 9
3 4 2
2 9 5
1
2 1 1
5 5 0
∞ 3
6
3 4 2
2 9 5
1
2 1 1
5 5 0
9 6 3
3 4 2
2 9 5
1
2 1 1
5 5 0
7 6 3
3 4 2
2 9 5
1
2 1 1
5 5 0
127
Bordas negativas
A eficiência do algoritmo de Dijkstra é baseada no fato de que o gráfico não contém
arestas negativas. Se houver uma aresta negativa, o algoritmo pode dar resultados
incorretos. Como exemplo, considere o seguinte gráfico:
2 2 3
1 4
6 3 −5
Implementação
A seguinte implementação do algoritmo de Dijkstra calcula as distâncias mínimas
de um nóxpara outros nós do gráfico. O gráfico é armazenado como listas de
adjacência para queajusteum]contém um par (b,c) sempre que houver uma aresta
do nóumpara nóbcom pesoc.
Uma implementação eficiente do algoritmo de Dijkstra requer que seja possível
encontrar eficientemente o nó de distância mínima que não foi processado. Uma estrutura
de dados apropriada para isso é uma fila de prioridade que contém os nós ordenados por
suas distâncias. Usando uma fila de prioridade, o próximo nó a ser processado pode ser
recuperado em tempo logarítmico.
No código a seguir, a fila de prioridadesqcontém pares da forma (-d,x), o que
significa que a distância atual até o nóxée. A matrizdistânciacontém a distância
para cada nó e a matrizprocessadoindica se um nó foi processado. Inicialmente a
distância é de 0 axe∞para todos os outros nós.
128
Observe que a fila de prioridade contémnegativodistâncias para nós. A razão para
isso é que a versão padrão da fila de prioridades C++ encontra o máximo de elementos,
enquanto queremos encontrar o mínimo de elementos. Ao usar distâncias negativas,
podemos usar diretamente a fila de prioridades padrão3. Observe também que pode
haver várias instâncias do mesmo nó na fila de prioridades; no entanto, apenas a
instância com a distância mínima será processada.
A complexidade de tempo da implementação acima éO(n+mregistroeu), porque o
algoritmo percorre todos os nós do grafo e adiciona para cada aresta no máximo uma
distância à fila de prioridades.
Algoritmo de Floyd–Warshall
Exemplo
Vamos considerar como o algoritmo Floyd-Warshall funciona no gráfico a seguir:
7
3 4 2
2 9 5
2 1 1
5
1 2 3 4 5
1 0 5∞ 9 1
2 5 0 2 ∞ ∞
3∞ 2 0 7 ∞
49 ∞ 7 0 2
51 ∞∞ 2 0
3Claro, também poderíamos declarar a fila de prioridades como no Capítulo 4.5 e usar distâncias positivas, mas a
implementação seria um pouco mais longa.
4O algoritmo recebeu o nome de RW Floyd e S. Warshall, que o publicaram independentemente em 1962
[23, 70].
129
O algoritmo consiste em rodadas consecutivas. Em cada rodada, o algoritmo seleciona um
novo nó que pode atuar como um nó intermediário em caminhos a partir de agora, e as
distâncias são reduzidas usando esse nó.
Na primeira rodada, o nó 1 é o novo nó intermediário. Há um novo caminho entre
os nós 2 e 4 com comprimento 14, porque o nó 1 os conecta. Há também um novo
caminho entre os nós 2 e 5 com comprimento 6.
1 2 3 4 5
1 0 5∞ 9 1
2 5 0 2 14 6
3∞ 2 0 7 ∞
49 14 7 0 2
51 6∞ 2 0
1 2 3 4 5
1 0 5 7 9 1
25 0 2 14 6
37 20 78
4 9 14 7 02
5 1 68 20
12345
105791
2 5 0 296
372078
4 997 0 2
516820
O algoritmo continua assim, até que todos os nós tenham sido nomeados nós
intermediários. Após o algoritmo terminar, o array contém as distâncias mínimas
entre quaisquer dois nós:
12345
105731
250286
372078
438702
516820
Por exemplo, a matriz nos diz que a menor distância entre os nós 2 e 4 é 8. Isso
corresponde ao seguinte caminho:
130
Traduzido do Inglês para o Português - [Link]
7
3 4 2
2 9 5
2 1 1
5
Implementação
A vantagem do algoritmo Floyd–Warshall é que ele é fácil de implementar. O
código a seguir constrói uma matriz de distância ondedistância[um][b] é a menor
distância entre nósumeb. Primeiro, o algoritmo inicializadistânciausando a matriz
de adjacênciaajustedo gráfico:
Depois disso, as distâncias mais curtas podem ser encontradas da seguinte forma:
131
132
Capítulo 14
Algoritmos de árvore
5 1 4
8 6 2 3 7
Ofolhasde uma árvore são os nós com grau 1, ou seja, com apenas um vizinho.
Por exemplo, as folhas da árvore acima são os nós 3, 5, 7 e 8.
Em umenraizadoárvore, um dos nós é nomeado oraizda árvore, e todos os
outros nós são colocados abaixo da raiz. Por exemplo, na árvore a seguir, o nó 1 é
o nó raiz.
2 3 4
5 6 7
133
A estrutura de uma árvore enraizada érecursivo:cada nó da árvore atua como a
raiz de umasubárvoreque contém o nó em si e todos os nós que estão nas
subárvores de seus filhos. Por exemplo, na árvore acima, a subárvore do nó 2
consiste nos nós 2, 5, 6 e 8:
5 6
Travessia de árvores
Algoritmos gerais de travessia de grafos podem ser usados para percorrer os nós de
uma árvore. No entanto, a travessia de uma árvore é mais fácil de implementar do que
a de um grafo geral, porque não há ciclos na árvore e não é possível alcançar um nó de
múltiplas direções.
A maneira típica de percorrer uma árvore é iniciar uma busca em profundidade em um nó
arbitrário. A seguinte função recursiva pode ser usada:
vaziodfs(Inteiroe,Inteiroe) {
// nó do processo s para(
autovocê : adj[s]) {
se(u != e) dfs(u, s);
}
}
dfs(x, 0);
Programação dinâmica
A programação dinâmica pode ser usada para calcular algumas informações durante uma
travessia de árvore. Usando a programação dinâmica, podemos, por exemplo, calcular emO(não)
tempo para cada nó de uma árvore enraizada, o número de nós em sua subárvore ou o
comprimento do caminho mais longo do nó até uma folha.
134
Como exemplo, vamos calcular para cada nóeum valorcontar[e]: o número de nós
em sua subárvore. A subárvore contém o nó em si e todos os nós nas subárvores de
seus filhos, então podemos calcular o número de nós recursivamente usando o
seguinte código:
vaziodfs(Inteiroe,Inteiroe) {
contagem[s] = 1;
para(autovocê : adj[s]) {
se(você == e)continuar;
dfs(u, s);
contagem[s] += contagem[u];
}
}
Diâmetro
Odiâmetrode uma árvore é o comprimento máximo de um caminho entre dois nós. Por
exemplo, considere a seguinte árvore:
5 1 4
6 2 3 7
5 1 4
6 2 3 7
Note que pode haver vários caminhos de comprimento máximo. No caminho acima, poderíamos
substituir o nó 6 pelo nó 5 para obter outro caminho com comprimento 4.
A seguir discutiremos doisO(não) algoritmos de tempo para calcular o diâmetro de uma
árvore. O primeiro algoritmo é baseado em programação dinâmica, e o segundo algoritmo
usa duas buscas em profundidade.
Algoritmo 1
Uma maneira geral de abordar muitos problemas de árvore é primeiro enraizar a árvore
arbitrariamente. Depois disso, podemos tentar resolver o problema separadamente para cada
subárvore. Nosso primeiro algoritmo para calcular o diâmetro é baseado nessa ideia.
Uma observação importante é que cada caminho em uma árvore enraizada tem umponto
mais alto: o nó mais alto que pertence ao caminho. Assim, podemos calcular para cada
135
nó o comprimento do caminho mais longo cujo ponto mais alto é o nó. Um desses
caminhos corresponde ao diâmetro da árvore.
Por exemplo, na árvore a seguir, o nó 1 é o ponto mais alto do caminho que
corresponde ao diâmetro:
2 3 4
5 6 7
Algoritmo 2
Outra maneira eficiente de calcular o diâmetro de uma árvore é com base em duas
buscas em profundidade. Primeiro, escolhemos um nó arbitrárioumna árvore e
encontre o nó mais distantebdeum. Então, encontramos o nó mais distantecdeb. O
diâmetro da árvore é a distância entrebec.
No gráfico a seguir,um,becpoderia ser:
5 1 4
b um c
6 2 3 7
136
b x c
6 2 1 4 7
5 3
um
3 5
1 2
4 6
nóx 123456
comprimento máximo(x) 2 2 3 3 3 3
Também neste problema, um bom ponto de partida para resolver o problema é enraizar a árvore
arbitrariamente:
2 3 4
5 6
137
1
2 3 4
5 6
Esta parte é fácil de resolver emO(não) tempo, porque podemos usar programação dinâmica
como fizemos anteriormente.
Então, a segunda parte do problema é calcular para cada nóxo comprimento
máximo de um caminho através de seu paip. Por exemplo, o caminho mais longo
do nó 3 passa pelo seu pai 1:
2 3 4
5 6
2 3 4
5 6
• comprimento máximo2(x) o comprimento máximo de um caminho dexem outra direção que não o
primeiro caminho
138
Árvores binárias
UMárvore bináriaé uma árvore enraizada onde cada nó tem uma subárvore esquerda e direita.
É possível que uma subárvore de um nó esteja vazia. Assim, cada nó em uma árvore binária tem
zero, um ou dois filhos.
Por exemplo, a árvore a seguir é uma árvore binária:
2 3
4 5 7
Os nós de uma árvore binária têm três ordenações naturais que correspondem a diferentes
maneiras de percorrer recursivamente a árvore:
• pedido antecipado: primeiro processe a raiz, depois atravesse a subárvore esquerda e depois
atravesse a subárvore direita
• em ordem: primeiro percorra a subárvore esquerda, depois processe a raiz e depois percorra
a subárvore direita
Para a árvore acima, os nós em pré-ordem são [1, 2, 4, 5, 6, 3, 7], em ordem [4, 2, 6,
5, 1, 3, 7] e em pós-ordem [4, 6, 5, 2, 7, 3, 1].
Se soubermos a pré-ordem e a ordem interna de uma árvore, podemos reconstruir a
estrutura exata da árvore. Por exemplo, a árvore acima é a única árvore possível com pré-ordem
[1, 2, 4, 5, 6, 3, 7] e ordem interna [4, 2, 6, 5, 1, 3, 7]. De forma semelhante, a pós-ordem e a
ordem interna também determinam a estrutura de uma árvore.
No entanto, a situação é diferente se conhecermos apenas a pré-ordem e a pós-ordem
de uma árvore. Neste caso, pode haver mais de uma árvore que corresponda às
ordenações. Por exemplo, em ambas as árvores
1 1
2 2
a pré-ordem é [1, 2] e a pós-ordem é [2, 1], mas as estruturas das árvores são
diferentes.
139
140
Capítulo 15
Árvores de abrangência
UMárvore de extensãode um gráfico consiste em todos os nós do gráfico e algumas das arestas
do gráfico, de modo que haja um caminho entre quaisquer dois nós. Como árvores em geral,
árvores de abrangência são conectadas e acíclicas. Normalmente, há várias maneiras de
construir uma árvore de abrangência.
Por exemplo, considere o seguinte gráfico:
5
32 39
1 6 3 4
55 67
2
5
32 39
1 3 4
5 6
2
O peso de uma árvore de extensão é a soma dos pesos de suas arestas. Por
exemplo, o peso da árvore de extensão acima é 3+5+9+3+2=22.
UMárvore de extensão mínimaé uma árvore de abrangência cujo peso é o menor
possível. O peso de uma árvore de abrangência mínima para o gráfico de exemplo é 20, e
tal árvore pode ser construída da seguinte forma:
32 3
1 3 4
55 67
2
141
De forma semelhante, umárvore de extensão máximaé uma árvore de abrangência
cujo peso é o maior possível. O peso máximo de uma árvore de abrangência para o gráfico
de exemplo é 32:
5
2 39
1 6 4
55 6 7
Observe que um gráfico pode ter várias árvores de abrangência mínima e máxima, portanto,
as árvores não são únicas.
Acontece que vários métodos gulosos podem ser usados para construir árvores de
abrangência mínima e máxima. Neste capítulo, discutimos dois algoritmos que processam
as arestas do gráfico ordenadas por seus pesos. Focamos em encontrar árvores de
abrangência mínima, mas os mesmos algoritmos podem encontrar árvores de abrangência
máxima processando as arestas em ordem reversa.
Algoritmo de Kruskal
Exemplo
Vamos considerar como o algoritmo de Kruskal processa o seguinte gráfico:
5
32 39
1 6 3 4
55 67
2
142
borda peso
5–6 2
1–2 3
3–6 3
1–5 5
2–3 5
2–5 6
4–6 7
3–4 9
Depois disso, o algoritmo percorre a lista e adiciona cada aresta à árvore se ela unir
dois componentes separados.
Inicialmente, cada nó está em seu próprio componente:
2 3
1 4
5 6
A primeira aresta a ser adicionada à árvore é a aresta 5–6 que cria um componente
{5, 6} unindo os componentes {5} e {6}:
2 3
1 4
5 6
2
Depois disso, as arestas 1–2, 3–6 e 1–5 são adicionadas de forma semelhante:
32 3
1 3 4
55 6
2
143
Por fim, a aresta 4–6 será incluída na árvore:
32 3
1 3 4
55 67
2
Depois disso, o algoritmo não adicionará nenhuma nova aresta, porque o grafo
está conectado e há um caminho entre quaisquer dois nós. O grafo resultante é uma
árvore geradora mínima com peso 2+3+3+5+7=20.
2 3
1 4
5 6
Entretanto, não é possível que a árvore acima seja uma árvore de abrangência
mínima para o gráfico. A razão para isso é que podemos remover uma aresta da árvore
e substituí-la pela aresta de peso mínimo 5–6. Isso produz uma árvore de abrangência
cujo peso émenor:
2 3
1 4
5 6
2
Por essa razão, é sempre ótimo incluir a aresta de peso mínimo na árvore para produzir uma
árvore de abrangência mínima. Usando um argumento semelhante, podemos mostrar que
também é ótimo adicionar a próxima aresta na ordem de peso à árvore, e assim por diante.
Portanto, o algoritmo de Kruskal funciona corretamente e sempre produz uma árvore de
abrangência mínima.
144
Implementação
Ao implementar o algoritmo de Kruskal, é conveniente usar a representação da lista de
arestas do gráfico. A primeira fase do algoritmo classifica as arestas na lista emO(eu
registroeu) tempo. Depois disso, a segunda fase do algoritmo constrói a árvore de
abrangência mínima como segue:
para(...) {
se(!mesmo(a,b)) unir(a,b);
}
Estrutura de união-descoberta
Estrutura
Em uma estrutura union-find, um elemento em cada conjunto é o representante do conjunto, e
há uma cadeia de qualquer outro elemento do conjunto para o representante. Por exemplo,
suponha que os conjuntos sejam {1, 4, 7}, {5} e {2, 3, 6, 8}:
4 5 2
1 7
3
6 8
2A estrutura apresentada aqui foi introduzida em 1971 por JD Hopcroft e JD Ullman [38]. Mais tarde,
em 1975, RE Tarjan estudou uma variante mais sofisticada da estrutura [64] que é discutida em muitos
livros didáticos de algoritmos atualmente.
145
Neste caso os representantes dos conjuntos são 4, 5 e 2. Podemos encontrar o
representante de qualquer elemento seguindo a cadeia que começa no elemento. Por
exemplo, o elemento 2 é o representante do elemento 6, porque seguimos a cadeia 6→
3→2. Dois elementos pertencem ao mesmo conjunto exatamente quando seus
representantes são os mesmos.
Dois conjuntos podem ser unidos conectando o representante de um conjunto ao
representante do outro conjunto. Por exemplo, os conjuntos {1, 4, 7} e {2, 3, 6, 8} podem ser
unidos da seguinte forma:
4 2
1 7
3
6 8
Implementação
A estrutura union-find pode ser implementada usando arrays. Na implementação a
seguir, o arraylinkcontém para cada elemento o próximo elemento na cadeia ou o
próprio elemento se for um representante, e a matriztamanhoindica para cada
representante o tamanho do conjunto correspondente.
Inicialmente, cada elemento pertence a um conjunto separado:
Inteiroencontrar(Inteirox) {
146
boolmesmo(Inteiroum,Inteirob) {
retornarencontrar(a) == encontrar(b);
}
vaziounir(Inteiroum,Inteirob) {
a = encontrar(a);
b = encontrar(b);
se(tamanho[a] < tamanho[b]) swap(a,b);
tamanho[a] += tamanho[b];
link[b] = a;
}
Algoritmo de Prim
Exemplo
Vamos considerar como o algoritmo de Prim funciona no gráfico a seguir:
5
32 39
1 6 3 4
55 67
2
3O algoritmo recebeu o nome de RC Prim, que o publicou em 1957 [54]. No entanto, o mesmo
algoritmo já foi descoberto em 1930 por V. Jarník.
147
Inicialmente, não há arestas entre os nós:
2 3
1 4
5 6
32 3
1 4
5 6
5
32 3
1 4
5 6
O processo continua até que todos os nós tenham sido incluídos na árvore:
5
32 3
1 3 4
5 67
2
Implementação
Assim como o algoritmo de Dijkstra, o algoritmo de Prim pode ser eficientemente implementado
usando uma fila de prioridades. A fila de prioridades deve conter todos os nós que podem ser
conectados ao componente atual usando uma única aresta, em ordem crescente dos pesos das
arestas correspondentes.
A complexidade de tempo do algoritmo de Prim éO(n+mregistroeu) que é igual à
complexidade de tempo do algoritmo de Dijkstra. Na prática, os algoritmos de Prim e Kruskal
são ambos eficientes, e a escolha do algoritmo é uma questão de gosto. Ainda assim, a maioria
dos programadores competitivos usa o algoritmo de Kruskal.
148
Capítulo 16
Grafos direcionados
Classificação topológica
1 2 3
4 5 6
4 1 5 2 3 6
149
Algoritmo
A ideia é percorrer os nós do gráfico e sempre começar uma busca em
profundidade no nó atual se ele ainda não tiver sido processado. Durante as
buscas, os nós têm três estados possíveis:
Exemplo 1
No gráfico de exemplo, a pesquisa prossegue primeiro do nó 1 ao nó 6:
1 2 3
4 5 6
Agora o nó 6 foi processado, então ele é adicionado à lista. Depois disso, também os nós
3, 2 e 1 são adicionados à lista:
1 2 3
4 5 6
1 2 3
4 5 6
150
Assim, a lista final é [6, 3, 2, 1, 5, 4]. Processamos todos os nós, então uma ordenação
topológica foi encontrada. A ordenação topológica é a lista reversa [4, 5, 1, 2, 3, 6]:
4 5 1 2 3 6
Observe que uma classificação topológica não é única e pode haver várias classificações
topológicas para um gráfico.
Exemplo 2
Vamos agora considerar um grafo para o qual não podemos construir uma ordenação
topológica, porque o grafo contém um ciclo:
1 2 3
4 5 6
1 2 3
4 5 6
A busca chega ao nó 2 cujo estado é 1, o que significa que o grafo contém um ciclo.
Neste exemplo, há um ciclo 2→3→5→2.
Programação dinâmica
Se um grafo direcionado for acíclico, a programação dinâmica pode ser aplicada a ele. Por
exemplo, podemos resolver eficientemente os seguintes problemas relativos a caminhos de
um nó inicial para um nó final:
151
Contando o número de caminhos
Como exemplo, vamos calcular o número de caminhos do nó 1 ao nó 6 no gráfico a
seguir:
1 2 3
4 5 6
• 1→2→3→6
• 1→4→5→2→3→6
• 1→4→5→3→6
ondeum1,um2, . . . ,umosão os nós dos quais há uma aresta parax. Como o gráfico é acíclico, os
valores decaminhos(x) pode ser calculado na ordem de uma ordenação topológica. Uma
ordenação topológica para o gráfico acima é a seguinte:
1 4 5 2 3 6
1 2 3
1 2 3
4 5 6
1 1 3
152
Estendendo o algoritmo de Dijkstra
3
1 2 8
2
5 4 5
3 4 1
2
3
1 2
2
5 4 5
3 4 1
2
1 1
3
1 2
2
5 4 5
3
3 4 1
2
2 3
153
0 1 2 3 4 5 6
Caminhos sucessores
9 3 1 2 5
7 6
4 8
4 6 2 5 2 5 2
154
{
sucesso(x) k =1
sucesso(x,o)=
sucesso(sucesso(x,o/2),o/2) k >1
O pré-cálculo dos valores levaO(nãoregistrovocê) tempo, porqueO(registrovocê) valores são
calculados para cada nó. No gráfico acima, os primeiros valores são os seguintes:
x1 2 3 4 5 6 7 8 9
sucesso(x, 1) 3 5 7 6 2 2 1 6 3 sucesso(x, 2)
7 2 1 2 5 5 3 2 7 sucesso(x, 4) 3 2 7 2 5 5 1 2
3 sucesso(x, 8) 7 2 1 2 5 5 3 2 7
···
Depois disso, qualquer valor desucesso(x,o) pode ser calculado apresentando o número de
passosocomo uma soma de potências de dois. Por exemplo, se quisermos calcular o valor de
sucesso(x, 11), primeiro formamos a representação 11=8+2+1. Usando isso,
Detecção de ciclo
Considere um grafo sucessor que contém apenas um caminho que termina em um
ciclo. Podemos fazer as seguintes perguntas: se começarmos nossa caminhada no nó
inicial, qual é o primeiro nó do ciclo e quantos nós o ciclo contém?
Por exemplo, no gráfico
1 2 3 4 5
155
Algoritmo de Floyd
Algoritmo de Floyd2caminha para frente no gráfico usando dois ponteirosumeb.
Ambos os ponteiros começam em um nóxque é o nó inicial do gráfico. Então, em
cada volta, o ponteiroumdá um passo à frente e o ponteirobanda dois passos para
frente. O processo continua até que os ponteiros se encontrem:
a = succ(x);
b = succ(succ(x));
enquanto(a != b) {
a = succ(a);
b = sucesso(sucesso(b));
}
um = x;
enquanto(a != b) {
a = succ(a);
b = succ(b);
}
primeiro = a;
b = succ(a);
comprimento = 1;
enquanto(a != b) {
b = succ(b);
comprimento++;
156
Capítulo 17
Conectividade forte
1 2 1 2
3 4 3 4
O gráfico da direita não está fortemente conectado porque, por exemplo, não há
caminho do nó 2 para o nó 1.
Ocomponentes fortemente conectadosde um gráfico, divida o gráfico em partes
fortemente conectadas que sejam tão grandes quanto possível. Os componentes
fortemente conectados formam um acíclicográfico de componentesque representa a
estrutura profunda do gráfico original.
Por exemplo, para o gráfico
1 2 3
4 5 6
1 2 3
4 5 6
157
O gráfico do componente correspondente é o seguinte:
UM
C E
Algoritmo de Kosaraju
Pesquisar 1
4 5 6
4/5 3/6 11/12
1De acordo com [1], SR Kosaraju inventou este algoritmo em 1978, mas não o publicou. Em
1981, o mesmo algoritmo foi redescoberto e publicado por M. Sharir [57].
158
nó tempo de processamento
4 5
5 6
2 7
1 8
6 12
7 13
3 14
Pesquisa 2
1 2 3
4 5 6
Depois disso, o algoritmo percorre a lista de nós criada pela primeira busca, em
reverterordem. Se um nó não pertencer a um componente, o algoritmo cria um novo
componente e inicia uma busca em profundidade que adiciona todos os novos nós
encontrados durante a busca ao novo componente.
No gráfico de exemplo, o primeiro componente começa no nó 3:
1 2 3
4 5 6
Observe que, como todas as arestas são invertidas, o componente não “vaza” para outras
partes do gráfico.
159
Os próximos nós na lista são os nós 7 e 6, mas eles já pertencem a um
componente, então o próximo novo componente começa no nó 1:
1 2 3
4 5 6
1 2 3
4 5 6
Problema 2SAT
A forte conectividade também está ligada àProblema 2SAT2. Neste problema, nos é
dada uma fórmula lógica
(um1∨b1)∧(um2∨b2)∧···∧(umeu∨beu),
onde cadaumeuebeué uma variável lógica (x1,x2, . . . ,xnão) ou uma negação de uma
variável lógica (¬x1,¬x2, . . . ,¬xnão). Os símbolos ”∧" e "∨” denotam operadores lógicos
”e” e ”ou”. Nossa tarefa é atribuir a cada variável um valor para que a fórmula seja
verdadeira, ou declarar que isso não é possível.
Por exemplo, a fórmula
eu1=(x2∨¬x1)∧(¬x1∨¬x2)∧(x1∨x3)∧(¬x2∨¬x3)∧(x1∨x4)
-
--x
--1=falso
-x2=falso
--
--x 3=verdadeiro
-
x4=verdadeiro
2O algoritmo aqui apresentado foi introduzido em [4]. Há também outro algoritmo de tempo linear
bem conhecido [19] que é baseado em retrocesso.
160
No entanto, a fórmula
eu2=(x1∨x2)∧(x1∨¬x2)∧(¬x1∨x3)∧(¬x1∨¬x3)
¬x3 x2 ¬x1 x4
¬x4 x1 ¬x2 x3
¬x1
x3 x2 ¬x2 ¬x3
x1
A estrutura do gráfico nos diz se é possível atribuir os valores das variáveis para
que a fórmula seja verdadeira. Acontece que isso pode ser feito exatamente quando
não há nósxeue¬xeude modo que ambos os nós pertençam ao mesmo componente
fortemente conectado. Se houver tais nós, o gráfico contém um caminho dexeupara¬x
eue também um caminho de¬xeuparaxeu, então ambosxeue¬xeudeveria ser verdade, o
que não é possível.
No gráfico da fórmulaeu1não há nósxeue¬xeude modo que ambos os nós
pertencem ao mesmo componente fortemente conectado, então existe uma solução.
No gráfico da fórmulaeu2todos os nós pertencem ao mesmo componente fortemente
conectado, então não existe solução.
Se existir uma solução, os valores para as variáveis podem ser encontrados
percorrendo os nós do gráfico de componentes em uma ordem de classificação topológica
reversa. Em cada etapa, processamos um componente que não contém arestas que levam a
um componente não processado. Se as variáveis no componente não tiverem valores
atribuídos, seus valores serão determinados de acordo com os valores no componente e, se
161
elas já têm valores, elas permanecem inalteradas. O processo continua até que
cada variável tenha recebido um valor.
O gráfico de componentes para a fórmulaeu1é o seguinte:
UM B C E
162
Capítulo 18
Consultas de árvore
Este capítulo discute técnicas para processar consultas em subárvores e caminhos de uma
árvore enraizada. Por exemplo, tais consultas são:
Encontrando ancestrais
4 5 2
3 7 6
Uma maneira fácil de calcular qualquer valor deantepassado(x,o) é realizar uma sequência
deomove na árvore. No entanto, a complexidade de tempo deste método éO(o), o que pode ser
lento, porque uma árvore denãoos nós podem ter uma cadeia denãonós.
163
Felizmente, usando uma técnica semelhante à usada no Capítulo 16.3, qualquer valor de
antepassado(x,o) pode ser calculado eficientemente emO(registroo) tempo após o pré-
processamento. A ideia é pré-calcular todos os valoresantepassado(x,o) ondeo≤nãoé uma
potência de dois. Por exemplo, os valores para a árvore acima são os seguintes:
x1 2 3 4 5 6 7 8
antepassado(x, 1) 0 1 4 1 1 2 4 7
antepassado(x, 2) 0 0 1 0 0 1 1 4
antepassado(x, 4) 0 0 0 0 0 0 0 0
···
Subárvores e caminhos
2 3 4 5
6 7 8 9
2 3 4 5
6 7 8 9
1 2 6 3 4 7 8 9 5
164
Consultas de subárvore
1 2 6 3 4 7 8 9 5
• atualizar o valor de um nó
2
1
32 53 43 51
6 7 8 9
4 4 3 1
id do nó 1 2 6 3 4 7 8 9 5
tamanho da subárvore 9 2 1 1 4 1 1 1 1
valor do nó 2 3 4 5 3 4 3 1 1
Usando esta matriz, podemos calcular a soma dos valores em qualquer subárvore
descobrindo primeiro o tamanho da subárvore e então os valores dos nós correspondentes. Por
exemplo, os valores na subárvore do nó 4 podem ser encontrados da seguinte forma:
id do nó 1 2 6 3 4 7 8 9 5
tamanho da subárvore 9 2 1 1 4 1 1 1 1
valor do nó 2 3 4 5 3 4 3 1 1
Para responder às consultas de forma eficiente, basta armazenar os valores dos nós em uma
árvore indexada binária ou de segmento. Depois disso, podemos atualizar um valor e calcular a
soma dos valores emO(registronão) tempo.
165
Consultas de caminho
Usando um array de travessia de árvore, também podemos calcular eficientemente somas de valores
em caminhos do nó raiz para qualquer nó da árvore. Considere um problema em que nossa tarefa é
dar suporte às seguintes consultas:
• alterar o valor de um nó
4
1
52 33 45 52
6 7 8 9
3 5 3 1
Podemos resolver esse problema como antes, mas agora cada valor na última
linha do array é a soma dos valores em um caminho da raiz até o nó. Por exemplo,
o array a seguir corresponde à árvore acima:
id do nó 1 2 6 3 4 7 8 9 5
tamanho da subárvore 9 2 1 1 4 1 1 1 1
soma do caminho 4 9 12 7 9 14 12 10 6
id do nó 1 2 6 3 4 7 8 9 5
tamanho da subárvore 9 2 1 1 4 1 1 1 1
soma do caminho 4 9 12 7 10 15 13 11 6
Assim, para suportar ambas as operações, devemos ser capazes de aumentar todos os valores em
um intervalo e recuperar um único valor. Isso pode ser feito emO(registronão) tempo usando uma
árvore indexada binária ou de segmento (veja Capítulo 9.4).
166
Menor ancestral comum
Omenor ancestral comumde dois nós de uma árvore enraizada é o nó mais baixo cuja
subárvore contém ambos os nós. Um problema típico é processar eficientemente consultas
que pedem para encontrar o ancestral comum mais baixo de dois nós.
Por exemplo, na árvore a seguir, o menor ancestral comum dos nós 5 e 8 é o
nó 2:
2 3 4
5 6 7
Método 1
Uma maneira de resolver o problema é usar o fato de que podemos encontrar com
eficiência o oº ancestral de qualquer nó na árvore. Usando isso, podemos dividir o
problema de encontrar o menor ancestral comum em duas partes.
Usamos dois ponteiros que inicialmente apontam para os dois nós cujo ancestral comum mais
baixo devemos encontrar. Primeiro, movemos um dos ponteiros para cima, de modo que ambos os
ponteiros apontem para nós no mesmo nível.
No cenário de exemplo, movemos o segundo ponteiro um nível acima para que ele
aponte para o nó 6, que está no mesmo nível do nó 5:
2 3 4
5 6 7
167
Depois disso, determinamos o número mínimo de passos necessários para mover ambos os
ponteiros para cima, de modo que eles apontem para o mesmo nó. O nó para o qual os
ponteiros apontam depois disso é o ancestral comum mais baixo.
No cenário de exemplo, basta mover ambos os ponteiros um passo para cima, até
o nó 2, que é o menor ancestral comum:
2 3 4
5 6 7
Método 2
Outra maneira de resolver o problema é com base em uma matriz de travessia de árvore1. Mais uma
vez, a ideia é percorrer os nós usando uma busca em profundidade:
2 3 4
5 6 7
168
Armazenamos dois valores no array: o identificador do nó e a profundidade do
nó na árvore. O array a seguir corresponde à árvore acima:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
id do nó 1 2 5 2 6 8 6 2 1 3 1 4 7 4 1
profundidade 1 2 3 2 3 4 3 2 1 2 1 2 3 2 1
id do nó 1 2 5 2 6 8 6 2 1 3 1 4 7 4 1
profundidade 1 2 3 2 3 4 3 2 1 2 1 2 3 2 1
↑
profundidade(um)+profundidade(b)−2·profundidade(c),
2 3 4
5 6 7
169
O ancestral comum mais baixo dos nós 5 e 8 é o nó 2. As profundidades dos nós
sãoprofundidade(5)=3,profundidade(8)=4 eprofundidade(2)=2, então a distância
entre os nós 5 e 8 é 3+4−2·2=3.
Algoritmos offline
Até agora, discutimoson-linealgoritmos para consultas de árvore. Esses algoritmos são capazes
de processar consultas uma após a outra, de modo que cada consulta seja respondida antes de
receber a próxima consulta.
No entanto, em muitos problemas, a propriedade online não é necessária. Nesta seção,
focamos emdesconectadoalgoritmos. Esses algoritmos recebem um conjunto de consultas que
podem ser respondidas em qualquer ordem. Geralmente é mais fácil projetar um algoritmo
offline em comparação a um algoritmo online.
2
1
32 53 43 51
6 7 8 9
4 4 3 1
Neste problema, podemos usar estruturas de mapa para responder às consultas. Por
exemplo, os mapas para o nó 4 e seus filhos são os seguintes:
1 3 4
1 2 1
4 3 1
1 1 1
170
Se criarmos tal estrutura de dados para cada nó, podemos processar facilmente todas as
consultas fornecidas, porque podemos manipular todas as consultas relacionadas a um nó
imediatamente após criar sua estrutura de dados. Por exemplo, a estrutura de mapa acima para
o nó 4 nos diz que sua subárvore contém dois nós cujo valor é 3.
No entanto, seria muito lento criar todas as estruturas de dados do zero. Em vez
disso, em cada nóe, criamos uma estrutura de dados iniciale[e] que contém apenas o
valor dee. Depois disso, passamos pelos filhos deeemesclare[e] e todas as estruturas de
dadose[você] ondevocêé filho dee.
Por exemplo, na árvore acima, o mapa para o nó 4 é criado pela fusão dos
seguintes mapas:
3 4 3 1
1 1 1 1
trocar(a,b);
171
Por exemplo, suponha que queremos encontrar os ancestrais comuns mais baixos dos
pares de nós (5, 8) e (2, 7) na seguinte árvore:
2 3 4
5 6 7
Nas árvores a seguir, nós cinzas denotam nós visitados e grupos tracejados de nós
pertencem ao mesmo conjunto. Quando o algoritmo visita o nó 8, ele percebe que o nó
5 foi visitado e o nó mais alto em seu conjunto é 2. Assim, o ancestral comum mais
baixo dos nós 5 e 8 é 2:
2 3 4
5 6 7
2 3 4
5 6 7
172
Capítulo 19
Caminhos e circuitos
• UmCaminho Eulerianoé um caminho que passa por cada aresta exatamente uma vez.
Caminhos Eulerianos
UmCaminho Euleriano1é um caminho que passa exatamente uma vez por cada aresta do
gráfico. Por exemplo, o gráfico
1 2
4 5
1.
1 2 5.
2. 4. 3
4 5 6.
3.
1L. Euler estudou tais caminhos em 1736 quando resolveu o famoso problema da ponte de Königsberg. Este foi o
nascimento da teoria dos grafos.
173
Umcircuito eulerianoé um caminho euleriano que começa e termina no mesmo nó.
Por exemplo, o gráfico
1 2
4 5
6.
1 2 5.
1. 3. 3
2.
4 5 4.
Existência
A existência de caminhos e circuitos eulerianos depende dos graus dos nós. Primeiro, um
grafo não direcionado tem um caminho euleriano exatamente quando todas as arestas
pertencem ao mesmo componente conectado e
• o grau de exatamente dois nós é ímpar, e o grau de todos os outros nós é par.
1 2
4 5
174
• em um nó, o grau de entrada é uma unidade maior que o grau de saída, em outro nó, o grau de
saída é uma unidade maior que o grau de entrada e em todos os outros nós, o grau de entrada
é igual ao grau de saída.
1 2
4 5
os nós 1, 3 e 4 têm tanto o grau de entrada 1 quanto o grau de saída 1, o nó 2 tem o grau de
entrada 1 e o grau de saída 2, e o nó 5 tem o grau de entrada 2 e o grau de saída 1. Portanto, o
gráfico contém um caminho euleriano do nó 2 ao nó 5:
5.
1 2 1.
4. 6. 3
4 5 2.
3.
Algoritmo de Hierholzer
Algoritmo de Hierholzer2é um método eficiente para construir um circuito Euleriano. O
algoritmo consiste em várias rodadas, cada uma das quais adiciona novas arestas ao
circuito. Claro, assumimos que o gráfico contém um circuito Euleriano; caso contrário, o
algoritmo de Hierholzer não consegue encontrá-lo.
Primeiro, o algoritmo constrói um circuito que contém algumas (não necessariamente todas)
das arestas do gráfico. Depois disso, o algoritmo estende o circuito passo a passo adicionando
subcircuitos a ele. O processo continua até que todas as arestas tenham sido adicionadas ao
circuito.
O algoritmo estende o circuito sempre encontrando um nóxque pertence ao
circuito, mas tem uma aresta de saída que não está incluída no circuito. O algoritmo
constrói um novo caminho a partir do nóxque contém apenas arestas que ainda não
estão no circuito. Mais cedo ou mais tarde, o caminho retornará ao nóx, que cria um
subcircuito.
Se o gráfico contiver apenas um caminho euleriano, ainda podemos usar o algoritmo
de Hierholzer para encontrá-lo adicionando uma aresta extra ao gráfico e removendo a
aresta após o circuito ter sido construído. Por exemplo, em um gráfico não direcionado,
adicionamos a aresta extra entre os dois nós de grau ímpar.
A seguir, veremos como o algoritmo de Hierholzer constrói um circuito euleriano para um
grafo não direcionado.
175
Exemplo
Vamos considerar o seguinte gráfico:
2 3 4
5 6 7
1
1.
3.
2.
2 3 4
5 6 7
1
1.
6.
5.
2 3 4
4.
2.
5 6 7
3.
1
1.
10.
9. 5.
2 3 4
2. 8. 4. 6.
5 6 7
3. 7.
176
Agora todas as arestas estão incluídas no circuito, então construímos com sucesso um
circuito euleriano.
Caminhos hamiltonianos
UMCaminho hamiltonianoé um caminho que visita cada nó do gráfico exatamente uma vez. Por
exemplo, o gráfico
1 2
4 5
1 2 4.
1. 3. 3
4 5
2.
1.
1 2 2.
5. 3
4 5 3.
4.
Existência
Nenhum método eficiente é conhecido para testar se um grafo contém um caminho hamiltoniano, e o
problema é NP-difícil. Ainda assim, em alguns casos especiais, podemos ter certeza de que um grafo
contém um caminho hamiltoniano.
Uma observação simples é que se o gráfico for completo, ou seja, houver uma aresta entre
todos os pares de nós, ele também contém um caminho hamiltoniano. Também foram obtidos
resultados mais fortes:
• Teorema de Ore:Se a soma dos graus de cada par de nós não adjacentes for pelo
menosnão, o gráfico contém um caminho hamiltoniano.
177
Uma propriedade comum nesses teoremas e outros resultados é que eles garantem a
existência de um caminho hamiltoniano se o gráfico tiverum grande númerode arestas.
Isso faz sentido, porque quanto mais arestas o gráfico contém, mais possibilidades há de
construir um caminho hamiltoniano.
Construção
Como não há uma maneira eficiente de verificar se um caminho hamiltoniano existe, fica claro
que também não há um método para construir o caminho de forma eficiente, porque, do
contrário, poderíamos apenas tentar construir o caminho e ver se ele existe.
Uma maneira simples de procurar um caminho hamiltoniano é usar um algoritmo de
retrocesso que percorre todas as maneiras possíveis de construir o caminho. A complexidade de
tempo de tal algoritmo é de pelo menosO(não!), porque existemnão! diferentes maneiras de
escolher a ordem denãonós.
Uma solução mais eficiente é baseada na programação dinâmica (ver Capítulo
10.5). A ideia é calcular valores de uma funçãopossível(S,x), ondeSé um
subconjunto de nós exé um dos nós. A função indica se existe um caminho
hamiltoniano que visita os nós deSe termina no nóx. É possível implementar esta
solução emO(2nãonão2) tempo.
Sequências de De Bruijn
1 01 1
00 1 0 11
0 1
0 10 0
178
Passeios de cavaleiros
1 4 11 16 25
12 17 2 5 10
3 20 7 24 15
18 13 22 9 6
21 8 19 14 23
Regra de Warnsdorf
Regra de Warnsdorfé uma heurística simples e eficaz para encontrar o passeio de um cavaleiro3.
Usando a regra, é possível construir um tour eficientemente mesmo em um tabuleiro grande. A
ideia é sempre mover o cavalo de modo que ele termine em uma casa onde o número de
movimentos possíveis seja opequenoquanto possível.
Por exemplo, na situação a seguir, há cinco casas possíveis para as quais o
cavalo pode se mover (casasum. . .e):
1 um
2
b e
c e
Nessa situação, a regra de Warnsdorf move o cavalo para a casaum, porque depois
dessa escolha, há apenas um único movimento possível. As outras escolhas moveriam
o cavalo para casas onde haveria três movimentos disponíveis.
3Esta heurística foi proposta no livro de Warnsdorf [69] em 1823. Existem também algoritmos polinomiais
para encontrar os passeios do cavaleiro [52], mas eles são mais complicados.
179
180
Capítulo 20
Fluxos e cortes
1 3 8 6
4 4 5 2
1
Fluxo máximo
Nofluxo máximoproblema, nossa tarefa é enviar o máximo de fluxo possível da
fonte para o coletor. O peso de cada aresta é uma capacidade que restringe o fluxo
que pode passar pela aresta. Em cada nó intermediário, o fluxo de entrada e saída
tem que ser igual.
Por exemplo, o tamanho máximo de um fluxo no gráfico de exemplo é 7. A imagem
a seguir mostra como podemos rotear o fluxo:
6/6
3/5 2 3 5/5
1 3/3 1/8 6
4/4 4 5 2/2
1/1
181
A notaçãovocê/osignifica que um fluxo devocêunidades são roteadas através de
uma aresta cuja capacidade éounidades. O tamanho do fluxo é 7, porque a fonte envia
3+4 unidades de vazão e o coletor recebe 5+2 unidades de fluxo. É fácil ver que esse
fluxo é máximo, porque a capacidade total das bordas que levam à pia é 7.
Corte mínimo
Nocorte mínimoproblema, nossa tarefa é remover um conjunto de arestas do
gráfico de modo que não haja caminho da fonte até o coletor após a remoção e o
peso total das arestas removidas seja mínimo.
O tamanho mínimo de um corte no gráfico de exemplo é 7. Basta remover as
arestas 2→3 e 4→5:
6
5 2 3 5
1 3 8 6
4 4 5 2
1
Algoritmo Ford–Fulkerson
OAlgoritmo Ford–Fulkerson[25] encontra o fluxo máximo em um gráfico. O
algoritmo começa com um fluxo vazio e, a cada passo, encontra um caminho da
fonte para o coletor que gera mais fluxo. Finalmente, quando o algoritmo não
pode mais aumentar o fluxo, o fluxo máximo foi encontrado.
O algoritmo usa uma representação especial do gráfico onde cada aresta
original tem uma aresta reversa em outra direção. O peso de cada aresta indica
quanto mais fluxo poderíamos rotear através dela. No início do algoritmo, o peso
de cada aresta original é igual à capacidade da aresta e o peso de cada aresta
reversa é zero.
182
A nova representação para o gráfico de exemplo é a seguinte:
6
2 3
5 0 5
0 0
1 3 0 0 8 6
4 2
0 1 0
4 5
0
Descrição do algoritmo
O algoritmo Ford–Fulkerson consiste em várias rodadas. Em cada rodada, o algoritmo
encontra um caminho da fonte para o coletor de modo que cada aresta no caminho tenha
um peso positivo. Se houver mais de um caminho possível disponível, podemos escolher
qualquer um deles.
Por exemplo, suponha que escolhemos o seguinte caminho:
6
2 3
5 0 5
0 0
1 3 0 0 8 6
4 2
0 1 0
4 5
0
4
2 3
3 2 5
2 0
1 3 0 2 6 6
4 0
0 1 2
4 5
0
A ideia é que aumentar o fluxo diminui a quantidade de fluxo que pode passar
pelas bordas no futuro. Por outro lado, é possível cancelar o fluxo mais tarde
usando as bordas reversas do gráfico se for descoberto que seria benéfico rotear o
fluxo de outra forma.
O algoritmo aumenta o fluxo enquanto houver um caminho da fonte para o coletor
através de arestas de peso positivo. No exemplo presente, nosso próximo caminho pode
ser o seguinte:
183
4
2 3
3 2 5
2 0
1 3 0 2 6 6
4 0
0 1 2
4 5
0
1
2 3
3 5 2
2 3
1 0 3 2 6 6
1 0
3 1 2
4 5
0
Ainda precisamos de mais duas rodadas antes de atingir o fluxo máximo. Por
exemplo, podemos escolher os caminhos 1→2→3→6 e 1→4→5→3→6. Ambos os
caminhos aumentam o fluxo em 1, e o gráfico final é o seguinte:
0
2 3
2 6 0
3 5
1 0 3 1 7 6
0 0
4 0 2
4 5
1
Não é mais possível aumentar o fluxo, porque não há caminho da fonte para o
coletor com pesos de aresta positivos. Portanto, o algoritmo termina e o fluxo
máximo é 7.
Encontrando caminhos
184
OAlgoritmo de Edmonds–Karp[18] escolhe cada caminho de modo que o número de
arestas no caminho seja o menor possível. Isso pode ser feito usando busca em largura em
vez de busca em profundidade para encontrar caminhos. Pode ser provado que isso
garante que o fluxo aumenta rapidamente, e a complexidade de tempo do algoritmo éO(eu
2não).
Oalgoritmo de escala[2] usa busca em profundidade para encontrar caminhos onde
cada peso de aresta é pelo menos um valor limite. Inicialmente, o valor limite é um número
grande, por exemplo, a soma de todos os pesos de aresta do gráfico. Sempre que um
caminho não pode ser encontrado, o valor limite é dividido por 2. A complexidade de tempo
do algoritmo éO(eu2registroc), ondecé o valor limite inicial.
Na prática, o algoritmo de escala é mais fácil de implementar, porque a busca em profundidade
pode ser usada para encontrar caminhos. Ambos os algoritmos são eficientes o suficiente para
problemas que normalmente aparecem em concursos de programação.
Cortes mínimos
Acontece que, uma vez que o algoritmo Ford–Fulkerson encontrou um fluxo máximo, ele
também determinou um corte mínimo. SejaUMseja o conjunto de nós que podem ser
alcançados a partir da fonte usando arestas de peso positivo. No gráfico de exemplo,UM
contém os nós 1, 2 e 4:
0
2 3
2 6 0
3 5
1 0 3 1 7 6
0 0
4 0 2
4 5
1
Agora, o corte mínimo consiste nas arestas do gráfico original que começam em
algum nó emUM, terminam em algum nó externoUM, e cuja capacidade é totalmente
utilizada no fluxo máximo. No gráfico acima, tais arestas são 2→3 e 4→5, que
correspondem ao corte mínimo 6+1=7.
Por que o fluxo produzido pelo algoritmo é máximo e por que o corte é mínimo? O
motivo é que um gráfico não pode conter um fluxo cujo tamanho seja maior que o peso de
qualquer corte do gráfico. Portanto, sempre que um fluxo e um corte são igualmente
grandes, eles são um fluxo máximo e um corte mínimo.
Consideremos qualquer corte do gráfico tal que a fonte pertença aUM, a pia
pertence aBe há algumas arestas entre os conjuntos:
UM B
185
O tamanho do corte é a soma das arestas que vão deUMparaB. Este é um limite
superior para o fluxo no gráfico, porque o fluxo tem que prosseguir deUMpara B.
Assim, o tamanho de um fluxo máximo é menor ou igual ao tamanho de qualquer
corte no gráfico.
Por outro lado, o algoritmo Ford-Fulkerson produz um fluxo cujo tamanho éexatamente
tão grande quanto o tamanho de um corte no gráfico. Assim, o fluxo tem que ser um fluxo
máximo e o corte tem que ser um corte mínimo.
Caminhos disjuntos
2 3
1 6
4 5
2 3
1 6
4 5
Caminhos nó-disjuntos
Consideremos agora outro problema: encontrar o número máximo decaminhos
nodososdisjuntosda fonte ao coletor. Neste problema, cada nó, exceto
186
para a fonte e o coletor, podem aparecer no máximo em um caminho. O número de
caminhos nodedisjoint pode ser menor que o número de caminhos edge-disjoint.
Por exemplo, no gráfico anterior, o número máximo de caminhos disjuntos entre
nós é 1:
2 3
1 6
4 5
2 2 3 3
1 6
4 4 5 5
2 2 3 3
1 6
4 4 5 5
Correspondências máximas
187
Encontrando correspondências máximas
Os nós de um grafo bipartido podem ser sempre divididos em dois grupos, de modo
que todas as arestas do grafo vão do grupo esquerdo para o grupo direito. Por
exemplo, no grafo bipartido a seguir, os grupos são {1, 2, 3, 4} e {5, 6, 7, 8}.
1 5
2 6
3 7
4 8
1 5
2 6
3 7
4 8
1 5
2 6
3 7
4 8
1 5
2 6
3 7
4 8
188
Teorema de Hall
Teorema de Hallpode ser usado para descobrir se um grafo bipartido tem uma
correspondência que contém todos os nós esquerdos ou direitos. Se o número de nós
esquerdos e direitos for o mesmo, o teorema de Hall nos diz se é possível construir um
combinação perfeita que contém todos os nós do gráfico.
Suponha que queremos encontrar uma correspondência que contenha todos os nós esquerdos. DeixeX
seja qualquer conjunto de nós esquerdos e deixee(X) seja o conjunto de seus vizinhos. De acordo com o
teorema de Hall, uma correspondência que contém todos os nós esquerdos existe exatamente quando para
cadaX,a condição|X|≤ |e(X)|segura.
Vamos estudar o teorema de Hall no gráfico de exemplo. Primeiro, vamosX ={1, 3} que
produze(X)={5, 6, 8}:
1 5
2 6
3 7
4 8
1 5
2 6
3 7
4 8
Nesse caso,|X| =2 e|e(X)| =1, então a condição do teorema de Hall não se mantém.
Isso significa que não é possível formar uma correspondência perfeita para o gráfico.
Esse resultado não é surpreendente, porque já sabemos que a correspondência
máxima do gráfico é 3 e não 4.
Se a condição do teorema de Hall não for válida, o conjuntoXfornece uma
explicaçãopor quenão podemos formar tal correspondência. DesdeXcontém mais nós
do que e(X), não há pares para todos os nós [Link] exemplo, no gráfico acima, os nós
2 e 4 devem estar conectados ao nó 7, o que não é possível.
Teorema de Kőnig
UMcobertura mínima de nóde um grafo é um conjunto mínimo de nós tal que cada aresta do
grafo tem pelo menos um ponto final no conjunto. Em um grafo geral, encontrar uma cobertura
mínima de nós é um problema NP-difícil. No entanto, se o grafo for bipartido, Teorema de Kőnig
nos diz que o tamanho de uma cobertura de nó mínima e o tamanho
189
de uma correspondência máxima são sempre iguais. Assim, podemos calcular o tamanho de uma
cobertura de nó mínima usando um algoritmo de fluxo máximo.
Vamos considerar o seguinte gráfico com uma correspondência máxima de tamanho 3:
1 5
2 6
3 7
4 8
Agora, o teorema de Kőnig nos diz que o tamanho de uma cobertura mínima de nós também é 3. Tal
cobertura pode ser construída da seguinte forma:
1 5
2 6
3 7
4 8
1 5
2 6
3 7
4 8
Caminhos de cobertura
190
Traduzido do Inglês para o Português - [Link]
1 2 3 4
5 6 7
Uma cobertura mínima de caminho nó-disjunto deste grafo consiste em três caminhos. Por
exemplo, podemos escolher os seguintes caminhos:
1 2 3 4
5 6 7
Observe que um dos caminhos contém apenas o nó 2, então é possível que um caminho não
contenha nenhuma aresta.
Podemos encontrar uma cobertura mínima de caminho nó-disjunto construindo um
gráfico de correspondênciaonde cada nó do gráfico original é representado por dois nós:
um nó esquerdo e um nó direito. Há uma aresta de um nó esquerdo para um nó direito se
houver tal aresta no gráfico original. Além disso, o gráfico correspondente contém uma
fonte e um coletor, e há arestas da fonte para todos os nós esquerdos e de todos os nós
direitos para o coletor.
Uma correspondência máxima no gráfico resultante corresponde a uma cobertura de
caminho mínima nodedisjoint no gráfico original. Por exemplo, o seguinte gráfico de
correspondência para o gráfico acima contém uma correspondência máxima de tamanho 4:
1 1
2 2
3 3
4 4
5 5
6 6
7 7
191
Cobertura de caminho geral
UMcobertura de caminho geralé uma cobertura de caminho onde um nó pode pertencer a mais de
um caminho. Uma cobertura de caminho geral mínima pode ser menor do que uma cobertura de
caminho nó-disjunto mínima, porque um nó pode ser usado várias vezes em caminhos. Considere
novamente o seguinte gráfico:
1 2 3 4
5 6 7
A cobertura mínima do caminho geral deste grafo consiste em dois caminhos. Por exemplo,
o primeiro caminho pode ser o seguinte:
1 2 3 4
5 6 7
1 2 3 4
5 6 7
Uma cobertura de caminho geral mínima pode ser encontrada quase como uma cobertura de
caminho mínima de nós disjuntos. É suficiente adicionar algumas novas arestas ao gráfico
correspondente para que haja uma arestaum→bsempre quando há um caminho deumparabno gráfico
original (possivelmente através de várias arestas).
O gráfico correspondente ao gráfico acima é o seguinte:
1 1
2 2
3 3
4 4
5 5
6 6
7 7
192
Teorema de Dilworth
Umanticadeiaé um conjunto de nós de um grafo tal que não há caminho de nenhum nó
para outro nó usando as arestas do [Link] de Dilworthafirma que em um grafo
acíclico direcionado, o tamanho de uma cobertura de caminho geral mínima é igual ao
tamanho de uma anticadeia máxima.
Por exemplo, os nós 3 e 7 formam uma anticadeia no gráfico a seguir:
1 2 3 4
5 6 7
193
194
Parte III
Tópicos avançados
195
Capítulo 21
Teoria dos númerosé um ramo da matemática que estuda números inteiros. A teoria dos números é
um campo fascinante, porque muitas questões envolvendo números inteiros são muito difíceis de
resolver, mesmo que pareçam simples à primeira vista.
Como exemplo, considere a seguinte equação:
x3+e3+por3=33
Primos e fatores
Um númeroumé chamado defatorou umdivisorde um númerobseumdivideb. Seumé um
fator deb, nós escrevemosum | b, e caso contrário escrevemosum-b. Por exemplo, os
fatores de 24 são 1, 2, 3, 4, 6, 8, 12 e 24.
Um númeron >1 é ummelhorse seus únicos fatores positivos forem 1 enão. Por exemplo,
7, 19 e 41 são primos, mas 35 não é primo, porque 5·7=35. Para cada número n >1,
há um únicofatoração prima
n = pum11pum22 · · · pum
o
o,
84=22·31·71.
197
Onúmero de fatoresde um númeronãoé
∏o
τ(não)= (umeu+1),
eu=1
porque para cada primopeu, háumeu+1 maneiras de escolher quantas vezes ele
aparece no fator. Por exemplo, o número de fatores de 84 éτ(84)=3·2·2=12. Os
fatores são 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42 e 84.
Osoma de fatoresdenãoé
∏o ∏o pum
eueu+1−1
σ(não)= (1+peu+. . .+pum eueu)= ,
eu=1 eu=1 peu−1
µ(não)=nãoτ(não)/2,
Número de primos
É fácil mostrar que existe um número infinito de primos. Se o número de primos fosse
finito, poderíamos construir um conjuntoP ={p1,p2, . . . ,pnão} que conteria todos os
primos. Por exemplo,p1=2,p2=3,p3=5, e assim por diante. No entanto, usandoP,
poderíamos formar um novo primo
p1p2···pnão+1
que é maior do que todos os elementos emP. Isso é uma contradição, e o número de
primos tem que ser infinito.
Densidade de primos
A densidade de primos significa a frequência com que há primos entre os números.
Deixeπ(não) denotam o número de primos entre 1 enão. Por exemplo,π(10)=4,
porque há 4 números primos entre 1 e 10: 2, 3, 5 e 7.
É possível mostrar que
não
π(não)≈ ,
emnão
o que significa que os primos são bastante frequentes. Por exemplo, o número de
primos entre 1 e 106éπ(106)=78498 e 106/ em 106≈72382.
198
Conjecturas
Existem muitosconjecturasenvolvendo primos. A maioria das pessoas pensa que as
conjecturas são verdadeiras, mas ninguém conseguiu prová-las. Por exemplo, as
seguintes conjecturas são famosas:
• Conjectura de Goldbach: Cada inteiro parn >2 pode ser representado como uma
soman = a+ bpara que ambosumebsão primos.
Algoritmos básicos
p
Se um númeronãonão é primo, pode ser representado como um produtoum·b, ondeum≤ não
p p
oub≤não, então certamente tem um fator entre 2 ebnãoc. Usando esta observação,
podemos testar se um número é primo e encontrar a fatoração prima de um número
p
emO(não) tempo.
A seguinte funçãomelhorverifica se o número fornecidonãoé primo. O
p
função tenta dividirnãopor todos os números entre 2 ebnãoc, e se nenhum deles se
dividirnão, entãonãoé primo.
boolmelhor(Inteiron) {
se(n < 2)retornar falso; para(Inteiro
x = 2; x*x <= n; x++) {
se(n%x == 0)retornar falso;
}
retornar verdadeiro;
vetor<Inteiro> fatores(Inteiron) {
vetor<Inteiro> f;
para(Inteirox = 2; x*x <= n; x++) {
enquanto(n%x == 0) {
f.push_back(x);
n /= x;
}
}
se(n > 1) f.push_back(n);
retornare;
}
199
Note que cada fator primo aparece no vetor tantas vezes quantas divide o
número. Por exemplo, 24=23·3, então o resultado da função é [2, 2, 2, 3].
Crivo de Eratóstenes
Openeira de Eratóstenesé um algoritmo de pré-processamento que constrói uma matriz com a
qual podemos verificar eficientemente se um determinado número entre 2. . .nãoé primo e, se
não for, encontre um fator primo do número.
O algoritmo constrói uma matrizpeneiracujas posições 2, 3, . . . ,nãosão usados. O
valorpeneira[o]=0 significa queoé primo, e o valorpeneira[o]6=0 significa que onão é
primo e um dos seus fatores primos épeneira[o].
O algoritmo itera pelos números 2 . . .nãoum por um. Sempre quando um novo
primoxé encontrado, o algoritmo registra que os múltiplos dex(2x, 3x, 4x, . . .) não
são primos, porque o númeroxos divide.
Por exemplo, sen =20, a matriz é a seguinte:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 0 2 0 3 0 2 3 5 0 3 0 7 5 2 0 3 0 5
Na verdade, o algoritmo é mais eficiente, porque o loop interno será executado somente se
o númeroxé primo. Pode-se mostrar que o tempo de execução do algoritmo é apenasO(não
registro de lognão), uma complexidade muito próxima deO(não).
Algoritmo de Euclides
Omáximo divisor comumde númerosumeb, mdc(um,b), é o maior número que
divide ambosumeb, e omínimo múltiplo comumdeumeb, mcm(um,b), é o menor
número que é divisível por ambosumeb. Por exemplo, mdc(24, 36)=12 e mmc(24,
36)=72.
O máximo divisor comum e o mínimo múltiplo comum são conectados como
segue:
sobre
mcm(um,b)=
mdc(um,b)
200
Algoritmo de Euclides1fornece uma maneira eficiente de encontrar o maior valor comum
divisor de dois números. O algoritmo é baseado na seguinte fórmula:
{
um b =0
mdc(um,b)=
mdc(b,ummodb) b6=0
Por exemplo,
Inteiromdc(Inteiroum,Inteirob) {
se(b == 0)retornarum;
retornarmdc(b, a%b);
}
Aritmética modular
Emaritmética modular, o conjunto de números é limitado de modo que apenas os
números 0, 1, 2, . . . ,m-1 são usados, ondeeué uma constante. Cada númeroxé
representado pelo númeroxmodeu: o resto após a divisãoxporeu. Por exemplo, se m =
17, então 75 é representado por 75 mod 17=7.
Frequentemente podemos pegar restos antes de fazer cálculos. Em particular, as seguintes
fórmulas são válidas:
201
Exponenciação modular
Muitas vezes é necessário calcular de forma eficiente o valor dexnãomodeu. Isso pode ser feito
emO(registronão) tempo usando a seguinte recursão:
-
--1 n =0
xnão/2·xnão/2
xnão= nãoé par
--
-xn−1·x nãoé estranho
Inteiromodpow(Inteirox,Inteiron,Inteirom) {
se(n == 0)retornar1%m; longo
longou = modpow(x,n/2,m); u =
(u*u)%m;
se(n%2 == 1) u = (u*x)%m;
retornarvocê;
}
xm-1modm =1
xϕ(eu)modm =1
Inverso modular
O inverso dexmóduloeué um númerox−1tal que
xx−1modm =1.
202
de 36/6 mod 17, podemos usar a fórmula 2·3 mod 17, porque 36 mod 17=2 e 6−1
mod 17=3.
No entanto, um inverso modular nem sempre existe. Por exemplo, sex =2 e m =
4, a equação
xx−1modm =1
não pode ser resolvido, porque todos os múltiplos de 2 são pares e o resto nunca pode
ser 1 quandom =4. Acontece que o valor dex−1modeupode ser calculado exatamente
quandoxeeusão coprimos.
Se existir um inverso modular, ele pode ser calculado usando a fórmula
x−1=xϕ(eu)−1.
x−1=xm-2.
Por exemplo,
6−1mod 17=617−2mod 17=3.
xx−1modm =1.
Aritmética de computador
Na programação, inteiros sem sinal são representados módulo 2o, ondeoé o número
de bits do tipo de dado. Uma consequência comum disso é que um número se enrola
se ele se torna muito grande.
Por exemplo, em C++, números do tipoint sem sinalsão representados módulo
232. O código a seguir declara umint sem sinalvariável cujo valor é 123456789.
Depois disso, o valor será multiplicado por ele mesmo, e o resultado é 1234567892
mod 232=2537071545.
203
Resolvendo equações
Equações diofantinas
UMEquação diofantinaé uma equação da forma
ax+ por = c,
Uma equação diofantina pode ser resolvida secé divisível por mdc(um,b), caso contrário não
poderá ser resolvido.
Como exemplo, vamos encontrar númerosxeeque satisfaçam a seguinte equação:
39x+15e =12
A equação pode ser resolvida, porque mdc(39, 15)=3 e 3|12. Quando o algoritmo
de Euclides calcula o máximo divisor comum de 39 e 15, ele produz a seguinte
sequência de chamadas de função:
39−2·15 = 9
15−1·9 = 6
9−1·6 = 3
39·2+15·(−5)=3
39·8+15·(−20)=12,
204
Teorema do resto chinês
OTeorema do resto chinêsresolve um grupo de equações da forma
x = um1modeu1
x = um2modeu2
···
x = umnãomodeunão
−1 −1
x = um1X1X1 eu1+ um2 X 2X2eu+·
2
+· · um
nãoXX−1
nm . não
−1
umoXoXquilômetros modeuo= umo,
o
porque
−1
XoX quilômetroso
modeuo=1.
Como todos os outros termos da soma são divisíveis poreuo, não têm efeito sobre
o restante, exmodeuo= umo.
Por exemplo, uma solução para
x = 3 mod 5
x = 4 mod 7
x = 2 mod 3
é
3·21·1+4·15·1+2·35·2=263.
Uma vez que encontramos uma soluçãox, podemos criar um número infinito de outras
soluções, porque todos os números da forma
x+m1eu2···eunão
são soluções.
Outros resultados
Teorema de Lagrange
Teorema de Lagrangeafirma que todo número inteiro positivo pode ser representado como
uma soma de quatro quadrados, ou seja,um2+b2+c2+e2. Por exemplo, o número 123 pode ser
representado como a soma 82+52+52+32.
205
Teorema de Zeckendorf
Teorema de Zeckendorfafirma que todo inteiro positivo tem uma representação única
como uma soma de números de Fibonacci, de modo que nenhum número é igual ou
consecutivo a números de Fibonacci. Por exemplo, o número 74 pode ser representado
como a soma 55+13+5+1.
Triplos pitagóricos
UMtriplo pitagóricoé um triplo (um,b,c) que satisfaz o teorema de Pitágoras um2+b2=c2, o
que significa que existe um triângulo retângulo com lados de comprimentoum,be c. Por
exemplo, (3, 4, 5) é uma tripla pitagórica.
Se (um,b,c) é um triplo pitagórico, todos os triplos da forma (ok,KB-KB ...,kc) também
são triplos pitagóricos ondek >1. Um triplo pitagórico éprimitivoseum,be csão coprimos, e
todos os triplos pitagóricos podem ser construídos a partir de triplos primitivos usando um
multiplicadoro.
Fórmula de Euclidespode ser usado para produzir todos os triplos pitagóricos primitivos.
Cada um desses triplos é da forma
(não2−eu2, 2nm,não2+eu2),
onde 0<m < n,nãoeeusão coprimos e pelo menos um denãoeeué par. Por exemplo,
quandom =1 en =2, a fórmula produz o menor triplo pitagórico
Teorema de Wilson
Teorema de Wilsonafirma que um númeronãoé primo exatamente quando
Portanto, o teorema de Wilson pode ser usado para descobrir se um número é primo.
No entanto, na prática, o teorema não pode ser aplicado a grandes valores denão, porque é
difícil calcular valores de (n−1)! quandonãoé grande.
206
Capítulo 22
Combinatória
• 1+1+1+1 • 2+2
• 1+1+2 • 3+1
• 1+2+1 • 1+3
• 2+1+1 •4
207
que se baseia no fato de que existemn−1 posições possíveis para sinais + na soma e
podemos escolher qualquer subconjunto deles.
Coeficientes binomiais
(não)
Ocoeficiente binomialoé igual ao número de maneiras pelas quais podemos escolher um subconjunto
(5)
deoelementos de um conjunto denãoelementos. Por exemplo,3=10, porque o conjunto {1, 2, 3, 4,
5} tem 10 subconjuntos de 3 elementos:
{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2 , 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}
Fórmula 1
Os coeficientes binomiais podem ser calculados recursivamente da seguinte forma:
()( )( )
não n−1 n−1
= +
o k−1 o
A ideia é consertar um elementoxno conjunto. Sexestá incluído no subconjunto,
temos que escolherk−1 elementos den−1 elementos, e sexnão está incluído no
subconjunto, temos que escolheroelementos den−1 elementos.
Os casos base para a recursão são
()()
não
= =1,
0 não
Fórmula 2
Outra maneira de calcular coeficientes binomiais é a seguinte:
()
não não!
= .
o o!(n−k)!
Propriedades
208
porque na verdade dividimos um conjunto denãoelementos em dois subconjuntos: o primeiro
contém oelementos e o segundo contémn−kelementos.
A soma dos coeficientes binomiais é
()()() ()
nnn não
+++ . . . + =2não.
012 não
A razão do nome “coeficiente binomial” pode ser vista quando o binômio (um +
b) é elevado aonãoª potência:
() () ( ) ()
não não não um1bn−1+ não
(um + b)não= umnãob0+ umn−1b1+. . .+ um0bnão.
0 1 n−1 não
Os coeficientes binomiais também aparecem emTriângulo de Pascalonde cada valor é
igual à soma dos dois valores acima:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...............
Caixas e bolas
“Caixas e bolas” é um modelo útil, onde contamos as maneiras de colocarobolas dentronão
caixas. Vamos considerar três cenários:
Cenário 1: Cada caixa pode conter no máximo uma bola. Por exemplo, quandon =5
ek =2, existem 10 soluções:
(
Neste cenário, a resposta é diretamente o coeficiente binomialnão) o.
Cenário 2: Uma caixa pode conter várias bolas. Por exemplo, quandon =5 e k =
2, existem 15 soluções:
209
O processo de colocação das bolas nas caixas pode ser representado como uma
sequência que consiste nos símbolos “o” e “→”. Inicialmente, suponha que estamos na
caixa mais à esquerda. O símbolo ”o” significa que colocamos uma bola na caixa atual, e
o símbolo ”→" significa que passamos para a próxima caixa à direita.
Usando esta notação, cada solução é uma string que contémovezes o símbolo
“o” en−1 vezes o símbolo ”→”. Por exemplo, a solução superior direita na imagem
acima corresponde à string ”→ →o→o→”. Assim, o número de
soluções ék+n−1)o .
Cenário 3: Cada caixa pode conter no máximo uma bola e, além disso,
nenhuma caixa adjacente pode conter uma bola. Por exemplo, quandon =5 ek =2,
existem 6 soluções:
n−2k+1.
Coeficientes multinomiais
Ocoeficiente multinomial
( )
não não!
= ,
o1,o2, . . . ,oeu o1!o2!···oeu!
Números catalães
ONúmero catalãoCnãoé igual ao número de expressões entre parênteses válidas que
consistem emnãoparênteses esquerdos enãoparênteses direitos.
Por exemplo,C3=5, porque podemos construir as seguintes expressões entre
parênteses usando três parênteses esquerdo e direito:
• ()()()
• (())()
• ()(())
• ((()))
• (()())
210
Expressões entre parênteses
O que é exatamente umexpressão entre parênteses válida? As regras a seguir definem precisamente
todas as expressões de parênteses válidas:
Fórmula 1
Os números catalães podem ser calculados usando a fórmula
− 1∑
não
Cnão= CeuCn−eu−1.
eu=0
A soma passa pelas maneiras de dividir a expressão em duas partes, de modo que
ambas as partes sejam expressões válidas e a primeira parte seja a mais curta possível,
mas não vazia. Para qualquereu, a primeira parte contémeu +1 par de parênteses e o
número de expressões é o produto dos seguintes valores:
Fórmula 2
Os números catalães também podem ser calculados usando coeficientes binomiais:
()
1 2não
Cnão=
n+1 não
211
A ideia é inverter cada parêntesis que pertence a tal prefixo. Por exemplo, a
expressão ())()( contém um prefixo ()), e após inverter o prefixo, a expressão se
torna )((()(.
A expressão
O número resultante
de tais é2não) emn +1 parênteses en −1 parênteses à direita.
consiste
expressões
n+1 , que eq vocêtambémpara
ele n você
membro
Contando árvores
Os números catalães também estão relacionados às árvores:
Inclusão-exclusão
Inclusão-exclusãoé uma técnica que pode ser usada para contar o tamanho de uma
união de conjuntos quando os tamanhos das interseções são conhecidos, e vice-versa.
Um exemplo simples da técnica é a fórmula
|Um∪B| = |A|+|B|−|A∩B|,
UM UM∩B B
212
Nosso objetivo é calcular o tamanho da uniãoUM∪Bque corresponde à área da
região que pertence a pelo menos um círculo. A figura mostra que podemos
calcular a área deUM∪Bsomando primeiro as áreas deUMeBe então subtraindo a
área deUM∩B.
A mesma ideia pode ser aplicada quando o número de conjuntos é maior. Quando há
três conjuntos, a fórmula de inclusão-exclusão é
|Um∪B∪C| = |A|+|B|+|C|−|A∩B|-|Um∩C|-|B∩C|+|A∩B∩C|
e a imagem correspondente é
UM∩C B∩C
UM∩B∩C
UM B
UM∩B
|Um∩B| = |A|+|B|−|A∪B|
|Um∩B∩C| = |A|+|B|+|C|−|A∪B|-|Um∪C|-|B∪C|+|A∪B∪C|.
Perturbações
Como exemplo, vamos contar o número deperturbaçõesde elementos {1, 2, . . . ,não}, ou
seja, permutações onde nenhum elemento permanece em seu lugar original. Por exemplo,
quandon =3, há duas perturbações: (2, 3, 1) e (3, 1, 2).
Uma abordagem para resolver o problema é usar inclusão-exclusão. DeixeXoseja o
conjunto de permutações que contém o elementoona posiçãoo. Por exemplo, quandon =3,
os conjuntos são os seguintes:
não!−|X1∪X2∪···∪Xnão|,
213
então é suficiente calcular o tamanho da união. Usando inclusão-exclusão, isso se reduz ao
cálculo de tamanhos de interseções que podem ser feitos de forma eficiente. Por exemplo,
quandon =3, o tamanho de|X1∪X2∪X3|é
|X1|+|X2|+|X3|-|X1∩X2|-|X1∩X3|-|X2∩X3|+|X1∩X2∩X3| 2+2+2−1−1−
= 1+1 4,
=
Lema de Burnside
Lema de Burnsidepode ser usado para contar o número de combinações de modo que
apenas um representante seja contado para cada grupo de combinações simétricas. O
lema de Burnside afirma que o número de combinações é
∑nãoc(o)
,
k=1 não
214
Hánãomaneiras de mudar a posição de um colar, porque podemos girá-lo 0, 1, . . . ,n−1
passo no sentido horário. Se o número de passos for 0, todoseunãoos colares permanecem
os mesmos, e se o número de passos for 1, apenas oeucolares onde cada pérola tem a
mesma cor permanecem os mesmos.
De forma mais geral, quando o número de etapas éo, um total de
eumdc(o,não)
os colares permanecem os mesmos, onde mdc(o,não) é o máximo divisor comum deo enão.
A razão para isso é que blocos de pérolas de tamanho mdc(o,não) irão substituir-se
mutuamente. Assim, de acordo com o lema de Burnside, o número de colares é
∑mdc(eu,não)
− 1eu
não
.
eu=0 não
34+3+32+3
=24.
4
Fórmula de Cayley
1 2 3 4
2 3 4 1 3 4 1 2 4 1 2 3
1 2 3 4 1 2 4 3 1 3 2 4
1 3 4 2 1 4 2 3 1 4 3 2
2 1 3 4 2 1 4 3 2 3 1 4
2 4 1 3 3 1 2 4 3 2 1 4
A seguir, veremos como a fórmula de Cayley pode ser derivada usando códigos de Prüfer.
215
Código Prüfer
UMCódigo Prüferé uma sequência den−2 números que descrevem uma árvore
rotulada. O código é construído seguindo um processo que removen−2 folhas da
árvore. A cada passo, a folha com o menor rótulo é removida, e o rótulo de seu único
vizinho é adicionado ao código.
Por exemplo, vamos calcular o código de Prüfer do seguinte gráfico:
1 2
3 4
3 4
216
Capítulo 23
Matrizes
Operações
A somaUm + Bde matrizesUMeBé definido se as matrizes são do mesmo tamanho.
O resultado é uma matriz onde cada elemento é a soma dos elementos
correspondentes emUMeB.
217
Por exemplo,
[ ] [ ] [ ] [ ]
6 1 4 4 9 3 6+4 1+9 4+3 10 10 7
+ = = .
3 9 2 8 1 3 3+8 9+1 2+3 11 10 5
Multiplicação de matrizes
O produtoSobrede matrizesUMeBé definido seUMé de tamanhoum×nãoeBé de tamanho
não×b, ou seja, a largura deUMé igual a altura deB. O resultado é uma matriz de tamanho
um×bcujos elementos são calculados usando a fórmula
∑não
Sobre[eu,eu]= UM[eu,o]·B[o,eu].
k=1
UM Sobre
Por exemplo,
- - - - - -
1 4 [ ] 1·1+4·2 1·6+4·9 9 42
1 6
-3 9-· =-3·1+9·2 3·6+9·9-=-21 8·6+ 99 -.
2 9
8 6 8·1+6·2 6·9 20 102
A multiplicação de matrizes é associativa, entãoUM(AC)=(Sobre)Cé válido, mas não é
comutativo, entãoAB = BAgeralmente não se sustenta.
Ummatriz identidadeé uma matriz quadrada onde cada elemento na diagonal
é 1 e todos os outros elementos são 0. Por exemplo, a matriz a seguir é a 3×3
matriz identidade:
- -
1 0 0
Eu =-0 1 0-
0 0 1
218
Multiplicar uma matriz por uma matriz identidade não a altera. Por exemplo,
- -- -- - - - - -
1 0 0 1 4 1 4 1 4 [ ] 1 4
10
-0 1 0-·-3 9-=-3 9- e - 0 0 1 8 6 8 6 3 9-· =-3 9-.
01
8 6 8 6
Poder da matriz
︷···UM︸
UMo=︸UM·UM·︷UM
ovezes
Por exemplo,
[ ] [ ][ ][ ] [ ]
2 53 2 5 2 5 2 5 48 165
= · · = .
1 4 1 4 1 4 1 4 33 114
Além disso,UM0é uma matriz identidade. Por exemplo,
[ ] [ ]
2 50 1 0
= .
1 4 0 1
Determinante
Odeterminantedet(UM) de uma matrizUMé definido seUMé uma matriz quadrada. Se UMé
do tamanho 1×1, então det(UM)=UM[1, 1]. O determinante de uma matriz maior é
calculado recursivamente usando a fórmula
∑não
det(UM)= UM[1,eu]C[1,eu],
j=1
C[eu,eu]=(−1)eu+jdet(M[eu,eu]),
1O primeiro algoritmo deste tipo foi o algoritmo de Strassen, publicado em 1969 [63], cuja complexidade
temporal éO(não2.80735); o melhor algoritmo atual [27] funciona emO(não2.37286) tempo.
219
ondeM[eu,eu] é obtido removendo a linhaeue colunaeudeUM. Devido ao
coeficiente (−1)eu+jno cofator, todos os outros determinantes são positivos e
negativos. Por exemplo,
[ ]
3 4
det( ) =3·6−4·1=14
1 6
e
- -
2 4 3 [ ] [ ] [ ]
1 6 5 6 5 1
det(-5 1 6-)=2·det( ) − 4·det( ) + 3·det( ) =81.
2 4 7 4 7 2
7 2 4
UM−[eu
1
,eu]=
C[eu,eu]
.
det(UM)
Por exemplo,
- - - - - -
2 4 3 − 8 − 10 21 1 0 0
-5 1 6- 1 · -22 − 13 3 -=-0 1 0-.
81
724 3 24 − 18 0 0 1
︸ ︷︷ ︸ ︸ ︷︷ ︸ ︸ ︷︷ ︸
UM UM−1 EU
Recorrências lineares
e(não)=c1e(n−1)+c2e(n−2)+. . .+coe(n−k),
Números de Fibonacci
220
Para calcular eficientemente os números de Fibonacci, representamos a fórmula de Fibonacci
como uma matriz quadradaXde tamanho 2×2, para o qual se aplica o seguinte:
[ ][ ]
e(eu) e(eu +1)
X· =
e(eu +1) e(eu +2)
Assim, os valorese(eu) ee(eu +1) são fornecidos como “entrada” paraX,eXcalcula valores
e(eu +1) ee(eu +2) a partir deles. Acontece que tal matriz é
[ ]
0 1
X= .
1 1
Por exemplo,
[ ][ ][ ][][][ ]
0 1 e(5) 0 1 5 8 e(6)
· = ·= = .
1 1 e(6) 1 1 8 13 e(7)
Assim, podemos calculare(não) usando a fórmula
[ ] [] [ ] não[ ]
e(não) e(0) 0 1 0
=Xnão· = · .
e(n+1) e(1) 1 1 1
O valor deXnãopode ser calculado emO(registronão) tempo, então o valor dee(não) também pode ser
calculado emO(registronão) tempo.
Caso geral
Consideremos agora o caso geral em quee(não) é qualquer recorrência linear. Novamente, nosso
objetivo é construir uma matrizXpara qual
- - - -
e(eu) e(eu +1)
- e(eu +1) - -e(eu +2)-
- - - -
X·- .. -=- . . -.
- . - - . -
e(eu + k−1) e(eu + k)
Tal matriz é - -
01 0 0 ··· 0
- 0 1 0 0 --
-0 ···
- -
-0 0 0 1 ··· 0-
X =- - . . .. --.
- .. .. ...
.. .. .. .-
- -
-0 0 0 0 ··· 1-
cock−1 ck−2 ck−3 ···c1
No primeirok−1 linhas, cada elemento é 0, exceto que um elemento é 1. Essas linhas
substitueme(eu) come(eu +1),e(eu +1) come(eu +2), e assim por diante. A última linha
contém os coeficientes da recorrência para calcular o novo valore(eu + k).
Agora,e(não) pode ser calculado emO(o3registronão) tempo usando a fórmula
- - - -
e(não) e(0)
- e(n+1) - - e(1) -
- - - -
- -=Xnão · - .. -.
- ... - - . -
e(n+ k−1) e(k−1)
221
Gráficos e matrizes
Contando caminhos
1 2 3
4 5 6
a matriz de adjacência é
- -
000100
--1 0 0 0 1 1-
-
-
-0 1 0 0 0 0- -
V =- -.
-0 1 0 0 0 0-
- -
-0 0 0 0 0 0-
001010
- -
001110
--2 0 0 0 2 2-
-
- -
=-2 0 0 0 0-
V4 -0 -
-0 2 0 0 0 0-
- -
-0 0 0 0 0 0-
001110
contém o número de caminhos de 4 arestas entre os nós. Por exemplo, V4[2, 5]=2,
porque existem dois caminhos de 4 arestas do nó 2 ao nó 5: 2→1→4→2→5 e 2→6→3
→2→5.
Usando uma ideia semelhante em um gráfico ponderado, podemos calcular para cada par de nós o
comprimento mínimo de um caminho entre eles que contém exatamentenãoarestas. Para calcular
isso, temos que definir a multiplicação de matrizes de uma nova maneira, para que não calculemos os
números de caminhos, mas minimizemos os comprimentos dos caminhos.
222
Como exemplo, considere o seguinte gráfico:
2 4
1 2 3
4 1 1 2 3
4 5 6
2
Vamos construir uma matriz de adjacência onde∞significa que uma aresta não
existem, e outros valores correspondem aos pesos das arestas. A matriz é
- -
∞ ∞ ∞4∞ ∞
--2∞ ∞ ∞1 2 -
-
- -
-∞4∞ ∞ ∞ ∞-
V =- -.
-∞1∞ ∞ ∞ ∞-
- -
-∞ ∞ ∞ ∞ ∞ ∞-
∞ ∞3∞2∞
Em vez da fórmula
∑não
Sobre[eu,eu]= UM[eu,o]·B[o,eu]
k=1
agora usamos a fórmula
não
Sobre[eu,eu]=mínimoUM[eu,o]+B[o,eu]
k=1
para multiplicação de matrizes, então calculamos um mínimo em vez de uma soma, e uma soma
de elementos em vez de um produto. Após essa modificação, as potências de matrizes
correspondem aos caminhos mais curtos no gráfico.
Por exemplo, como - -
∞ ∞10 11 9∞
--9∞ ∞ ∞8 9 --
- -
-∞11∞ ∞ ∞ ∞-
V4=- -,
-∞8∞ ∞ ∞ ∞-
- -
-∞ ∞ ∞ ∞ ∞ ∞-
∞ ∞12 13 11∞
podemos concluir que o comprimento mínimo de um caminho de 4 arestas do nó
2 ao nó 5 é 8. Esse caminho é 2→1→4→2→5.
Teorema de Kirchhoff
Teorema de Kirchhofffornece uma maneira de calcular o número de árvores de abrangência de um
gráfico como um determinante de uma matriz especial. Por exemplo, o gráfico
1 2
3 4
223
tem três árvores de abrangência:
1 2 1 2 1 2
3 4 3 4 3 4
224
Capítulo 24
Probabilidade
Cálculo
Para calcular a probabilidade de um evento, podemos usar combinatória ou
simular o processo que gera o evento. Como exemplo, vamos calcular a
probabilidade de tirar três cartas com o mesmo valor de um baralho de cartas
embaralhado (por exemplo,♠8,♣8 e♦8).
Método 1
Podemos calcular a probabilidade usando a fórmula
225
Método 2
Outra maneira de calcular a probabilidade é simular o processo que gera o evento.
Neste exemplo, tiramos três cartas, então o processo consiste em três etapas.
Exigimos que cada etapa do processo seja bem-sucedida.
Tirar a primeira carta certamente dá certo, porque não há restrições. O
segundo passo dá certo com probabilidade 3/51, porque há 51 cartas restantes e 3
delas têm o mesmo valor que a primeira carta. De forma similar, o terceiro passo
dá certo com probabilidade 2/50.
A probabilidade de que todo o processo seja bem-sucedido é
3 2 1
1· ·= .
51 50 425
Eventos
Um evento na teoria da probabilidade pode ser representado como um conjunto
UM⊂X,
X ={1, 2, 3, 4, 5, 6}.
Um ={2, 4, 6}.
p(2)+p(4)+p(6)=1/2.
226
Complemento
A probabilidade do complementoUMé calculado usando a fórmula
P(UM)=1-P(UM).
União
A probabilidade da uniãoUM∪Bé calculado usando a fórmula
P(UM∪B)=P(UM)+P(B)-P(UM∩B).
e
B ="o resultado é menor que 4”
é
UM∪B ="o resultado é par ou menor que 4”,
e sua probabilidade é
P(UM∪B)=P(UM)+P(B)-P(UM∩B)=1/2+1/2−1/6=5/6.
P(UM∪B)=P(UM)+P(B).
Probabilidade condicional
Oprobabilidade condicional
P(UM∩B)
P(Um|B)=
P(B)
é a probabilidade deUMassumindo queBacontece. Portanto, ao calcular a probabilidade de
UM, consideramos apenas os resultados que também pertencem aB.
Usando os conjuntos anteriores,
P(Um|B)=1/3,
porque os resultados deBsão {1, 2, 3}, e um deles é par. Esta é a probabilidade de
um resultado par se sabemos que o resultado está entre 1 . . . 3.
227
Interseção
Usando probabilidade condicional, a probabilidade da intersecçãoUM∩Bpode ser
calculado usando a fórmula
P(UM∩B)=P(UM)P(B|A).
EventosUMeBsãoindependentese
P(Um|B)=P(UM) eP(B|A)=P(B),
P(UM∩B)=P(UM)P(B).
e
B ="o valor é quatro”
P(UM∩B)=P(UM)P(B)=1/4·1/13=1/52.
Variáveis aleatórias
Por exemplo, se os resultados forem [4, 6] (o que significa que primeiro tiramos um quatro e
depois um seis), então o valor deXé 10.
Nós denotamosP(X = x) a probabilidade de que o valor de uma variável aleatória
X éx. Por exemplo, ao lançar dois dados,P(X =10)=3/36, porque o número total de
resultados é 36 e há três maneiras possíveis de obter a soma 10: [4, 6], [5, 5] e [6,
4].
228
Valor esperado
Ovalor esperadoE[X] indica o valor médio de uma variável aleatóriaX. O valor
esperado pode ser calculado como a soma
∑
P(X = x)x,
x
1/6·1+1/6·2+1/6·3+1/6·4+1/6·5+1/6·6=7/2.
Uma propriedade útil dos valores esperados élinearidade. Isso significa que a soma E[X
1+X2+···+Xnão] sempre é igual à somaE[X1]+E[X2]+··· +E[Xnão]. Esta fórmula é válida mesmo
que variáveis aleatórias dependam umas das outras.
Por exemplo, ao lançar dois dados, a soma esperada é
E[X1+X2]=E[X1]+E[X2]=7/2+7/2=7.
0+0+1 +1 1
= .
4 2
No caso geral, a probabilidade de uma única caixa estar vazia é
(n−1)não
,
não
porque nenhuma bola deve ser colocada nele. Portanto, usando a linearidade, o número
esperado de caixas vazias é
(n−1)não
não· .
não
Distribuições
Odistribuiçãode uma variável aleatóriaXmostra a probabilidade de cada valor que
Xpode ter. A distribuição consiste em valoresP(X = x). Por exemplo, ao lançar dois
dados, a distribuição para sua soma é:
x 2 3 4 5 6 7 8 9 10 11 12
P(X = x) 1/36 2/36 3/36 4/36 5/36 6/36 5/36 4/36 3/36 2/36 1/36
229
Em umdistribuição uniforme, a variável aleatóriaXtemnãovalores possíveis
um,um+1, . . . ,be a probabilidade de cada valor é 1/não. Por exemplo, ao lançar
um dado,um =1,b =6 eP(X = x)=1/6 para cada valorx.
O valor esperado deXem uma distribuição uniforme é
um + b
E [X ]= .
2
Em umdistribuição binomial,nãotentativas são feitas e a probabilidade de que
uma única tentativa seja bem-sucedida ép. A variável aleatóriaXconta o número de
tentativas bem-sucedidas e a probabilidade de um valorxé
()
P(X = x)=px(1−p)n−xnão ,
x
onde
(não)
px e (1−p)n−xcorresponde às tentativas bem-sucedidas e malsucedidas e é o número de
E[X]=pn.
P(X = x)=(1−p)x−1p,
1
E[X]=.
p
Cadeias de Markov
230
1 1/2 1/2 1/2
1 2 3 4 5
Algoritmos aleatórios
Às vezes podemos usar a aleatoriedade para resolver um problema, mesmo que o
problema não esteja relacionado a probabilidades. Aalgoritmo randomizadoé um
algoritmo baseado na aleatoriedade.
UMAlgoritmo de Monte Carloé um algoritmo randomizado que pode, às vezes,
dar uma resposta errada. Para que tal algoritmo seja útil, a probabilidade de uma
resposta errada deve ser pequena.
231
UMAlgoritmo de Las Vegasé um algoritmo randomizado que sempre dá a resposta
correta, mas seu tempo de execução varia aleatoriamente. O objetivo é projetar um
algoritmo que seja eficiente com alta probabilidade.
A seguir, veremos três problemas de exemplo que podem ser resolvidos usando
aleatoriedade.
Estatísticas de pedidos
1Em 1961, CAR Hoare publicou dois algoritmos que são eficientes em média:classificação rápida
[36] para classificar matrizes eseleção rápida[37] para encontrar estatísticas de pedidos.
2RM Freivalds publicou este algoritmo em 1977 [26], e às vezes é chamadoAlgoritmo de
Freivalds.
232
A complexidade temporal do algoritmo éO(não2), porque podemos calcular as matrizes
ABXeCXemO(não2) tempo. Podemos calcular a matrizABX eficientemente usando a
representaçãoUM(BX), então apenas duas multiplicações denão×não enão×São necessárias
matrizes de tamanho 1.
A desvantagem do algoritmo é que há uma pequena chance de que o
algoritmo cometa um erro ao relatar queAB = C. Por exemplo,
[ ] [ ]
6 8 8 7
6= ,
1 3 3 2
mas [ ][ ] [ ][ ]
6 8 3 8 7 3
= .
1 3 6 3 2 6
Entretanto, na prática, a probabilidade de o algoritmo cometer um erro é pequena,
e podemos diminuir a probabilidade verificando o resultado usando múltiplos
vetores aleatóriosXantes de relatar issoAB = C.
Coloração de gráficos
Dado um gráfico que contémnãonós eeuarestas, nossa tarefa é encontrar uma maneira de
colorir os nós do gráfico usando duas cores para que, pelo menos,eu/2 arestas, os pontos
finais têm cores diferentes. Por exemplo, no gráfico
1 2
3 4
1 2
3 4
233
234
Capítulo 25
Neste capítulo, focaremos em jogos de dois jogadores que não contenham elementos aleatórios.
Nosso objetivo é encontrar uma estratégia que possamos seguir para vencer o jogo, não
importa o que o oponente faça, se tal estratégia existir.
Acontece que existe uma estratégia geral para tais jogos, e podemos analisar
os jogos usando ateoria nim. Primeiro, analisaremos jogos simples em que os
jogadores removem gravetos de montes e, depois disso, generalizaremos a
estratégia usada nesses jogos para outros jogos.
Estados do jogo
UMestado vencedoré um estado em que o jogador vencerá o jogo se jogar de forma otimizada,
e umestado perdedoré um estado em que o jogador perderá o jogo se o oponente jogar de
forma otimizada. Acontece que podemos classificar todos os estados de um jogo de modo que
cada estado seja um estado vencedor ou um estado perdedor.
No jogo acima, o estado 0 é claramente um estado perdedor, porque o jogador não pode fazer
nenhum movimento. Os estados 1, 2 e 3 são estados vencedores, porque podemos remover 1,
235
2 ou 3 palitos e ganhar o jogo. O estado 4, por sua vez, é um estado perdedor, porque qualquer
movimento leva a um estado que é um estado vencedor para o oponente.
Mais genericamente, se há um movimento que leva do estado atual para um estado
perdedor, o estado atual é um estado vencedor, e caso contrário, o estado atual é um estado
perdedor. Usando essa observação, podemos classificar todos os estados de um jogo
começando com estados perdedores onde não há movimentos possíveis.
Os estados 0 . . . 15 do jogo acima podem ser classificados da seguinte forma (Cdenota um
estado vencedor eeudenota um estado perdedor):
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
eu C C C eu C C C eu C C C eu C C C
É fácil analisar este jogo: um estadooé um estado perdedor seoé divisível por
4, e caso contrário é um estado vencedor. Uma maneira ótima de jogar o jogo é
sempre escolher um movimento após o qual o número de palitos no monte é divisível
por 4. Finalmente, não há mais palitos e o oponente perdeu.
Claro que esta estratégia requer que o número de varas sejanãodivisível por 4
quando for nossa vez. Se for, não há nada que possamos fazer, e o oponente vencerá o
jogo se jogar de forma otimizada.
Gráfico de estado
Vamos agora considerar outro jogo de palitos, onde em cada estadoo, é permitido
remover qualquer númeroxde varas tais quexé menor queoe divideo. Por exemplo, no
estado 8 podemos remover 1, 2 ou 4 palitos, mas no estado 7 o único movimento
permitido é remover 1 palito.
A imagem a seguir mostra os estados 1. . . 9 do jogo como umgráfico de estado,
cujos nós são os estados e as arestas são os movimentos entre eles:
1 2
4
5
7
8
6
O estado final neste jogo é sempre o estado 1, que é um estado perdedor, porque não
há movimentos válidos. A classificação dos estados 1 . . . 9 é a seguinte:
1 2 3 4 5 6 7 8 9
eu C eu C eu C eu C eu
Surpreendentemente, neste jogo, todos os estados pares são estados vencedores, e todos
os estados ímpares são estados perdedores.
236
Jogo Nim
Ojogo nimé um jogo simples que tem um papel importante na teoria dos jogos, porque
muitos outros jogos podem ser jogados usando a mesma estratégia. Primeiro, focamos em
nim, e então generalizamos a estratégia para outros jogos.
Hánãomontes em nim, e cada monte contém um certo número de gravetos. Os
jogadores se movem alternadamente, e em cada turno, o jogador escolhe um monte que
ainda contém gravetos e remove qualquer número de gravetos dele. O vencedor é o
jogador que remove o último graveto.
Os estados em nim são da forma [x1,x2, . . . ,xnão], ondexodenota o número de
gravetos na pilhao. Por exemplo, [10, 12, 5] é um jogo onde há três montes com
10, 12 e 5 palitos. O estado [0, 0, . . . ,0] é um estado perdedor, porque não é
possível remover nenhum palito, e este é sempre o estado final.
Análise
Acontece que podemos facilmente classificar qualquer estado nim calculando onim sum s =
x1⊕x2⊕···⊕xnão, onde⊕é a operação xor1. Os estados cuja soma nim é 0 são estados
perdedores, e todos os outros estados são estados vencedores. Por exemplo, a soma nim
de [10, 12, 5] é 10⊕12⊕5=3, então o estado é um estado vencedor.
Mas como a soma nim está relacionada ao jogo nim? Podemos explicar isso
observando como a soma nim muda quando o estado nim muda.
Estados perdedores:O estado final [0, 0, . . . , 0] é um estado perdedor, e sua soma nim é 0,
como esperado. Em outros estados perdedores, qualquer movimento leva a um estado
vencedor, porque quando um único valorxomuda, a soma nim também muda, então a soma nim
é diferente de 0 após a mudança.
Estados vencedores:Podemos passar para um estado de perda se houver algum monte
opara qual xo⊕s < xo. Neste caso, podemos remover os gravetos da pilhaopara que
contenha xo⊕epaus, o que levará a um estado perdedor. Sempre há uma pilha dessas,
onde xotem um bit na posição do bit mais à esquerda dee.
Como exemplo, considere o estado [10, 12, 5]. Este estado é um estado vencedor, porque
sua soma nim é 3. Portanto, tem que haver um movimento que leve a um estado perdedor. A
seguir, descobriremos tal movimento.
A soma nim do estado é a seguinte:
10 1010
12 1100
5 0101
3 0011
Neste caso, o heap com 10 bastões é o único heap que tem um bit na posição
do bit mais à esquerda da soma nim:
10 1010
12 1100
5 0101
3 0011
1A estratégia ótima para nim foi publicada em 1901 por CL Bouton [10].
237
O novo tamanho do heap deve ser 10⊕3=9, então removeremos apenas um stick.
Depois disso, o estado será [9, 12, 5], que é um estado perdedor:
9 1001
12 1100
5 0101
0 0000
Jogo Misère
Em umjogo misère, o objetivo do jogo é oposto, então o jogador que remover o
último palito perde o jogo. Acontece que o jogo misère nim pode ser jogado de
forma otimizada quase como o jogo nim padrão.
A ideia é primeiro jogar o jogo misère como o jogo padrão, mas mudar a
estratégia no final do jogo. A nova estratégia será introduzida em uma situação em
que cada pilha conteria no máximo um bastão após o próximo movimento.
No jogo padrão, devemos escolher um movimento após o qual haja um número par de montes
com um pedaço de madeira. No entanto, no jogo misère, escolhemos um movimento para que haja
um número ímpar de montes com um pedaço de madeira.
Essa estratégia funciona porque um estado onde a estratégia muda sempre
aparece no jogo, e esse estado é um estado vencedor, porque contém exatamente um
monte que tem mais de um bastão, então a soma nim não é 0.
Teorema de Sprague–Grundy
A ideia é calcular para cada estado do jogo um número Grundy que corresponde ao
número de palitos em um heap nim. Quando sabemos os números Grundy de todos os
estados, podemos jogar o jogo como o jogo nim.
Números Grundy
ONúmero Grundyde um estado de jogo é
mexicano({g1,g2, . . . ,gnão}),
238
ondeg1,g2, . . . ,gnãosão os números de Grundy dos estados para os quais podemos nos
mover, e a função mex fornece o menor número não negativo que não está no conjunto.
Por exemplo, mex({0, 1, 3})=2. Se não houver movimentos possíveis em um estado, seu
número de Grundy é 0, porque mex(;)=0.
Por exemplo, no gráfico de estado
0 1 0
2 0 2
*
*
* * * * @
0 1 0 1
0 1 2
0 2 1 0
3 0 4 1
0 4 1 3 2
239
Assim, cada estado do jogo do labirinto corresponde a um monte no jogo nim. Por exemplo, o
número Grundy para o quadrado inferior direito é 2, então é um estado vencedor. Podemos chegar a
um estado perdedor e vencer o jogo movendo-nos quatro passos para a esquerda ou dois passos para
cima.
Note que, diferentemente do jogo nim original, pode ser possível mover para um
estado cujo número Grundy seja maior que o número Grundy do estado atual. No entanto,
o oponente sempre pode escolher um movimento que cancele tal movimento, então não é
possível escapar de um estado perdedor.
Subjogos
Em seguida, assumiremos que nosso jogo consiste em subjogos, e em cada turno, o jogador
primeiro escolhe um subjogo e então um movimento no subjogo. O jogo termina quando não é
possível fazer nenhum movimento em nenhum subjogo.
Neste caso, o número Grundy de um jogo é a soma nim dos números Grundy
dos subjogos. O jogo pode ser jogado como um jogo nim calculando todos os
números Grundy para subjogos e então sua soma nim.
Como exemplo, considere um jogo que consiste em três labirintos. Neste jogo,
em cada turno, o jogador escolhe um dos labirintos e então move a figura no
labirinto. Suponha que o estado inicial do jogo seja o seguinte:
@ @ @
0 1 0 1 0 1 2 3 0 1 2 3 4
0 1 2 1 0 0 1 1 0
0 2 1 0 2 0 1 2 2 1
3 0 4 1 3 1 2 0 3 2
0 4 1 3 2 4 0 2 5 3 4 0 1 2 3
No estado inicial, a soma nim dos números de Grundy é 2⊕3⊕3=2, então o primeiro
jogador pode ganhar o jogo. Um movimento ótimo é subir dois degraus no primeiro
labirinto, o que produz a soma nim 0⊕3⊕3=0.
Jogo do Grundy
Às vezes, um movimento em um jogo divide o jogo em subjogos que são
independentes uns dos outros. Neste caso, o número Grundy do jogo é
mexicano({g1,g2, . . . ,gnão}),
240
Traduzido do Inglês para o Português - [Link]
e(8)=mexicano({e(1)⊕e(7),e(2)⊕e(6),e(3)⊕e(5)}).
Neste jogo, o valor dee(não) é baseado nos valores dee(1), . . . ,e(n−1). Os casos
base sãoe(1)=e(2)=0, porque não é possível dividir os montes de 1 e 2 gravetos. Os
primeiros números de Grundy são:
e(1) = 0
e(2) = 0
e(3) = 1
e(4) = 0
e(5) = 2
e(6) = 1
e(7) = 0
e(8) = 2
241
242
Capítulo 26
Algoritmos de string
Este capítulo trata de algoritmos eficientes para processamento de strings. Muitos problemas de strings
podem ser facilmente resolvidos emO(não2) tempo, mas o desafio é encontrar algoritmos que funcionem em
O(não) ouO(nãoregistronão) tempo.
Por exemplo, um problema fundamental de processamento de strings é ocorrespondência
de padrõesproblema: dada uma sequência de comprimentonãoe um padrão de comprimentoeu,
nossa tarefa é encontrar as ocorrências do padrão na string. Por exemplo, o padrãoabc ocorre
duas vezes na stringABABCBABC.
O problema de correspondência de padrões pode ser facilmente resolvido emO(nm) tempo
por um algoritmo de força bruta que testa todas as posições onde o padrão pode ocorrer na
string. No entanto, neste capítulo, veremos que existem algoritmos mais eficientes que
requerem apenasO(n+m) tempo.
Terminologia de strings
Ao longo do capítulo, assumimos que a indexação de base zero é usada em strings. Assim,
uma stringede comprimentonãoconsiste em caracterese[0],e[1], . . . ,e[n−1]. O conjunto de
caracteres que podem aparecer em strings é chamado dealfabeto. Por exemplo, o alfabeto
{A,B, . . . ,Z}consiste nas letras maiúsculas do inglês.
UMsubstringé uma sequência de caracteres consecutivos em uma string. Usamos a notação
e[um. . .b] para se referir a uma substring deeque começa na posiçãoume termina na posiçãob.
Uma sequência de comprimentonãotemnão(n+1)/2 substrings. Por exemplo, as substrings de
ABCDsãoA, B, C, D, AB, BC, CD, ABC, BCDeABCD.
UMsubsequênciaé uma sequência de caracteres (não necessariamente consecutivos) em
uma string em sua ordem original. Uma string de comprimentonãotem 2não−1 subsequências.
Por exemplo, as subsequências deABCDsãoA, B, C, D, AB, CA, AD, BC, BD, CD, ABC, ABD, ACD,
BCDeABCD.
UMprefixoé uma substring que começa no início de uma string e umasufixo é uma
substring que termina no final de uma string. Por exemplo, os prefixos deABCD sãoA,
AB, ABCeABCD,e os sufixos deABCDsãoD, CD, BCDeABCD.
UMrotaçãopode ser gerado movendo os caracteres de uma string um por um
do início ao fim (ou vice-versa). Por exemplo, as rotações deABCD sãoABCD, BCDA,
CDABeDABC.
243
UMperíodoé um prefixo de uma string tal que a string pode ser construída
repetindo o período. A última repetição pode ser parcial e conter apenas um prefixo do
período. Por exemplo, o período mais curto deABCABCAéABC.
UMfronteiraé uma string que é um prefixo e um sufixo de uma string. Por exemplo, as
bordas deABACABAsãoUm, ABAeABACABA.
As strings são comparadas usando oordem lexicográfica(que corresponde à
ordem alfabética). Isso significa quex < yse qualquer umx6=eexé um prefixo dee,
ou há uma posiçãootal quex[eu]=e[eu] quandoeu < kex[o]<e[o].
Estrutura Trie
UMtenteé uma árvore enraizada que mantém um conjunto de strings. Cada string no conjunto é
armazenada como uma cadeia de caracteres que começa na raiz. Se duas strings têm um prefixo
comum, elas também têm uma cadeia comum na árvore.
Por exemplo, considere o seguinte teste:
C E
UM O
Não E
*
UM E R
eu E E
* * *
Inteirotrie[N][A];
244
ondeNãoé o número máximo de nós (o comprimento total máximo das strings no
conjunto) eUMé o tamanho do alfabeto. Os nós de uma trie são numerados 0, 1,
2, . . . de modo que o número da raiz é 0, etente[e][c] é o próximo nó na cadeia
quando passamos do nóeusando personagemc.
Hash de string
Hash de stringé uma técnica que nos permite verificar eficientemente se duas strings
são iguais1. A ideia do hash de strings é comparar valores de hash de strings em vez de
seus caracteres individuais.
(s[0]UMn−1+e[1]UMn−2+···+e[n−1]UM0) modB,
ondee[0],e[1], . . . ,e[n−1] são interpretados como os códigos dos caracteres dee,e UMeBsão
constantes pré-selecionadas.
Por exemplo, os códigos dos caracteres deALÉIAsão:
UMeu eu E E
65 76 76 69 89
Pré-processamento
Usando hash polinomial, podemos calcular o valor de hash de qualquer substring de uma string
eemO(1) tempo após umO(não) pré-processamento de tempo. A ideia é construir uma matrizotal
quee[o] contém o valor hash do prefixoe[0 . . .o]. Os valores da matriz podem ser calculados
recursivamente da seguinte forma:
e[0] = e[0]
e[o] = (h[k−1]Um +e[o]) modB
p[0] = 1
p[o] = (p[k−1]UM) modB.
245
A construção dessas matrizes requerO(não) tempo. Depois disso, o valor hash de qualquer
substringe[um. . .b] pode ser calculado emO(1) tempo usando a fórmula
(h[b]−e[uma−1]p[b-a+1]) modB
Colisões e parâmetros
Um risco evidente ao comparar valores de hash é umcolisão, o que significa que duas
strings têm conteúdos diferentes, mas valores de hash iguais. Nesse caso, um
algoritmo que depende dos valores de hash conclui que as strings são iguais, mas na
realidade não são, e o algoritmo pode dar resultados incorretos.
As colisões são sempre possíveis, porque o número de strings diferentes é maior que o
número de valores hash diferentes. No entanto, a probabilidade de uma colisão é pequena
se as constantesUMeBsão cuidadosamente escolhidos. Uma maneira usual é escolher
constantes aleatórias perto de 109, por exemplo, como segue:
UM= 911382323
B = 972663749
Usando tais constantes, olongo longotipo pode ser usado ao calcular valores de
hash, porque os produtosSobreeBBvai caber emlongo [Link] será que basta ter
cerca de 109valores de hash diferentes?
Vamos considerar três cenários onde o hash pode ser usado:
246
Cenário 1:Cordasxeesão comparados entre si. A probabilidade de uma colisão é 1/B
assumindo que todos os valores de hash são igualmente prováveis.
Cenário 2:Uma cordaxé comparado com stringse1,e2, . . . ,enão. A probabilidade de
uma ou mais colisões é
1
1−(1−)não.
B
Cenário 3:Todos os pares de stringsx1,x2, . . . ,xnãosão comparados entre si. A
probabilidade de uma ou mais colisões é
B·(B-1)·(B-2)···(B− n+1)
1− .
Bnão
Algoritmo Z
OMatriz Zporde uma cordaede comprimentonãocontém para cadak =0, 1, . . . ,n −1 o
comprimento da substring mais longa deeque começa na posiçãooe é um prefixo de
247
[Link] isso,e[o]=pnos diz quee[0. . .p −1] é igual ae[o. . .k + p −1]. Muitos problemas de
processamento de strings podem ser resolvidos eficientemente usando o Z-array.
Por exemplo, a matriz Z deACBACDACBACBACDAé o seguinte:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Descrição do algoritmo
A seguir descrevemos um algoritmo, denominadoAlgoritmo Z2, que constrói
eficientemente a matriz Z emO(não) tempo. O algoritmo calcula os valores do Z-array
da esquerda para a direita usando informações já armazenadas no Z-array e
comparando substrings caractere por caractere.
Para calcular eficientemente os valores da matriz Z, o algoritmo mantém um
intervalo [x,e] tal quee[x. . .e] é um prefixo deeeeé o maior possível. Como
sabemos quee[0 . . .y− x] ee[x. . .e] são iguais, podemos usar essas informações ao
calcular valores Z para posiçõesx+1,x+2, . . . ,e.
Em cada posiçãoo, primeiro verificamos o valor dee[k - x]. Seo +e[k - x]<e, sabemos
quee[o]=e[k− x]. No entanto, sek+e[k− x]≥e,e[0 . . .e-k] é igual ae[o. . .e], e para
determinar o valor dee[o] precisamos comparar as substrings caractere por caractere.
Ainda assim, o algoritmo funciona emO(não) tempo, porque começamos a comparar
em posiçõesy− k+1 ee+1.
Por exemplo, vamos construir a seguinte matriz Z:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
UM C B UM C E UM C B UM C B UM C E UM
– ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
x e
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
UM C B UM C E UM C B UM C B UM C E UM
– 0 0 2 0 0 5 ? ? ? ? ? ? ? ? ?
2O algoritmo Z foi apresentado em [32] como o método mais simples conhecido para correspondência de
padrões de tempo linear, e a ideia original foi atribuída a [50].
248
x e
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
UM C B UM C E UM C B UM C B UM C E UM
– 0 0 2 0 0 5 0 0 ? ? ? ? ? ? ?
x e
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
UM C B UM C E UM C B UM C B UM C E UM
– 0 0 2 0 0 5 0 0 ? ? ? ? ? ? ?
Entretanto, não temos informações sobre a string após a posição 10, então
precisamos comparar as substrings caractere por caractere:
x e
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
UM C B UM C E UM C B UM C B UM C E UM
– 0 0 2 0 0 5 0 0 ? ? ? ? ? ? ?
x e
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
UM C B UM C E UM C B UM C B UM C E UM
– 0 0 2 0 0 5 0 0 7 ? ? ? ? ? ?
Depois disso, todos os valores restantes da matriz Z podem ser determinados usando
as informações já armazenadas na matriz Z:
x e
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
UM C B UM C E UM C B UM C B UM C E UM
– 0 0 2 0 0 5 0 0 7 0 0 2 0 0 1
249
Usando a matriz Z
Geralmente é uma questão de gosto usar hash de string ou o algoritmo Z. Ao
contrário do hash, o algoritmo Z sempre funciona e não há risco de colisões. Por
outro lado, o algoritmo Z é mais difícil de implementar e alguns problemas só
podem ser resolvidos usando hash.
Como exemplo, considere novamente o problema de correspondência de padrões, onde
nossa tarefa é encontrar as ocorrências de um padrãopem uma sequênciae. Já resolvemos esse
problema de forma eficiente usando hash de strings, mas o algoritmo Z fornece outra maneira
de resolver o problema.
Uma ideia usual no processamento de strings é construir uma string que consiste
em múltiplas strings separadas por caracteres especiais. Neste problema, podemos
construir uma stringp#e, ondepeesão separados por um caractere especial # que não
ocorre nas strings. A matriz Z dep#enos diz as posições ondepocorre eme, porque tais
posições contêm o comprimento dep.
Por exemplo, ses =HATTIVATTIep =ATT,a matriz Z é a seguinte:
0 1 2 3 4 5 6 7 8 9 10 11 12 13
UM E E # O UM E E EU V UM E E EU
– 0 0 0 0 3 0 0 0 0 3 0 0 0
Implementação
Aqui está uma breve implementação do algoritmo Z que retorna um vetor que
corresponde à matriz Z.
Inteiron = [Link]();
vetor<Inteiro> z(n);
Inteirox = 0, y = 0;
para(Inteiroeu = 1; eu < n; eu++) {
z[i] = máx(0,min(z[ix],y-i+1));
enquanto(i+z[i] < n && s[z[i]] == s[i+z[i]]) {
x = eu; y = i+z[i]; z[i]++;
}
}
retornarpor;
}
250
Capítulo 27
UMalgoritmo de raiz quadradaé um algoritmo que tem uma raiz quadrada em seu tempo
complexidade. Uma raiz quadrada pode ser vista como um “logaritmo do homem pobre”: a complexidade
p
O(não) é melhor queO(não) mas pior queO(registronão). Em qualquer caso, muitos algoritmos
de raiz quadrada são rápidos e utilizáveis na prática.
Como exemplo, considere o problema de criar uma estrutura de dados que suporte duas
operações em um array: modificar um elemento em uma dada posição e calcular a soma dos
elementos no intervalo dado. Nós resolvemos o problema anteriormente usando árvores
indexadas binárias e de segmento, que suportam ambas as operações em O(registronão) tempo.
No entanto, agora resolveremos o problema de outra forma usando um
estrutura de raiz quadrada que nos permite modificar elementos emO(1) tempo e calcular
p
somas emO(não) tempo.
p
A ideia é dividir a matriz emblocosde tamanhonãopara que cada bloco contenha a
soma dos elementos dentro do bloco. Por exemplo, um array de 16 elementos será
dividido em blocos de 4 elementos como segue:
21 17 20 13
5 8 6 3 2 7 2 6 7 1 7 5 6 2 3 2
21 15 20 13
5 8 6 3 2 5 2 6 7 1 7 5 6 2 3 2
21 15 20 13
5 8 6 3 2 5 2 6 7 1 7 5 6 2 3 2
251
p
Como o número de elementos individuais éO( não) e o número de blocos é
p p p
tambémO( não), a consulta de soma levaO(não) tempo. O propósito do tamanho do bloconãoé
p
que issosaldosduas coisas: a matriz é dividida emnãoblocos, cada um dos quais
p
contémnãoelementos.
p
Na prática, não é necessário usar o valor exato denãocomo parâmetro,
p
e em vez disso podemos usar parâmetrosoenão/oondeoé diferente denão.
O parâmetro ideal depende do problema e da entrada. Por exemplo, se um
o algoritmo geralmente percorre os blocos, mas raramente inspeciona elementos individuais dentro
p
os blocos, pode ser uma boa ideia dividir a matriz emk < nblocos, cada um dos
p
que contémnão/k > nelementos.
Combinando algoritmos
Nesta seção, discutimos dois algoritmos de raiz quadrada que são baseados na combinação de
dois algoritmos em um algoritmo. Em ambos os casos, poderíamos usar qualquer um dos
algoritmos sem o outro e resolver o problema emO(não2) tempo. No entanto, por
p
combinando os algoritmos, o tempo de execução é apenasO(não).
Processamento de casos
Suponha que nos seja dada uma grade bidimensional que contémnãocélulas. Cada
célula recebe uma letra, e nossa tarefa é encontrar duas células com a mesma letra
cuja distância seja mínima, onde a distância entre as células (x1,e1) e (x2,e2) é|x1−x2
|+|e1−e2|. Por exemplo, considere a seguinte grade:
UM F B UM
C E G E
B E UM F
UM C B E
252
No entanto, podemoscombinaros dois algoritmos e usar algoritmos diferentes para
letras diferentes dependendo de quantas vezes cada letra aparece na grade.
p
Suponha que uma cartacapareceovezes. Seo≤não, usamos o Algoritmo 1, e se
p
k > n, usamos o Algoritmo 2. Acontece que, ao fazer isso, o total de execução
p
o tempo do algoritmo é apenasO(não).
Primeiro, suponha que usamos o Algoritmo 1 para uma letrac. Desdecaparece no máximo p
p
nãovezes na grade, comparamos cada célula com a letrac O(células. não) vezes com outros
p
Assim, o tempo usado para processar todas essas células éO(não não). Então, suponha
p
que usamos o Algoritmo 2 para uma letrac. Existem no máximo nãotais letras, então
p
processar essas cartas também levaO(não) tempo.
Processamento em lote
Nosso próximo problema também lida com uma grade bidimensional que contémnãocélulas.
Inicialmente, cada célula, exceto uma, é branca. Nós realizamosn−1 operação, cada uma das quais
primeiro calcula a distância mínima de uma determinada célula branca até uma célula preta e, então,
pinta a célula branca de preto.
Por exemplo, considere a seguinte operação:
Primeiro, calculamos a distância mínima da célula branca marcada com * até uma célula
preta. A distância mínima é 2, porque podemos nos mover dois passos para a esquerda até uma
célula preta. Então, pintamos a célula branca de preto:
253
operação, a distância mínima para uma célula preta é a distância calculada
pelo Algoritmo 1 ou a distância calculada pelo Algoritmo 2.
p
O algoritmo resultante funciona emO(não) tempo. Primeiro, o Algoritmo 1 é realizado
p
formadoO(não) vezes, e cada pesquisa funciona emO(não) tempo. Segundo, ao usar
p
Algoritmo 2 em um lote, a lista contémO(não) células (porque limpamos a lista
p
entre os lotes) e cada operação levaO(não) tempo.
Partições inteiras
Alguns algoritmos de raiz quadrada são baseados na seguinte observação: se um positivo
inteironãoé representado como uma soma de números inteiros positivos, tal soma sempre contém
p
no máximoO(não)distintonúmeros. A razão para isso é que para construir uma soma que
contenha um número máximo de números distintos, devemos escolherpequeno números.
Se escolhermos os números 1, 2, . . . ,o, a soma resultante é
o(k+1)
.
2
p
Assim, a quantidade máxima de números distintos ék = O(não). Em seguida iremos
discuta dois problemas que podem ser resolvidos eficientemente usando esta observação.
Mochila
Suponha que nos seja dada uma lista de pesos inteiros cuja soma énão. Nossa tarefa é descobrir
todas as somas que podem ser formadas usando um subconjunto dos pesos. Por exemplo, se os
pesos forem {1, 3, 3}, as somas possíveis são as seguintes:
• 0 (conjunto vazio)
•1
•3
• 1+3=4
• 3+3=6
• 1+3+3=7
Usando a abordagem padrão da mochila (ver Capítulo 7.4), o problema pode ser
resolvido da seguinte forma: definimos uma funçãopossível(x,o) cujo valor é 1 se a soma x
pode ser formado usando o primeiroopesos e 0 caso contrário. Como a soma dos pesos é
não, existem no máximonãopesos e todos os valores da função podem ser calculados emO(
não2) tempo usando programação dinâmica.
No entanto, podemos tornar o algoritmo mais eficiente usando o fato de que
p
há no máximoO(não)distintopesos. Assim, podemos processar os pesos em
grupos que consistem em pesos semelhantes. Podemos processar cada grupo emO(não) tempo,
p
que produz umO(não) algoritmo de tempo.
A ideia é usar um array que registre as somas de pesos que podem ser formadas usando os
grupos processados até agora. O array contémnãoelementos: elementooé 1 se a somaopode
ser formado e 0 caso contrário. Para processar um grupo de pesos, varremos a matriz da
esquerda para a direita e registramos as novas somas de pesos que podem ser formadas
usando este grupo e os grupos anteriores.
254
Construção de cordas
Dada uma stringede comprimentonãoe um conjunto de cordasEcujo comprimento total éeu,
considere o problema de contar o número de maneirasepode ser formado como uma
concatenação de strings emE. Por exemplo, see=ABABeE ={{A, B, AB},Existem 4 maneiras:
• UM+B+UM+B
• Sobre+UM+B
• UM+B+Sobre
• Sobre+Sobre
Algoritmo de Mo
• bum1/oc = bum2/oceb1<b2.
1De acordo com [12], este algoritmo recebeu o nome de Mo Tao, um programador competitivo chinês,
mas a técnica já apareceu anteriormente na literatura [44].
255
Assim, todas as consultas cujos pontos finais esquerdos estão em um determinado bloco são processadas
um após o outro, classificados de acordo com seus pontos finais corretos. Usando esta ordem, o
p
algoritmo só executaO(não não) operações, porque o ponto final esquerdo se move
p p
O(não) vezesO( não) passos, e o ponto final direito se moveO( não) vezesO(não) passos.
p
Assim, ambos os pontos finais movem um total deO(não) etapas durante o algoritmo.
Exemplo
Como exemplo, considere um problema em que nos é dado um conjunto de consultas, cada uma
delas correspondendo a um intervalo em uma matriz, e nossa tarefa é calcular para cada
consulta o número dedistintoelementos no intervalo.
No algoritmo de Mo, as consultas são sempre ordenadas da mesma forma,
mas depende do problema como a resposta à consulta é mantida. Neste problema,
podemos manter um arraycontarondecontar[x] indica o número de vezes que um
elementoxocorre na faixa ativa.
Quando passamos de uma consulta para outra, o intervalo ativo muda. Por
exemplo, se o intervalo atual for
4 2 5 4 2 4 3 3 4
e o próximo intervalo é
4 2 5 4 2 4 3 3 4
256
Capítulo 28
Uma árvore de segmento é uma estrutura de dados versátil que pode ser usada para resolver um
grande número de problemas de algoritmo. No entanto, há muitos tópicos relacionados a árvores de
segmento que ainda não abordamos. Agora é hora de discutir algumas variantes mais avançadas de
árvores de segmento.
Inteirosoma(Inteiroum,Inteirob) {
um += n; b += n;
Inteiros = 0;
enquanto(a <= b) {
se(a%2 == 1) s += árvore[a++]; se
(b%2 == 0) s += árvore[b--]; a /=
2; b /= 2;
}
retornare;
}
Inteirosoma(Inteiroum,Inteirob,Inteirook,Inteirox,Inteiroe) {
se(b < x || a > y)retornar0; se(a <= x e y
<= b)retornarárvore[k]; Inteirod = (x+y)/2;
retornarsoma(a,b,2*k,x,d) + soma(a,b,2*k+1,d+1,y);
}
Agora podemos calcular qualquer valor desomaq(um,b) (a soma dos valores da matriz no intervalo [um,b]) do
seguinte modo:
257
O parâmetrooindica a posição atual emá[Link]é igual a 1, porque
começamos na raiz da árvore. O intervalo [x,e] corresponde aoe é inicialmente [0,n−1].
Ao calcular a soma, se [x,e] está fora [um,b], a soma é 0, e se [x,e] está completamente
dentro [um,b], a soma pode ser encontrada emá[Link] [x,e] está parcialmente dentro
[um,b], a busca continua recursivamente para a metade esquerda e direita
de [x,e]. A metade esquerda é [x,e] e a metade direita é [e +1,e] onded =bx+y 2c.
A figura a seguir mostra como ocorre a busca ao calcular o valor desomaq(um,
b). Os nós cinza indicam nós onde a recursão para e a soma pode ser encontrada
emárvore.
72
39 33
22 17 20 13
13 9 9 8 8 12 8 5
5 8 6 3 2 7 2 6 7 1 7 5 6 2 3 2
um b
Propagação preguiçosa
Vamos considerar um exemplo onde nosso objetivo é construir uma árvore de segmentos que
suporte duas operações: aumentar cada valor em [um,b] por uma constante e calculista
258
a soma dos valores em [um,b].
Construiremos uma árvore onde cada nó tem dois valorese/por:edenota a soma dos valores
no intervalo epordenota o valor de uma atualização lenta, o que significa que todos os valores
no intervalo devem ser aumentados empor. Na árvore a seguir,z =0 em todos os nós, então não
há atualizações lentas em andamento.
72/0
39/0 33/0
5 8 6 3 2 7 2 6 7 1 7 5 6 2 3 2
90/0
45/0 45/0
5 8 6 3 2 9 2 6 7 1 7 5 6 2 3 2
um b
259
Tanto em atualizações quanto em consultas, o valor de uma atualização preguiçosa é
sempre propagado para os filhos do nó antes de processar o nó. A ideia é que as
atualizações sejam propagadas para baixo somente quando necessário, o que garante que
as operações sejam sempre eficientes.
A imagem a seguir mostra como a árvore muda quando calculamos o valor de
somaum(um,b). O retângulo mostra os nós cujos valores mudam, porque uma
atualização lenta é propagada para baixo.
90/0
45/0 45/0
5 8 6 3 2 9 2 6 7 1 7 5 6 2 3 2
um b
Note que às vezes é necessário combinar atualizações preguiçosas. Isso acontece quando
um nó que já tem uma atualização preguiçosa recebe outra atualização preguiçosa. Ao calcular
somas, é fácil combinar atualizações preguiçosas, porque a combinação de atualizaçõespor1epor
2corresponde a uma atualizaçãopor1+por2.
Atualizações polinomiais
Atualizações preguiçosas podem ser generalizadas para que seja possível atualizar intervalos usando
polinômios da forma
p(você)=paraovocêo+ ok−1vocêk−1+···+para0.
Neste caso, a atualização para um valor na posiçãoeuem [um,b] ép(eu - um). Por
exemplo, adicionando o polinômiop(você)=você +1 a [um,b] significa que o valor na posição
umaumenta em 1, o valor na posiçãoum+1 aumenta em 2, e assim por diante.
Para suportar atualizações polinomiais, cada nó é atribuídok+2 valores, ondeo é
igual ao grau do polinômio. O valoreé a soma dos elementos do intervalo e os valores
por0,por1, . . . ,porosão os coeficientes de um polinômio que corresponde a uma
atualização preguiçosa.
Agora, a soma dos valores em um intervalo [x,e] é igual a
e−∑x
o
s+ por
você
o + pork−1vocêk−1+···+por0.
você=0
260
O valor de tal soma pode ser calculado eficientemente usando fórmulas de soma.
Por exemplo, o termopor0corresponde à soma (y− x+1)por0, e o termopor1você
corresponde à soma
Árvores dinâmicas
Uma árvore de segmento comum é estática, o que significa que cada nó tem uma posição
fixa na matriz e a árvore requer uma quantidade fixa de memória. Em um árvore de
segmento dinâmico, a memória é alocada apenas para nós que são realmente acessados
durante o algoritmo, o que pode economizar uma grande quantidade de memória.
Os nós de uma árvore dinâmica podem ser representados como estruturas:
estruturanó {
Inteirovalor;
Inteirox, e;
nó *esquerda, *direita;
nó(Inteirovocê,Inteirox,Inteiroy) : valor(v), x(x), y(y) {}
};
// cria novo nó
nó *x =novonó(0, 0, 15); //
alterar valor
x->valor = 5;
Uma árvore de segmento dinâmica é útil quando a matriz subjacente éescasso, ou seja, o intervalo [0,
n−1] de índices permitidos é grande, mas a maioria dos valores de array são zeros. Enquanto uma
árvore de segmento comum usaO(não) memória, uma árvore de segmento dinâmica usa apenas O(o
registronão) memória, ondeoé o número de operações realizadas.
UMárvore de segmento esparsoinicialmente tem apenas um nó [0,n −1] cujo valor
é zero, o que significa que todo valor de array é zero. Após atualizações, novos nós são
adicionados dinamicamente à árvore. Por exemplo, sen =16 e os elementos nas
posições 3 e 10 foram modificados, a árvore contém os seguintes nós:
261
[0, 15]
[3] [10]
Qualquer caminho do nó raiz para uma folha contémO(registronão) nós, então cada operação
adiciona no máximoO(registronão) novos nós para a árvore. Assim, apósooperações, a árvore contém
no máximoO(oregistronão) nós.
Note que se sabemos que todos os elementos devem ser atualizados no início do
algoritmo, uma árvore de segmento dinâmica não é necessária, porque podemos usar uma
árvore de segmento comum com compressão de índice (Capítulo 9.4). No entanto, isso não
é possível quando os índices são gerados durante o algoritmo.
Após cada atualização, a maioria dos nós da árvore permanece a mesma, portanto, uma maneira
eficiente de armazenar o histórico de modificações é representar cada árvore no histórico como uma
262
combinação de novos nós e subárvores de árvores anteriores. Neste exemplo, o histórico de
modificações pode ser armazenado da seguinte forma:
Estruturas de dados
Em vez de valores únicos, os nós em uma árvore de segmentos também podem conterestruturas de
dados que mantêm informações sobre os intervalos correspondentes. Em tal árvore, as operações
ocorremO(e(não) registronão) tempo, ondee(não) é o tempo necessário para processar um único nó
durante uma operação.
Como exemplo, considere uma árvore de segmentos que suporta consultas do tipo
“quantas vezes um elementoxaparecem no intervalo [um,b]?” Por exemplo, o elemento
1 aparece três vezes no seguinte intervalo:
3 1 2 3 1 1 1 2
Para dar suporte a essas consultas, construímos uma árvore de segmentos onde cada nó
recebe uma estrutura de dados que pode ser questionada quantas vezes qualquer elementox
aparece no intervalo correspondente. Usando esta árvore, a resposta a uma consulta pode ser
calculada combinando os resultados dos nós que pertencem ao intervalo.
Por exemplo, a seguinte árvore de segmentos corresponde à matriz acima:
1 2 3
4 2 2
1 2 3 1 2
1 1 2 3 1
1 3 2 3 1 1 2
1 1 1 1 2 1 1
3 1 2 3 1 1 1 2
1 1 1 1 1 1 1 1
263
Podemos construir a árvore de modo que cada nó contenha ummapaestrutura. Neste caso, o
tempo necessário para processar cada nó éO(registronão), então a complexidade de tempo total de
uma consulta éO(registro2não). A árvore usaO(nãoregistronão) memória, porque existemO(registro
não) níveis e cada nível contémO(não) elementos.
Bidimensionalidade
UMárvore de segmento bidimensionalsuporta consultas relacionadas a subarrays
retangulares de um array bidimensional. Tal árvore pode ser implementada como árvores
de segmento aninhadas: uma árvore grande corresponde às linhas do array, e cada nó
contém uma árvore pequena que corresponde a uma coluna.
Por exemplo, na matriz
7 6 1 6
8 7 5 2
3 9 7 1
8 5 3 8
a soma de qualquer submatriz pode ser calculada a partir da seguinte árvore de segmentos:
86
53 33
26 27 16 17
42 44
28 14 25 19
15 13 6 8 11 14 10 9
20 22 20 24
13 7 15 7 12 8 13 11
264
Capítulo 29
Geometria
Depois disso, basta somar as áreas dos triângulos. A área de um triângulo pode ser
ser calculado, por exemplo, usandoFórmula de Heron
√
e(s-um)(s− b)(s-c),
265
No entanto, há outra maneira de traçar a linha que funciona:
Para um humano é claro qual das linhas é a escolha correta, mas a situação é difícil
para um computador.
No entanto, acontece que podemos resolver o problema usando outro método que
é mais conveniente para um programador. Ou seja, há uma fórmula geral
x1e2−x2e1+x2e3−x3e2+x3e4−x4e3+x4e1−x1e4,
que calcula a área de um quadrilátero cujos vértices são (x1,e1), (x2,e2), (x3,e3) e (x4,
e4). Esta fórmula é fácil de implementar, não há casos especiais e podemos até
generalizar a fórmula paratodospolígonos.
Números complexos
p
UMnúmero complexoé um número da formax+ yi, ondeeu = −1 é oimagine-
unidade nary. Uma interpretação geométrica de um número complexo é que ele
representa um ponto bidimensional (x,e) ou um vetor da origem até um ponto (x,e).
Por exemplo, 4+2eucorresponde ao seguinte ponto e vetor:
(4, 2)
266
Por exemplo, o código a seguir define um pontop =(4, 2) e imprime suas
coordenadas x e y:
P p = {4,2};
corte << pX <<" "<< pY <<"\n";// 4 2
P v = {3,1};
P você = {2,2};
P s = v+u;
corte << sX <<" "<< sim <<"\n";// 5 3
Funções
Nos exemplos a seguir, o tipo de coordenada élongo duplo.
O fu √nçãoabdômen(você) calcula o comprimento|vocêde um vetorvocê =(x,e) usando o
fórmula x2+e2. A função também pode ser usada para calcular a distância
entre pontos (x1,e1) e (x2,e2), porque essa distância é igual ao comprimento do
vetor (x2−x1,e2−e1).
O código a seguir calcula a distância entre os pontos (4, 2) e (3,−1):
P a = {4,2};
P b = {3,-1};
cout << abs(ba) <<"\n";// 3.16228
P v = {4,2};
cout << arg(v) <<"\n";// 0,463648 v *=
polar(1,0,0,5);
cout << arg(v) <<"\n";// 0,963648
267
Pontos e linhas
Oproduto cruzadoum×bde vetoresum =(x1,e1) eb =(x2,e2) é calculado usando a
fórmulax1e2−x2e1. O produto vetorial nos diz sebvira para a esquerda (valor positivo),
não vira (zero) ou vira para a direita (valor negativo) quando é colocado diretamente
apósum.
A imagem a seguir ilustra os casos acima:
b b
b
um um um
Por exemplo, no primeiro casoum =(4, 2) eb =(1, 2). O código a seguir calcula o
produto vetorial usando a classecomplexo:
P a = {4,2};
P b = {1,2};
C p = (conj(a)*b).Y;// 6
Localização do ponto
Os produtos cruzados podem ser usados para testar se um ponto está localizado no lado
esquerdo ou direito de uma linha. Suponha que a linha passe por pontose1ee2, estamos
olhando dee1parae2e o ponto ép.
Por exemplo, na imagem a seguir,pestá no lado esquerdo da linha:
e2
e1
O produto vetorial (p− s1)×(p− s2) nos diz a localização do pontop. Se o produto vetorial
for positivo,pestá localizado no lado esquerdo e, se o produto vetorial for negativo,pestá
localizado no lado direito. Finalmente, se o produto vetorial for zero, os pontos e1,e2ep
estão na mesma linha.
268
Intersecção de segmento de reta
e
b
c
um
Neste caso, podemos usar produtos cruzados para verificar se todos os pontos estão na
mesma linha. Depois disso, podemos ordenar os pontos e verificar se os segmentos de linha se
sobrepõem.
Caso 2:Os segmentos de reta têm um vértice comum que é o único ponto de
intersecção. Por exemplo, na figura a seguir o ponto de intersecção éb = c:
b=c
um
um
Outra característica dos produtos cruzados é que a área de um triângulo pode ser calculada
usando a fórmula
|(uma-c)×(b- c)|
,
2
269
ondeum,becsão os vértices do triângulo. Usando esse fato, podemos derivar uma
fórmula para calcular a menor distância entre um ponto e uma reta. Por exemplo,
na figura a seguireé a menor distância entre o pontop e a linha que é definida
pelos pontose1ee2:
p
e2
e1
um
um
270
Área do polígono
(2,4)
(4,3) (7,3)
(4,1)
é
|(2·5−5·4)+(5·3−7·5)+(7·1−4·3)+(4·3−4·1)+(4·4−2·3)|
=17/2.
2
A ideia da fórmula é percorrer trapézios cujo um lado é um lado do polígono e
o outro lado está na linha horizontale =0. Por exemplo:
(5,5)
(2,4)
(4,3) (7,3)
(4,1)
271
Teorema de Pick
Teorema de Pickfornece outra maneira de calcular a área de um polígono, desde que
todos os vértices do polígono tenham coordenadas inteiras. De acordo com o teorema
de Pick, a área do polígono é
um + b/2−1,
(2,4)
(4,3) (7,3)
(4,1)
é 6+7/2−1=17/2.
Funções de distância
UMfunção de distânciadefine a distância entre dois pontos. A função de distância
usual é aDistância euclidianaonde a distância entre os pontos (x1,e1) e (x2,e2) é
√
(x2−x1)2+(e2−e1)2.
Uma função de distância alternativa é aDistância de Manhattanonde a distância
entre os pontos (x1,e1) e (x2,e2) é
|x1−x2|+|e1−e2|.
Por exemplo, considere a seguinte imagem:
(5, 2) (5, 2)
(2, 1) (2, 1)
272
Distância euclidiana Distância de Manhattan
Coordenadas rotativas
Alguns problemas são mais fáceis de resolver se as distâncias de Manhattan forem usadas
em vez das distâncias euclidianas. Como exemplo, considere um problema em que nos são
dadasnão pontos no plano bidimensional e nossa tarefa é calcular a distância máxima de
Manhattan entre quaisquer dois pontos.
Por exemplo, considere o seguinte conjunto de pontos:
C
UM
E
B
C
UM
E
B
UM
C
B
E
273
UM
C
B
E
|1−3|+|0−3| =máx(|1−6|,|-1−0|)=5.
274
Capítulo 30
John
Maria
Peter
Lisa
275
John
Maria
Peter
Lisa
++ + −−+−−
12 3 21210
Pontos de intersecção
É fácil resolver o problema emO(não2) tempo, porque podemos percorrer todos os pares possíveis de
segmentos de reta e verificar se eles se cruzam. No entanto, podemos resolver o problema de forma mais
eficiente emO(nãoregistronão) tempo usando um algoritmo de linha de varredura e uma estrutura de dados
de consulta de intervalo.
A ideia é processar os pontos finais dos segmentos de linha da esquerda para a direita
e focar em três tipos de eventos:
276
Os seguintes eventos correspondem ao exemplo:
1 2
3 3
1 2
1 2
Passamos pelos eventos da esquerda para a direita e usamos uma estrutura de dados
que mantém um conjunto de coordenadas y onde há um segmento horizontal ativo. No
evento 1, adicionamos a coordenada y do segmento ao conjunto, e no evento 2,
removemos a coordenada y do conjunto.
Os pontos de intersecção são calculados no evento 3. Quando há um segmento
vertical entre os pontose1ee2, contamos o número de segmentos horizontais ativos
cuja coordenada y está entree1ee2, e adicione esse número ao número total de pontos
de intersecção.
Para armazenar coordenadas y de segmentos horizontais, podemos usar uma árvore indexada binária
ou de segmento, possivelmente com compressão de índice. Quando tais estruturas são usadas, o
processamento de cada evento levaO(registronão) tempo, então o tempo total de execução do algoritmo éO(
nãoregistronão).
Dado um conjunto denãopontos, nosso próximo problema é encontrar dois pontos cuja
distância euclidiana seja mínima. Por exemplo, se os pontos são
Este é outro exemplo de um problema que pode ser resolvido emO(nãoregistronão) tempo
usando um algoritmo de linha de varredura1. Passamos pelos pontos da esquerda para a direita
e mantemos um valore: a distância mínima entre dois pontos vistos até agora. Em
1Além desta abordagem, existe também umaO(nãoregistronão) algoritmo de divisão e conquista do tempo [56] que
divide os pontos em dois conjuntos e resolve recursivamente o problema para ambos os conjuntos.
277
cada ponto, encontramos o ponto mais próximo à esquerda. Se a distância for menor
quee, é a nova distância mínima e atualizamos o valor dee.
Se o ponto atual for (x,e) e há um ponto à esquerda a uma distância menor que
e, a coordenada x de tal ponto deve estar entre [x−d,x] e a coordenada y deve estar
entre [e-d,e + d]. Assim, basta considerar apenas os pontos que estão localizados
nesses intervalos, o que torna o algoritmo eficiente.
Por exemplo, na figura a seguir, a região marcada com linhas tracejadas
contém os pontos que podem estar a uma distância deedo ponto ativo:
UMcasco convexoé o menor polígono convexo que contém todos os pontos de um dado conjunto.
Convexidade significa que um segmento de reta entre quaisquer dois vértices do polígono está
completamente dentro do polígono.
Por exemplo, para os pontos
278
Algoritmo de Andrew[3] fornece uma maneira fácil de construir o casco convexo para um
conjunto de pontos emO(nãoregistronão) tempo. O algoritmo primeiro localiza os pontos mais à
esquerda e mais à direita, e então constrói o casco convexo em duas partes: primeiro o casco
superior e então o casco inferior. Ambas as partes são similares, então podemos focar na
construção do casco superior.
Primeiro, classificamos os pontos principalmente de acordo com as coordenadas x e,
secundariamente, de acordo com as coordenadas y. Depois disso, passamos pelos pontos e
adicionamos cada ponto ao casco. Sempre depois de adicionar um ponto ao casco, garantimos
que o último segmento de linha no casco não vire à esquerda. Enquanto ele virar à esquerda,
removemos repetidamente o segundo último ponto do casco.
As imagens a seguir mostram como o algoritmo de Andrew funciona:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
279
280
Bibliografia
[3] AM Andrew. Outro algoritmo eficiente para cascos convexos em duas dimensões. Cartas
de Processamento de Informações, 9(5):216–219, 1979.
[9] J. Bentley e D. Wood. Um algoritmo de pior caso ideal para relatar interseções
de retâ[Link]ções IEEE em computadores, C-29(7):571–577, 1980.
281
[14] EW Dijkstra. Uma nota sobre dois problemas em conexão com gráficos.
Matemática Numérica, 1(1):269–271, 1959.
[20] D. Fanding. Um algoritmo mais rápido para o caminho mais curto – [Link] da
Universidade Southwest Jiaotong, 2, 1994.
[21] PM Fenwick. Uma nova estrutura de dados para tabelas de frequência cumulativa.
Software: Prática e Experiência, 24(3):327–336, 1994.
[24] LR Ford. Teoria do fluxo de rede. RAND Corporation, Santa Monica, Califórnia,
1956.
[26] R. Freivalds. Máquinas probabilísticas podem usar menos tempo de execução. EmCongresso
IFIP, 839–842, 1977.
282
[30] A. Grønlund e S. Pettie. Trios, degenerados e triângulos amorosos. EmAnais do
55º Simpósio Anual sobre Fundamentos da Ciência da Computação, 621–630,
2014.
283
[47] DE Knuth.A Arte da Programação de Computadores. Volume 3: Classificação e
Pesquisa, Addison–Wesley, 1998 (2ª edição).
[51] J. Pachocki e J. Radoszewski. Onde usar e como não usar hash de string
[Link]íadas em Informática, 7(1):90–100, 2013.
[60] SZKOpuł,[Link]
[64] RE Tarjan. Eficiência de um algoritmo de união de conjuntos bom, mas não [Link]
da ACM, 22(2):215–225, 1975.
284
[65] RE Tarjan. Aplicações de compressão de caminho em árvores [Link]
da ACM, 26(4):690–715, 1979.
285
286