Operaatori μx(n 1) abil ()-arvutatavatest funktsioonidest saadud funktsioonide ()-arvutatavus (0)

Tallinna Ülikool - Matemaatika - Matemaatiline loogika ja algoritmiteooria

1 Hindamata

Operaatori μx n 1-abil---arvutatavatest funktsioonidest saadud funktsioonide---arvutatavus #1

Operaatori μx n 1-abil---arvutatavatest funktsioonidest saadud funktsioonide---arvutatavus #2

Operaatori μx n 1-abil---arvutatavatest funktsioonidest saadud funktsioonide---arvutatavus #3

Operaatori μx n 1-abil---arvutatavatest funktsioonidest saadud funktsioonide---arvutatavus #4

Operaatori μx n 1-abil---arvutatavatest funktsioonidest saadud funktsioonide---arvutatavus #5

Operaatori μx n 1-abil---arvutatavatest funktsioonidest saadud funktsioonide---arvutatavus #6

Operaatori μx n 1-abil---arvutatavatest funktsioonidest saadud funktsioonide---arvutatavus #7

Operaatori μx n 1-abil---arvutatavatest funktsioonidest saadud funktsioonide---arvutatavus #8

Operaatori μx n 1-abil---arvutatavatest funktsioonidest saadud funktsioonide---arvutatavus #9

50 punkti Autor soovib selle materjali allalaadimise eest saada 50 punkti.

~ 9 lehte Lehekülgede arv dokumendis

2014-04-08 Kuupäev, millal dokument üles laeti

12 laadimist Kokku alla laetud

0 arvamust Teiste kasutajate poolt lisatud kommentaarid

Pedemunn112 Õppematerjali autor

Käesolevas referaadis keskendume operaatori μ abil saadud funktsioonide (*)-arvutatavusele, need funktsioonid on osaliselt rekursiivsed. Selleks, et uurida selliseid protsesse toome sisse vajalikud mõisted ja definitsioonid ning tõestame lemma, mis tõestab, et (*)-arvutatavatest funktsioonidest operaatori μx_(n 1) abil saadud funktsioonid on samuti (*)-arvutatavad. Anname ka sellise teoreemi tõestamise idee, mis ütleb, et iga osaliselt rekursiivne funktsioon on Turingi mõttes arvutatav ehk antud juhul (*)-arvutatav.

matemaatiline loogika matemaatika turing masin lint müü operaator

Sarnased õppematerjalid

pdf

Rekursiooni ja keerukusteooria eksami konspekt

Rekursiooni ja keerukusteooria eksami jaoks tehu korralik ja sisukas konspekt koos joonistega. Teemad: Lõplikud automaadid ja regulaarsed keeled. Regulaarsete keelte omadusi. Regulaarsed avaldised. Deterministlikud ja mittedeterministlikud lõplikud automaadid. Regulaarsete avaldiste ja lõplike automaatide samaväärsus. Keele regulaarsuse tarvilik tingimus (pumpamise lemma). Myhill-Nerode teoreem. Fraasisturktuuri grammatikad ja keeled. KV keeled. KV keelte ühesus. KV grammatika Chomsky normaalkuju. KV-keelte süntaksanalüüsi ülesanne. CKY-algoritm. Pinuautomaadid. KV grammatikat realiseeriv pinuautomaat. Ühe olekuga pinuautomaatide ja Greibachi mõttes normaliseeritud KV-grammatikate ekvivalentsus. Taandatud KV grammatikad. KV-keelte tarvilikkuse tingimus. Kontesist sõltuvad keeled ja Turingi masina keeled. Turingi masin ja registermasin. Lahenduvad ja rekursiivselt loenduvad hulgad. Turingi masina kodeerimine. Algoritmiliselt mittelahenduvad ülesanded. Church-Turingi tees. Lihtrekursiivsed funktsioonid, nende arvutatavus Turingi mõttes. Minimeerimisoperaator. Osaliselt rekursiivsed funktsioonid. Cantori funktsioonid. Arvutatava funktsiooni ühekohalised esindajad. Rekursiivsete funktsioonide arvutatavus. Ühekohaliste funktsioonide arvutatavus. Gödeli numbrid. Kleene' s-n-m-teoreem. Rekursiivsete funktsioonide püsipunktiprintsiip. Rice'i teoreem. Posti vastavuse probleemi mittelahenduvus. Mittelahenduvate ülesannete näited. Ülesannete redutseeritavus. KV keelte ühesuse mittelahenduvus. Algoritmide keerukuse hindamine. Algoritmi keerukuse sõltuvus arvutamismudelist. Ülesannete keerukusklassid. Deterministlik vs mittedeterministlik keerukus. Ülesannete polünomiaalne redutseeritavus ja NP-täielikud ülesanded. SAT kui NP täielik ülesanne. Randomiseeritud algoritmid. Las Vegase ja Monte Carlo tüüpi algoritmid. Fermat väike teoreem ja algarvulisuse testid.

Informaatika

doc

Teoreetilibe informaatika kordamisküsimused

Kordamisküsimuste vastused

Teoreetiline informaatika

pdf

SML kordamisküsimustele vastused.

Kordamine eksamiks aines \"Sissejuhatus matemaatilisse loogikasse\"2011. sügisMõned tõestused jäetud väljakirjutamata, lisatud õpiku leheküljed, kus neid leida saab . Õpik on Moodle\'s ka väljas, kui endal pole :)PS, mul google drive'is suur University kaust, kus leiab kõike õppematerjale perioodil 2010-2013 informaatika erialal. Kellel soov ligi saada, kirjutage :)

Sissejuhatus matemaatilisse loogikasse