Baixe o app para aproveitar ainda mais
Prévia do material em texto
ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação Questões de Revisão Programação Dinâmica 1. Algoritmos criados para resolver um mesmo problema podem diferir de forma drástica quanto a sua eficiência. Para evitar este fato, são utilizadas técnicas algorítmicas, isto é, conjunto de técnicas que compreendem os métodos de codificação de algoritmos de forma a salientar sua complexidade, levando-se em conta a forma pela qual determinado algoritmo chega à solução desejada. Considerando os diferentes paradigmas e técnicas de projeto de algoritmos, analisem as afirmações, a seguir. I. A técnica de tentativa e erro (backtracking) efetua uma escolha ótima local, na esperança de obter uma solução ótima global. II. A técnica de divisão e conquista pode ser dividida em três etapas: dividir a instância do problema em duas ou mais instâncias menores; resolver as instâncias menores recursivamente; obter a solução para as instâncias originais (maiores) por meio da combinação dessas soluções. III. A técnica de programação dinâmica decompõe o processo em um número finito de subtarefas parciais que devem ser exploradas exaustivamente. IV. O uso de heurísticas (ou algoritmos aproximados) é caracterizado pela ação de um procedimento chamar a si próprio, direta ou indiretamente. É correto apenas o que se afirma em A. I B. II C. I e IV D. II e III E. III e IV 2. Analise as afirmativas a seguir. I. A programação dinâmica é um método ascendente que aborda um dado problema subdividindo-o em problemas mínimos, soluciona esses subproblemas, guarda as soluções parciais, combina os subproblemas e sub-resultados para obter e resolver os problemas maiores, até recompor e resolver o problema original. II. A divisão e conquista é um método recursivo e, por isso, descendente que decompõe sucessivamente um problema em subproblemas independentes triviais, resolvendo-os e combinando ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação as soluções em uma solução para o problema original. III. Um algoritmo guloso sempre faz escolhas que parecem ser as melhores no momento, ou seja, escolhas ótimas locais acreditando que estas escolhas o levem a uma solução ótima global. Por essa estratégia, nem sempre asseguram-se soluções ótimas, mas, para muitos problemas, as soluções são ótimas. Os problemas ideais para essa estratégia não devem ter a propriedade de subestrutura ótima. A análise permite concluir que A. todas as afirmativas são verdadeiras. B. todas as afirmativas são falsas. C. apenas as afirmativas I e II são verdadeiras. D. apenas as afirmativas II e III são verdadeiras. E. apenas a afirmativa III é verdadeira. 3. Cm base nos paradigmas de projeto de algoritmos, relacione a coluna da esquerda com a coluna da direita. (I) Tentativa e Erro. (A) Solução com garantia de distância da ótima. (II) Divisão e Conquista. (B) Subdivisão de problemas em partes menores, de tamanho semelhante. (III) Balanceamento. (C) Calcula a solução para os subproblemas, dos problemas menores para os maiores, armazenando os resultados parciais durante o processo, reutilizando-os assim que possível. (IV) Algoritmos Aproximados. (D) Geralmente exaurem-se todas as possibilidades para se encontrar uma solução. Todos os passos em direção à solução final são registrados. Se alguns dos passos não estiverem relacionados com a solução final, podem ser apagados. (V) Programação Dinâmica. (E) Divide problema em partes menores e combina sua solução em uma solução global. Assinale a alternativa que contém a associação correta. A. I-A, II-D, III-B, IV-C, V-E. B. I-B, II-A, III-C, IV-E, V-D. C. I-B, II-A, III-E, IV-D, V-C. D. I-C, II-A, III-D, IV-B, V-E. E. I-D, II-E, III-B, IV-A, V-C. ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação 4. Quanto à análise de algoritmos, considere as afirmativas a seguir. I. A programação dinâmica pode levar a soluções eficientes para algoritmos recursivos com complexidade exponencial. II. Os algoritmos tentativa e erro são impraticáveis com solução recursiva, pois são aplicados exaustivamente. III. Um algoritmo recursivo tem tempo de execução inferior à codificação iterativa para a solução do mesmo problema. IV. Uma árvore binária de pesquisa é adequada para a solução de problemas de natureza recursiva. Assinalem a alternativa correta. A. Somente as afirmativas I e II são corretas. B. Somente as afirmativas I e IV são corretas. C. Somente as afirmativas III e IV são corretas. D. Somente as afirmativas I, II e III são corretas. E. Somente as afirmativas II, III e IV são corretas. 5. Alice vai sair em uma viagem longa, que começa na estrada no quilômetro 0 (zero). Ao longo do caminho existem n hotéis, nos quilômetros a1 < a2 < ... < an, onde cada ai é medido partindo do ponto inicial. Os únicos lugares onde você pode parar são esses hotéis, mas pode escolher dentre eles em qual parar. Alice tem de parar no hotel final (no quilômetro an), que é o seu destino. Ela gostaria, idealmente, de viajar 200 quilômetros por dia, mas isso pode não ser possível (dependendo do espaçamento de hotéis). Se Alice viaja x quilômetros durante um dia, a penalização para aquele dia é (200 – x)2. Você quer planejar a sua viagem para minimizar a penalização total – ou seja, a soma das penalizações em todos os dias. Sendo assim, é possível aplicar programação dinâmica para tal problema de modo a desenvolver um algoritmo eficiente que determine a sequência ótima de hotéis nos quais parar? Justifiquem. Sim, pois se observa o princípio da otimalidade, uma vez que o custo ótimo global consiste em uma sequência ótima de hoteis – o que intrinsecamente compreende subproblemas sobrepostos, afinal incluir ou não um hotel acarreta em penalizações e podem impactar as demais decições em busca do ótimo global. Pode-se armazenar as penalizações em memória auxiliar, e numa visão bottom-up calcular as distâncias entre os hotéis e identificar aqueles ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação que minimizam as penalizações com base nos cálculos efetuados. 6. Yuckdonald's está pensando em abrir uma série de restaurantes ao longo da Quaint Valley Highway (QVH). Os n possíveis lugares estão ao longo de uma linha reta e as distâncias desses lugares partindo do começo da QVH são, em quilômetros e em ordem crescente, m1, m2, ..., mn. As restrições são as seguintes: • Em cada lugar, Yuckdonald's pode abrir no máximo um restaurante. O lucro esperado de abrir um restaurante no lugar i é pi, onde pi > 0 e i = 1, 2, ..., n. • Quaisquer dois restaurantes devem estar a, pelo menos, k quilômetros um do outro, onde k é um inteiro positivo. É viável aplicar programação dinâmica para computar o lucro total esperado máximo sujeito às dadas restrições? Justifiquem. Sim, pois se observa o princípio da otimalidade, uma vez que o lucro ótimo global consiste em uma sequência ótima de locais que provêem lucro máximo – o que intrinsecamente compreende subproblemas sobrepostos, afinal decidir sobre o local que garanta um lucro ótimo local impacta as demais decisões. Sob a visão bottom-up, pode-se calcular os lucros nos n lugares ao longo da linha rede identificar aqueles que maximizam o lucro global. 7. O seguinte algoritmo é basedo em programação dinâmica? Justifiquem. algoritmo7 (cn, …, c1, L) 1 para m 1 ← até n faça 2 X[m] ← 3 k m← 4 s c← m 5 enquanto k > 1 e s L ≤ faça 6 X’ (L − s)← 3 + X[k−1] 7 se X0 < X[m] então X[m] X’← 8 k k − 1← 9 s s + 1 + c← k 10 se s L ≤ então X[m] 0← 11 retorna X[1] Sim, pois se percebe um algoritmo iterativo no quala inicialização de área de memória auxiliar (2 a ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação 4), e sob uma visão bottom-up observamos que cálculos são efetuados a cada passo (subproblemas) de modo que a construção das soluções dos subproblemas são baseadas em valores ótimos (7). Os resultados são calculados, portanto, a partir de cálculos previamente calculados e armazenados em memória auxiliar (X). 8. O seguinte algoritmo é baseado em programação dinâmica? Justifiquem. algoritmo8 (n, p, c, v) 1 para b 0 ← até c faça 2 X[0, b] 0← 3 para j 1 ← até n faça 4 x X[j − 1, b]← 5 se b − pj 0≥ 6 então y X[j − 1, b − p← j] + vj 7 se x < y então x y← 8 X[j, b] x← 9 retorna X[n, c] Sim, pois se percebe um algoritmo iterativo no qual a inicialização de área de memória auxiliar (2), e sob uma visão bottom-up observamos que cálculos são efetuados a cada passo (subproblemas) de modo que a construção das soluções dos subproblemas são baseadas em valores ótimos (5 a 7). Os resultados são calculados, portanto, a partir de cálculos previamente calculados e armazenados em memória auxiliar (X). ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação Questões de Revisão Programação Dinâmica Nome: ___________________________________________________ Nome: ___________________________________________________ Data: 25/10/2016 Respostas Marque X na alternativa escolhida. Questão Resposta 1 A B C D E 2 A B C D E 3 A B C D E 4 A B C D E 5 A B C D E 6 A B C D E 7 A B C D E 8 A B C D E 9 A B C D E 10 A B C D E 11 A B C D E 12 A B C D E 13 A B C D E 14 A B C D E 15 A B C D E 16 A B C D E 17 A B C D E 18 A B C D E 19 A B C D E 20 A B C D E 21 A B C D E 22 A B C D E ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação Questão Resposta 23 A B C D E 24 A B C D E 25 A B C D E 26 A B C D E 27 A B C D E 28 A B C D E 29 A B C D E 30 A B C D E Questões de Revisão Questões de Revisão Respostas
Compartilhar