aa22-P2

Prévia do material em texto

Prova 2 – Análise de Algoritmos 2022.2 – UFABC
Aritanan Gruber
aritanan.gruber@ufabc.edu.br
http://professor.ufabc.edu.br/∼aritanan.gruber
Entrega via Moodle até 28/08/2022 às 23h59
(120/100 pontos)
A prova é individual, sem consulta a colegas e internet. Você pode tirar dúvidas de enunciados com o professor e monitor.
Você pode ainda consultar suas anotações, a bibliografia indicada e os vídeos fornecidos. Caso o faça, indique clara e
sucintamente no início das questões o material consultado. Exemplos: seções X e Y de Cormen et al.; anotações/vídeo
sobre o tópico Z.
1. (15) Sejam A[1..n] e B[1..n] vetores com inteiros positivos que você pode ordená-los como desejar. No que segue,
considere A[i] e B[i] como os i-ésimos elementos de A e B após as ordenações. Descreva um algoritmo guloso com
consumo de tempo polinomial em n que maximiza a função prêmio f(A,B) =
∏n
i=1A[i]
B[i]. Prove que seu algoritmo
é correto (naturalmente, você deve explicitar quais ordens foram usadas em A e B).
2. (20) Seja S = {a1, a2, . . . , an} um conjunto de tarefas, em que a tarefa ai requer pi unidades de tempo de processa-
mento ininterrupto. Denote por fi o tempo de término de ai, que é o instante em que ai tem seu processamento
finalizado – observe que fi é uma variável que depende da ordem em que as tarefas são escalonadas.
Defina o tempo médio de término de um escalonamento σ para S como σ(S) = 1n
∑n
i=1 fi. Descreva um algoritmo
guloso que determina um escalonamento σ para as tarefas em S tal que σ(S) seja o menor possível. Prove a correção
e analise o consumo de tempo de seu algoritmo.
Exemplo: Para S = {a1, a2} com p1 = 5 e p2 = 3, o escalonamento σ1 = 〈a1, a2〉 tem f1 = 5, f2 = 8 e σ1(S) =
(5+8)/2 = 6.5. Já o escalonamento σ2 = 〈a2, a1〉 tem f2 = 3, f1 = 8 e σ2(S) = (3+8)/2 = 5.5 e, portanto, é melhor
que o primeiro.
3. (15) Seja D = (V,A) um digrafo acíclico (sem ciclos dirigidos) e suponha que os vértices de D estão ordenados como
v1, v2, . . . , vn tal que se (vi, vj) ∈ A, então i < j – uma tal ordenação é chamada de linear ou topológica e é uma
ordem total: quaisquer dois elementos são comparáveis, é reflexiva, assimétrica e transitiva.
Sejam ainda w : A → R uma função de pesos reais nos arcos de D e s, t ∈ V dois vértices distintos. Descreva um
algoritmo guloso ou baseado em programação dinâmica que recebe (D,w, s, t) e determina, em tempo polinomial em
n = |V | e m = |A|, um (s, t)-caminho P = 〈s = u0, u1, . . . , uk = t〉 em D cujo peso w(P ) =
∑k
i=1 w(ui−1, ui) seja o
maior possível e analise seu consumo de tempo.
Exemplo de um grafo dirigido acíclico (sem os pesos) ordenado topologicamente: v1 = j, v2 = m, . . . , v16 = b.
Nota: a simplicidade estrutural do problema permite que ele seja interpretado e resolvido eficientemente das duas
formas, com uma clara relação entre elas – mas isto não faz parte da questão e fica como um bom exercício para
passar o tempo.
4. (15+20+20+15) Lembre-se que:
• o problema da mochila binária (KP) consiste em, dados inteiros positivos n e W e vetores de inteiros
positivos v[1..n] e w[1..n], determinar x[1..n] ∈ {0, 1}n com
∑n
i=1 w[i] · x[i] ≤W e tal que
∑n
i=1 v[i] · x[i] seja o
maior possível; sem perda de generalidade, max{w[i] : i ∈ [n]} ≤W ≤
∑n
i=1 w[i];
• o problema da mochila fracionária (FKP) relaxa a integralidade de x de forma que queremos determinar
x[1..n] ∈ [0, 1]n satisfazendo a mesma restrição e o mesmo objetivo.
Nesta questão, vamos explorar algumas variações.
mailto:aritanan.gruber@ufabc.edu.br
http://professor.ufabc.edu.br/~aritanan.gruber
(a) Sejam x∗b e x
∗
f as respectivas soluções ótimas de (KP) e (FKP) para uma mesma instância (n, v, w,W ) e seja
k = min
{
j ∈ [n] :
∑j
i=1 w[i] > W
}
o índice do elemento crítico para (FKP) – tal que x∗f [i] = 1 se i < k,
x∗f [k] ∈ [0, 1], x∗f [i] = 0 se i > k. Denote o valor ótimo associado a x∗b por v∗b e tome
v∗a = max
{
v[k],
k−1∑
i=1
v[i]
}
.
Mostre que v∗b ≤ 2v∗a ≤ 2v∗b .
Nota: isso mostra que a estratégia gulosa de (FKP) possibilita obtermos uma aproximação de fator 2 para
(KP), sendo a solução x∗a a que obtém v∗a dentre os vetores característicos dos conjuntos {1, 2, . . . , k− 1} e {k}.
(b) Fizemos um algoritmo baseado em programação dinâmica que resolve (KP) em tempo O(nW ). A recorrência
em pesos não é a única forma de resolvermos (KP).
Seja V ≥ 0 um limitante superior ao valor de uma solução ótima – por exemplo, podemos ter V = d2v∗ae, do
item anterior. Determine (com prova) uma recorrência para (KP) em valores e forneça um algoritmo baseado
em programação dinâmica que a avalie em tempo O(nV ).
Nota: o fato dos valores serem inteiros é crucial aqui, como o foi o fato dos pesos inteiros na solução O(nW ).
Dica: defina c[j, k] como o peso de um subconjunto S ⊆ {1, 2, . . . , j} o mais leve possível tal que
∑
i∈S w[i] ≤W
e
∑
i∈S v[i] = k.
(c) O problema da mochila inteira (IKP) consiste na substituição da restrição x[1..n] ∈ {0, 1}n em (KP) por
x[1..n] ∈ Zn≥0. De outra forma, temos acesso a um número ilimitado de cada um dos itens para colocar-mos
na mochila. Determine (e prove) uma recorrência em pesos para (IKP) e forneça um algoritmo baseado em
programação dinâmica que a avalie em tempo O(nW ).
Nota: a recorrência de (KP) claramente não funciona aqui, mas uma modificação simples e judiciosa dela sim.
(d) O problema da mochila inteira com limitantes (BKP) consiste na adição de um vetor b[1..n] de inteiros
positivos à instância de (IKP) e na substituição da restrição x[1..n] ∈ Zn≥0 pelo conjunto de restrições x[i] ∈
{0, 1, . . . , b[i]} para i ∈ [n]. De outra forma, agora temos um número limitado de cada um dos ítens para
colocar-mos na mochila. Reduza (BKP) a (KP), mostrando como resolver (BKP) utilizando uma solução para
(KP) como subrotina, argumente a correção e analise precisamente o consumo de tempo da sua solução. O
tempo de sua redução é polinomial?