Prova de Algoritimos e Estruturas de dados

Prévia do material em texto

Universidade de São Paulo – USP 
Instituto de Ciências Matemáticas e de Computação – ICMC 
Departamento de Ciências de Computação – SCC 
SCE-183 - Algoritmos e Estruturas de Dados II 
Responsável: Professor Gustavo Batista 
 Nota 
1 
2 
3 
T 
 
 
Nome:___________________________________________ 
 
Primeira Avaliação - Grafos 
 
1. [3,0] Dados dois recipientes, o primeiro com capacidade de 7L e o segundo de 5L 
inicialmente vazios. Deseja-se colocar 4L de água em um dos recipientes, conforme 
a seguinte figura: 
 
Estado 	Inic ia l Estado 	Fina l
? 4L0L 0L
 
 
As operações possíveis são: 
1. Encher um dos recipientes com água (existe uma fonte inesgotável de água que 
permite encher os recipientes tantas vezes quanto necessário); 
2. Transferir o conteúdo de um dos recipientes para o outro de forma que o 
recipiente destino fique cheio; 
3. Esvaziar um dos recipientes 
 
a) [1,5] Mostre como um grafo pode fornecer todas as soluções para este 
problema; 
b) [0,5] Forneça o menor caminho entre o estado inicial e a solução; 
c) [1,0] Mostre como esse grafo seria representado por meio de uma lista de 
adjacência. 
 
2. [4,0] Diversas universidades desejam criar uma rede multimídia ao redor do mundo. 
Uma rede de computadores foi montada para conectar essas universidades usando 
linhas de comunicação. É necessário instalar um servidor de arquivos em uma das 
escolas para compartilhar arquivos entre todas elas. Supondo que o custo de 
transferência de dados é proporcional ao número de conexões utilizadas, responda: 
 
a) [1,0] Qual escola deve ser escolhida de forma que o custo máximo de 
transmissão seja o menor possível? 
b) [1,0] Descreva um algoritmo que dado um conjunto de escolas e conexões 
determine a escola que minimize o custo de transmissão. 
c) [2.0] Supondo que existam 7 escolas rotuladas de 1 a 7 e as 6 conexões a 
seguir: (1,4); (2,3); (2,4); (4,6); (4,7) e (5,6). Mostre os passos necessários para 
encontrar a escola na qual deve ser instalado o servidor. 
 
 
3. [3,0] Existem 8 ilhas em um lago e o governo deseja construir sete pontes 
conectando-as de forma que cada ilha possa ser alcançada de qualquer outra ilha 
por meio de uma ou mais pontes. O governo deseja que o custo das construções 
seja mínimo, sendo o custo de construção de cada ponte proporcional ao seu 
comprimento. As distâncias entre os pares de ilhas são dados na tabela abaixo: 
 
 1 2 3 4 5 6 7 8 
1 - 240 210 340 280 200 345 120 
2 - - 265 175 215 180 185 155 
3 - - - 260 115 350 435 195 
4 - - - - 160 330 295 230 
5 - - - - - 360 400 170 
6 - - - - - - 175 205 
7 - - - - - - - 305 
8 - - - - - - - - 
 
a) [1,0] Como esse problema pode ser solucionado utilizando grafos? 
b) [2,0] Mostre graficamente e passo a passo como seria a construção do grafo que 
fornece a solução para este problema.