Viivästetyn hyväksynnän algoritmi ja sen sovellukset kouluhakuun

No Thumbnail Available
Files
Viljakainen_Roope_2024.pdf (460.72 KB)
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu | Bachelor's thesis
Electronic archive copy is available locally at the Harald Herlin Learning Centre. The staff of Aalto University has access to the electronic bachelor's theses by logging into Aaltodoc with their personal Aalto user ID. Read more about the availability of the bachelor's theses.
Date
2024-05-15
Department
Major/Subject
Tietotekniikka
Mcode
SCI3027
Degree programme
Teknistieteellinen kandidaattiohjelma
Language
fi
Pages
23
Series
Abstract
Tässä kandidaatintutkielmassa olen tutkinut Gale ja Shapleyn (1962) esittelemää parien muodostamiseen tarkoitettua viivästetyn hyväksynnän algoritmia. Algoritmi muodostaa kahden ryhmän välille pareja, jotka perustuvat kummankin ryhmän jäsenten omiin preferensseihin. Muodostuvat parit ovat vakaita, jolloin ei ole olemassa paria, joka olisi paremmassa tilanteessa toistensa kanssa kuin saatujen pariensa kanssa. Algoritmin toteutusta varten tarvitaan kaksi ryhmää, sekä jokaisen ryhmän jäsenen preferenssit listana toisesta ryhmästä. Näiden avulla pystytään rakentamaan tietorakenteet, joiden avulla algoritmi voidaan laskea ajassa O(n2). (Kleinberg ja Tardos, 2006.) Viivästetyn hyväksynnän algoritmilla on useita sovelluksia sekä muunnelmia. Alkuperäisessä artikkelissa (Gale ja Shapley, 1962) esiteltiin ns. avioliitto-ongelma sekä opiskelijoiden korkeakouluhaut, joista etenkin jälkimmäisen sovellukset ovat yhä käytössä monissa maissa. Algoritmin sovellukset myös esim. taloustieteen saralla, etenkin Rothin tutkimuksista, ovat johtaneet jopa ”Taloustieteiden Nobeliin” vuonna 2012. Viivästetyn hyväksynnän algoritmia on tutkittu yli 60 vuotta, mutta koneiden kehittyessä sen käyttämismahdollisuudet laajenevat entisestään. Laskenta-aika kasvaa nopeasti n kasvaessa, mutta nykyaikaisten tietokoneiden suorituskyvyn avulla tätä voidaan soveltaa entistä isompiin datajoukkoihin.
Description
Supervisor
Savioja, Lauri
Thesis advisor
Hirvonen, Juho
Keywords
viivästetyn hyväksynnän algoritmi, kouluhaku, algoritminen peliteoria, peliteoria
Other note
Citation