Kordamisküsimused

ITT0010 Teoreetiline informaatika

2006/07 õ.-a.

1. Hulkade spetsifitseerimine, tehted hulkadega, hulgateooria paradoksid.
2. Relatsioonid. Ekvivalentsi- ja järjestusseosed.
3. Kujutused. Hulga võimsus.
4. Graafid. Puude esitused. Programmide esitamine puuna
5. Programmeerimiskeelte klassid.
6. Programmeerimiskeelte formaalne spetsifitseerimine. Transleerimisprotsessi osad.
7. Keel kui matemaatiline objekt.
8. Fraasistruktuuri grammatikad. Chomsky klassifikatsioon.
9. Regulaarsed avaldised ja hulgad.
10. Lõplikud automaadid. Mittedeterministlike automaatide teisendamine deterministlikeks.
11. Regulaarsete avaldiste, lineaarsete grammatikate ja lõplike automaatide samaväärsus.
12. Keele regulaarsuse tarvilikud tingimused.
13. KV-keelte süntaksi- ja tuletuspuud.
14. KV-grammatikate redutseerimine.
15. KV-grammatikate normaalkujud.
16. KV-keelte süntaksanalüüsi ülesanne. CKY-algoritm.
17. Earley algoritm.
18. Magasinmäluga automaadid.
19. Ühe olekuga magasinmäluga automaatide ja Greibachi mõttes normaliseeritud KV-grammatikate ekvivalentsus.
20. KV-keelte tarvilikkuse tingimus.
21. Atribuutgrammatika, programmi semantika leidmine.
22. Turingi masin ja registermasin. Lahenduvad ja genereeritavad hulgad.
23. Turingi masina kodeerimine. Algoritmiliselt mittelahenduvad ülesanded. Church-Turingi tees.
24. Lihtrekursiivsed funktsioonid, nende arvutatavus Turingi mõttes.
25. Minimeerimisoperaator. Osaliselt rekursiivsed funktsioonid.
26. Cantori funktsioonid. Arvutatava funktsiooni ühekohalised esindajad.
27. Arvutatavate funktsioonide klassi universaalne funktsioon.
28. Ühekohaliste funktsioonide arvutatavus. Gödeli numbrid.
29. Kleene’ s-n-m-teoreem ja püsipunktiprintsiip.
30. Rice’i teoreem.
31. Posti vastavuse probleemi mittelahenduvus. Mittelahenduvate ülesannete näited.
32. Algoritmide keerukuse hindamine. Ülesannete keerukusklassid. NP ja NP-täielikud ülesanded.