Algoritmi ``Podijeli pa vladaj''

master's thesis

• Author: Petra Penzer
• Mentor: Saša Singer (mentor)
• Committee member: Saša Singer (predsjednik povjerenstva)
• Committee member: Vedran Krčadinac (član povjerenstva)
• Committee member: Tina Bosner (član povjerenstva)
• Committee member: Robert Manger (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2016-09-26, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Ovaj diplomski rad opisuje metodu "podijeli pa vladaj" koja se koristi za oblikovanje algoritama. Rad je podijeljen u tri poglavlja. Prvo poglavlje detaljnije opisuje spomenutu metodu, a navedeni su i koraci algoritama oblikovani ovom metodom. Također, u ovom poglavlju opisane su rekurzivne relacije, koje koristimo prilikom analize vremenske složenosti algoritama opisanih u drugom poglavlju. Drugo poglavlje opisuje algoritam binarnog pretraživanja, mergesort algoritam, quick-sort algoritam, algoritam množenja velikih cijelih brojeva te algoritam množenja matrica koji su oblikovani navedenom metodom. Za navedene algoritme je analizirana njihova vremenska složenost te je naveden njihov pseudokod. U trećem poglavlju rada implementirani su neki od navedenih algoritama u programskom jeziku C++. Algoritmi su testirani mjerenjem vremena izvršavanja u odnosu na veličinu ulaznih podataka, a rezultati testiranja su prikazani tablicom i grafom. Dakle, ovim diplomskom radom dolazimo do zaključka da je proučavana metoda ”podijeli pa vladaj” vrlo važna metoda dizajniranja algoritama koja se u praksi često koristi. Ovom metodom se mogu dobiti efikasni algoritmi za rješavanje nekih problema te je vrlo jednostavna i zanimljiva za korištenje.

Abstract (english)

This master thesis describes the “divide and conquer” method which is used in the design of algorithms. The thesis is divided into three chapters. The first chapter describes the basic principles of ”divide and conquer”, and general steps of the algorithms designed by this method. Also, in this chapter, there is a brief review of main results from the theory of recursive relations that are used in the analysis of time complexity of the algorithms mentioned in the second chapter. The second chapter contains several algorithms which are designed by the ”divide and conquer” method: the binary search algorithm, mergesort, quicksort, multiplication of large integers, and multiplication of matrices. For these algorithms, there is an analysis of their time complexity and their pseudocode. In the third chapter of this thesis, we give implementations of some of the before mentioned algorithms in the C++ programming language. The algorithms are tested by measuring the execution time for various sizes of the input data. The results of each test are presented in table and graphic forms. This master thesis on the ”divide and conquer” method concludes that this is a very important method for the design of algorithms. This method is widely used in practice because it can produce efficient algorithms for solving some of the problems. The method is also very simple and interesting

• Keywords: metoda "podjeli pa vladaj"; algoritam binarnog pretraživanja; mergesort algoritam; quick-sort algoritam; algoritam množenja velikih cijelih brojeva; algoritam množenja matrica; programski jezik C++
• Keywords (english): “divide and conquer” method; binary search algorithm; mergesort algorithm; quicksort algorithm; multiplication of large integers algorithm; multiplication of matrices algorithm; C++ programming language
• Language: croatian
• URN:NBN: urn:nbn:hr:217:799000
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-01-29 11:53:02