aalto1 untyped-item.component.html
Generalized poset sorting and its subproblems
Loading...
Files
Aalto login required (access for Aalto Staff only).
URL
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.
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Department
Major/Subject
Mcode
SCI3027
Degree programme
Language
en
Pages
22
Series
Abstract
Sorting algorithms solve the well known problem of finding the total order of a set by making comparisons. The problem of sorting can be generalized in two independent ways. The first generalization is to relax the requirement that the set must be ordered by a total order; instead only a partial order is required, yielding the poset sorting problem. The second is to restrict the set of comparisons the algorithm can make, yielding the generalized sorting problem. When both generalizations are combined one gets the generalized poset sorting problem. Additionally, there are various intermediary problems. This thesis surveys the current best algorithms for each variation of the aforementioned sorting problems. Additionally, the thesis presents an algorithm that solves generalized poset sorting in O(nlog(n)+nk+j²) queries where j=n(n-1)-m denotes the number of forbidden queries. This is an improvement over the naïve O(nlog(n)+nk+nj) query complexity.
Järjestämisalgoritmit ovat algoritmeja, jotka järjestävät joukon alkioita vertailemalla alkiopareja keskenään. Tämän järjestämisongelman voi yleistää kahdella toisistaan riippumattomalla tavalla. Ensimmäinen tapa on sallia joukon olla ainoastaan osittain järjestetty. Tätä kutsutaan osittaisjärjestämisongelmaksi (poset sorting problem). Toinen tapa on rajoittaa sallittujen parien joukkoa, mitä kutsutaan rajoitettujen vertailujen järjestysongelmaksi (generalized sorting problem). Tämän sallitujen parien joukon voi tulkita suuntaamattomaksi graafiksi, ja sitä merkitään kirjaimella G.
Näiden kahden yleistämisen yhdistelmää kutsutaan rajoitettujen vertailujen osittaisjärjestämisongelmaksi. On olemassa myös väliongelmia, joissa G:llä on jokin tietty ominaisuus. Esimerkiksi G voi olla kaksijakoinen tai Erdős–Rényi -satunnainen.
Tämän kandidaatintyön tavoite on koota tämänhetkinen tieto näistä ongelmista ja parhaista algoritmeista vertailujen asymptoottisen määrän mukaan (query complexity), sekä pohtia miten algoritmeja voisi parantaa erityisesti soveltamalla jo olemassaolevia algoritmeja. Työn on tarkoitus myös toimia johdatuksena aiheeseen ja tukea erityisesti niiden julkaisujen lukemista, joissa tämänhetkiset parhaat algoritmit on määritelty. Nämä julkaisut ovat työn pääasiallinen aineisto. Työssä ei ole kokeellista osuutta.
Työssä todistetaan uutena tuloksena, että kun G on lähes täydellinen, eli siitä puuttuu vain j kaarta, on olemassa algoritmi, joka ratkaisee rajoitettujen vertailujen osittaisjärjestämisongelman tekemällä ainoastaan O(j²) ylimääräistä vertailua informatioteoreettiseen minimikompleksisuuteen verrattuna, mikä on parempi kuin aiempi triviaali O(jn)-kompleksisuus, missä n on joukon koko.
Työssä todetaan, että järjestys- ja osittaisjärjestysalgoritmeja joissa G oletetaan täydelliseksi on vaikea yleistää rajoittaisen G:n järjestämiseen. Tätä perustellaan esittämällä kompleksisuustuloksia mielivaltaisten parien vertailuun (konkreettisesti mielivaltainen vertailu on Ω(n)). Toisaalta osoitetaan, että rajoitettujen vertailujen järjestysalgoritmit tarvitsevat lisäksi tavan kerätä tietoa toisistaan vertaamattomista pareista.
Työssä myös todistetaan järjestysongelmille jo tiedossa olevat informaatioteoreettiset minimikompleksisuudet ja osittain järjestetyn joukon järjestysongelmalle annetaan algoritmi, joka todistetaan kompleksisuudeltaan optimaaliseksi. Sen lisäksi muiden osa-ongelmien algoritmien toiminnasta ja komplekisuuden todistamisesta annetaan kuvaus. Työssä myös vertaillaan eri osa-ongelmien algoritmeja ja arvioidaan niiden soveltuvuutta muihin osa-ongelmiin.