prikaz prve stranice dokumenta Optimizacija na matroidu
  Preuzmi
PDF 364.76 KB
diplomski rad
Optimizacija na matroidu
Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2017. urn:nbn:hr:217:402545
Badrov, Nikola
Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Institucijski repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta

Citirajte ovaj rad

Badrov, N. (2017). Optimizacija na matroidu (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:217:402545

Badrov, Nikola. "Optimizacija na matroidu." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2017. https://urn.nsk.hr/urn:nbn:hr:217:402545

Badrov, Nikola. "Optimizacija na matroidu." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2017. https://urn.nsk.hr/urn:nbn:hr:217:402545

Badrov, N. (2017). 'Optimizacija na matroidu', Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 22.11.2024., https://urn.nsk.hr/urn:nbn:hr:217:402545

Badrov N. Optimizacija na matroidu [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2017 [pristupljeno 22.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:402545

N. Badrov, "Optimizacija na matroidu", Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2017. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:402545

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:402545
Podaci o radu
NaslovOptimizacija na matroidu
AutorNikola Badrov
MentorVedran Krčadinac (mentor)
Član povjerenstvaVedran Krčadinac (predsjednik povjerenstva)
Član povjerenstvaMarko Tadić (član povjerenstva)
Član povjerenstvaMiljenko Huzak (član povjerenstva)
Član povjerenstvaMladen Vuković (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
(Matematički odsjek)
Zagreb
Datum i država obrane2017-02-24, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Sažetak
U ovom smo radu izložili osnove teorije matroida s naglaskom na primjene u optimizaciji. Pokazali smo da je matroid, struktura utemeljena na apstrahiranom pojmu nezavisnosti, prirodna struktura u pozadini pohlepnog algoritma. Dokazavši da je svaka matrica i graf matroid, definirali smo neke optimizacijske probleme u terminima teorije matroida te ih riješili koristeći odgovarajuće varijante pohlepnog algoritma. Nadalje, koristivši dualnu teoriju matroida, definirali smo algoritam plavog pravila i crvenog pravila, apstrahiranu varijantu mnogih pohlepnih algoritama, naročito koristan u teoriji grafova. Na kraju smo uveli pojam presjeka matroida te ga protumačili u terminima teorije grafova te dokazali Königov teorem.
Sažetak (engleski)
In this thesis we introduced the basics of theory of matroids with emphasis on its application in optimization. We showed that a matroid, a structure based on an abstract notion of independence, is the natural structure behind the greedy algorithm. By showing that every matrix and graph is a matroid, we were able to define some optimization problems in terms of matroid theory and solve them by using appropriate variants of the greedy algorithm. Furthermore, by using duality theory in matroids, we defined the blue rule - red rule algorithm, an abstract variant of many greedy algorithms, especially useful in graph theory. To conclude, we introduced matroid intersection and described it in terms of graph theory and proved König's theorem.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:217:402545
Studijski programNaziv: Financijska i poslovna matematika
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2017-04-20 09:25:58