Divide and Conquer
868 palavras
4 páginas
Divisão e ConquistaBruno Santos de Lima RA: 141251093
Eymar Ferrario de Lima RA: 141257792
Algoritmos e Técnicas de Programação II
1
Introdução
No estudo da resolução de problemas de maneira algorítmica encontramos uma serie de paradigmas da computação, que nada mais são que métodos ou estratégias de resolver um determinado problema.
Nesta coletânea abordaremos um desses paradigmas denominado Divisão e Conquista (Divide and Conquer).
2
Divisão e Conquista
Paradigma de Divide-and-conquer.
Consiste em:
Tendo um determinado problema, ocorre a divisão deste em subproblemas que são resolvidos e combinados para obter a solução do problema inicial.
3
4
Passo 1 - Divisão
Divisão do problema original subproblemas do mesmo tipo.
O processo de divisão ocorre até que a instancia do subproblema se torne muito pequena e de simples resolução.
em
5
Passo 2 - Conquista
No segundo passo ocorre a resolução de maneira recursiva de cada um dos subproblemas
Gerado pelo passo da divisão de maneira individual.
6
Passo 3 - Combinação
Por fim temos o terceiro e ultimo passo do processo.
Ocorre a combinação das soluções dos subproblemas.
Forma a solução do problema principal. 7
Divisão e Conquista
Busca Binária.
Algoritmo da mediana.
MergeSort.
QuickSort.
Algoritmo de Karatsuba e Ofman.
Algoritmo de Strassen.
8
QuickSort
Algoritmo de ordenação.
Charles Antony Richard Hoare, C.
A. R. Horare, em 1960.
Publicado em 1962.
É o algoritmo de ordenação mais eficientes que se conhece para a maioria dos casos, sendo assim um dos mais utilizados.
9
QuickSort
C. A. R. Horare, inicialmente criou o algoritmo ao tentar traduzir um dicionário de inglês para russo.
Ordenando as palavras.
Tentando reduzir o problema original em problemas menores e mais simples de serem resolvidos.
10
QuickSort
Escolha de um pivô arbitrário.
A esquerda, contendo somente elementos menores que o pivô.