Tahad USA Amazonist või mõnes muust online poest osta, kuid nad ei saada Eestisse? Osta läbi Shipito! Tee tasuta konto Sulge
Facebook Like
Küsitlus
Add link


Rekursiooni ja keerukusteooria eksami konspekt (1)

5 VÄGA HEA
Punktid

Esitatud küsimused

  • Kuidas on sisend seotud väljundiga ?
  • Kui SÜT(a, p) = 1, siis kas ap-1 / p jääk on 1 ?
Vasakule Paremale
Rekursiooni ja keerukusteooria eksami konspekt #1 Rekursiooni ja keerukusteooria eksami konspekt #2 Rekursiooni ja keerukusteooria eksami konspekt #3 Rekursiooni ja keerukusteooria eksami konspekt #4 Rekursiooni ja keerukusteooria eksami konspekt #5 Rekursiooni ja keerukusteooria eksami konspekt #6 Rekursiooni ja keerukusteooria eksami konspekt #7 Rekursiooni ja keerukusteooria eksami konspekt #8 Rekursiooni ja keerukusteooria eksami konspekt #9 Rekursiooni ja keerukusteooria eksami konspekt #10 Rekursiooni ja keerukusteooria eksami konspekt #11 Rekursiooni ja keerukusteooria eksami konspekt #12
Punktid 100 punkti Autor soovib selle materjali allalaadimise eest saada 100 punkti.
Leheküljed ~ 12 lehte Lehekülgede arv dokumendis
Aeg2016-01-23 Kuupäev, millal dokument üles laeti
Allalaadimisi 71 laadimist Kokku alla laetud
Kommentaarid 1 arvamus Teiste kasutajate poolt lisatud kommentaarid
Autor Kastepiisad Õppematerjali autor

Lisainfo

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.

Märksõnad

Mõisted


Kommentaarid (1)

RainerMMM profiilipilt
RainerMMM: Väärt kraam :)
11:19 16-01-2019


Sarnased materjalid

37
doc
Teoreetilibe informaatika kordamisküsimused
2
pdf
Rekursiooni- ja keerukusteooria harjutus 3
816
pdf
Matemaatika - Õhtuõpik
575
docx
Nimetu
555
doc
Programmeerimiskeel
20
pdf
Diskreetne matemaatika I IAY0010 eksami konspekt
80
pdf
Algoritmid ja andmestruktuurid eksamiks kordamine
42
pdf
Diskreetse matemaatika mõisted selgitustega





Registreeri ja saadame uutele kasutajatele
faili e-mailile TASUTA

Konto olemas? Logi sisse

Faili allalaadimiseks, pead sisse logima
või
Kasutajanimi / Email
Parool

Unustasid parooli? | Tee tasuta konto

Sellel veebilehel kasutatakse küpsiseid. Kasutamist jätkates nõustute küpsiste ja veebilehe üldtingimustega Nõustun