Zmena kodovania diakritiky na:

• CP-1250
• ISO-LATIN-2
• Bez diakritiky

Teoria vypocitatelnosti

Pozor skuska !!!
Terminy skusok su vypisane v harkoch na Katedre informatiky
Skuska sa kona hromadne (v 2 terminoch)

• Sylaby na skusku

Kurz z vypocitatelnosti je ponukany v dvoch paralelnych prednaskach: jednu prednasa RNDr. Chladny (Teoria vypocitatelnosti), druhu Ing. Komara (Teoria vypocitatelnosti pre programatorov).

Spolocne ramcove sylaby pre obe verzie prednasok

Funkcie a ciastocne funkcie, projekcie, skladanie funkcii, trojice cislovacich (parovacich) funkcii. Univerzalne funkcie a ciastocne funkcie. Primitivne rekurzivne, rekurzivne funkcie a ciastocne rekurzivne (vypocitatelne) funkcie (na mnozine N). Primitivne rekurzivne, rekurzivne a rekurzivne spocitatelne mnoziny a predikaty a ich vlastnosti. Modely vypocitatelnosti (Turingove stroje a ine modely). Ekvivalentnost modelov vypocitatelnosti. Churchova teza. Problem zastavenia a ine nerozhodnutelne problemy. Kodovanie neciselnych oborov (oborov slov) do prirodzenych cisel.

!!! Tato stranka obsahuje informacie k prednaske, ktoru prednasa RNDr. Chladny.
(Teoria vypocitatelnosti) !!!

Prednasajuci: RNDr. M. Chladny (M-249)
E-mail: chladny@dcs.fmph.uniba.sk
Rozsah vyuky: 2/2 S
Cas a miesto konania prednasky: Stvrtok 8:10, akvarium IV
Cas a miesto konania cviceni: Stvrtok 11:30, akvarium IV

Ciele predmetu

Hlavnym cielom predmetu je formalizavat pojmy algoritmickej riesitelnosti problemov a vypocitatelnosti funkcii a uviest aplikacie takychto formalizmov v informatike, logike apod. Pojde pritom o standardny klasicky vyklad pojmov teorie vypocitatelnosti, ktory bude vedeny formou teoretickej prednasky doplnenej teoretickymi cviceniami.

Prednaska je logicky rozclenena do troch casti. Prva cast prednasky bude vykladat pojmy teorie vypocitatelnosti nezavisle od konkretneho vypoctoveho modelu, v druhej sa budeme zaoberat vypoctovymi modelmi, a to registrovymi a Turingovymi strojmi. Ide teda o modely teoreticke, pri ktorych sa casto pouziva abstrakcia potencialnej uskutocnitelnosti, t.j. tieto modely nebudeme programovat na skutocnych pocitacoch. Tretia cast prednasky sa bude zaoberat aplikaciami teorie vypocitatelnosti, najma problematikou (ciastocnej) (ne)rozhodnutelnosti problemov, ktore prirodzene vznikaju vramci informatiky, logiky, resp. vypoctov s realnymi cislami apod.

Podrobne sylaby predmetu

(rozclenenie na jednotlive body nezodpoveda rozcleneniu na jednotlive prednasky)

• Zakladne pojmy teorie: ciastocne a totalne funkcie. Skladanie funkcii. Klony (ciastocnych) funkcii. Trojice cislovacich funkcii.
• Operator primitivnej rekurzie, klon PRec. Konkretne primitivne rekurzivne funkcie. Operacie, na ktore je uzavrety. Kodovanie postupnosti do exponentov. Ine rekurzivne schemy, na ktore je PRec uzavrety.
• Univerzalne (ciastocne) funkcie. Diagonalizacia. Kodovanie primitivne rekurzivnych funkcii a funkcia pre ne univerzalna. Regularna minimalizacia. Rekurzivne funkcie. Neohranicena minimalizacia a ciastocne rekurzivne funkcie.
• Primitivne rekurzivne, rekurzivne mnoziny a predikaty. Rekurzivne spocitatelne mnoziny a ciastocne rekurzivne predikaty. Uzavretost tried mnozin a predikatov na operacie. Ohranicena a neohranicena kvantifikacia. Postova veta.
• Registrove stroje a vypocty na nich. Kodovanie registrovych strojov. Univerzalny registrovy stroj. Kleeneho veta o normalnej forme. Ekvivalencia vypocitatelnosti a vypocitatelnosti na registrovych strojoch.
• Rozsirenie pojmov z ciselnych mnozin na jazyky. Vypocty na Turingovych strojoch. Churchova teza.
• Indexacia. s-m-n veta. Veta o rekurzii. Charakterizacia rekurzivnych a ciastocne rekurzivnych funkcii pomocou +, ., non-eq, mi. Gamma-kodovanie postupnosti.
• Problem zastavenia a s nim pribuzne problemy. Redukcie. Nerozhodnutelne a ciastocne rozhodnutelne problemy. Riceova a Rice-Shapirova veta.
• Many-to-one redukcia, degrees of unsolvability, kreativne a proste mnoziny. Rekurzivna (ne)oddelitelnost. Ohranicenie casu vypoctu a poctu registrov stroja.
• Rekurzivne realne cisla a nerozhodnutelne problemy v tejto oblasti.
• Aritmeticka hierarchia predikatov (Sigma_i, Pi_i). Aritmeticka definovatelnost. Nedefinovatelnost pravdy. Nerozhodnutelnost a neuplnost aritmetiky. Goedelova veta o neuplnosti.

Ku prednaske je k dispozicii elektronicky ucebny text

Ivan Korec: Uvod do teorie algoritmov (pristupne len vramci MFF UK).

Pozor: Budu prednasane (a teda aj skusane) aj casti, ktore tento text nepokryva !!!

Zoznam odporucanej literatury

• I. Korec: Uvod do teorie algoritmov, elektronicky ucebny text.
• A. Malcev: Algoritmy i rekursivnyje funkcii, Moskva, 1965.
• H. Rogers: Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.
• D. E. Cohen: Computability and Logic, Ellis Horwood, Chichester, 1987.