Baixe o app para aproveitar ainda mais
Prévia do material em texto
ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação Lista de Exercícios de Fixação 07 Método Guloso 1. Eis um problema que ocorre em análise automática de programas. Para um conjunto de variáveis x1, …, xn, são dadas algumas restrições de igualdade, da forma “xi = xj” e algumas restrições de desigualdade “xi ≠ xj”. Será que é possível satisfazer todas elas? Por exemplo, as restrições x1 = x2, x2 = x3, x3 = x4, x1 ≠ x4, não podem ser satisfeitas. Sendo assim, é possível utilizar o método guloso para elaborar um algoritmo eficiente que tome como entrada m restrições sobre n variáveis e decida se as restrições podem ser satisfeitas? Justifique. 2. Nem sempre é possível aplicar um algoritmo guloso para resolver um problema. Existem 2 características que podem indicar que os problemas podem ser resolvidos utilizando a estratégia gulosa. Sendo assim, explique porque o problema da mochila binária não pode ser resolvido por um algoritmo guloso. 3. Considere um jogo do tipo 8-puzzle, cujo objetivo é conduzir o tabuleiro esquematizado na figura abaixo para o seguinte estado final. Considere ainda que, em determinado instante do jogo, se tenha o estado E0 a seguir. Pelas regras desse jogo, sabe-se que os próximos estados possíveis são os estados E1, E2 e E3 mostrados a seguir. ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação Considere uma função heurística h embasada na soma das distâncias das peças em relação ao estado final desejado, em que a distância d a que uma peça p está da posição final é dada pela soma do número de linhas com o número de colunas que a separam da posição final desejada. Por exemplo, em E1, d(1) = 2 + 1 = 3. Sendo assim, pode-se afirmar que se utilizando um algoritmo de busca gulosa pela melhor escolha que utiliza a função h, o próximo estado no desenvolvimento do jogo a partir do estado E0 tem de ser E3? Justifique. 4. Considere o problema: Dado um grupo de cidades em uma região que está nos estágios iniciais de planejamento e seus administradores estão decidindo onde colocar escolas. Há apenas 2 restrições: cada escola deve ser em uma cidade e ninguém deve viajar mais que 50 km para alcançar uma delas. Qual o número mínimo de escolas necessário? Você recomenda o uso da estratégia gulosa para o problema? Justifique. 5. Suponha uma série de eventos, por exemplo, as transações feitas na bolsa de valores, na forma compra Dell, vende HP, compra Google, … Uma certa ação pode acontecer mais de uma vez nessa sequência. Dada uma outra sequência, decida o mais rápido possível, se ela é uma subsequência da primeira. Elabore um algoritmo eficiente para as sequências de tamanho m e n. 6. Foi desenvolvido um novo algoritmo para encontrar árvores espalhadas mínimas, baseado na seguinte propriedade: Selecione qualquer ciclo no grafo e seja e, a aresta mais pesada deste ciclo. Então, existe uma árvore espalhada mínima que não contém e . A entrada é algum grafo não-direcionado G = (V, E), em formato de lista de adjacência, com pesos nas arestas {we}. Segue o algoritmo. ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação ordene as arestas de acordo com seus pesos para cada aresta e E, em ordem decrescente de we: se e é parte de um ciclo de G: G = G – e //quer dizer, remova e de G retornar G O algoritmo é baseado no método guloso? Justifique. Lista de Exercícios de Fixação 07
Compartilhar