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

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.

Teoreetilibe informaatika kordamisküsimused

Kordamisküsimuste vastused

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 :)

Matemaatiline analüüs II kontrolltöö

Matemaatilise analüüsi 2.teooriakontrolltöö punktide vastused

J. Kurvitsa teooria vastused

Esimeses kollokviumis on osad punktid puudu, kuid teine on korralikum.

Matemaatiline analüüs l.

Matemaatilise analüüsi l küsimused ja vastused (1-45). Õpetaja on Jaan Janno

Matemaatiline analüüs KT2 vastused

TTÜ Matemaatilise analüüsi teise kontrolltöö kordamisküsimused vastustega

Ettevalmistus kvantmehhaanika eksamiks