Hyppää sisältöön
    • Suomeksi
    • In English
Trepo
  • Suomeksi
  • In English
  • Kirjaudu
Näytä viite 
  •   Etusivu
  • Trepo
  • Opinnäytteet - ylempi korkeakoulututkinto
  • Näytä viite
  •   Etusivu
  • Trepo
  • Opinnäytteet - ylempi korkeakoulututkinto
  • Näytä viite
JavaScript is disabled for your browser. Some features of this site may not work without it.

0-1 lait äärellisissä malleissa

VAHTERA, SATU (2012)

 
Avaa tiedosto
gradu06581.pdf (463.9Kt)
Lataukset: 



VAHTERA, SATU
2012

Matematiikka/tilastotiede - Mathematics/Statistics
Informaatiotieteiden yksikkö - School of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2012-02-14
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on
https://urn.fi/urn:nbn:fi:uta-1-23413
Tiivistelmä
Äärellisten mallien teoria on tietotekniikan kehityksen tarpeiden seurauksena kasvanut matemaattisen logiikan osa-alue. Teorian ensimmäisiä tuloksia oli Trakhtenbrotin tulos vuodelta 1950, jonka mukaan validius äärellisissä malleissa ei ole rekursiivisesti numeroituva. Nykyisin äärellisten mallien logiikat ovat usein perusta tietokantakyselyiden luomiseen ja äärellisten mallien teorian tekniikoiden avulla todistetaan hakujärjestelmien ilmaisuvoimaa ja monimuotoisuutta.

Äärellisissä malleissa, kuten suuntaamattomissa äärellisissä verkoissa, voidaan tutkia tietyn ominaisuuden toteutuvuuden todennäköisyyttä. Kun verkon solmujen määrä lähenee ääretöntä, saadaan ominaisuudelle asymptoottinen todennäköisyys. Matemaattisessa logiikassa hyvin mielenkiintoinen ilmiö on 0–1 lait, jotka käsittelevät ominaisuuksien asymptoottista todennäköisyyttä eri logiikoissa. Jos logiikalla on 0–1 laki, kaikkien siinä määriteltävien ominaisuuksien asymptoottinen todennäköisyys on 0 tai 1. Tässä tutkielmassa esitellään muutamia logiikoita ja tutkitaan onko niillä 0–1 laki.

Työssä tutustutaan aluksi verkkojen ominaisuuksiin ja määritellään kiintopisteen käsite, sekä muutama kiintopistelogiikka. Kiintopistelogiikoiden käsittelyä jatketaan määrittelemällä rajoitetun muuttujamäärän logiikat. Ehrenfeucht-Fraïssén peleistä esitellään helmipelit, joiden avulla saadaan todistettua tärkeitä tuloksia liittyen asymptoottisiin todennäköisyyksiin ja kyselyihin eri logiikoissa. Työn lopussa määritellään vielä laajennusaksioomat, jotka ovat tarpeellinen apuväline 0–1 lain todistamisessa.

Viitekirjoina työssä ovat Libkin, Leonid: Elements of Finite Model Theory ja Ebbinghaus, Heinz-Dieter & Flum, Jorg: Finite Model Theory.
Kokoelmat
  • Opinnäytteet - ylempi korkeakoulututkinto [35903]
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste
 

 

Selaa kokoelmaa

TekijätNimekkeetTiedekunta (2019 -)Tiedekunta (- 2018)Tutkinto-ohjelmat ja opintosuunnatAvainsanatJulkaisuajatKokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste