Partition Problem

bachelor's thesis

Emil Batakliev (Author), Borut Robič (Mentor), Anita Valmarska (Co-mentor)

Abstract

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.

Keywords

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

Data

Language:	English
Year of publishing:	2020
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[E. Batakliev]
UDC:	004(043.2)
COBISS:	27794179
Views:	1940
Downloads:	112
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Problem razdelitve
Secondary abstract:	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.
Secondary keywords:	podtabela;algoritem;zahtevnost;računalništvo in informatika;univerzitetni študij;diplomske naloge;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000468
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	47 str.
ID:	12025903