Kaksoislaskenta
Airta, Ella (2022-06-30)
Airta, Ella
E. Airta
30.06.2022
© 2022 Ella Airta. Ellei toisin mainita, uudelleenkäyttö on sallittu Creative Commons Attribution 4.0 International (CC-BY 4.0) -lisenssillä (https://creativecommons.org/licenses/by/4.0/). Uudelleenkäyttö on sallittua edellyttäen, että lähde mainitaan asianmukaisesti ja mahdolliset muutokset merkitään. Sellaisten osien käyttö tai jäljentäminen, jotka eivät ole tekijän tai tekijöiden omaisuutta, saattaa edellyttää lupaa suoraan asianomaisilta oikeudenhaltijoilta.
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:oulu-202206303215
https://urn.fi/URN:NBN:fi:oulu-202206303215
Tiivistelmä
Tämän pro gradu -tutkielman tarkoituksena on esitellä kaksoislaskentaa diskreetin matematiikan näkökulmasta. Lyhyesti määriteltynä kaksoislaskenta tarkoittaa laskutapaa, jossa lasketaan samat joukot kahdella eri tavalla ja lopputulos on yhtäsuuri. Kaksoislaskennan perusajatus tiivistyy hyvin esimerkkiin, jossa äärellinen määrä ihmisiä tapaa juhlissa ja jotkut heistä kättelevät, mutta kukaan ei itseään eikä ketään kahdesti. Tällöin niiden ihmisten määrä, jotka kättelevät parittoman määrän muita ihmisiä, on aina parillinen. Tästä esimerkistä saadaan Kättelylemma, joka todistetaan kappaleessa 2.3.
Tutkielmassa tarkastellaan kaksoislaskennasta kahta mielenkiintoista ongelmaa. Ensimmäisenä tutkitaan kiintopisteen olemassaoloa. Monista kiintopistelauseista paneudutaan Brouwerin kiintopistelauseeseen tasossa ja havannoidaan sen käyttöä muun muassa peliteoriassa. Toinen kiinnostava ongelma on, kuinka suuria tai pieniä joukot voivat olla jollain tietyillä ehdoilla. Tällaisten ongelmien ratkaiseminen antaa lopputuloksena hyödyllisiä ylä- tai alarajoja esimerkiksi erilaisten verkkojen koolle.
Tutkielma pohjautuu teokseen Matousek, Nesetril: Invitation to discrete mathematics. Oxford OUP, Oxford, 2008. Tämä teos on lähteenä ellei toisin mainita. Tutkielman ymmärtämiseksi oletetaan lukijalta perustietoja yliopistotason matematiikasta. Verkkoteoriaa käsittelevä kappale on tiivistetty suoraan kandidaatin työstäni, jossa on sama lähdeteos.
Tutkielmassa tarkastellaan kaksoislaskennasta kahta mielenkiintoista ongelmaa. Ensimmäisenä tutkitaan kiintopisteen olemassaoloa. Monista kiintopistelauseista paneudutaan Brouwerin kiintopistelauseeseen tasossa ja havannoidaan sen käyttöä muun muassa peliteoriassa. Toinen kiinnostava ongelma on, kuinka suuria tai pieniä joukot voivat olla jollain tietyillä ehdoilla. Tällaisten ongelmien ratkaiseminen antaa lopputuloksena hyödyllisiä ylä- tai alarajoja esimerkiksi erilaisten verkkojen koolle.
Tutkielma pohjautuu teokseen Matousek, Nesetril: Invitation to discrete mathematics. Oxford OUP, Oxford, 2008. Tämä teos on lähteenä ellei toisin mainita. Tutkielman ymmärtämiseksi oletetaan lukijalta perustietoja yliopistotason matematiikasta. Verkkoteoriaa käsittelevä kappale on tiivistetty suoraan kandidaatin työstäni, jossa on sama lähdeteos.
Kokoelmat
- Avoin saatavuus [29359]