Divisao e conquista : uma tecnica para paralelizacao de algoritmos

Abstract

Neste trabalho é feito um estudo de algoritmos baseados na técnica de divisão e conquista. Para tanto, foi descrita a técnica com seus princípios e exemplificada através de alguns algoritmos. Entre os objetivos deste trabalho estão presentes a análise do ganho de rapidez na solução do problema (complexidade) e a análise das potencialidades de paralelização. Uma introdução à complexidade de algoritmos e noções sobre as classes de complexidade. Por fim, foram analisados vários problemas em que esta técnica tem se mostrado eficiente na solução dos problemas.

In this work is presented a algorithms study based on the divide and conquer technic. So, it was described the technic with its principies and showes by some algorithms. This work has objectives like analysis and complexity of algorithms and the analysis of the potential of the parallelization. This work approachs also the sequential and parallel algorithms and notions of classes of complexity. At last, many problems, in which this technic is efficient in the solution of problems were analysed.