Algoritmos e Estruturas de dados para Engenharia Elétrica - Poli - P2 2017

Prévia do material em texto

Solução
PCS3110 - Algoritmos e Estruturas de Dados para a Engenharia Elétrica Prova 2 - 20/10/2017
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
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 Marcos 2 Fábio 3 Romero 4 Anarosa
Marque as caixas ao lado para formar o seu número USP, as caixas acima para
sua turma e seu nome abaixo.
Nome (completo):
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Instruções para a prova
1 Esta prova contém 2 questões dissertativas e 8 testes. Verifique atentamente se todas elas estão presentes. Em
caso de dúvida chame o professor.
2 Preencha seu nome e número USP. Provas não identificadas não serão corrigidas. Alunos cujos NUSP possuem
7 dígitos devem iniciar o preenchimento com um ZERO, da esquerda para a direita.
3 Resolva as questões dissertativas apenas no espaço a elas reservado. Respostas fornecidas fora do local a elas
destinadas não serão corrigidas.
4 A duração total da prova é de 100 minutos.
5 É proibido o uso de calculadoras, relógios, incluindo analógicos e/ou mecânicos e qualquer outro aparelho
eletrônico.
6 É proibido retirar o grampo da prova.
7 A interpretação da questão faz parte da avaliação dos alunos. Caso considere alguma hipótese que não esteja
explicitada no enunciado, indique claramente na resposta.
8 A prova é SEM CONSULTA.
Solução
[2,6 pontos] Questão 1
Uma distribuidora de gás metano, localizada na cidade de Winnipeg, gostaria de ligar as cidades descritas no mapa de
milhagem dados na tabela 1 usando a menor milhagem de gasoduto possível.
Tabela 1 Tabela 2
Des Moines Milwaukee Minneapolis Omaha Pierre Winnipeg
Bismarck 670 758 427 581 211 369
Des Moines 361 252 132 492 680
Milwaukee 332 493 690 759
Minneapolis 357 394 431
Omaha 391 650
Pierre 521
Bismarck A
Des Moines B
Milwaukee C
Minneapolis D
Omaha E
Pierre F
Winnipeg G
a [0,4 pontos] Qual(is) algoritmo(s) dentre os disponíveis no início desta prova podem ser usados para resolver o
problema? Por que?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 3 4
Algoritmo(s):Prim e Kruskal
Por quê? Ambos encontram a árvore geradora mínima, que dá a solução para o problema.
b [0,8 pontos] Indique um dos algoritmos citados no item a) para executar e calcular a milhagem mínima de
gasoduto necessária para ligar a distribuidora às demais cidades. Indique a ordem de arestas inseridas na tabela
3, usando quantas céluas forem necessárias, e desenhe o grafo que dá a solução do problema no espaço reservado
ao Subgrafo da solução do problema.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 3 4 5 6 7 8
Algoritmo: Kruskal
Ordem de inserção das arestas (represente arestas pelo par de vértices que as define - exemplo (A,B)):
1a. 2a. 3a. 4a. 5a. 6a. 7a. 8a. 9a. 10a. 11a. 12a. 13a. 14a.
(B,E) (A,F) (B,D) (C,D) (A,G) (E,F)
Milhagem mínima de gasoduto: 132+211+252+332+369+391=1687
Outra opção de resposta Algoritmo: Prim com vértice inicial em A
Ordem de inserção das arestas (represente arestas pelo par de vértices que as define - exemplo (A,B)):
1a. 2a. 3a. 4a. 5a. 6a. 7a. 8a. 9a. 10a. 11a. 12a. 13a. 14a.
(A,F) (A,G) (F,E) (E,B) (B,D) (D,C)
Milhagem mínima de gasoduto: 1687
Solução
Subgrafo da solução do problema Subgrafo de redundância
d) Após a construção do gasoduto de milhagem mínima os cidadãos da cidade de Des Moines decidiram, em
plebiscito, que eles iriam arcar com o custo de construção de gasodutos alternativos para garantir o fornecimento
de gás na cidade. Esta medida foi tomada tendo em vista cortes de fornecimento causados por grevistas que
interrompiam o fluxo do gás a partir de suas cidades, prejudicando Des Moines e outras cidades. Por questões
sismológicas não é possível ligar diretamente a distribuidora a Des Moines. Pergunta-se:
c.1 [0,4 pontos] Quais são as arestas do grafo que poderiam afetar o fornecimento de gás para Des Moines?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 3 4
Arestas: (represente-as pelo par de vértices que as define) (B,E), (E,F), (A,F), (A,G)
c.2 [0,6 pontos] Quais são as arestas deveriam ser incluídas no grafo para garantir redundância no oferecimento de
gás para a cidade de Des Moines com milhagem mínima?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 3 4 5 6
Arestas: (represente-as pelo par de vértices que as define) (B,F) e (A,B)
Justifique a escolha das arestas acima.
Para esta questão a correção considerou outras soluções que tratavam de redundância sem a milhagem mínima.
- A aresta (G, B) ligava a fonte diretamente ao Des Moines com apenas 680 milhas e eliminava o problema de
desabastecimento oriundos de cidades no caminho de G a B.
- A aresta (B,F) cria um caminho mínimo alternativo entre G e B se o fornecimento for cortado entre (B,E) ou
entre (E,F) e a aresta (F,G) cria um caminho alternativo entre G e B se o fornecimento for cortado entre A e F
ou entre A e G
c.3 [0,3 pontos] Desenhe o grafo com redundância para Des Moines no espaço reservado ao Subgrafo de redun-
dância.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 1 2 3
Solução
[2,6 pontos] Questão 2
A operação Al-Khwarizmi realizada pela Polícia Federal identificou diversas movimentações financeiras suspeitas entre
empresas, partidos políticos e políticos. Para entender essas movimentações, os investigadores criaram o grafo abaixo.
Os vértices representam empresas, partidos políticos ou políticos; as arestas representam as movimentações, com seu
peso indicando o valor em milhões de reais envolvido.
Em
pr
e
sa
 
