Revisão 2 (Exercícios) - Algoritmos e Estruturas de Dados

Prévia do material em texto

Universidade Federal de Pernambuco – UFPE
Centro de Informa´tica
Sistemas de Informac¸a˜o
IF672 – Algoritmos e Estruturas de Dados
Professor: Renato Vimieiro
2a Lista de exerc´ıcios de fixac¸a˜o Entrega: 17/06/16
1. Mostre o vetor de antecessores apo´s a busca em largura e profundidade no seguinte grafo
2. (Kleinberg e Tardos – ex 3.2) Implemente um algoritmo em C++ para detectar se um grafo simples conte´m
ciclos. Se houver ciclos, o algoritmo deve exibir um (e somente um). Seu algoritmo deve ter complexidade
O(V + E).
3. Modifique a busca em largura para verificar se um grafo e´ bipartido. Dica: use cores para diferenciar ve´rtices
de uma partic¸a˜o da outra.
4. (Livitin – ex.3.5.11) Suponha que voceˆ precise dividir 8 litros de um l´ıquido em duas partes iguais, mas na˜o
possui instrumentos adequados para isso exceto treˆs jarras de 8, 5 e 3 litros. Se os 8 litros esta˜o inicialmente
na primeira jarra (de 8 litros), mostre como a busca em largura pode resolver esse problema.
5. Um problema bastante estudado em teoria dos grafos e´ o problema de encontrar um conjunto de ve´rtices no
grafo em que na˜o existe aresta conectando seus elementos. Esse problema e´ chamado de conjunto independente.
Existem diversas aplicac¸o˜es pra´ticas e teo´ricas para o problema de determinar um conjunto independente em
um grafo. Para grafos irrestritos, esse problema e´ computacionalmente dif´ıcil e na˜o se conhece um algoritmo
que encontre uma soluc¸a˜o em tempo polinomial para ele. Contudo, a depender das restric¸o˜es impostas sobre o
grafo, esse problema pode ser resolvido em tempo polinomial.
Por exemplo, considere um grafo caminho com n ve´rtices e n− 1 arestas. As arestas desse grafo conectam dois
ve´rtices i e j se, e somente se, |i− j| = 1. Supondo que os ve´rtices desse grafo esta˜o associados a pesos, mostre
que e´ poss´ıvel encontrar um conjunto independente de peso ma´ximo em tempo O(n). Apresente o algoritmo
que calcule o peso ma´ximo de um conjunto independente e o conjunto que possui esse valor.
6. Encontre uma a´rvore geradora mı´nima usando o algoritmo de Prim, e Kruskal no seguinte grafo na˜o-direcionado:
A B C D E F
A 5 6 4
B 4 2
C 2 5 3
D 4
E 4
F
7. Um problema bastante estudado em computac¸a˜o e´ o chamado problema da mochila. Dado uma mochila com
capacidade para armazenar um peso ma´ximo W , o problema consiste em escolher dentre um conjunto de n
itens, cada um com peso wi e valor vi, um subconjunto de maior valor agregado que possa ser transportado na
mochila. Por exemplo, considere os cinco itens na tabela a seguir:
item peso (kg) valor (R$)
1 3 25
2 2 20
3 1 15
4 4 40
5 5 50
Supondo uma mochila com capacidade para 6kg, poder´ıamos levar os itens 1, 2 e 3 com valor agregado de
R$60, ou os itens 3 e 5 com valor R$65.
Pede:
1
(a) Desenvolva um algoritmo de programac¸a˜o dinaˆmica para resolver o problema da mochila. Mostre e discuta
todas as etapas do desenvolvimento.
(b) Aplique o algoritmo ao exemplo acima para determinar a melhor escolha de itens.
8. Aplique o algoritmo de Floyd-Warshall no seguinte grafo e mostre a matriz de distaˆncia entre os ve´rtices.
9. Considere o seguinte fluxo:
(a) Qual o valor do fluxo atual na rede?
(b) Esse fluxo e´ ma´ximo? Se for, demonstre sua resposta. Se na˜o for, qual o fluxo ma´ximo?
10. Os administradores de um hospital desejam planejar a quantidade de cirurgias que podera˜o ser executadas
durante um per´ıodo de tempo. Sabe-se que existem 4 tipos de sangue: A, B, AB e O. Cada tipo e´ determinado
pela presenc¸a do ant´ıgeno A ou B na superf´ıcie das hema´cias, sendo que o grupo AB corresponde a`s pessoas
que possuem os dois ant´ıgenos e o O pela auseˆncia de ambos. Dessa forma, pessoas do grupo O so´ podem
receber transfuso˜es do mesmo grupo; pessoas do grupo A podem receber transfuso˜es dos grupos A e O; pessoas
do grupo B dos grupos B e O; e pessoas do grupo AB podem receber de qualquer outro grupo. O hospital
possui suprimentos e demandas para os grupos conforme a seguinte tabela:
grupo suprimento demanda
O 50 45
A 36 42
B 11 8
AB 8 3
total 105 100
As 105 unidades de sangue dispon´ıveis sa˜o suficientes para atender a demanda de 100 unidades do hospital?
Pede-se:
(a) Modele o problema como um problema de fluxo em redes. Defina claramente ve´rtices, arestas e capaci-
dades.
(b) Mostre uma alocac¸a˜o de recursos que permita ao hospital atender o maior nu´mero de pacientes poss´ıvel,
satisfazendo ao ma´ximo sua demanda.
2