Técnicas de Algoritmos

Técnicas de Algoritmos.

1) Explique o conceito de divisão e conquista?
Esta técnica consiste em dividir um problema maior recursivamente em problemas menores até que o problema possa ser resolvido diretamente. Então a solução do problema inicial é dada através da combinação dos resultados de todos os problemas menores computados.
2) Quais os passos básicos desta técnica.
Os passos básicos desta técnica são:
1- Dividir:
Dividir o problema em uma ou mais subproblemas
2- Conquistar:
Resolver os subproblemas caso esses sejam suficientemente pequenos, caso contrário continuar a divisão.
3- Combinar:
O resultado dos problemas menores são combinados até que seja obtida a solução do problema maior.
Combinar
3) Quais as vantagens de utilizar está técnica(divisão e conquista)?
Eficiência do algoritmo;Tratamento da complexidade; Paralelismo; Acesso à memória;
Indicado para aplicações que tem restrição de tempo; É de fácil implementação;
Simplifica problemas complexos.
4) Quando utilizar esta técnica (divisão e conquista)?
Existem três condições que indicam que a estratégia de divisão e conquista pode ser utilizada com sucesso:
1- Deve ser possível decompor uma instância em sub-instâncias.
2- A combinação dos resultados deve ser eficiente.
3- As sub-instâncias devem ser mais ou menos do mesmo tamanho.
5) Cite 3 algoritmos que utilize técnica (divisão e conquista) e explique de forma resumida estes algoritmos.? Obs: não utilizar nenhum dos algoritmos já vistos em outros exercícios/tarefas.
Algoritmo de Karatsuba:
É um método para multiplicar números grandes eficientemente, descoberto por em
Anatolii Alexeievitch Karatsuba 1960.
Algoritmo Strassen:

É um algoritmo utilizado para realizar a multiplicação de matrizes. Ele é assintoticamente mais rápido que o algoritmo tradicional, e é útil na prática ao lidar com matrizes grandes.
6 )Explique a técnica de Algoritmo Gulosos e para que é utilizada esta técnica.
Para resolver um problema, um