B
Em
pr
e
sa
 
A
Em
pr
e
sa
 
C
Em
pr
e
sa
 
D
Em
pr
e
sa
 
E
Pa
rti
do
 
A
Pa
rti
do
 
B
Pa
rti
do
 
C
Po
lít
ic
o
 
A
Po
lít
ic
o
 
B
Po
lít
ic
o
 
C
Po
lít
ic
o
 
D
Po
lít
ic
o
 
E
1
4
5 3 2 7
2
0
3
3
4
1
0
1
2
51
5
2
8
3
a [0,2 pontos] Ao analisar o grafo, a Polícia Federal concluiu que a Empresa B repassou todo o dinheiro que ela
recebeu em movimentações suspeitas. Quanto dinheiro o Partido C recebeu mas não repassou a seus políticos?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 .5 1 2
Resposta: 8
b [0,8 pontos] Crie o algoritmo Valor-Ganho(G, p) que calcula quanto dinheiro uma empresa ou partido político
recebeu mas não repassou para outros participantes do esquema. Caso a empresa ou partido político tenha
repassado mais dinheiro do que recebeu, o valor deve ser negativo. Considere as funções Possui-Aresta(G, x,
y) que informa se existe uma aresta de x para y; e Peso(G, x, y) que obtém o peso da aresta de x para y.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 .5 1 2 3 4 5 6 7 8
Valor-Ganho(G, p)
1 ganho = 0
2 for each v ∈ G.V - {p}
3 if Possui-Aresta(G, v, p)
4 ganho = ganho + Peso(G,v, p)
5 if Possui-Aresta(G, p, v)
6 ganho = ganho - Peso(G, p, v)
7
8
9 return ganho
Solução
c [1,0 ponto] A defesa de um político alega que as provas envolvendo algumas empresas foram obtidas ilegalmente.
Por causa disso o político não teria relação com uma das principais empresas envolvidas. Por exemplo, caso
não se considere a Empresa B, o Político D não teria relação direta ou indireta com a Empresa C. Preencha
o algoritmo Tem-Relacao(G, e, p, Ignorar) que retorna verdadeiro se um vértice e fez uma movimentação
diretamente ou indiretamente para um vértice p sem considerar os vértices na lista Ignorar (para saber se um
vértice está na lista, use o operador ∈). Retorne falso caso contrário. Use como referência o algoritmo de Busca
em Largura, mas altere-o para não usar cores. Para isso guarde na lista Encontrados os vértices encontrados
(representando vértices cinza ou preto).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 .5 1 2 3 4 5 6 7 8 9 10
Tem-Relacao(G, e, p, Ignorar)
1 Seja Descobertos uma Fila de Vértices
2 Seja Encontrados uma Lista de Vértices
3 Enqueue(Descobertos, e)
4 Encontrados = Encontrados ∪ {e}
5 while not Queue-Empty(Descobertos)
6 atual = Dequeue(Descobertos)
7 for each v ∈ G.Adjacencia[atual]
8 if v 6∈ Encontrados and v 6∈ Ignorar
9 if v == p
10 return TRUE
11 Enqueue(Descobertos, v)
12 Encontrados = Encontrados ∪ {v}
13
14
15 return FALSE
Solução
d [0,6 pontos] A procuradoria deseja que as movimentações financeiras de empresas para partidos ou políticos sejam
divididas em movimentações legais (informadas ao TSE) e ilegais. Como isso pode ser representado no grafo?
Use o subgrafo envolvendo a Empresa E e o Político A como exemplo, considerando que a Empresa E fez uma
doação legal de 1 milhão ao Político A e uma doação ilegal de 2 milhões. Além disso, explique como isso poderia
ser representado computacionalmente, considerando o uso de uma lista de adjacência.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Para uso do professor: 0 .5 1 2 3 4 5 6
Exemplo com o subgrafo envolvendo a Empresa E e o Político A (0,2)
Original Proposta
Explicação da representação computacional usando uma lista de adjacência (0,4)
Cada elemento da lista ligada possuirá dois outros dados satélites, além do vértice: o valor legal e o ilegal.
Solução
[4,8 pontos] Testes
Teste 1 Dado o grafo desconexo abaixo, assinale todas as afirmações corretas.
A Aplicando o algoritmo de PRIM a partir do nó a, a ordem de inserção das arestas seria: (a,e), (e,d), (d,b), (b,c).
B Aplicando o algoritmo de KRUSKAL a partir do nó f, esse entraria em loop infinito.
C Aplicando o algoritmo de KRUSKAL no grafo, a ordem de inserção das arestas seria: (d,e), (d,b), (a,e), (b,c),
(g,i), (g,h), (g,f).
D Aplicando o algoritmo DFS no grafo, a partir do vértice d obtém-se a sequência de vértices d, a, e, c, b.
E Aplicando o algoritmo de PRIM no grafo, obtém-se uma árvore geradora mínima com 9 nós.
Teste 2 Percorrida uma árvore binária, a partir da raiz A, em ordem simétrica, obteve-se a sequência XEYAZIK.
Com relação a essa árvore, sabendo-se que consoantes são folhas, assinale todas as afirmações corretas.
A O percurso em pós-ordem geraria XYEZIKA.
B O percurso em pré-ordem geraria AEXYIZK.
C O percurso em pós-ordem geraria XYEZKIA.
D O percurso em pré-ordem geraria AEIXYZK.
Teste 3 O grafo abaixo resume algumas das relações entre pessoas envolvidas em casos de “malas de dinheiro” no
Brasil. Assinale todas as alternativas com possíveis ordenações topológicas para esse grafo:
A Geddel, Temer, Loures, Joesley, Saud, Funaro,
Aécio, Fred.
B Loures, Funaro, Temer, Geddel, Joesley, Saud,
Aécio, Fred.
C Joesley, Aécio, Geddel, Saud, Funaro, Temer,
Fred, Loures.
D Joesley, Geddel, Temer, Loures, Aécio, Fred,
Saud, Funaro.
E Geddel, Joesley, Aécio, Temer, Saud, Fred, Lou-
res, Funaro.
F Aécio, Fred, Temer, Loures, Geddel, Joesley,
Saud, Funaro.
Solução
Teste 4 Assinale todas as afirmações corretas sobre os dois grafos mostrados abaixo. Nas questões sobre percurso
e ordenação, considere ordem alfabética:
A O grafo 2 é uma árvore binária de busca (ABB).
B A mesma frase é obtida se os grafos 1 e 2 forem percorridos em ordem simétrica (inorder).
C O grafo 1 é uma árvore binária de busca (ABB).
D A mesma frase é obtida se os grafos 1 e 2 forem percorridos, respectivamente, em ordem simétrica e em pré-ordem.
Teste 5 Com relação às árvores abaixo, indique a alternativa verdadeira, assinale todas as afirmações corretas.
A A1 é uma árvore binária cheia.
B A2 é uma árvore binária de busca.
C A execução do algoritmo BFS em A1, partindo do vértice 3, resulta na sequência 3, 1, 2, 7, 6, 4, 5.
D A1 é uma árvore binária de busca.
Solução
Teste 6 O setor de propinas da Odebrecht deseja utilizar Código de Huffman para comprimir sua extensa planilha
de nomes/apelidos. Considerando a distribuição de nomes abaixo, assinale todas as afirmações corretas sobre a
árvore resultante, usando a convenção de que 1 corresponde ao ramo da árvore com maior percentagem (obs.: os nomes
e a soma das distribuições por partido são reais).
Apelido Nome %
Itacaré Celso Russomano (PRB) 2
Kibe Gilberto Kassab (PSD) 8
M&M Geraldo Alckmin (PSDB) 15
Vizinho José Serra (PSDB) 16
Amigo Lula (PT) 28
Barbie Marta Suplicy (PMDB) 31
A Itacaré e Kibe são ambos representados com 4 bits.
B Amigo e Barbie são ambos representados com 2 bits.
C M&M e Vizinho são ambos representados com 3 bits.
Teste 7 Assinale todas as afirmações corretas sobre o grafo de figuras políticas abaixo:
A É completo, logo pode ser denotado K6.
B Permite mais de um caminho acíclico entre Temer
e Lula.
C Apresenta um ciclo de Euler.
D Um de seus subgrafos tem um ciclo de Euler de
comprimento > 3.
E Tem o mesmo número de vértices e arestas.
F É conexo e bipartido.
Teste 8 Com relação aos algoritmos de caminhos mínimos Dijkstra e Bellman-Ford, assinale todas as afirmações
corretas.
A Após a execução do algoritmo Dijkstra, não é possível que mais de um nó possua o mesmo predecessor.
B O algoritmo Dijkstra pode ser aplicado apenas a grafos não-dirigidos.
C O algoritmo de Bellman-Ford pode ser usado em grafos em que haja arestas com pesos negativos, enquanto o de
Dijkstra não.
D O algoritmo de Bellman-Ford retorna falso se possuir pelo menos um ciclo de custo negativo.