[PosComp] [2016] Questão 25

QUESTÃO 25 – Em relação ao projeto de algoritmos, relacione a Coluna 1 à Coluna 2.

Coluna 1

1. Tentativa e Erro.
2. Divisão e Conquista.
3. Guloso.
4. Aproximado.
5. Heurística.

Coluna 2

( ) O algoritmo decompõe o processo em um número finito de subtarefas parciais que devem ser exploradas exaustivamente.
( ) O algoritmo divide o problema a ser resolvido em partes menores, encontra soluções para as partes e então combina as soluções obtidas em uma solução global.
( ) O algoritmo constrói por etapas uma solução ótima. Em cada passo, após selecionar um elemento da entrada (o melhor), decide se ele é viável (caso em que virá a fazer parte da solução) ou não. Após uma sequência de decisões, uma solução para o problema é alcançada.
( ) O algoritmo gera soluções cujo resultado encontra-se dentro de um limite para a razão entre a solução ótima e a produzida pelo algoritmo.
( ) O algoritmo pode produzir um bom resultado, ou até mesmo obter uma solução ótima, mas pode também não produzir solução nenhuma ou uma solução distante da solução ótima.
A ordem correta de preenchimento dos parênteses, de cima para baixo, é:

A) 1 – 2 – 3 – 4 – 5.
B) 2 – 3 – 4 – 5 – 1.
C) 3 – 4 – 5 – 1 – 2.
D) 4 – 5 – 1 – 2 – 3.
E) 5 – 1 – 2 – 3 – 4.


Resposta

A) 1 – 2 – 3 – 4 – 5.

Tentativa e erro: decompor o processo em um número finito de subtarefas parciais que devem ser exploradas exaustivamente. O processo de tentativa gradualmente constrói e percorre uma árvore de subtarefas.

Algoritmos tentativa e erro não seguem regra fixa de computação: 
– Passos em direção à solução final são tentados e registrados; 
– Caso esses passos tomados não levem à solução final, eles pode m ser retirados e apagados do registro. 

Quando a pesquisa na árvore de soluções cresce rapidamente é necessário usar algoritmos aproximados ou heurísticas que não garantem a solução ótima mas são rápidas.

Divisão e conquista: Consiste em dividir o problema em partes menores, encontrar soluções para as partes, e combiná-las em uma solução global.

Gulosos: Resolve problemas de otimização. 
• Ex: encontrar o menor caminho entre dois vértices de um grafo. – Escolhe a aresta que parece mais promissora em qualquer instante; – Independente do que possa acontecer, nunca reconsidera a decisão. 
• Não necessita avaliar alternativas, ou usar procedimentos sofisticados para desfazer decisões tomadas previamente. 
• Problema geral: dado um conjunto C, determine um subconjunto S ⊆ C tal que: – S satisfaz uma dada propriedade P, e – S é mínimo (ou máximo) em relação a algum critério α. 
• O algoritmo guloso consiste em um processo iterativo em que S é construído adicionando-se ao mesmo elementos de C um a um.
Para construir a solução ótima existe um conjunto ou lista de candidatos. 
• São acumulados um conjunto de candidatos considerados e escolhidos, e o outro de candidatos considerados e rejeitados. 
• Existe função que verifica se um conjunto particular de candidatos produz uma solução (sem considerar otimalidade no momento).
• Outra função verifica se um conjunto de candidatos é viável (também sem preocupar com a otimalidade).
• Uma função de seleção indica a qualquer momento quais dos candidatos restantes é o mais promissor. 
• Uma função objetivo fornece o valor da solução encontrada, como o comprimento do caminho construído (não aparece de forma explicita no algoritmo guloso).


Aproximado: Problemas que somente possuem algoritmos exponenciais para resolvê-los são considerados “difíceis”. 
• Problemas considerados intratáveis ou difíceis são muito comuns. 
• Exemplo: problema do caixeiro viajante cuja complexidade de tempo é O ( n!). 
• Diante de um problema difícil é comum remover a exigência de que o algoritmo tenha sempre que obter a solução ótima. 
• Neste caso procuramos por algoritmos eficientes que não garantem obter a solução ótima, mas uma que seja a mais próxima possível da solução ótima.

Heuristica: é um algoritmo que pode produzir um bom resultado, ou até mesmo obter a solução ótima, mas pode também não produzir solução alguma ou uma solução que está distante da solução ótima.