diplomsko delo
Domen Grzin (Avtor), Jurij Mihelič (Mentor)

Povzetek

Predstavimo problem strnjenega polnjenja košev, podamo formalno definicijo problema in navedemo primer za boljšo predstavo bralcu ter kasnejšo razlago algoritmov. Predstavimo tudi preslikavo problema razvršča\-nja štud\-entov v predavalnice na ta problem in druge uporabe. Predstavimo tri natančne in dva približna algoritma, s katerimi rešujemo optimizacijske probleme, kot je problem strnjenega polnjenja košev. Razvijemo implementacije predstavljenih algoritmov za problem. Implementacije algoritmov ekperimentalno ovrednotimo in med seboj primerjamo po času, ki ga porabijo, da pridejo do rešitve. Približne algoritme primerjamo tudi po tem, kako blizu je njihova rešitev optimalni.

Ključne besede

optimizacijski problem;požrešni algoritem;izčrpno preiskovanje;razveji in omeji;iskanje v širino;eksperimentalno ovrednotenje;univerzitetni študij;diplomske naloge;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UL FRI - Fakulteta za računalništvo in informatiko
Založnik: [D. Grzin]
UDK: 004(043.2)
COBISS: 100742915 Povezava se bo odprla v novem oknu
Št. ogledov: 187
Št. prenosov: 26
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Contiguous bin packing problem
Sekundarni povzetek: We present the problem of contiguous bin packing, give a formal definition of the problem and an example, for a better presentation to the reader and an easier explanation of the algorithms in later chapters. We also present a mapping of classifying students into lecture halls onto our problem and other uses. We present three exact algorithms and two heuristic algorithms for solving optimization problems such as the problem of contiguous bin packing. We develop an implementation for each of the presented algorithms. After developing the implementations we experimentally evaluate them and compare with each other in terms of the time it takes for them to return a solution. For approximate algorithms we also compare their given solutions, specifically how close these are to the correct ones given by the exact algorithms.
Sekundarne ključne besede: optimization problem;greedy algorithm;exhaustive enumeration;branch and bound;breadth-first search;experimental evaluation;computer science;diploma;Računalništvo;Univerzitetna in visokošolska dela;
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: 44 str.
ID: 14728278