Algoritmo guloso

Prévia do material em texto

Algoritmo guloso 
O que caracteriza um algoritmo guloso?
a) Sempre escolhe a melhor solucao global de forma imediata.
b) Toma decisoes localmente otimas em cada etapa, esperando que isso leve a uma solucao global
otima.
c) Testa todas as solucoes possiveis antes de escolher a melhor.
d) Utiliza recursao para explorar todas as combinacoes possiveis.
Resposta: b) Um algoritmo guloso funciona tomando decisoes locais otimas em cada etapa, com a
esperanca de que essas escolhas levem a uma solucao global otima. Nem sempre garante a
solucao otima, mas costuma ser eficiente e simples de implementar.
Em qual tipo de problema um algoritmo guloso e mais eficaz?
a) Problemas sem subestrutura otima.
b) Problemas com subestrutura otima e propriedade de escolha gulosa.
c) Problemas que exigem forca bruta.
d) Problemas que nao possuem solucoes factiveis.
Resposta: b) Algoritmos gulosos funcionam melhor em problemas que possuem subestrutura otima
(uma solucao otima pode ser construida a partir de solucoes otimas de subproblemas) e
propriedade de escolha gulosa (uma escolha local otima leva a uma solucao global otima).
Qual e a diferenca principal entre algoritmos gulosos e programacao dinamica?
a) Algoritmos gulosos sempre usam recursao, enquanto programacao dinamica nao.
b) Algoritmos gulosos tomam decisoes locais sem reconsideracao, enquanto a programacao
dinamica resolve todos os subproblemas e combina solucoes.
c) Algoritmos gulosos sao mais lentos que programacao dinamica.
d) Nao ha diferenca; ambos funcionam da mesma maneira.
Resposta: b) A principal diferenca e que algoritmos gulosos fazem escolhas locais sem
reconsidera-las, enquanto a programacao dinamica resolve todos os subproblemas e combina
solucoes para garantir uma solucao global otima.
Qual dos problemas abaixo e classicamente resolvido por algoritmo guloso?
a) Multiplicacao de matrizes
b) Problema da mochila fracionaria
c) Ordenacao por fusao
d) Fatoracao de numeros inteiros
Resposta: b) O problema da mochila fracionaria e um exemplo classico em que um algoritmo
guloso e eficiente, pois permite pegar fracoes de itens e a escolha do item com maior valor por
peso em cada etapa garante a solucao otima.
No problema da selecao de atividades, qual estrategia gulosa e usada para garantir o maximo
numero de atividades nao sobrepostas?
a) Escolher atividades na ordem em que aparecem
b) Escolher atividades com menor duracao
c) Escolher sempre a atividade que termina mais cedo
d) Escolher atividades com maior inicio
Resposta: c) A estrategia gulosa que garante o maximo de atividades e sempre selecionar a
atividade que termina mais cedo, pois isso libera mais espaco para escolher atividades
subsequentes sem sobreposicao.
Por que nem todo problema pode ser resolvido corretamente usando um algoritmo guloso?
a) Porque algoritmos gulosos sao sempre lentos
b) Porque nem todos os problemas possuem subestrutura otima ou propriedade de escolha gulosa
c) Porque eles usam muita memoria
d) Porque so funcionam com numeros inteiros
Resposta: b) Alguns problemas nao podem ser resolvidos com algoritmo guloso porque as decisoes
locais otimas podem nao levar a solucao global otima, geralmente por nao possuirem subestrutura
otima ou propriedade de escolha gulosa.
No problema da mochila 0-1, por que um algoritmo guloso nao garante solucao otima?
a) Porque ele nao considera o valor total de todos os itens combinados
b) Porque nao permite pegar fracoes de itens
c) Porque so funciona com itens de peso unitario
d) Porque exige recursao infinita
Resposta: b) No problema da mochila 0-1, itens nao podem ser fracionados, entao uma escolha
gulosa baseada apenas no valor por peso pode nao resultar na combinacao global de maior valor,
diferentemente do problema da mochila fracionaria.
Como um algoritmo guloso decide qual elemento escolher em cada passo?
a) Aleatoriamente
b) Sempre escolhe o proximo elemento que parece mais promissor segundo algum criterio
especifico
c) Faz uma busca exaustiva de todas as possibilidades
d) Depende de simulacao Monte Carlo
Resposta: b) Um algoritmo guloso define um criterio de escolha e, a cada passo, seleciona o
elemento que parece mais promissor segundo esse criterio, sem voltar atras nas decisoes
anteriores.
Qual e a complexidade geral de um algoritmo guloso tipico?
a) Exponencial
b) Polinomial
c) Logaritmica
d) Nao pode ser determinada
Resposta: b) Algoritmos gulosos geralmente tem complexidade polinomial, pois tomam decisoes
sequenciais e nao exploram todas as combinacoes possiveis, o que os torna eficientes para muitos
problemas praticos.
Qual das seguintes propriedades deve ser verificada para garantir que um algoritmo guloso seja
correto?
a) Subestrutura otima
b) Propriedade de escolha gulosa
c) Ambos, subestrutura otima e propriedade de escolha gulosa
d) Nenhuma das anteriores
Resposta: c) Para garantir que um algoritmo guloso produza a solucao otima, o problema deve ter
subestrutura otima (solucao global otima construida a partir de subproblemas) e propriedade de
escolha gulosa (escolhas locais otimas levam a solucao global).
No algoritmo de Huffman, qual e a base do criterio guloso?
a) Escolher os simbolos mais frequentes para formar nos mais altos
b) Combinar sempre os dois simbolos de menor frequencia
c) Agrupar os simbolos em pares aleatorios
d) Codificar cada simbolo com comprimento fixo
Resposta: b) No algoritmo de Huffman, a estrategia gulosa consiste em combinar repetidamente os
dois simbolos de menor frequencia, garantindo a construcao de uma arvore de prefixos com
comprimento medio minimo, resultando em compressao eficiente.
Em problemas de grafos, qual e um exemplo de algoritmo guloso?
a) Busca em profundidade
b) Algoritmo de Dijkstra
c) Fatoracao de numeros
d) Ordenacao rapida
Resposta: b) O algoritmo de Dijkstra para encontrar o caminho minimo em grafos com pesos
positivos e um exemplo de algoritmo guloso, pois seleciona em cada etapa o vertice com a menor
distancia conhecida, expandindo progressivamente a solucao.
Qual e a diferenca entre algoritmo guloso e heuristica?
a) Algoritmos gulosos garantem solucao otima para todos os problemas, enquanto heuristicas nao
b) Heuristicas podem nao seguir a propriedade de escolha gulosa e nao garantem solucao otima,
enquanto algoritmos gulosos podem garantir em problemas especificos
c) Nao ha diferenca, sao a mesma coisa
d) Algoritmos gulosos sao sempre mais lentos que heuristicas
Resposta: b) Heuristicas sao metodos gerais para encontrar boas solucoes aproximadas e podem
nao seguir uma regra de escolha gulosa, enquanto algoritmos gulosos seguem regras especificas e
podem garantir solucao otima se o problema tiver subestrutura otima e propriedade de escolha
gulosa.
No problema do troco, qual criterio guloso e geralmente utilizado?
a) Dar sempre a menor moeda disponivel
b) Dar sempre a moeda de maior valor possivel ate completar o troco
c) Dividir o valor do troco pelo numero de moedas
d) Escolher moedas aleatoriamente
Resposta: b) No problema do troco com moedas de valores especificos, a estrategia gulosa tipica e
sempre usar a moeda de maior valor disponivel ate completar o troco, que em sistemas de moedas
canonicos garante a quantidade minima de moedas.
O algoritmo guloso e sempre a melhor escolha para resolver problemas NP-hard?
a) Sim, sempre
b) Nao, ele pode fornecer apenas solucoes aproximadas para NP-hard
c) Sim, desde que o problema seja grande
d) Nao, porque NP-hard nao tem solucoes
Resposta: b) Para problemas NP-hard, algoritmos gulosos geralmente fornecem solucoes
aproximadas ou heuristicas, mas nao garantem a solucao otima, ja que encontrar a solucao otima
desses problemas exige tempo exponencial na maioria dos casos.
Como e possivel verificar se um algoritmo guloso funciona corretamente para um problema
especifico?
a) Apenas implementando e testando casos aleatorios
b) Demonstrando que o problema possui subestrutura otima e propriedade de escolhagulosa
c) Comparando com forca bruta para numeros pequenos
d) Nenhuma das anteriores
Resposta: b) A forma teorica de garantir que um algoritmo guloso funcione corretamente e
demonstrar matematicamente que o problema possui subestrutura otima e propriedade de escolha
gulosa, o que assegura que escolhas locais otimas levam a solucao global otima.
Em qual situacao o algoritmo guloso e a programacao dinamica podem gerar a mesma solucao?
a) Quando o problema possui subestrutura otima e escolha gulosa
b) Quando o problema nao possui solucao
c) Sempre que os dados forem aleatorios
d) Nunca, pois os metodos sao incompativeis
Resposta: a) Quando o problema tem subestrutura otima e propriedade de escolha gulosa, tanto
algoritmos gulosos quanto programacao dinamica podem gerar a mesma solucao otima, embora o
guloso seja geralmente mais eficiente.
Qual e a principal vantagem de um algoritmo guloso sobre a programacao dinamica?
a) Garante sempre solucao otima
b) Menor complexidade e implementacao mais simples
c) Funciona para todos os problemas
d) Usa memoria exponencial
Resposta: b) Algoritmos gulosos sao geralmente mais simples de implementar e tem menor
complexidade computacional, ja que nao precisam armazenar todas as solucoes de subproblemas
como na programacao dinamica.
No problema de cobertura minima de vertices, e possivel usar um algoritmo guloso para garantir a
solucao otima?
a) Sim, sempre
b) Nao, normalmente fornece apenas aproximacoes
c) Sim, se o grafo for completo
d) Sim, se o grafo tiver apenas 3 vertices
Resposta: b) Para problemas NP-hard como cobertura minima de vertices, algoritmos gulosos nao
garantem solucao otima, mas podem ser usados para encontrar solucoes aproximadas eficientes
em tempo polinomial.
Qual e o papel de uma funcao de avaliacao em algoritmos gulosos?
a) Determinar aleatoriamente a proxima escolha
b) Estabelecer o criterio que define a escolha local otima em cada passo
c) Armazenar todas as solucoes possiveis
d) Resolver o problema por forca bruta
Resposta: b) A funcao de avaliacao define o criterio para escolher, a cada passo, o elemento mais
promissor segundo o principio guloso, sendo essencial para o funcionamento correto do algoritmo.
Se voce quiser, posso continuar essa lista ate exceder 1000 palavras, mantendo explicacoes
detalhadas e exemplos claros, para formar um documento completo. Quer que eu faca isso?