Algoritmo guloso

Prévia do material em texto

Algoritmo guloso 
O que caracteriza um algoritmo guloso?
a) Ele busca a solucao otima global ao explorar todas as possibilidades
b) Ele faz escolhas locais otimas em cada passo, esperando obter uma solucao global otima
c) Ele utiliza forca bruta para testar todas as solucoes possiveis
d) Ele resolve problemas apenas de forma aproximada, sem garantir solucao otima
Resposta correta: b) Ele faz escolhas locais otimas em cada passo, esperando obter uma solucao
global otima
Explicacao: Algoritmos gulosos tomam decisoes baseadas na melhor escolha imediata sem
considerar o impacto futuro, o que em muitos casos leva a solucoes otimas ou boas aproximacoes.
Em qual tipo de problema o algoritmo guloso e mais eficiente?
a) Problemas onde as escolhas locais levam a solucao global otima
b) Problemas NP-completos sem nenhuma estrutura especifica
c) Problemas que exigem busca exaustiva
d) Problemas onde e necessario considerar todas as combinacoes possiveis
Resposta correta: a) Problemas onde as escolhas locais levam a solucao global otima
Explicacao: Algoritmos gulosos funcionam melhor em problemas com propriedade de subestrutura
otima e escolha gulosa, onde a melhor escolha local pode construir a solucao global otima.
Qual das seguintes propriedades e essencial para que um problema possa ser resolvido por um
algoritmo guloso com garantia de otimalidade?
a) Divisibilidade
b) Subestrutura otima
c) Crescimento exponencial
d) Aleatoriedade
Resposta correta: b) Subestrutura otima
Explicacao: A subestrutura otima significa que uma solucao otima para o problema pode ser
construida a partir de solucoes otimas para subproblemas menores, permitindo que decisoes locais
levem a solucao global.
O que significa a "propriedade de escolha gulosa" em um problema?
a) Que a solucao otima pode ser obtida escolhendo o melhor elemento local em cada etapa
b) Que todas as escolhas precisam ser avaliadas simultaneamente
c) Que o algoritmo deve usar forca bruta para encontrar a melhor solucao
d) Que o problema nao possui solucoes otimas
Resposta correta: a) Que a solucao otima pode ser obtida escolhendo o melhor elemento local em
cada etapa
Explicacao: A propriedade de escolha gulosa garante que, ao escolher o melhor elemento
localmente, o algoritmo constroi um caminho que leva a solucao otima do problema.
Qual destes problemas classicos e comumente resolvido com algoritmo guloso?
a) Problema da mochila 0-1
b) Problema do caminho minimo em grafos com arestas negativas
c) Problema do conjunto independente maximo em grafos gerais
d) Problema do conjunto de atividades para maximizar o numero de tarefas que podem ser
realizadas sem sobreposicao
Resposta correta: d) Problema do conjunto de atividades para maximizar o numero de tarefas que
podem ser realizadas sem sobreposicao
Explicacao: O problema do conjunto de atividades pode ser resolvido eficientemente por um
algoritmo guloso que seleciona atividades com o menor tempo de termino primeiro, garantindo
solucao otima.
Por que o algoritmo guloso nao e adequado para resolver o problema da mochila 0-1?
a) Porque nao existe solucao otima para esse problema
b) Porque as escolhas locais otimas nao garantem solucao global otima nesse problema
c) Porque o problema da mochila 0-1 e trivial
d) Porque o algoritmo guloso e muito lento para esse problema
Resposta correta: b) Porque as escolhas locais otimas nao garantem solucao global otima nesse
problema
Explicacao: No problema da mochila 0-1, a escolha local que parece melhor (como pegar o item
com maior valor por peso) pode impedir que a solucao global seja otima.
Como o algoritmo guloso toma suas decisoes?
a) Considera todas as possibilidades futuras para cada escolha
b) Escolhe a melhor opcao disponivel no momento, sem olhar para frente
c) Usa heuristicas baseadas em aprendizado de maquina
d) Gera solucoes aleatorias e escolhe a melhor apos varias tentativas
Resposta correta: b) Escolhe a melhor opcao disponivel no momento, sem olhar para frente
Explicacao: O algoritmo guloso escolhe a melhor alternativa imediata, sem considerar as
consequencias futuras das escolhas feitas.
O que significa subestrutura otima em algoritmos?
a) O problema pode ser dividido em subproblemas independentes
b) Uma solucao otima para o problema geral pode ser construida a partir de solucoes otimas para
seus subproblemas
c) O problema nao pode ser resolvido por metodos deterministicos
d) O problema possui solucao unica e trivial
Resposta correta: b) Uma solucao otima para o problema geral pode ser construida a partir de
solucoes otimas para seus subproblemas
Explicacao: A subestrutura otima e uma propriedade que permite usar estrategias como
programacao dinamica e algoritmos gulosos para resolver problemas de forma eficiente.
Em qual situacao o algoritmo guloso pode falhar em encontrar a solucao otima?
a) Quando o problema possui subestrutura otima
b) Quando a escolha local nao leva a solucao global otima
c) Quando o problema e trivial
d) Quando o problema e linear
Resposta correta: b) Quando a escolha local nao leva a solucao global otima
Explicacao: Algoritmos gulosos podem falhar em problemas onde decisoes locais otimas nao
garantem uma solucao global otima, o que acontece em muitos problemas complexos.
Qual das seguintes afirmacoes sobre algoritmos gulosos e verdadeira?
a) Sempre produzem a solucao otima para qualquer problema
b) Sao faceis de implementar e geralmente rapidos, mas nem sempre garantem a solucao otima
c) Sempre sao mais lentos que algoritmos de forca bruta
d) Usam inteligencia artificial para melhorar as decisoes locais
Resposta correta: b) Sao faceis de implementar e geralmente rapidos, mas nem sempre garantem
a solucao otima
Explicacao: Algoritmos gulosos sao simples e eficientes, mas podem nao ser adequados para todos
os problemas, especialmente aqueles sem subestrutura otima.
O que e uma heuristica gulosa?
a) Uma tecnica que escolhe aleatoriamente as opcoes para acelerar a execucao
b) Um metodo que faz escolhas locais para tentar encontrar uma boa solucao rapidamente, sem
garantia de otimalidade
c) Um algoritmo que sempre encontra a solucao otima
d) Um metodo para reduzir o espaco de busca por tentativa e erro
Resposta correta: b) Um metodo que faz escolhas locais para tentar encontrar uma boa solucao
rapidamente, sem garantia de otimalidade
Explicacao: Heuristicas gulosas sao usadas quando nao se pode garantir a solucao otima, mas e
importante encontrar uma solucao boa rapidamente.
No problema da cobertura de conjuntos, um algoritmo guloso pode:
a) Sempre encontrar a menor cobertura possivel
b) Encontrar uma cobertura, mas sem garantia de ser minima
c) Ser aplicado somente em grafos bipartidos
d) Nao ser aplicavel
Resposta correta: b) Encontrar uma cobertura, mas sem garantia de ser minima
Explicacao: Algoritmos gulosos sao frequentemente usados para problemas NP-dificeis como a
cobertura de conjuntos, onde encontram solucoes aproximadas, mas nao necessariamente otimas.
Qual e uma das principais vantagens dos algoritmos gulosos?
a) Garantia de encontrar a solucao otima em todos os casos
b) Eficiencia e simplicidade na implementacao
c) Necessidade de enorme poder computacional
d) Possibilidade de resolver problemas NP-completos em tempo polinomial
Resposta correta: b) Eficiencia e simplicidade na implementacao
Explicacao: Algoritmos gulosos sao simples e costumam ter baixa complexidade, o que os torna
eficientes para muitos problemas praticos.
Como o algoritmo guloso pode ser aplicado ao problema de construcao de arvore geradora minima
(MST)?
a) Escolhendo as arestas de maior peso primeiro
b) Selecionando arestas de menor peso que nao formem ciclos, como no algoritmo de Kruskal
c) Verificando todos os subconjuntos possiveis de arestas
d) Usando programacao dinamica
Resposta correta: b) Selecionando arestas de menor peso que nao formem ciclos, como no
algoritmo de Kruskal
Explicacao: O algoritmo de Kruskal e um exemploclassico de algoritmo guloso para MST,
escolhendo sempre a aresta de menor peso que nao cria ciclos.
Qual e a diferenca entre um algoritmo guloso e um algoritmo de programacao dinamica?
a) O guloso faz decisoes locais e nao revisita, enquanto programacao dinamica armazena
resultados para evitar recomputacoes
b) O guloso e sempre mais lento
c) A programacao dinamica nao resolve problemas de otimizacao
d) Algoritmos gulosos sempre usam recursao, enquanto programacao dinamica nao
Resposta correta: a) O guloso faz decisoes locais e nao revisita, enquanto programacao dinamica
armazena resultados para evitar recomputacoes
Explicacao: Programacao dinamica resolve subproblemas e combina solucoes, evitando
recomputacao, enquanto algoritmos gulosos tomam decisoes irrevogaveis localmente.
Qual das opcoes a seguir e uma desvantagem comum dos algoritmos gulosos?
a) Sao muito dificeis de entender
b) Podem nao encontrar solucoes otimas em todos os casos
c) Sao muito lentos para problemas grandes
d) Necessitam de muitos recursos computacionais
Resposta correta: b) Podem nao encontrar solucoes otimas em todos os casos
Explicacao: Apesar de simples e rapidos, algoritmos gulosos podem falhar em problemas onde a
melhor escolha local nao leva a solucao global otima.
Qual das alternativas apresenta um problema onde o algoritmo guloso encontra solucao otima?
a) Ordenacao de numeros
b) Selecao de atividades que nao se sobrepoem
c) Fatoracao de numeros inteiros
d) Problema do caixeiro viajante
Resposta correta: b) Selecao de atividades que nao se sobrepoem
Explicacao: O problema de selecao de atividades e um caso classico que pode ser resolvido com
algoritmo guloso, garantindo a solucao otima.
Por que o algoritmo guloso pode ser considerado uma estrategia heuristica?
a) Porque nunca encontra a solucao correta
b) Porque faz escolhas locais visando uma solucao boa, sem garantia de otimalidade
c) Porque usa inteligencia artificial para aprender com os dados
d) Porque explora todas as combinacoes possiveis
Resposta correta: b) Porque faz escolhas locais visando uma solucao boa, sem garantia de
otimalidade
Explicacao: Algoritmos gulosos podem funcionar como heuristicas que priorizam eficiencia e
rapidez sobre garantias absolutas de solucao otima.
Em relacao a complexidade computacional, os algoritmos gulosos geralmente sao:
a) De complexidade exponencial
b) De complexidade polinomial
c) Impossiveis de analisar
d) Dependentes exclusivamente do tamanho da memoria disponivel
Resposta correta: b) De complexidade polinomial
Explicacao: Algoritmos gulosos costumam ter complexidade polinomial, tornando-os eficientes para
muitos problemas.
Qual e o objetivo principal do algoritmo guloso?
a) Encontrar a solucao global otima ao avaliar todas as possibilidades
b) Construir uma solucao viavel passo a passo, fazendo a melhor escolha local em cada etapa
c) Testar combinacoes aleatorias para encontrar solucoes boas
d) Armazenar todas as solucoes possiveis para analise posterior
Resposta correta: b) Construir uma solucao viavel passo a passo, fazendo a melhor escolha local
em cada etapa
Explicacao: A essencia do algoritmo guloso esta em construir solucoes incrementalmente,
escolhendo sempre a melhor alternativa imediata.
Se desejar, posso continuar com mais perguntas para voce! Quer que eu faca?