Optimizacija na matroidu

diplomski rad

• Autor: Nikola Badrov
• Mentor: Vedran Krčadinac (mentor)
• Član povjerenstva: Vedran Krčadinac (predsjednik povjerenstva)
• Član povjerenstva: Marko Tadić (član povjerenstva)
• Član povjerenstva: Miljenko Huzak (član povjerenstva)
• Član povjerenstva: Mladen 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 obrane: 2017-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: matroid; optimizacija; pohlepni algoritam; algoritam plavog pravila i crvenog pravila; Königov teorem
• Ključne riječi (engleski): matroid; optimization; greedy algorithm; blue rule - red rule algorithm; König's theorem
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:402545
• Studijski program: Naziv: Financijska i poslovna matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2017-04-20 09:25:58