| dc.date.accessioned |
2015-10-06T08:29:33Z |
und |
| dc.date.accessioned |
2017-10-24T12:21:46Z |
|
| dc.date.available |
2015-10-06T08:29:33Z |
und |
| dc.date.available |
2017-10-24T12:21:46Z |
|
| dc.date.issued |
2015-10-06T08:29:33Z |
|
| dc.identifier.uri |
http://radr.hulib.helsinki.fi/handle/10138.1/5074 |
und |
| dc.identifier.uri |
http://hdl.handle.net/10138.1/5074 |
|
| dc.title |
Inflatorinen kiintopistelogiikka ja polynomisen ajan vaativuusluokka |
fi |
| ethesis.discipline |
Mathematics |
en |
| ethesis.discipline |
Matematiikka |
fi |
| ethesis.discipline |
Matematik |
sv |
| ethesis.discipline.URI |
http://data.hulib.helsinki.fi/id/44bc4f03-6035-4697-993b-cfc4cea667eb |
|
| ethesis.department.URI |
http://data.hulib.helsinki.fi/id/61364eb4-647a-40e2-8539-11c5c0af8dc2 |
|
| ethesis.department |
Institutionen för matematik och statistik |
sv |
| ethesis.department |
Department of Mathematics and Statistics |
en |
| ethesis.department |
Matematiikan ja tilastotieteen laitos |
fi |
| ethesis.faculty |
Matematisk-naturvetenskapliga fakulteten |
sv |
| ethesis.faculty |
Matemaattis-luonnontieteellinen tiedekunta |
fi |
| ethesis.faculty |
Faculty of Science |
en |
| ethesis.faculty.URI |
http://data.hulib.helsinki.fi/id/8d59209f-6614-4edd-9744-1ebdaf1d13ca |
|
| ethesis.university.URI |
http://data.hulib.helsinki.fi/id/50ae46d8-7ba9-4821-877c-c994c78b0d97 |
|
| ethesis.university |
Helsingfors universitet |
sv |
| ethesis.university |
University of Helsinki |
en |
| ethesis.university |
Helsingin yliopisto |
fi |
| dct.creator |
Karpansalo, Aleksi |
|
| dct.issued |
2015 |
|
| dct.language.ISO639-2 |
fin |
|
| dct.abstract |
Tutkielmassa esitetään kuvailevan vaativuusteorian tulos inflatorisen kiintopistelogiikan ja polynomisen ajan vaativuusluokan yhteydestä. Tuloksen todistamiseen tarvittavat logiikan ja vaativuusteorian pohjatiedot käydään tutkielmassa läpi. Joukko-opin perusteet ja yleiset merkinnät toivotaan lukijalle entuudesta tutuiksi.
Inflatorinen kiintopistelogiikka on ensimmäisen kertaluvun logiikan laajennus, johon on lisätty inflatoriseksi kiintopistekvantifioinniksi kutsuttu kaavanmuodostussääntö. Inflatorinen kiintopistekvantifiointi määrittelee relaation induktiivisesti ja sopii hyvin kuvailemaan tietokoneiden iteratiivisia ja rekursiivisia toimenpiteitä. Rajoittumalla äärellisiin järjestettyihin malleihin saadaan inflatorisen kiintopistelogiikan ilmaisuvoima vastaamaan vaativuusteorian polynomisen ajan vaativuusluokkaa.
Vaativuusteoriassa käytetään Turingin koneita työkaluna ongelmien ratkaisemiseen tarvittavia resursseja arvioitaessa. Resurssivaativuuksiltaan samankaltaisia ongelmia luokitellaan vaativuusluokkiin. Polynomisen ajan vaativuusluokka on luokka kaikille ongelmille, jotka voidaan ratkaista syötteen pituudesta polynomisesti riippuvassa määrässä Turingin koneen laskennan askelia.
Inflatorisen kiintopistelogiikan ja polynomisen ajan vaativuusluokan yhteyden osoittamiseksi tutkielmassa esitetään, kuinka kuvailla logiikan malleja Turingin koneilla ja Turingin koneita logiikan kaavoilla. Tarvittavien työkalujen esittelyjä seuraa tutkielman päätulos: inflatorinen kiintopistelogiikka karakterisoi polynomisen ajan vaativuusluokan. Lopuksi käydään läpi järjestyksen olettamisen tarpeellisuutta. |
fi |
| dct.language |
fi |
|
| ethesis.language.URI |
http://data.hulib.helsinki.fi/id/languages/fin |
|
| ethesis.language |
Finnish |
en |
| ethesis.language |
suomi |
fi |
| ethesis.language |
finska |
sv |
| ethesis.thesistype |
pro gradu-avhandlingar |
sv |
| ethesis.thesistype |
pro gradu -tutkielmat |
fi |
| ethesis.thesistype |
master's thesis |
en |
| ethesis.thesistype.URI |
http://data.hulib.helsinki.fi/id/thesistypes/mastersthesis |
|
| dct.identifier.urn |
URN:NBN:fi-fe2017112251225 |
|
| dc.type.dcmitype |
Text |
|
