Problemi razvrščanja intervalov

MIHELAK, PRIMOŽ (author), Hočevar, Tomaž (mentor)

Problemi razvrščanja intervalov so problemi, pri katerih imamo podane posle oziroma intervale, ki jih je potrebno procesirati ob določenem času. V večini primerov ne moremo procesirati vseh, zato se moramo odločiti, katere obdržimo in katere zavržemo. V diplomskem delu so predstavljene različice tega problema, med njimi takšne, kjer so intervali uteženi, ali pa imamo na voljo več procesorjev. Podane so tudi implementacije večine predstavljenih algoritmov v programskem jeziku Python. Izbrane algoritme tudi primerjamo glede njihovih časovnih zahtevnosti, ki so pred tem predstavljene poleg njihovih prostorskih zahtevnosti.

• Language: Slovenian
• Keywords: interval, razvrščanje, algoritem
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2024
• PID: 20.500.12556/RUL-161454
• COBISS.SI-ID: 212626435
• Publication date in RUL: 11.09.2024

Secondary language

• Language: English
• Title: Interval scheduling problems

Abstract

Interval scheduling problems are problems where we are given a set of jobs or intervals to process at a given time. In most cases, we are unable to process all of them, so we have to decide which we keep and which we discard. In the thesis, multiple variations of the problem are presented, in some of which the intervals have weights or there are multiple processors available. The implementations of most of the presented algorithms are also given in the Python programming language. Chosen algorithms are also compared regarding their time complexities, which were earlier presented together with their space complexities.

• Keywords: interval, scheduling, algorithm