Embed Size (px)
Citation preview
Questões de Divisão e Conquista
1. Potência de inteiros
Certo ou errado? O algoritmo abaixo Pot(n,k) calcula nk, para n e k inteiros.
Sua complexidade é O(k):
Pot(n, k):
se (k = 0):
retornar 1
senão se (k é par):
retornar Pot(n,k/2)*Pot(n/k2)
senão:
retornar n*Pot(n,k/2)*Pot(n,k/2)
2. Seqüência de Farey
Uma fração h/k é dita “própria” se ela situa-se entre 0 e 1 e se h e k não
possuem fatores comuns. Para um inteiro n ≥ 1, a Sequência de Farey de
ordem n, Fn, é a sequência das frações próprias cujos denominadores não
excedem 1, incluindo-se as “frações” 0/1 e 1/1, em ordem crescente. Por
exemplo, F5 é a sequência:
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
O aluno Davi Barreto descobriu uma forma recursiva interessante de criar a
seqüência, para n > 2. Começa-se com as frações 0/1 1/2 1/1, e
seleciona-se a fração 1/2.
Recursivamente, cria-se, primeiro à esquerda e depois à direita da fração
selecionada, uma nova fração. A fração criada à esquerda , tem o numerador
obtido pela soma do numerador da fração selecionada com o numerador da
fração anterior na sequência, até o momento. O denominador é obtido de
forma semelhante. A fração da direita é obtida pela operação análoga entre a
fração selecionada e a próxima fração da sequência, até o momento. As novas
frações só são criadas se o denominador calculado for menor ou igual a n.
Após a criação de cada uma dessas frações, aplica-se a mesma operação a
cada uma delas. a) Escrever um algoritmo para criar a seqüência
3. Solução do Gustavo para Torneio
O aluno Gustavo Ribeiro inventou uma solução especial para a tabela de
Torneio, quando n é um quadrado ímpar (9, 25,...). Nessa solução,
trabalha-se com grupos de k elementos (k = n1/2). Escreve-se a tabela
básica para k. Em seguida, substitui-se cada número da coluna 1 por uma
matriz kx1, contendo os números do grupo k. No restante da matriz, cada
número é substituido por uma permutação circular adequada dos elementos
do grupo e o “bye” é substituído pela solução básica de emparelhamento do
próprio grupo. Exemplificar essa solução para n = 9 e argumentar que ela é
correta.
4. Seleção
Quer-se selecionar o k-ésimo menor elemento de um conjunto de números.
Escrever um algoritmo recursivo, baseado no procedimento de partição usado
no Quicksort, para fazer essa seleção.
5. 2 Moedas Falsas
Tem-se n moedas numeradas de 1 a n. O peso de uma moeda normal é k.
Sabe-se que duas das moedas são falsas e pesam k+1 cada uma. Quer-se
descobrir as moedas falsas com um número de pesagens pequeno, O(log n).
Você dispõe de uma balança eletrônica que dá o peso de uma seqüência de
moedas. Ao executar o Procedimento Peso(i1, i
2), um mecanismo coloca a
seqüência de moedas de números i1
a i2
na balança e retorna o peso dessas
moedas.
a) Escrever um algoritmo para fazer essa tarefa.
b) Argumentar que o número de pesagens é o desejado.
6. Busca por Faixa em árvores binárias de busca
Descrever uma solução recursiva para o problema de busca por faixa em uma
árvore binária de busca. Escrever o algoritmo correspondente e analisar sua
complexidade. Na busca por faixa são dados os valores iniciais e finais de um
intervalo (p, q) e quer-se listar, em ordem ascendente, todas as chaves da
árvore compreendidas entre esses dois valores (inclusive).
7. Torre de Hanói revisitada
Refazer o algoritmo para a torre de Hanoi, considerando que se tenha 4
varetas e não mais 3. Explicar a idéia recursiva utilizada e avaliar a
complexidade do algoritmo sugerido.
8. Azulejos
Dada uma parede de dimensões 2 x n, escrever as recorrência para calcular
T(n) = número de maneiras distintas para azulejar essa parede, usando:
a) apenas azulejos de dimensões 2 x 1. b) azulejos de dimensões 2 x 1 ou 2 x 2.
Por exemplo, para o caso a), T(2) = 2 e T(8) = 34. Já, para o caso b),
T(2) = 3 e T(8) = 171 .
9. Potência de Matrizes
Em inúmeras aplicações matemáticas, é necessário calcular Mk a potência k
de uma matriz M(n x n), com k inteiro. Escrever um algoritmo recursivo
para fazer esse cálculo e determinar a complexidade do algoritmo.
Evidentemente, deseja-se um algoritmo com complexidade inferior a k.n3.
10. Sequências de 1’s
Escrever a recorrência e o correspondente algoritmo de Programação
Dinâmica para a solução do seguinte problema: Determinar a quantidade de
strings de bits de tamanho n onde não existem 2 ou mais bits 1 em sequência.
Ex: para n = 3, T(3) = 5, correspondendo aos strings 000, 001, 010, 100,
101.Dica: formular a recorrência considerando a terminação dos strings do
tipo procurado.
11. Maior retângulo
Tem-se uma praça retangular, cujas coordenadas do ponto inferior esquerdo
são (0,0) e do canto superior direito (L,C) e três árvores no meio da praça,
simplificadamente representadas pelos pontos p1(X1, Y1), p2(X2,Y2) e
P3(X3,Y3). Quer-se construir uma quadra de tênis que seja o maior retângulo
possível, com lados paralelos aos eixos, e que não contenha nenhuma árvore
dentro.
Descrever uma idéia para resolver o problema por divisão e conquista. Em
seguida, escrever o algoritmo correspondente.
Dica: Um ponto dentro de um retângulo redefine problemas menores de
mesma natureza de que forma?
12. Par de pontos mais próximos no plano
Tem-se n pontos (xi, y
i), 1 ≤ i ≤ n, no plano, já ordenados pela coordenada x.
Explique como seria uma abordagem de divisão e conquista para determinar o
par de pontos mais próximos desse conjunto. Não precisa escrever o
algoritmo.
13. Bipartição de Conjuntos.
Dado um conjunto S de números 1 a n, uma bipartição de S é a realocação de
seus elementos em dois subconjuntos não vazios. Por exemplo, para S = {1,2,3},
as bipartições distintas são {{1}{2, 3}} {{1,2} {3}} e {{1, 3}, {2}}.
a) Escrever a recorrência que calcula o número de bipartições distintas de S.
Explicar a recorrência.
b) Escrever um algoritmo recursivo com memorização para esse problema.
14. Quadrados de Feynman
Feynman, um físico famoso que gostava de quebra-cabeças, propôs o seguinte
problema: determinar T(n), o número de quadrados distintos em um grid n x n
formados de quadradinhos 1 x 1. O exemplo abaixo mostra que T(2) = 5.
a) Escrever a recorrência que calcula T(n).
b) Escrever um algoritmo de Divisão e Conquista com memorização para
calcular T(n).
15. Gray Code refletido
Um Gray Code para n bits é uma sequência de todas as 2n codificações
distintas com n bits, tal que um termo da sequência somente difere do anterior
em 1 bit. A primeira coluna da tabela abaixo mostra um GC para n = 2 e a
última, um GC para n = 3. Para n=1, o código é 0 1.
GC p/ n=2 GC p/ n = 3 00 000 000 000 01 001 001 001 11 011 011 011 10 010 010 010 010 110 011 111 001 101 000 100
Um Gray Code refletido para n bits é obtido do Gray Code para n-1 bits.
Acrescenta-se, inicialmente 0 antes de todos elemento, refle-se esse código e
depois troca-se o primeiro 0 por 1 na segunda metade. As colunas 2 a 4
mostram como obter GC p/ n = 3 a partir de um para n = 2. Escrever um
algoritmo recursivo para criar um Gray Code refletido para n bits.
16. Fibonacci por matriz
O n-ésimo (n > 0) termo da série de Fibonacci pode ser calculado através da
seguinte expressão, envolvendo matrizes:
(Fib(n) Fib(n-1)) = (1 0) x Mn-1 , onde M é a matriz 2 x 2:
M = 1 1
1 0
Escrever um algoritmo com complexidade O(log n) para calcular Fib(n).
Dica: usar a mesma idéia do exercício mostrado para potenciação de inteiros.
17. Pista de esquí
As alturas dos pontos de uma pista de esqui estão representadas em um
matriz n x n. Escrever um algoritmo de divisão e conquista que descobre qual
tamanho do maior percurso de descida. Em um percurso de descida, a
sequência de alturas têm que ser decrescentes. Suponha que se pode
movimentar na matriz apenas pelos pontos cardeais (N,S,L,O). Por exemplo, na
matriz 3 x 3 abaixo, o maior intinerário de descida tem tamanho 6 (10 9 8 7 6
5).
9 8 4 10 7 6 5 11 5
Dicas: 1. O problema infantil da recorrência é um ponto cujos vizinhos são todos
maiores que ele. O percurso de descida que começa nesse ponto tem valor 1. 2. Considere que a matriz tem duas linhas e duas colunas suplementares, nas
bordas da matriz, cuja altura é ∞∞.
18. Contagem de inversões.
O número de inversões de uma sequência é a soma, para cada elemento, do
número de elementos menores à sua direita. Por exemplo, a sequência B A D C
tem 2 inversões ( A depois de B e C depois de D). A contagem de inversões
pode ser feita usando o MERGESORT, durante os merges. Reescrever o
Mergesort para fazer essa contagem.
Questões de Programação Dinâmica
1. Partição de conjuntos
O número de maneiras distintas para se particionar um conjunto com n itens
distintos em exatamente k subconjuntos não vazios, T(n,k) é dado pela
recorrência:
T(n,k) = 0, se (n < k); T(n,k) = 1, se (k = 1);
T(n,k) = k.T(n-1,k) + T(n-1,k-1), se (k > 1);
Exemplo: T(4,3) = 6, correspondendo às partições: {{1},{2},{3,4}},
{{1},{2,3},{4}}, {{1},{2,4},{3}}, {{1,2},{3},{4}}, {{1,3},{2},{4}}, {{1,4},{2},{3}}.
a) Explicar a recorrência acima.
b) Escrever um algoritmo de Programação Dinâmica para calcular T(n,n).
2. Quadrados
Todo numero inteiro N maior que 1 pode ser escrito como a soma de
quadrados de números menores. Escrever um algoritmo de Programação
Dinâmica que descobre o menor número de termos nessa soma.
Ex: N = 4, 1 termo; N = 50, 2 termos; N = 3, 3 termos.
3. Percurso em Matriz
Considere uma matriz M(a x b) contendo inteiros e o seguinte jogo: você
começa na posição (x,1) e anda para a direita até chegar na última coluna da
matriz. Se você está na posição (x,y), então você pode passar para uma das
posições (x+1,y-1), (x+1,y), (x+1,y+1), se existirem. Em cada posição que
passa, recolhe o valor da mesma. Quer-se saber o maior valor que você
consegue quando chega no final do percurso.
a) Escreva um algoritmo de PD para resolver o problema.
b) Exemplifique na matriz 4 x 8 abaixo, começando no ponto (x,1), com
x = (NLPN mod 4 +1,1).
8 0 -3 15 -2 8 3 1
7 4 -4 5 8 3 -2 0
3 9 -1 4 7 0 -1 9
-1 6 0 1 2 -6 2 4
4. Salada de frutas.
Suponha que em um cesto existam n tipos de frutas, com as quantidades de
cada fruta expressas em um vetor F[1..n]. Escrever um algoritmo de
Programação Dinâmica que calcula quantas saladas de frutas distintas podem
ser feitas usando-se t frutas. (Duas saladas são diferentes se a quantidade de
qualquer fruta for diferente nas duas saladas).
Dica: Usar uma matriz C(txn), onde C(i,j) = solução do problema para t=i e n = j.
Exemplificar o algoritmo para t = 8 e n = 4, F= [2, 2, 3, 4].
5. Viagem
Suponha que uma matriz D(n x n) guarde os custos de viagens entre todos os
pares das n cidades de um país. Você quer fazer uma viagem da cidade A
para a cidade B, mas quer parar em alguma cidade diferente C no caminho.
Escreva um algoritmo para, dada a matriz D, as cidades A e B, escolher qual
deve ser a cidade C para o custo total da viagem ser mínimo. Justificar seu
algoritmo.
6. Número de soluções da Mochila
Escrever um algoritmo que determina, para cada valor de mochila, de 1 a M, o
número de soluções distintas. Existem q ítens com pesos dados no vetor W.
Ex com M=12, 4 ítens 2, 3, 2, 5
0 1 2 3 4 5 6 7 8 9 10 11 12
1 0 0 0 0 0 0 0 0 0 0 0 0
2 1 0 1 0 0 0 0 0 0 0 0 0 0
3 1 0 1 1 0 1 0 0 0 0 0 0 0
2 1 0 2 1 1 2 0 1 0 0 0 0 0
5 1 0 2 1 1 3 0 3 1 1 2 0 1
7. Corte de tronco
Um tronco de tamanho n deve ser dividido em tamanhos t1, t
2, ... tk, dados. O
custo de cada corte é proporcional ao tamanho do tronco. Escreva um
algoritmo indicando a melhor seqüência de cortes, para que se tenha custo
mínimo no processo.
8. Azulejos II
Quer-se azulejar uma parede de tamanho 2 x n, estando disponíveis
quantidades ilimitadas dos 2 tipos de azulejos seguintes. O primeiro é um
retângulo 1x2, o segundo é um trominó 2x1 (retângulo 2x2 sem um dos
quadradinhos).
a) Escrever a recorrência que calcula T(n) = número de maneiras
distintas de azulejar uma parede 2 x n, usando os 2 tipos de azulejos.
(Dica: considerar 2 recorrências interligadas: T(n) = como desejamos, ou
seja, paredes terminadas de forma lisa; T1(n) = paredes que terminam
com um trominó. Esta contagem é auxiliar, apenas).
b) Escrever um algoritmo de Programação Dinâmica(PD) para calcular
T(n).
c) Preencher a tabela de PD para n = 7.
9. Comboio
Um conjunto com n carros está em uma fila para atravessar uma ponte que
suporta no máximo dois carros de cada vez. São dados os tempos de
travessia dos carros (dois carros atravessando levam o tempo total do mais
lento). Determinar o tempo mínimo de travessia do conjunto, dados os tempos
de travessia de cada carro.
Ex: N = 10, e tempos de travessia como no vetor D:
1 2 3 4 5 6 7 8 9 10
5 10 9 2 3 7 6 5 9 2
21. Partição Monotônica de Inteiros
Uma partição monotônica de um inteiro n é uma forma de escrever n como
soma de números positivos distintos. Quer-se determinar T(n,n) = número de
maneiras distintas de fazer partições monotônicas para dado inteiro n.
a) Reescrever a recorrência da Partição de Inteiros estudada, para
considerar apenas o caso de partições monotônicas.
b) Reescrever o algoritmo de Programação Dinâmica correspondente.
Dica: observe que T(1,1) = 1; T(2,2) = 1; T(3,3) = 2; T(4,4) = 2; T(10,10) =
10.
22. Mochila com ítens alternativos
Considere o seguinte problema: tem-se t cartas, onde, em cada lado está
escrito um número distinto. Quer-se saber se é possível obter um valor M
usando combinações das cartas, mas só podendo usar um dos dois lados de
cada carta. Modifique o algoritmo da Mochila em vetor para resolver esse
problema:
Mochila():
K[0] ←← 0
para j ←← 1 até M incl.:
K[j] ←← -1
para i ←← 1 até t incl:
para j ←← M..P[i] incl.:
se ( K[j] = -1 e K[j-P[i]] ≥ 0 ):
K[j] ←← i
Mostrar o resultado do seu algoritmo para M=10 e o seguinte conjunto de 3
cartas: {(2, 5), {3, 6), (3, 9)}.
23. Recorrência 1
Considere a seguinte recorrência:
a) T(i, j) = 1, se i=0 ou j=0
b) T(i, j) = T(i+1, j-1) + T(i-1, j), se i > 0 e j > 0
Escreva um algoritmo de PD para calcular T(n, p).
24. Mochila com ítnes negativos
Considere o algoritmo para preenchimento da Mochila (0/1), em vetor:
Mochila():
K[0] ←← 0
para j ←← 1 até M incl.:
K[j] ←← -1
para i ←← 1 até t incl:
para j ←← M..P[i] incl.:
se ( K[j] = -1 e K[j-P[i]] ≥ 0 ):
K[j] ←← i
Explicar como modificar o algoritmo se quisermos considerar a possibilidade de
haver também pesos negativos. Considere que os pesos estão inversamente
ordenados (isto é, os negativos são os últimos a serem considerados).
Justificar o algoritmo.
25. Recorrência 2
Considere a seguinte recorrência:
a) T(, 0) = 1
b) T(0, p) = 0, se p > 0
c) T(n, p) = T(n-1, p+1) + T(n+1, p-1), n > 0, p > 0
É possível implementar essa recorrência com Programação Dinâmica? Explicar.
26. Troco facilitado
Considere um país com 6 tipos de moeda que valem 100, 50, 25, 10, 5 e 1,
respectivamente Suponha que você fez uma compra e pode facilitar o troco
para o vendedor, passando algumas moedas para ele. Tanto você quanto ele
dispõem de um número ilimitado de moedas de qualquer tipo. Escrever um
algoritmo para, dado um valor n, entre 1 e 1000, indicar o menor número de
moedas envolvidas em uma operação desse tipo. Por exemplo, se n = 95, o menor número de moedas envolvidas é 2, ou seja,
você dá uma moeda de 5 e recebe uma moeda de 100 como troco.
27. Particionamento de uma cadeia de dígitos decimais
Considere uma cadeia com 8 dígitos decimais, que deve ser particionada em
três partes tal que cada parte tenha pelo menos 1 dígito e a soma dos
números gerados seja máxima. Note que o particionamento pode gerar números
com zeros à esquerda
a) Escrever uma recorrência para a otimização. b) Escrever um algoritmo de PD para resolver o problema.
EX: 02300000 deve ser particionado com 0, 2, 300000, com soma 300002.
28. Jogo Matemático.
Dados n números inteiros, descobrir se existe uma expressão especial entre os
(n-1) primeiros, cujo resultado seja o último. Uma expressão especial é uma
expressão sem parêntesis, contendo somente os operadores binários + - * /,
que deve ser calculada da esquerda para a direita, sem prioridade especial de
operadores. O operador / funciona como o div do Pascal (divide e trunca).
Sabe-se também que nenhum resultado intermediário pode estar fora da faixa
–1000, 1000.
Ex: Dados 20 5 8 7 13, temos a expressão simples: 20*5-8/7 = 13.
Dica: Adaptar o algoritmo da Mochila.
29. Azulejos
Quer-se azulejar uma parede de tamanho 3 x n, estando disponíveis
quantidades ilimitadas dos 2 tipos de azulejos seguintes. O primeiro é um
retângulo 1x1, o segundo é um retângulo 2x2.
a) Escrever a recorrência que calcula T(n) = número de maneiras distintas
de azulejar uma parede 3 x n, usando os 2 tipos de azulejos.
b) Escrever um algoritmo de Programação Dinâmica(PD) para calcular T(n).
c) Preencher a tabela de PD para n = 7.
Questões de Guloso
1. Travessia
Tem-se n pessoas que querem atravessar uma ponte à noite, sendo que só
podem passar até 2 de cada vez. Só há uma lanterna, que é necessária para a
travessia. Cada pessoa leva um tempo distinto para a atravessar a ponte.
Escrever um algoritmo guloso que calcula o tempo total mínimo para a
travessia. Justificar o algoritmo.
Ex: Para n = 4, se os tempos individuais forem 10, 5, 2, 1, o tempo total mínimo
é 17; se forem 10, 10, 10, 1, o tempo mínimo é 32.
2. Abastecimento
Escrever um algoritmo guloso para a solução do seguinte problema:
"Dados n postos de gasolina, numerados de 1 a n, determinar o número mínimo
de paradas para abastecimento numa viagem que passa por todos os postos,
conhecendo-se as distâncias entre eles, o consumo e a capacidade do tanque
do carro e sabendo-se que a viagem começa no posto 1."
b) Argumentar que a solução é correta.
3. Seleção de Tarefas (problema do Paulo Vitor)
São dadas n tarefas unitárias que devem todas ser executadas por um único
processador. Para cada tarefa ti são dados 3 parâmetors: l
i, ri, p
i: lié a data
limite da mesma; rié a receita que será auferida se a tarefa for realizada até
a data limite; pi
é a penalidade que deverá ser paga pelo executor, caso a
tarefa não seja realizada até a data limite (se isso ocorrer ele não recebe a
receita e ainda paga a penalidade).
a) Escrever um algoritmo guloso que obtem a maior diferença entre as
receitas e as penalidades.
b) justificar que a solução gulosoa está correta.
4. Prestador de serviços.
Um prestador de serviços tem N tarefas para realizar. Para cada tarefa
são dadas duas informações: o tempo para sua realização (em dias) e uma
multa diária que o prestador de serviços tem que pagar para os dias
anteriores ao começo da tarefa. Em cada dia o prestador de serviços só
pode trabalhar em uma tarefa.
a) Escrever um algoritmo guloso que determina a menor multa total que o
prestador de serviços terá que pagar.
b) Argumentar que a solução do problema é gulosa.
Ex: Para N = 2, informações respectivas 2/5, 2/4, a multa mínima total
é 8.
5. Corte de chapa em quadrados
Quer-se cortar uma chapa retangular, de dimensões n x m, em quadrados 1x1
ou 2x2, tal que se tenha o menor número de quadrados possível. Veja o exemplo
para n = 3, m = 3, cujo número de quadrados é 6.
a) Descreva um algoritmo guloso para, dados n e m, determinar o número
mínimo de quadrados 1x1 e 2x2 possível.
b) Argumente que seu algoritmo está correto.
6. Prestador de serviços.
Um prestador de serviços tem N tarefas para realizar. Para cada tarefa são dadas duas
informações: o tempo para sua realização (em dias) e uma multa diária que o prestador de
serviços tem que pagar para os dias anteriores ao começo da tarefa. Em cada dia o
prestador de serviços só pode trabalhar em uma tarefa.
a) Escrever um algoritmo guloso que determina a menor multa total que o prestador de
serviços terá que pagar.
b) Argumentar que a solução do problema é gulosa.
Ex: Para N = 2, informações respectivas 2/5, 2/4, a multa mínima total é 8.
7. Batalhão.
Um batalhão com N soldados, comandados por um único oficial, tem que
executar N tarefas, cada uma delas sob a responsabilidade de um soldado
e cada uma independente das demais. Para a execução da tarefa, cada
soldado tem que ser treinado pelo comandante e, após o treinamento, pode
iniciar a tarefa. Para cada soldado são dados o tempo de treinamento e a
duração de sua tarefa.
a) Escrever um algoritmo guloso que determina o menor tempo possível para
executar todo o conjunto de tarefas. b) Argumentar que a solução do problema é gulosa.
Ex: Para N = 3, tempos 2/5, 3/2, 2/1, o tempo minimo é 8.
8. Cobertura por trechos unitários
Tem-se um segmento base sb = (0, n) e n segmentos s1...sn, cada s
i= (c
i, fi),
com 0 ≤ci< f
i≤ n, todos os valores inteiros. Quer-se saber se é possível e
como cobrir o segmento base com os segmentos dados, tal que cada um deles
cubra apenas uma parte de tamanho unitário. Escrever um algoritmo guloso
para fazer essa tarefa.
Por exemplo, se sb = (0, 4), s1= (1,3), s
2= (2,3), s
3= (0,4), s
4= (3, 4), é possível
cobrir sb, e a cobertura dos trechos unitários (0,1), ...(3,4) é, respectivamente,
a seguinte {s3, s1, s2, s4}.
Argumentar que o algoritmo está correto.
9. Corte de chapas
Uma máquina de corte tem capacidade para cortar até p chapas empilhadas e
faz apenas um corte reto de cada vez. O problema de determinar o número
mínimo de cortes para que uma chapa retangular com dimensões n x m seja
transformada em n.m quadrados de lado 1 pode ser resolvido de forma gulosa,
escolhendo-se para corte, a cada passo, as p chapas de maior área e
cortando-as aproximadamente ao meio.
Argumente que este enfoque guloso resolve corretamente o problema dado. Ex:
para uma chapa 5x6, com p = 5, são necessários 8 cortes.
10. Compra de produtos calóricos
Uma pessoa dispõe de n reais para comprar a maior quantidade possível de
calorias. Alguns dos produtos são vendidos por ítem e outros a granel. Cada
produto tem um preço pi
e um valor calórico viassociados, além do tipo de
venda, ti, é claro. Escrever um algoritmo que fornece o máximo desejado.
Justificar o algoritmo.
Ex: n = 13 item: (5, 15) (3, 3) granel (4, 8), (6,11)
0 1 2 3 4 5 6 7 8 9 10 11 12 13
5,10 0 0 0 0 0 15 15 15 15 15 30 30 30 30
3,6 0 0 0 3 3 15 15 15 18 18 30 30 30 33
0 1 2 3 4 5 6 7 8 9 10 11 12 13
0 2 4 6 8 15 17 19 21 23 30 32 34 36
Ex: N = 4, 1 termo; N = 50, 2 termos; N = 3, 3 termos.
11. Tarefas com máquinas universais
Tem-se duas máquinas que podem realizar uma série de tipos tarefas (1 a n).
As tarefas têm todas duração de 1 dia. Quando cada máquina muda a tarefa a
realizar, é necessária uma grande preparação para a mudança, que deve ser
evitada sempre que possível. Dada uma sequência de m tarefas (indicadas pelo
seu tipo), onde cada uma vai ser executada em um dia diferente, quer-se saber
o número mínimo de trocas de tarefas no conjunto das máquinas para realizar
toda a sequência das tarefas. Observe que em cada dia apenas uma das
máquinas estará trabalhando.
No exemplo abaixo, apenas 1 troca é feita, quando a máquina 1 muda da tarefa
1 para a 2.
Tarefas(tipos) 1 3 3 3 2 3
Máquina 1 2 2 2 1 2
a) Escreva um algoritmo guloso para o problema.
b) Argumente que a solução está correta.
12. Compra de ações
Suponha que você tenha 1000 reais e vai aplicar na Bolsa de Valores numa
determinada empresa, comprando e vendendo ações dessa empresa dentro de
determinado período. Suponha também que não há despesas para a compra e
venda de ações. Dadas as cotações diárias das ação dessa empresa no período,
considere o algoritmo para determinar o maior lucro possível que você poderia
ter feito no período.
a) descreva uma solução para o problema e argumente que a solução é gulosa.
b) Mostre que, para um período de 10 dias com as as seguintes cotações você
teria um lucro máximo de 5000 reais.
1 2 3 4 5 6 7 8 9 10
0 5 10 15 20 15 10 15 10 5
13. Parafusagem de placas
São dadas n placas já posicionadas em um telhado e quer-se parafusar todas
essas placas de maneira a formar um conjunto único. Para cada placa são
informadas as posições dos seus extremos. Suponha que cada parafuso pode
ser usado para juntar várias placas e que esse parafuso tenha largura
desprezível.
a)Escrever um algoritmo guloso para determinar o número mínimo de parafusos
a serem colocados para fazer essa tarefa.
b) Justificar sua solução.
Veja no exemplo que, para as l placas (1, 3), (4,6), (7,9), (2,8) são necessários 3
parafusos.
14. Foco.
Quer-se fazer fotos de uma cena com vários objetos. A cena desenrola-se ao
longo de um eixo horizontal. Cada objeto da cena só fica nítido se o centro da
foto estiver dentro de um intervalo desse eixo. Você quer tirar o menor
número de fotos para obter todos os objetos corretamente focados. Por
exemplo, se tivermos 3 objetos com intervalos de foco (1, 4), (2,5) e (5, 7),
basta tirar duas fotos. A primeira com centro do foco em qualquer ponto do
intervalo (2,4), conseguindo focar os dois primeiros objetos e a segunda com
centro em qualquer ponto do intervalo (5,7), focando o terceiro. Dados n
objetos e seus intervalos de foco, escrever um algoritmo guloso que
determina o menor número de fotos a serem tiradas para obter todos os
objetos em foco.
Justificar que seu algoritmo pode ser guloso.
15. Sequência NDNC
Fazer um algoritmo que constrói uma sequência NDNC com n números dados.
Analisar a complexidade do algoritmo e provar que ele está correto. Numa
sequência NDNC os números de índice ímpar formam uma sequência não
decrescente e os de índice par, uma sequência não crescente. Além disso, a
soma dos números de índice ímpar é maior ou igual à soma dos números de
índice par. Ex: 2 10 8 -1.
16. Seqüência antimonotônica.
Dada uma seqüência de números positivos inteiros S = {s1, s
2, ... sn}, uma
subseqüência A de S é uma sequência de elementos retirados de S, mantendo
a ordem relativa dos mesmos. A subseqüência A = {a1, a
2, ... an}, é dita
antimonotônica se ela tiver 1 ou 2 elementos ou, quando tiver mais que 2
elementos, e tormarmos quaisquer três elementos consecutivos de A, ai, a
i+1,
ai+2, temos uma das seguintes relações:
a) ai < ai+1 > ai+2, ou
b) ai > ai+1 < ai+2
Por exemplo, dada S = { 5, 4, 2, 6}, temos as subseqüências antimonotônicas:
{5}, {4}, {2}, {6}, {5,4}, {5,2}, {5,6}, {4,2}, {4,6}, {2,6}, {5,4,6}, {5,2,6}, {4,2,6} .
a) Mostrar uma subseqüência antimonotônica de tamanho máximo para cada um
dos seguintes casos: {5, 4, 3, 2, 1}, {1, 2, 3, 4, 5}, {1, 5, 2, 4, 3}, {1, 2, 3, 5, 4}.
b) Escrever um algoritmo guloso para determinar o tamanho da maior
subseqüência antimonotônica de uma seqüência dada S, representada em um
vetor de n elementos.
c) Argumentar que o algoritmo desenvolvido está correto.
Questões de Backtracking
1. Partição de inteiros
Escrever um algoritmo (backtracking) que gera todas as partições para dado
inteiro n. Ex: Para n = 4, a saída é:
1 1 1 1
1 1 2
1 3
2 2
4
2. Quadrado
Dados n varetas de tamanhos inteiros, verificar se é possível formar um
quadrado juntando as varetas em quatro segmentos de mesmo tamanho e
usando todas as varetas.
3. Resta 1 Simplificado
Escrever um algoritmo que calcula o número mínimo de pinos restantes em um
jogo Resta 1 simplificado, dada uma configuração inicial. No jogo simplificado
existem 12 buracos em série, sendo que, na configuração inicial, podem
existir de 0 a 12 pinos em qualquer posição. A retirada de um pino é feita
quando um vizinho “pula” esse pino, indo ocupar um buraco. Para uma
configuração, os buracos serão representados por ‘-‘ e os pinos por ‘o’.
Exemplos: ‘-ooo---ooo--‘ -> 4; ‘oooooooooooo’ -> 12; ‘------------‘ -> 0;
‘oooooooooo-o’ -> 1
4. Permutações com repetições.
Modificar o algoritmo de Backtracking de geração de Permutações, para o caso
em que há elementos repetidos no conjunto. Neste caso, não devem ser
impressas permutações iguais.
Ex: para {2, 7, 2, 2} as permutações são: 2 2 2 7, 2 2 7 2, 2 7 2 2
e 7 2 2 2.
5. Bigger Square, please!
Fazer um algoritmo que exiba, para n inteiro, todas as somas de
quadrados de números inteiros menores que n cujo valor seja n2.
6. Quadrado mágico 4 x 4
Escrever um algoritmo, usando Backtracking, para gerar todos os
quadrados mágicos 5 x 5. Um quadrado mágico n x n, com n ímpar, é uma
matriz n x n, onde cada elemento é distinto e pertence ao intervalo (1,
n2), sendo constante tanto a soma dos elementos das linhas, quanto das
colunas e diagonais. Essa constante é igual a n(n2 + 1)/2.
7. Grupamentos
Escrever um algoritmo, usando Backtracking, para gerar todos os grupamentos
binários distintos de um conjunto de n elementos, com n par. Um grupamento
binário é o particionamento do conjunto em n/2 outros conjuntos, com 2
elementos cada. Veja a seguir todos os 15 grupamentos binários distintos para
o conjunto de 6 elementos, {A, B, C, D, E, F}:
{AB} {CD} {EF} , {AB} {CE} {DF} , {AB} {CF} {DE} ,
{AC} {BD} {EF} , {AC} {BE} {DF} , {AC} {BF} {DE} ,
{AD} {BC} {EF} , {AD} {BE} {CF} , {AD} {BF} {CE} ,
{AE} {BC} {DF} , {AE} {BD} {CF} , {AE} {BF} {CE} ,
{AF} {BC} {DE} , {AF} {BD} {CE} , {AF} {BE} {CD} .
Dica: gerar lexicograficamente o resultado, que é uma permutação dos
elementos. Notar que, neste caso, só é possível preencher as posições de
ordem ímpar da permutação (primeiros elementos de cada um dos n/2
conjuntos da partição) com apenas um elemento.
8. Árvore de Jogo
Construir, avaliando, a árvore de Jogo para a continuação do jogo da velha,
cuja situação está expressa no seguinte diagrama:
X 0
X
0
O computador joga com X e é a vez dele jogar. Para a construção da árvore,
fazer a poda alfa-beta que diminui, sensivelmente, o número de nós da árvore.
9. Subconjuntos com soma limitada
Dado um conjunto T com n inteiros e um valor s, escrever um algoritmo que
conta o número de subconjuntos de T cuja soma dos elementos é igual ou
inferior a s.
10. Jogo da Velha
Mostrar, através da árvore de jogo, que a seguinte configuração do jogo da
velha é vitoriosa para o computador (é a vez do computador jogar, x = jogada
do computador, o do oponente):
x
o
Você deve usar a poda de valor limite e pode representar as configurações de
forma agrupada, quando a resposta do computador for a mesma para todas as
configurações do grupo.
11. Jogo de Palitos com 2 colunas
Uma versão diferente do Jogo de Palitos estudado em sala é quando existem 2
filas de palitos, contendo n1
e n2
palitos, respectivamente. A mudança da
regra é que, a cada vez, só se pode tirar palitos de uma fila. As demais regras
permanecem as mesmas. Mostrar e avaliar a árvore de jogo para n1= 3 e n
2=
2. Usar memorização, podas de simetria e valor limite, ordenação de
opções e a simetria especial: T(p,q) = T(q,p), onde p e q são as quantidades
de palitos de cada uma das filas.
12. Recorrência para o Jogo de Palitos
A solução do problema dos palitos pode ser dada pela recorrência abaixo:
T(n) = 1, se 1≤≤ n ≤≤ 3. T(n) = max (-T(n-1), -T(n-2), -T(n-3))
Prove, por indução, que a solução dessa recorrência é:
T(n) = -1 se n for múltiplo de 4; T(n) = 1, caso contrário.
15. Cavalos pacíficos
Escreva um algoritmo de backtracking que obtenha o número máximo de
cavalos que se pode colocar em um tabuleiro de xadrez n x n, tal que os
cavalos não se ataquem.
16. Jogo da Matriz
O jogo da matriz é jogado em turnos entre João e Maria. A matriz n x n tem
números positivos e negativos. João escolhe uma linha e Maria uma coluna.
Maria paga a João o valor da intersecção escolhida. O jogo segue, sendo que
cada nova escolha tem que ser para linha ou coluna não escolhida
anteriormente. Supondo que os dois jogadores joguem bem, quer-se saber
quanto João recebe no final (ou paga para Maria, caso o total seja negativo).
Esse problema tem uma solução por árvore de jogo, mas tem outra solução
examinando-se permutações de n elementos. Explique como é esta solução,
escreva o algoritmo e mostre o resultado ótimo na matriz abaixo, 3 x 3.
7 -9 1 2 5 -4 3 6 8
17. Jogo de Euclides
Criar e avaliar a árvore de jogo para o seguinte jogo de turnos: são dados dois
números a e b. A cada turno um jogador subtrai do maior número um múltiplo
do menor, desde que o resultado não seja negativo. O maior número é
substituído pela diferença. Ganha quem conseguir o número zero primeiro.
Por exemplo, para a = 12 e b = 7, uma seqüência do jogo poderia ter sido:
12 7
7 5
5 2
3 2
2 1
1 0 (neste caso ganha o primeiro jogador).
Usar a = 20 b = 6 + NLN mod 4 (NLN = número de letras do nome
completo).
18. Codificação binária
Escrever um algoritmo de Backtracking para gerar todas as configurações
binárias distintas com n bits, tendo exatamente p bits 0, para n e p dados.
Ex: para n = 4 e p = 2, a saída é:
0011, 0101, 0110, 1001, 1010, 1100.
19. Jogo de palitos com duas colunas
Considere o jogo de Palitos com duas colunas, uma delas contendo n1 palitos e
a outra n2, tal que, a cada rodada, o jogador da vez tem que retirar de 1 a 3
palitos de uma das colunas, vencendo aquele que retirar os últimos palitos.
Prove, usando indução finita e qualquer recurso de árvore de jogo, que o
primeiro jogador perde quando |n1- n
2| é divisível por 4 e ganha nos outros
casos.
QUESTÕES DE CERTO/ERRADO
Responder C(Certo) ou E(Errado), sendo que cada resposta errada anula uma
certa.
1.( ) Podemos fazer um algoritmo por Backtracking para resolver o problema
Torneio, mas sua complexidade é maior que a do algoritmo por Divisão e
Conquista.
2.( ) Em uma árvore de Huffman, se o símbolo A tem frequência maior que a
do símbolo B, então A está sempre em uma folha mais próxima da raiz que a da
folha de B.
3.( ) O Merge Ótimo entre 4 arquivos de tamanhos 300, 400, 500 e 600,
respectivamente, executa 3600 operações.
4.( ) A solução do problema Troco Mínimo usando um conjunto de 3 moedas
com valores {1, 7, 22} pode ser gulosa.
5.( ) Quando todas as chaves em um vetor são iguais, o Quicksort faz O(n)
comparações para ordenar esse vetor.
6.( ) Para encontrar uma solução (não necessariamente a ótima) para o
problema da Torre de Hanoi com n discos e 4 varetas (ao invés de 3), podemos
usar a seguinte ideia recursiva:
a) Se (n ≤ 3) o problema pode ser resolvido diretamente.
b) Se (n > 3) Então:
b.1) Leva n/2 discos da vareta 1 para a vareta 2, usando as 4
varetas como armazenamento temporário.
b.2) Leva n/2 discos restantes da vareta 1 para a 4, usando apenas
as varetas 1, 3 e 4 como armazenamento temporário.
b.3) Leva os n/2 discos da vareta 2 para a vareta 4, usando as 4
varetas como armazenamento temporário.
7.( ) Quando todas as chaves em um vetor são iguais, o Quicksort faz O(n)
comparações para ordenar esse vetor.
8.( ) Utilizando o algoritmo dos slides para montar uma tabela de Torneio,
onde o número de times é uma potência de 2, é sempre possível fazer com que
a última rodada do campeonato seja como no campeonato brasileiro, onde todos
os jogos são regionais (cada jogo envolve dois times de uma mesma região).
9.( ) Usando recursão com memorização para o problema Moedas, com as
moedas brasileiras, podemos afirmar que para calcular T(6, 600) o número de
subproblemas a serem resolvidos é sempre menor que 1000.
10.( ) O algoritmo abaixo Pot(n,k) calcula nk, para n e k inteiros. Sua
complexidade é O(k):
Pot(n, k):
Se (k = 0) Então Retornar 1
Senão Se (k é par) Então Retornar Pot(n,k/2)*Pot(n/k2);
Senão Retornar n*Pot(n,k/2)*Pot(n/k2);
11.( ) O algoritmo abaixo Comb(n,k) calcula o número de combinações de n k a
k. Sua complexidade é O(n*k);
Comb(n, k);
Se (k = n) Então Retornar 1
Senão Se (k > n) Então Retornar 0
Senão Se (k = 0) Então Retornar 1
Senão Retornar Comb(n-1,k)+Comb(n-1,k-1);
12.( ) A solução por Backtracking para o problema Damas Pacíficas em um
tabuleiro n x n testa apenas algumas das permutações de n elementos.
13.( ) Podemos fazer um algoritmo por Backtracking para resolver o
problema Torneiro, mas sua complexidade é maior que a do algoritmo por
Divisão e Conquista.
14.( ) A utilização da técnica de Árvore de Jogo sempre permite encontrar um
caminho vencedor para o computador.
15.( ) A complexidade do algoritmo de Partição Aproximada por Backtracking
é polinomial no número de inteiros a particionar.
16.( ) Considere a recorrência abaixo para resolver determinado problema,
onde queremos calcular T(m, m). Então podemos fazer um algoritmo de
programação dinâmica tal que preenchamos uma matriz T(m * m) por linha:
T(1, 1) = 1
T(n,p) = 0, p ≥ n T(n, p) = min
0 ≤ q ≤ n (T(n-q, p-1) + T(2n-q, p) + q) para p > 1, n > 1
17.( ) Considere a recorrência abaixo para resolver determinado problema,
onde queremos calcular T(m, m). Então podemos fazer um algoritmo de
programação dinâmica tal que preenchamos uma matriz T(m * m) por coluna:
T(1, 1) = 1
T(n,p) = 0, p ≥ n
T(n, p) = min0 ≤ q ≤ n (T(n-q, p-1) + T(2n-q, p) + q) para p > 1, n > 1
18.( ) A partir do preenchimento da matriz K(q * M) para o problema Mochila,
onde q é o número de ítens e M o tamanho da Mochila, podemos obter todas as
soluções para o preenchimento de determinada mochila com valor igual ou
inferior a M.
19.( ) Considerando um conjunto de q ítens e duas mochilas de capacidade M,
podemos preencher as duas mochilas de forma a se ter o máximo peso total,
usando a seguinte idéia: preenchemos a matriz para a capacidade 2M e
tomamos o menor valor menor ou igual a 2M para o qual foi encontrada uma
solução.
20.( ) Considerando um conjunto de q ítens e duas mochilas de capacidade M,
podemos preencher as duas mochilas de forma a se ter o máximo peso total,
usando a seguinte idéia: preenchemos a matriz para a capacidade M e tomamos
duas vezes o menor valor menor ou igual a M para o qual foi encontrada uma
solução.
21.( ) Na solução do Produto de Matrizes por programação Dinâmica, para se
obter a solução para o produto de uma sequência de matrizes M1...Mn, tem-se
que resolver todos os subproblemas envolvendo qualquer combinação de
produto das matrizes 1 a n.
22.( ) Considerando a matriz preenchida por programação dinâmica para o
problema Distância de Edição, podemos encontrar a sequência de
transformações começando uma busca na posição (0, 0).
23.( ) Em uma árvore de Huffman, se o símbolo A tem frequência maior que a
do símbolo B, então A está em uma folha mais próxima da raiz que a da folha de
B.
24.( ) O Merge Ótimo entre 4 arquivos de tamanhos 300, 400, 500 e 600,
respectivamente, executa 3600 operações.
25.( ) A solução do problema Troco Mínimo usando um conjunto de 3 moedas
com valores 1, 7 e 22 pode ser gulosa.
26.( ) Para encontrar uma solução (não necessariamente a ótima) para o
problema da Torre de
Hanoi com n discos e 4 varetas (ao invés de 3), podemos usar a
seguinte idéia recursiva:
a) Se (n ≤ 3) o problema pode ser resolvido diretamente.
b) Se (n > 3) Então:
b.1) Leva n/2 discos da vareta 1 para a vareta 2, usando as 4
varetas como armazenamento temporário.
b.2) Leva n/2 discos restantes da vareta 1 para a 4, usando apenas
as varetas 1, 3 e 4 como armazenamento temporário.
b.3) Leva os n/2 discos da vareta 2 para a vareta 4, usando as 4
varetas como armazenamento temporário.
27.( ) Quando todas as chaves em um vetor são iguais, o Quicksort faz O(n)
comparações para ordenar esse vetor.
28.( ) Usando recursão com memorização para o problema Moedas, com as
moedas brasileiras, podemos afirmar que para calcular T(6, 600) o número de
subproblemas a serem resolvidos é sempre menor que 1000.
29.( ) O algoritmo abaixo Pot(n,k) calcula nk, para n e k inteiros. Sua
complexidade é O(k):
Pot(n, k):
se (k = 0):
retornar 1
senão se (k mod 2 = 0):
retornar Pot(n,k/2)*Pot(n/k2)
senão:
retornar n*Pot(n,k/2)*Pot(n/k2)
30.( ) A solução por Backtracking para o problema Damas Pacíficas em um
tabuleiro n x n testa apenas algumas das permutações de n elementos.
31.( ) Podemos fazer um algoritmo por Backtracking para resolver o
problema Torneio, mas sua complexidade é maior que a do algoritmo por Divisão
e Conquista.
32.( ) Em uma árvore de Huffman, se o símbolo A tem frequência maior que a
do símbolo B, então A está em uma folha mais próxima da raiz que a da folha de
B.
33.( ) O Merge Ótimo entre 4 arquivos de tamanhos 300, 400, 500 e 600,
respectivamente, executa 3600 operações.
34.( ) A solução do problema Troco Mínimo usando um conjunto de 3 moedas
com valores 1, 7 e 22 pode ser gulosa.
35.( ) Considere a recorrência abaixo para resolver determinado problema,
onde queremos calcular T(m, m). Então podemos fazer um algoritmo de
programação dinâmica tal que preenchamos uma matriz T(m * m) por coluna:
T(1, 1) = 1
T(n,p) = 0, p ≥≥ n
T(n, p) = min0 ≤ q ≤ n (T(n-q, p-1) + T(2n-q, p) + q) para p > 1, n > 1
A CLASSIFICAR ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
Questão 3. (3 pontos) – Sequência decrescente máxima em matriz.
Dada uma matriz M(a x b) com inteiros positivos, escrever uma recorrência que determina,
para cada célula, qual o tamanho da sequência estritamente decrescente máxima começando
naquela célula e podendo prosseguir nas 4 direções cardeais. Escrever o algoritmo de PD
correspondente. No exemplo abaixo, a sequência máxima tem tamanho 9 e está ilustrada.
9 7
6
3 4 5
2
Questão 4. (3 pontos) – Árvore de Jogo
Reescrever o algoritmo da Mochila com peso e valor, itens únicos, usando recursão com
memorização.
Questão 2. (3 pontos) – Partições posicionais.
Escrever a recorrência para calcular o número de partições posicionais de um inteiro n. Nesse
tipo de partição a posição de cada parcela importa. Por exemplo, as partições posicionais de 3
são: 3, 2 1, 1 2, 1 1 1. Escrever um algoritmo de PD para resolver o problema.
Questão 3. (3 pontos) – Partição aproximada em 3 conjuntos
Explique (não precisa escrever o algoritmo) como seria um algoritmo para fazer a melhor
partição aproximada de um conjunto com n (n > 2) inteiros positivos, em três subconjuntos.
A melhor partição aproximada, nesse caso, seria aquela cuja soma das diferenças
absolutas entre os totais de cada par de subconjuntos fosse mínima.
Questão 3. (2 pontos) - Mochila fracionária
Na versão fracionária do problema Mochila Peso e Valor, os ítens podem ser fracionados
(por exemplo, os ítens são diversos metais em pó). Então, o problema pode ser descrito da
seguinte forma:
Dados n ítens com pesos respectivos p1 ... pn e valores respectivos v1 ... vn, determinar as
frações dos ítens que preenchem uma mochila de capacidade M com o maior valor total
possível.
a) Escreva um algoritmo guloso para resolver o problema.
b) Argumente que a solução é gulosa.
Questão 4. (2 pontos) - Arranjos com repetições
Escreva um algoritmo de Backtracking para, dados n e q gerar todos os arranjos com
repetições dos números 1 a n, com q elementos em cada arranjo. Por exemplo, se n=3 e q =
2, são gerados os arranjos:
1 1, 1 2, 1 3, 2 1, 2 2, 2 3, 3 1 , 3 2 , 3 3.
Questão 4. (2 pontos) – Combinações com repetições
Considere o algoritmo estudado, mostrado a seguir para exibir as combinações de n ítens, q a q.
Modifique esse algoritmo para listar combinações com repetições. Por exemplo, para n = 3, q =
2, ele deve dar como saída: 1 1, 1 2, 1 3, 2 2, 2 3, 3 3.
Comb(n, q, t):
Para i de t a n:
P[++np] ← i; Se |np = q) Então Imprimir P
Senão Comb(n, q, i+1);
np--;
Fp;
Fim;
Externamente: np ← 0; Comb(n, q, 1);
Questão 5. (2 pontos) – MDC de 3 números
Um algoritmo recursivo para calcular o MDC entre 2 números é o seguinte:
MDC(a,b):
Se (b = 0) Então Retornar a
Senão Retornar Retornar (b, a mod b);
Fim;
Completar o algoritmo recursivo abaixo, para calcular o MDC entre 3 números:
MDC3(a, b, c):
Se ((b = 0) e (c = 0)) Então Retornar a;
Senão se (c = 0) Então Retornar MDC3(b, a mod b, 0)
Senão Retornar ...
Fim;
Questão 2. (2,5 pontos) - Torres pacíficas em retângulos
É dado um tabuleiro n x n e n retângulos inscritos no retângulo do tabuleiro. Quer-se saber se
é possível colocar uma torre dentro de cada retângulo tal que as n torres não se ataquem.
Escrever um algoritmo guloso para indicar se o problema tem solução ou não e indicar a solução.
Argumentar que o algoritmo está correto.
T1
T2
T3 T4
Questão 3. (2,5 pontos) – Soma de quadrados
Escrever um algoritmo de backtracking para, dado um inteiro n > 0, escrever todas as formas
em que esse número pode ser escrito como soma de cubos menores.
Ex: n = 30 30 = 1+1+...+1+1
30= 1 + 1+...+1+8 30= 1 + 1+...+1+8 +8 30=1+1+1+1+1+1+8+8+8
30=1+1+1+27
Questão 2. (2,5 pontos) - Empacotamento.
Uma empresa vende 6 tipos de produtos, embalados em cubos de lados de valores 1 a 6,
respectivamente. Quando a empresa despacha uma venda, ela empacota os produtos comprados
apenas em pacotes cúbicos de lados 3 ou 6, total ou parcialmente preenchidos. Cadea pacote
pode conter vários produtos, desde que que as dimensões sejam coerentes. Dadas as
quantidades de compra de cada tipo de produto, determinar quantos pacotes que podem ser
formados, tal que seu volume seja mínimo. Se houver mais de uma solução, deve-se usar a que
usa o número mínimo de pacotes.
a) Escrever um algoritmo guloso para o problema.
b) Argumentar que a solução é gulosa.
Ex: Para compras de 100, 0, 6, 0, 1, 8 (respectivamente o número de produtos tipo 1, 2... 6), o
número mínimo de pacotes será 16 (9 de 6 e 7 de 3).
Questão 3. (3 pontos) – Particionamento aproximado em três subconjuntos
Discutir a idéia de um algoritmo (não precisa escrever esse algoritmo) para particionar um
conjunto de inteiros em 3 subconjuntos, A, B, C, de forma a minimizar a soma
|S(A)-S(B)|+|S(A)-S(C)|+|(S(B)-S(C)|, onde S(X) é a soma dos elementos de X .
Mostrar um exemplo.
Questão 4. (3 pontos) – Quadrado Latino
Um quadrado latino n x n é um quadrado n x n contendo apenas elementos de 1 a n,
tal que cada linha e cada coluna do quadrado seja uma permutação de 1 a n. Escrever
um algoritmo de backtracking que gera todos os quadrados latinos de tamanho n x n.
Veja um exemplo de um quadrado latino 4 x 4:
1 2 3 4 2 1 4 3 3 4 1 2 4 2 2 1
Dicas: usar duas matrizes QL e QC, ambas n x n, para guardar a informação de que
valores já foram usados em determinada linha e coluna, respectivamente. Começar o
preenchimento na célula (1,1) e preencher uma célula a cada passo do backtracking.
Questão 4. (3 pontos) – Vetores encadeados
São dados n vetores que devem ser encadeados formando uma cobertura. Quer-se saber qual a
área máxima possível dessa cobertura. Por exemplo, para o conjunto de vetores (1,0), (1,1) e
(2,1), a cobertura de área máxima é a da esquerda da figura(área de 0.5+1+2+2=5,5). A
configuração da direita é pior(área de 1+0,5+1+2=4,5). Argumentar que a solução do problema é
gulosa e consiste em ordenar adequadamente os vetores. Mostre o critério de ordenação.
Questão 3. (3 pontos) – 2 menores inteiros de um conjunto S com n elementos
O algoritmo seguinte obtém os 2 menores valores de um conjunto, por divisão e conquista.
DM(S);
Se (|S| = 1) Então retornar (s1, ∞∞) Senão Se (|S| = 2) Então
Se (s1 < s2) Então Retornar (s1, s2) Senão Retornar (s2,s1)
Senão
n ←← |S|; m ←⎣←⎣n/2⎦⎦; (a,b) ←← DM({s1,...,sm}); (c,d) ←← DM({sm+1,...sn}); Se (a < c) Então Retornar (a, min(b,c))
Senão Retornar (c, min(a,d));
Fim;
a) Argumentar que o algoritmo está correto
b) Calcular o número de comparações quando n é potência de 2. c) Escrever um algoritmo não recursivo para resolver o problema, fazendo o mesmo
número de comparações que esse algoritmo.
Questão 4. (3 pontos) – Representação Fibonacci de inteiros positivos
Qualquer inteiro positivo pode ser representado, de forma única, como soma de termos não
consecutivos da série Fibonacci (0 1 1 2 3 5 8 13 21 34 55..). Por exemplo: 44= 2 + 8 +34.
a) Escreva um algoritmo guloso para determinar os termos da soma da representação de um
inteiro positivo n (n ≤ 1000000000) nesse sistema..
b) Explique como as propriedades da representação são refletidas no algoritmo.
c) Qual seria a estratégia para provar que o algoritmo está correto?
Questão 3. (3 pontos) – Tarefas com penalidade total mínima
Considere uma variante do problema de Sequenciamento de Tarefas com Receita máxima,
onde para cada tarefa Ti estão associados três valores, li, ri e pi. Todas as tarefas têm que
ser executadas e aquelas feitas além da data limite (li), pagam uma penalidade diária (pi).
Escrever um algoritmo de backtracking para determinar um seqüenciamento das tarefas que
gera uma penalidade total mínima.
Questão 2. (2,5 pontos) – Palíndromos: Dado um string S de tamanho n, contendo caracteres nas posições 1 a n, quer-se calcular o
número de substrings distintos que formam palíndromos. Aquí chamamos substring o
resultado da eliminação de qualquer quantidade de caracteres do string inicial, não
necessariamente em sequência. A recorrência para esse cálculo, descrita a seguir, usa T(i,j) =
número buscado, considerando o substring contínuo das posições i a j de S. O cálculo de
T(i,j) pode ser feito pela recorrência abaixo:
T(i,i) = 1; T(i,j) = 0, se i > j;
T(i,j) = T(i,j-1)+T(i+1,j) + 1, se si = sj ou T(i,j-1)+T(i+1,j) -T(i+1,j-1), cc
sp = caracter na posição p de S.
Exemplo: S = ‘MARIA’ T(1,5) = 8. Os palíndromos são: ‘M’, ‘A’, ‘R’, ‘I’, ‘A’, ‘AA’, ‘ARA’, ‘AIA’.
a.1) Explicar a recorrência acima.
a.2) Mostrar o cálculo do número de palíndromos para o STRING ‘ARARA’.
a.3) Escrever um algoritmo recursivo com Memorização para calcular T(1,n).
Questão 3. (2,5 pontos) – Soma de quadrados e cubos
Todo número inteiro pode ser escrito como soma de quadrados e cubos de números
inteiros menores. Considere o problema de encontrar T(n) = menor número de parcelas
desse tipo para dado n. Escrever a recorrência para resolver o problema e, em seguida, o
algoritmo de PD correspondente. Exs: T(28) = 2 (12 + 33); T(29) = 2 (22 + 52);
Questão 4. (2,5 pontos) – Transformação na Distância de Edição
Escrever um algoritmo para mostrar uma possível transformação de um string A em outro
string B, segundo os conceitos de Distância de Edição. A saída deve ser assim:
a) se tiver havido a inclusão do caracter bj então escrever "+bj" b) se tiver havido a deleção do caracter ai então escrever "-ai" c) se o caracter ai tiver se mantido ou transformado para bj, escrever "aibj" Quando houver mais de uma alternativa, obedecer a prioridade de a) a c).
Por exemplo: na transformação de "AAT" para "ATA" a saída é "AA-A+A".
Questão 4. (2,5 pontos) – Backtracking + Mochila
Suponha que foi preenchida o vetor K para o problema da Mochila, com ítens únicos. Escrever
um algoritmo de Backtracking que, usando esse vetor, indique todas as soluções para o
problema, para dada capacidade da Mochila:
Ex: Para M = 8 e 5 itens com pesos 1, 2, 2, 3, 5, o programa deveria ter saída equivalente à
seguinte:
8 = 1+2+2+3
8 = 1+2+5
8 = 1+2+5
8 = 3+5
Questão 4. (3 pontos) – Contagem de grupamentos
Escrever a recorrência para contar os grupamentos distintos de n elementos, cada grupo com p
elementos, onde p é divisor de n. Em um grupamento, os n elementos são particionados em n/p
grupos com p elementos em cada grupo.
Por exemplo, para n = 6 e p = 2, sendo os elementos A B C D E F, a resposta é 15 e os 15
grupamentos distintos são:
AB CD EF, AB CE DF, AB CF DE,
AC BD EF, AC BE DF, AC BF DE,
AD BC EF, AD BE CF, AD BF CD,
AE BC DF, AE BD CF, AE BF CD,
AF BC DE, AF BD CE, AF BE CD
Questão 4. (3 pontos) – Backtracking x PD no dominó
São dadas n peças de dominó, e dois inteiros, x e y. Quer-se saber se é possível, de alguma
maneira, colocar as peças, em sentido vertical, lado a lado, tal que a soma superior seja igual a
x e a soma inferior seja igual a y.
a) Quando n ≈ 10, o problema pode ser resolvido eficientemente por Backtracking. Explicar um
algoritmo para fazer isso (não precisa escrever o algoritmo).
b) Quando n >> 10, a solução eficiente tem que ser por Programação Dinâmica. Escrever um
algoritmo para fazer isso.
Ex: para n = 3, x = 7, y = 11, peças: (2,3), (4,5), (0,4) é possível.
Para n = 3, x = 9, y = 9 e peças (2,3), (4,5), (0,4), não é possível,
Questão 3. (3 pontos) – k somas para atingir n.
Escrever um algoritmo de Backtracking que, para dados n e k, lista todas as maneiras distintas
de se obter uma soma de k elementos, cujo valor seja n, com todos as parcelas sendo números
inteiros entre 0 e n.
Ex: Para n = 4, k = 2, a saída é:
0+4
1+3
2+2
3+1
4+0
