Gale-Shapleyev algoritam, varijacije i primjene

diplomski rad

• Autor: Ante Mijoč
• Mentor: Saša Singer (mentor)
• Član povjerenstva: Saša Singer (predsjednik povjerenstva)
• Član povjerenstva: Dražen Adamović (član povjerenstva)
• Član povjerenstva: Goran Igaly (član povjerenstva)
• Član povjerenstva: Vedran Čačić (č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-09-25, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom diplomskom radu opisuje se problem stabilnih brakova te se definira njegovo rješenje – stabilno sparivanje, kao i ostala njegova svojstva. Obrađuje se i algoritam koji rješava problem stabilnih brakova – Gale Shapleyev algoritam. Govori se o njegovoj složenosti i svojstvima. Promatramo i poopćenja osnovnog problema stabilnih brakova. Dajemo i definiciju stroge stabilnosti te navodimo algoritam koji pronalazi strogo stabilno rješenje, ukoliko ono postoji. Govorimo o problemu bolnice–specijalizanti, kao i o daljnjim poopćenjima problema stabilnih brakova.

Sažetak (engleski)

In this master thesis, we describe the stable marriage problem and we define its solution – the stable matching. We also define its properties. We elaborate an algorithm that solves the stable marriage problem – the Gale–Shapley algorithm. We talk about its complexity and its properties. We consider generalizations of the stable marriage problem, and we define the strong stability. We also give an algorithm which finds a strongly stable matching, if one exists. We present an insight into the hospital–residents problem, as well as into some further generalizations of the problem.

• Ključne riječi: problem stabilnih brakova; stabilno sparivanje; Gale Shapleyev algoritam; stroga stabilnost
• Ključne riječi (engleski): stable marriage problem; stable matching; Gale–Shapley algorithm; strong stability
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:491232
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2018-02-28 13:25:24