Algoritmos Gulosos

TEMA 02

Os algoritmos fazem parte do dia-a-dia das pessoas. As instruções para o uso de medicamentos, as indicações de como montar um aparelho qualquer, uma receita de culinária são alguns exemplos de algoritmos. Um algoritmo nada mais é do que uma descrição que mostra passo a passo os procedimentos necessários para a resolução de uma tarefa. De acordo com Ziviani (2004), um algoritmo pode ser visto como uma sequência de ações executáveis para a obtenção de uma solução para um determinado tipo de problema, em geral, é uma descrição passo a passo de como um problema é solucionável. A descrição deve ser finita, e os passos devem ser bem definidos, sem ambiguidades, e executáveis computacionalmente.

Um dos campos de concentração de estudos na área de algoritmos está relacionado a técnicas de projetos de algoritmos, segundo Cormen et al. (2002), técnicas de Projeto de Algoritmos é formado por um conjunto de métodos de codificação de algoritmos de forma a salientar sua complexidade, levando em conta a forma pela qual determinado algoritmo chega a solução desejada.

Existem muitas maneiras de projetar algoritmos. FAZER UM LINK COM DIVISAO e CONQUISTA, PROGRAMAÇAO DINAMICA E GULOSO.

DIVISÃO E CONQUISTA

De acordo com Ziviani (2007), 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. A técnica soluciona o problema através de três fases:

Divisão: o problema maior é dividido em problemas menores e os problemas menores obtidos são novamente divididos sucessivamente de maneira recursiva.

Conquista: o resultado do problema é calculado quando o problema é pequeno o suficiente.

Combinação: os resultados dos problemas menores são combinados até que seja obtida a solução do problema maior.

Vários problemas podem ser solucionados através desta técnica, como por exemplo o da ordenação de números através do algoritmo merge sort.

A altura (h) da árvore de execução é O (log n) e a quantidade de operações em cada nível da árvore é assintoticamente igual a O(n), conclui-se então que a complexidade do algoritmo no

pior caso é O(n log n).

O MergeSort (ordenação por intercalação) divide o vetor de entrada em dois outros vetores com metade do tamanho do vetor original (em caso de tamanho ímpar, um deles terá um elemento a mais que o outro). Cada um destes vetores menores é ordenado recursivamente utilizando o mesmo procedimento.

O MergeSort garante que os dois subproblemas têm tamanho da ordem de n/2, mas requer alocação de memória para o vetor temporário de tamanho n.

Problemas que utilizam esta técnica podem tirar proveito de máquinas com múltiplos processadores pois a fase de divisão em problemas menores proporciona uma divisão natural do trabalho. Cada um dos problemas menores obtidos pode ser calculado separadamente em um processador sem depender dos demais.

A solução por esta técnica também é eficiente no uso da memória cache pois ao final da fase de divisão grande parte dos dados necessários para a fase de combinação já estão disponíveis na cache proporcionando um acesso mais veloz aos dados. Porém o caráter recursivo das soluções acaba gerando um trabalho de processamento maior devido ao uso de chamadas recursivas e o uso da pilha de chamadas.

PROGRAMAÇÃO DINÂMICA

A Programação Dinâmica pode ser caracterizada como um processo sequencial de tomada de decisões, onde uma decisão ótima global pode ser obtida através da otimização de subproblemas (ou ótimos locais) individuais.

Na Programação