Algoritmos e Estruturas de dados para Engenharia Elétrica - Poli - P3 2015

Prévia do material em texto

GABARITO
PCS3110 - Algoritmos e Estrutura de Dados para Engenharia Elétrica Prova 3 - 24/11/2015
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
Utilize caneta azul ou preta para marcar as caixas e preencha a caixa totalmente
para correta interpretação. Exemplo: �. Não use �.
1
Anna
2
Fábio
3
Anarosa
4
Romero
Marque as caixas ao lado para formar o seu número USP e escreva seu nome
abaixo.
Nome (completo):
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
[2,6 pontos] Questão 1
O algoritmo de Bellman-Ford é um algoritmo de grafo que usa programação dinâmica para, dado um vértice de
partida v, encontrar o menor caminho entre v e todos os demais vértices de um grafo orientado ponderado.
O algoritmo retorna TRUE se não há ciclo negativo, ou seja, um ciclo cuja soma dos pesos das arestas é negativa.
Neste caso, Bellman-Ford apresenta a solução correta para grafos com arestas de peso negativo.
Bellman-Ford (G, s)
1 Seja d[1...|G.V|] um novo arranjo
// d armazena na posição i a distância de s ao vertice vi
2 Seja pred[1...|G.V|] um novo arranjo
// pred armazena na posição i o predecessor de vi no menor caminho de s a vi
3 for each v ∈ G.V
4 d[v] = ∞
5 pred[v] = NIL
6 d[s] = 0
7 for i = 1 to |G.V|-1
// para cada i são criados caminhos com, no máximo, i arestas
8 for each (u,v) ∈ G.E
9 if d[v] > d[u] + G.Adjacencia[u,v]
10 d[v] = d[u] + G.Adjacencia[u,v] // seleciona a menor distância
11 pred[v] = u // atualiza o predecessor no menor caminho
12 for each (u,v) ∈ G.E
13 if d[v] > d[u] + G.Adjacencia[u,v]
14 return FALSE
15 return TRUE
GABARITO
(a) [1,0 ponto] Para o grafo da figura (a) simule Bellman-Ford, colocando na tabela 2 os valores de d[v] e
pred[v] para cada i do laço da linha 7. Para o laço da linha 8, considere a ordem de arestas da tabela 1. Ao
final da simulação, escreva dentro de cada vértice v do grafo da figura (b) o valor de d[v] e hachure as arestas
que representam o menor caminho de s a v.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 4 8
Tabela 1
(u,v) (s,v1) (s,v3) (v1, v2) (v1, v3) (v1, v4) (v2, v1) (v3, v2) (v3, v4) (v4, s) (v4, v2)
G.Adjacencia[u,v] 6 7 5 8 -4 -2 -3 9 2 7
Tabela 2
i d[1]/pred[v1] d[2]/pred[v2] d[3]/pred[v3] d[4]/pred[v4]
1 6/s ∞ 7/s ∞
2 6/s 4/v3 7/s 2/v1
3 2/v2 4/v3 7/s 2/v1
4 2/v2 4/v3 7/s -2/v1
(b) [0,5 ponto] O algoritmo Bellman-Ford adota uma abordagem top-down ou bottom-up de programação dinâ-
mica? Por que?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 4 5
Ele usa abordagem bottom-up porque parte do cálculo da solução ótima para subproblemas menores que depois
são combinadas na obtenção do problema geral.
(c) [0,5 pontos] Quem são as subestruturas ótimas do problema tratado pelo Bellman-Ford?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 4 5
Elas estão caracterizadas pelo caminho mínimo de s a todo v ∈ V, começando por caminhos de tamanho 1 até
finalizar com caminhos de tamanho n-1.
GABARITO
(d) [0,6 pontos] Analise a complexidade de Bellman-Ford.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 4 6
Bellman-Ford (G, s)
1 Seja d[1...|G.V|] um novo arranjo
2 Seja pred[1...|G.V|] um novo arranjo
3 for each v ∈ G.V
4 d[v] = ∞
5 pred[v] = NIL
6 d[s] = 0
7 for i = 1 to |G.V|-1
8 for each (u,v) ∈ G.E
9 if d[v] > d[u] + G.Adjacencia[u,v]
10 d[v] = d[u] + G.Adjacencia[u,v]
11 pred[v] = u
12 for each (u,v) ∈ G.E
13 if d[v] > d[u] + G.Adjacencia[u,v]
14 return FALSE
15 return TRUE
Custo de execução
1 1
2 1
3 |G.V|+1
4 |G.V|
5 |G.V|
6 1
7 |G.V|+1
8 |G.V|*(|G.E|+1)
9 |G.V|*|G.E|
10 irrelevante para cálculo assintótico
11 irrelevante para cálculo assintótico
12 |G.E|+1
13 |G.E|
14 irrelevante para cálculo assintótico
15 1
Complexidade de Bellman-Ford: Para efeito do cálculo de T (|G.V |, |G.E|), associamos custo 1 às linhas 1, 2,
6 e 15. A linha 3 é executada |G.V|+1 vezes, linhas 4 e 5 |G.V| vezes cada. O laço da linha 7 é executado
|G.V|+1 vezes e o laço aninhado a ele (linha 8) |G.V|*(|G.E|+1) vezes. A linha 9 é executada |G.V|*|G.E|
vezes e execução das linhas 10 e 11 dependem da condição verificada em 9. Para efeito do cálculo assintótico é
irrelevante incluí-las. Linha 12 é executada |G.E|+1 vezes, linha 13 |G.E| vezes, linha 14 depende da condição
verificada em 13, mas também é irrelevante para o cálculo. Assim,
T (|G.V |, |G.E|) = 4 + |G.V |+ 1 + 2∗ |G.V |+ |G.V |+ 1 + |G.V | ∗ (|G.E|+ 1) + |G.V | ∗ |G.E|+ |G.E|+ 1 + |G.E| =
= 7 + 5|G.V |+ 2|G.E|+ 2|G.V ||G.E| = Θ(|G.V ||G.E|)
[2,6 pontos] Questão 2
Considere os algoritmos a seguir, desenvolvidos por um novato mas que funcionam.
Alg1 (a,b,c) // obs: c ≥ 1
1 if c == 1
2 return a
3 else
4 return Alg1(a,b,c-1)+Alg1x(a,b,c)
Alg1aux (a,b,c) // obs: c ≥ 1
1 if c == 1
2 return a
3 else
4 return b * Alg1aux(a,b,c-1)
Alg2 (a,b,c) // obs: c ≥ 1
1 s == a
2 if c > 1
3 for i = 2 to c
4 p == a
5 for j = 2 to i
6 p = p * b
7 s = s + p
8 return a
GABARITO
(a) [1,0 ponto] O que fazem os algoritmos? Apresente uma explicação dissertativa ou uma fórmula matemática.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 4 8
Alg1: Devolve a soma dos primeiros c termos de uma PG de termo inicial a e razão b
Alg1aux: Devolve o termo na posição c de uma PG de termo inicial a e razão b
Alg2: Devolve a soma dos primeiros c termos de uma PG de termo inicial a e razão b
(b) [1,6 ponto] Determine a notação θ para os algoritmos Alg1 e Alg2, apresentando o cálculo efetuado (não será
considerada na avaliação deste item uma resposta sem a apresentação do cálculo).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor:
0 1 2 4 8 16
GABARITO
Teste 1 O problema da mochila (knapsack problem) é assim definido: dado um conjunto S de n objetos, cada
objeto i com um benefício bi e um peso wi (número inteiro), o objetivo consiste em encontrar um subconjunto T ⊆ S
que maximize
∑
i∈T bi, sujeito a
∑
i∈T wi ≤W , onde W é o máximo peso permitido na mochila. Este problema pode
ser resolvido por Programação Dinâmica com a seguinte relação de recorrência:
B[k,w] =
{
B[k − 1, w] se w < wk,
max{B[k − 1, w], bk +B[k − 1, w − wk]} caso contrário, (1)
sendo B[k,w] o benefício total máximo obtido usando um subconjunto de Sk; Sk = {1, 2, 3, . . . , k}, o conjunto
dos k primeiros objetos, S0 = ∅ e B[0, w] = 0 para w ≤ W , w = {0, 1, 2, 3, . . . ,W}. São fornecidos o peso
máximo W permitido na mochila e o conjunto S = {(i, bi, wi)}, i = 1, 2, . . . n, de n objetos com benefícios bi e
pesos wi. A solução desejada é então B[n,W ] e um respectivo T que satisfaça as restrições do problema. Para
S = {(1, 25, 7), (2, 15, 2), (3, 20, 3), (4, 36, 6)} e W = 10, assinale a alternativa que indica o maior benefíciototal conse-
guido por PD e quais seriam os objetos que iriam para a mochila nesta solução.
A
Máximo
∑
i∈T bi = 45, com T = {1, 3}
B
Máximo
∑
i∈T bi = 61, com T = {1 ,4}
C
Máximo
∑
i∈T bi = 35, com T = {2 ,4}
D
Máximo
∑
i∈T bi = 56, com T = {3, 4}
E
Máximo
∑
i∈T bi = 51, com T = {2, 4}
Teste 2 Você deve encontrar os 103 (mil) itens mais baratos a partir de uma lista de itens não ordenados contendo
107 itens diferentes. Dois esquemas de solução são oferecidos:
1. Esquema A: consiste de um único passo, que é repetir mil vezes a busca sequencial.
2. Esquema B: consiste de três passos: (i) converter a lista em um vetor; (ii) ordenar o vetor com o Mergesort e
(iii) recuperar os mil itens mais baratos.
Assinale a alternativa que indique os tempos TA e TB nos piores casos e o esquema mais eficiente. Observe que a
busca sequencial tem complexidade linear, assim como também é linear a complexidade de transformar uma lista em
um vetor. A complexidade do Mergesort é Θ(n log2 n). Despreze a complexidade do terceiro passo do Esquema B (e
respectiva contribuição no cálculo de TB). Ainda, assuma que: (i) a busca sequencial de 1 (um) item em uma lista
não ordenada de 100 (cem) itens leva 0,1 milissegundos (ms), (ii) a conversão de 100 (cem) itens de lista em vetor
também leva 0,1 ms e que (iii) a ordenação de 100 (cem) itens usando o Mergesort também leva 0,1 ms. Lembre-se
que logb(x
p) = p.logb(x).
A TA = 10 segundos, TB = 10
7
segundos, A é a melhor opção.
B TA = 10 segundos, TB = 35 segundos, A é a melhor opção.
C TA = 10
4
segundos, TB = 10 segundos, B é a melhor opção.
D TA = 10
4
segundos, TB = 45 segundos, B é a melhor opção.
E TA = 10
7
milissegundos, TB = 10
7
milissegundos, ambas são igualmente boas opções.
GABARITO
Teste 3 Considere o seguinte Max-heap: [8, 7, 4, 6, 5, 2, 3, 1]. Qual é o heap resultante após a função
Extrair-Maior ser chamada duas vezes?
Extrair-Maior (A)
1 if A.heap-size < 1
2 erro �underflow do heap�
3 maior = A[1]
4 A[1] = A[A.heap-size]
5 A.heap-size = A.heap-size - 1
6 Max-Heapify(A, 1)
7 return maior
Max-Heapify (A, i)
1 esq = Filho-Esquerda(i)
2 dir = Filho-Direita(i)
3 if esq <= A.heap-size and A[esq] > A[i]
4 maior = esq
5 else maior = i
6 if dir <= A.heap-size and A[dir] > A[maior]
7 maior = dir
8 if maior != i
9 temp = A[i]
10 A[i] = A[maior]
11 A[maior] = temp
12 Max-Heapify(A, maior)
A
[6, 4, 5, 2, 1, 3]
B
[6, 5, 4, 3, 1, 2]
C
[6, 3, 4, 1, 5, 2]
D
[4, 6, 5, 2, 3, 1]
E
[6, 5, 4, 1, 3, 2]
Teste 4 Um restaurante deseja criar um sistema para controlar os pedidos de pratos para a cozinha. Os pedidos
que foram feitos antes devem ter maior prioridade, porém dependendo do tipo do pedido ele pode ter uma prioridade
diferente. Pedidos de entrega (delivery) devem ter prioridade mais baixa que pedidos feitos no salão do restaurante.
No caso de pedidos no salão, entradas (saladas, porções, etc.) devem ter prioridade mais alta que pratos principais.
Um Engenheiro decidiu implementar essa lógica usando uma fila de prioridade e usando como chave a data/hora
do pedido incrementada por um valor não negativo, o qual é definido pelo tipo do pedido. Assinale a alternativa
incorreta sobre a solução desse problema:
A
Uma entrada pedida no salão pode estar atrás de uma entrega na fila de prioridade.
B
Um pedido pode ser tirado da fila de prioridade mesmo que a chave seja maior que a data/hora atual.
C
Um exemplo válido de cálculo da chave é fazer o pedido de entrega ter sua data/hora incrementada de 5 minutos,
o pedido de prato principal feito no salão de 2 minutos e o pedido de entrada feito no salão não ter incremento.
D
A fila de prioridade deverá usar um Min-Heap.
E
Deve-se impedir que pedidos fiquem com a mesma prioridade, já que o algoritmo de fila de prioridade não aceita
que a heap tenha valores iguais como chave.
GABARITO
Teste 5 Considere a seguinte chamada inicial do algoritmo dado a seguir: Quicksort(A, 1, 12) com A = [13, 19, 9,
5, 3, 8, 7, 4, 21, 2, 10, 6]. Assinale a alternativa que indique o estado correto do vetor A após a terceira (3a.) execução
do passo 2 do algoritmo Quicksort.
Partition (A, inicio, fim)
1 pivo = A[fim]
2 i = inicio - 1
3 for j = inicio to fim - 1
4 if A[j] <= pivo
5 i = i + 1
6 temp = A[i]
7 A[i] = A[j]
8 A[j] = temp
9 A[fim] = A[i + 1]
10 A[i + 1] = pivo
11 return i + 1
Quicksort (A, inicio, fim)
1 if inicio < fim
2 pivo = Partition(A, inicio, fim)
3 Quicksort(A, inicio, pivo � 1)
4 Quicksort(A, pivo + 1, fim)
A
A = [2, 3, 4, 5, 6, 8, 7, 9, 13, 10, 19, 21]
B
A = [2, 3, 4, 5, 6, 8, 7, 9, 21, 13, 10, 19]
C
Nenhuma das outras alternativas está correta.
D
A = [5, 3, 4, 2, 6, 9, 8, 7, 10, 13, 19, 21]
E
A = [2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 19, 21]
Teste 6 Deseja-se criar uma versão do algoritmo de inserção (Insertion-Sort) que evita a comparação i > 0 no
while interno (ou seja, usando uma sentinela). Para isso criou-se o seguinte código:
Insertion-Sort (A)
1 Arruma-Arranjo(A)
2 for j = 3 to A.tamanho
3 chave = A[j]
4 i = j - 1
5 while A[i] > chave
6 A[i + 1] = A[i] //shift de A[i]
7 i = i - 1
8 A[i + 1] = chave
O que a função Arruma-Arranjo deve fazer para que esse algoritmo funcione e sem alterar o tamanho do arranjo A?
A
Trocar o menor elemento do arranjo com o elemento da primeira posição.
B
Substituir o último elemento do arranjo por ∞.
C
Trocar o maior elemento do arranjo com o elemento da primeira posição.
D
Substituir o primeiro elemento do arranjo por -∞.
E
Trocar o maior elemento do arranjo com o elemento da última posição.
GABARITO
Teste 7 Como as lacunas das linhas 1 e 10 do algoritmo Selection-Sort-Recursivo abaixo devem ser preenchidas
para que se tenha uma versão recursiva do algoritmo de ordenação por seleção que ordena em ordem crescente?
A
1 indice <= A.tamanho
10 indice - 1
B
1 indice >= 1
10 indice + 1
C
1 indice >= A.tamanho
10 menor + 1
D
1 indice <= 1
10 indice - 1
E
1 indice >= A.tamanho
10 indice + 1
Selection-Sort-Recursivo (A, indice)
1 if
2 return
3 menor = indice
4 for j = indice + 1 to A.tamanho
5 if A[j] < A[menor]
6 menor = j
7 temporario = A[menor]
8 A[menor] = A[indice]
9 A[indice] = temporario
10 Selection-Sort-Recursivo(A, )
Teste 8 Assinale a alternativa que representa a complexidade assintótica do algoritmo de Prim simplificado, dado
a seguir, sabendo que o passo 4 tem complexidade linear no pior caso, a operação de união tem custo constante e
|G.V |= n.
Prim (G)
1 T = ∅
2 B = {v} //sendo v um nó arbitrário de G.V
3 while B 6= G.V
4 determine (u,v) de menor comprimento tal que u ∈ {G. V - B} e v ∈ B
5 T = T ∪ {(u,v)}
6 B = B ∪ {u}
A Θ(n2)
B Θ(n)
C Θ(log2 n)
D
Nenhuma das outras alternativas está correta.
E Θ(n log2 n)