Partition Problem

bachelor's thesis

Emil Batakliev (Avtor), Borut Robič (Mentor), Anita Valmarska (Komentor)

Povzetek

In this thesis we will focus on different algorithms for solving the Partition Problem. First, we will explain what the Partition Problem is and why it has been causing so many difficulties even in its simplest form. Then we will focus on different methods and algorithms for solving this problem that were published in the last few decades. We will explain their underlying ideas, positive and negative properties, asymptotic time complexities, and their actual speed. We will also present an algorithm that is based on our own ideas. All the algorithms will be experimentally evaluated on a set of problem instances. The goal of this work is not to find the best algorithm for the problem of partitioning, but rather to explain various algorithms for solving it, emphasize their positive and negative sides, thus allowing the user to pick the most appropriate algorithm for the scenario/problem instance at hand.

Ključne besede

subarray;algorithm;complexity;computer and information science;diploma;

Podatki

Jezik:	Angleški jezik
Leto izida:	2020
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[E. Batakliev]
UDK:	004(043.2)
COBISS:	27794179
Št. ogledov:	1940
Št. prenosov:	112
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Problem razdelitve
Sekundarni povzetek:	V delu se bomo osredotočili na razne algoritme za rešavanje Problema Razdelitve. Najprej bomo pojasili, kaj je problem razdelitve in zakaj je v preteklosti povzročil - celo v svoji najenostavnejši različici - toliko preglavic. Nato se bomo posvetili raznim metodam in algoritmom za rešavanje tega problema, ki so bili objavljeni v zadnjem desetletju. Razložili bomo njihove zamisli, prednosti in slabosti, njihove asimptotične časovne zahtevnosti in dejanske hitrosti. Predstavili bomo tudi algoritem, ki smo ga zasnovali sami. Vse algoritme bomo eksperimentalno ovrednotili, na množici primerov problema. Cilj našega dela ni poiskati najboljši algoritem za problem razdelitve, pač pa razložiti delovanje takšnih algoritmov, izpostaviti njihove prednosti in slabosti, in tako omogočiti uporabniku, da izbere tistega, ki je za rešitev njegove situacije/primera problema, najprimernejši.
Sekundarne ključne besede:	podtabela;algoritem;zahtevnost;računalništvo in informatika;univerzitetni študij;diplomske naloge;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000468
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	47 str.
ID:	12025903