Algoritmos gulosos Teoria dos Grafos e Análise de Algoritmos - Exercícios

Prévia do material em texto

Algoritmos gulosos – Teoria dos Grafos e Análise de Algoritmos 
Exercícios
1. Um problema tradicional em que algoritmos gulosos são aplicados é o de
escalonar os intervalos de tempo para uso de determinado recurso. Considerando
um conjunto R de n requisições, em que cada requisição i retém o recurso por um
intervalo de tempo [ s(i), f(i) ], o objetivo é atender ao maior número de solicitações
possível. Porém, requisições com sobreposição de tempo são descartadas.
Nesse cenário, analise as afirmações a seguir e a relação proposta entre elas:
I. Um algoritmo guloso que itera sobre R aceitando a primeira requisição i com o
menor f(i) possível, retorna um conjunto A com uma solução ótima, considerando
que, para todos os índices r ≤ k, tem-se f(ir) ≤ f(jk).
PORQUE
II. Se for assumido que A não é um conjunto composto pela solução ótima, uma
contradição é obtida para a condição de parada R = do algoritmo.∅
Assinale a alternativa correta.
Resposta correta.
B. As afirmações I e II são proposições verdadeiras e a II é uma justificativa correta da I.
A estratégia de aceitar a primeira requisição i com menor f(i) possível representa
uma   escolha   local   a   cada   iteração.   Logo,   é   uma estratégia gulosa.
Para saber se essa estratégia retorna um conjunto A contendo uma solução
ótima,   vamos   supor   que A não   é   ótimo.
Nesse caso, existe um conjunto ótimo B com mais requisições, ou seja, tem-se
que |B| = m > k = |A|.
Aplicando a premissa de que, para todos índices r ≤ k → f(ir) ≤ f(jk),  com r =
k, obtém-se f(ik) ≤ f(jk).
Dado m > k,  então  existe  uma   requisição jk+1 em B.  Essa   requisição  começa
depois   que   a   requisição jk finaliza   e,   portanto,   depois   que ik finaliza.
Nesse caso, depois de todas as requisições que têm sobreposição de tempo com
as   requisições i1, …, ik terem   sido   removidas,   o   conjunto   de   todas   possíveis
requisições R ainda contém jk+1. Porém, o algoritmo guloso para após iterar sobre
a última requisição ik e isso acontece quando R é vazio, o que, por sua vez, é uma
contradição,   já   que R contém jk+1.   Portanto,   ambas   as   afirmações   são
verdadeiras e a II justifica a I.
2. A construção de estratégias gulosas para a solução de problemas é uma
abordagem muito comum, em particular porque, em geral, várias opções podem ser
implementadas. Porém, nem sempre a melhor solução é possível de ser obtida com
essa abordagem.
Um exemplo é o problema da mochila 0-1. Uma mochila que suporta, no máximo,
um peso P deve ser carregada com os itens mais valiosos, dentre n disponíveis, de
forma a alcançar o maior valor total. Cada item i tem um peso pi e um
valor viassociado.
Considerando a instância do problema da mochila 0-1, analise as afirmativas a
seguir e marque V (verdadeira) ou F (falsa).
I. ( ) Qualquer que seja a estratégia gulosa utilizada, a solução ótima inclui os itens
2 e 3.
II. ( ) Ordenar e selecionar os itens por ordem crescente de peso conduz a uma
solução subótima.
III. ( ) A estratégia gulosa de selecionar os itens com maior razão vi/pi conduz à
solução ótima.
IV. ( ) Selecionar os itens em ordem crescente de valor conduz a uma solução
subótima.
Agora, assinale a alternativa que apresenta a sequência correta.
Você acertou!
D. V, V, F, V.
I. Verdadeira, porque a seleção dos itens 2 e 3 é a única que conduz à solução
ótima com   o   valor   da   mochila   em 220.
II. Verdadeira,   pois,   com   essa   estratégia,   apenas   os   itens 1 e 2 seriam
selecionados   gerando   uma   mochila   de peso 30.
III. Falsa,   uma   vez   que,   se   os   itens   forem   selecionados   de   acordo   com   a
razão vi/pi,   o   item 1 será   o primeiro selecionado   (60/10)   seguido   do
item 2 (100/20),   o   que   levará   a   uma   mochila   de   valor 160.
IV. Verdadeira,   já que uma mochila composta pelos itens 1 e 2 tem valor 180 e
é subótima.
3. Um típico problema em que algoritmos gulosos são aplicados é conhecido como
agendamento para minimizar o tempo médio de finalização. Várias estratégias têm
sido propostas para oferecer uma solução em tempo computacionalmente viável.
Suponha um conjunto S = ｛ a1, a2, …, an ｝ de tarefas, em que cada tarefa
ai demanda pi unidades de tempo para ser concluída a partir do momento em que é
iniciada. As tarefas podem ser executadas apenas uma por vez. Seja ci o tempo
para finalização da tarefa ai, isto é, o tempo em que a tarefa ai completa seu
processamento.
Considerando que o objetivo é minimizar o tempo médio para finalização de todas
as tarefas, ou seja, minimizar:
Analise as afirmativas a seguir e marque V (verdadeira) ou F (falsa):
I. ( ) Se as tarefas forem ordenadas pela quantidade de unidades de tempo para
serem finalizadas (pi), então a complexidade do algoritmo será O(n log n).
II. ( ) Um algoritmo guloso que processa as tarefas em ordem crescente de
pi obtém a solução ótima para qualquer conjunto de tarefas.
III. ( ) Considerando S composto apenas de duas tarefas a1 e a2 com p1 = 3 e p2 =
5, o tempo médio de finalização de S é independente da ordem de execução das
tarefas.
IV. ( ) Uma solução gulosa baseada no tempo de processamento de cada tarefa
apresenta uma estrutura local ótima em cada iteração.
Agora, assinale a alternativa que apresenta a sequência correta.
Você acertou!
D. V, V, F, V.
I. Verdadeira.   Considerando   a   ordenação   das   tarefas   pela   quantidade   de
unidades de tempo para serem finalizadas (pi), o tempo de execução do algoritmo
será dominado superiormente por essa operação. Como não é possível definir um
valor máximo para todos os pi  possíveis, então a ordenação não pode ser feita
em tempo linear.   Nesse   caso,   algoritmos   como Merge Sort ou Quick
Sort podem ser  empregados  a   fim  de  se  alcançar  o melhor desempenho na
ordenação,   ou   seja, O(n log n).
II. Verdadeira, porque, como o tempo médio para finalização de todas as tarefas
está associado às unidades de tempo pi requeridas por cada tarefa, tomando as
tarefas   em ordem crescente de pi, vai conduzir ao menor tempo médio.
III. Falsa. Considerando S composto apenas de duas tarefas a1 e a2 com p1 = 3 e
p2 = 5, temos que, quando a2 é executada primeiro que a1, o tempo médio para
finalização   de  S   é   dado   por (5 + 8) / 2 = 6.5.   Porém,   quando   a ordem de
execução é inversa,   tem-se   que   o   tempo   médio   é (3 + 8) / 2 = 5.5.
IV. Verdadeira. Nesse caso, cada decisão local vai representar uma ação viável,
localmente ótima e irrevogável.
4. Vários são os problemas que podem ser modelados com grafos. Dentre os vários
benefícios dessa modelagem, estão o uso de estruturas de dados otimizadas e a
possibilidade de projetar algoritmos gulosos adaptados às particularidades do
cenário. Um exemplo tradicional é o problema conhecido como cobertura de
conjunto: dados um conjunto a ser coberto e uma coleção de subconjuntos, o
objetivo é encontrar a menor coleção de subconjuntos cuja união resulte no
conjunto informado. Uma típica aplicação desse problema é na distribuição de
instalações a um custo mínimo.
Um Estado brasileiro está no início de um planejamento e está decidindo onde
instalar escolas. Existem apenas duas restrições: cada escola deve estar em
apenas uma cidade e ninguém deve ter que viajar mais do que 30 quilômetros para
chegar a uma delas. A figura a seguir descreve as cidades que estão a 30
quilômetros umas das outras. O objetivo é definir o número mínimo de escolas
necessárias satisfazendo às restrições.
Esse é um problema típico de cobertura de conjunto. Para cada cidade x, seja Sx o
conjunto de cidades distantes 30km dele. Uma escola em x irá essencialmente
“cobrir” essas outras cidades. Um modelo computacional comum para esse cenário
é o uso de grafos: cada conjunto Sx vai ser representado por vértices e as
distâncias de30km que unem cada par de cidades por arestas.
Considere esse cenário e o seguinte algoritmo guloso para ele:
Algoritmo guloso
Entrada: Um conjunto de elementos B e uma coleção S1, …, Sm.
Saída: A seleção dos Si cuja união é B.
1. Repetir até que todos os elementos de B estejam cobertos.
2. Pegue o conjunto Si com maior número de elementos não cobertos.
3. Adicione Si à seleção que será retornada.
Analise as afirmativas a seguir:
I – O algoritmo guloso encontra a solução ótima para o problema.
II – O primeiro Si selecionado pelo algoritmo corresponde ao vértice "a".
III – Na segunda iteração, o algoritmo deve escolher entre quatro elementos 
possíveis.
IV – O vértice de maior grau compõe a solução ótima para o problema.
Quais estão corretas?
Resposta correta.
E. II e III.
I   – Falsa.  A solução ótima é   composta  pelos elementos (vértices) "b", "e" e
"i" e   essa   solução   não   é   alcançada   pelo   algoritmo   proposto.
II – Verdadeira. Como a decisão local do algoritmo é baseada no elemento Si com
maior número de elementos não cobertos (vértices com maior grau), o elemento
"a" é o primeiro a ser escolhido.
III   – Verdadeira.   Depois   da   escolha   do   elemento   "a",   o   algoritmo   terá
a sua disposição   os elementos "c", "j", "f" e "g".
IV – Falsa.  A solução ótima é composta pelos elementos (vértices) "b", "e" e
"i".
5. Os conceitos que fundamentam a construção de estratégias gulosas são
importantes para que uma modelagem precisa possa ser empregada durante a
proposição de soluções. Essa análise deve preceder, inclusive, a etapa de projeto
de um algoritmo guloso.
Nesse contexto, dado um conjunto ｛ x1, x2, …, xn ｝ de pontos na reta dos
números reais, analise as afirmativas a seguir e a relação proposta entre elas:
I. É possível projetar uma estratégia gulosa para encontrar o menor conjunto de
intervalos fechados de comprimento 1 (um) contendo todos os pontos.
PORQUE
II. A cada etapa da estratégia gulosa, uma escolha local ótima pode ser feita de
forma a garantir a obtenção de uma solução final ótima.
Assinale a alternativa correta.
Você acertou!
B. As afirmações I e II são proposições verdadeiras e a II é uma justificativa correta da I.
Considere o intervalo mais à esquerda. Sabe-se que não adianta estender mais
para a esquerda do que o ponto mais à esquerda,  porém esse intervalo deve
conter o ponto mais à esquerda. Então,  seu   lado  esquerdo  é  exatamente  o
ponto mais à esquerda. Portanto, simplesmente remove-se qualquer ponto que
não pertença ao conjunto informado e que esteja a uma unidade de distância
do ponto mais à esquerda,   uma   vez   que   eles   estão   contidos   nesse   único
intervalo.   Em   seguida,   apenas repete-se esse processo até que todos os
pontos sejam cobertos.  Como,   em cada  etapa,   há  uma  escolha   claramente
ótima de onde colocar o intervalo mais à esquerda, essa solução final é ótima.
Portanto, ambas as afirmativas são verdadeiras e a II justifica a I.
	Algoritmos gulosos – Teoria dos Grafos e Análise de Algoritmos
	Exercícios