Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2022/2023

Vyčíslitelnost

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
NI-VYC Z,ZK 4 2P+2C česky
Přednášející:
Jan Starý (gar.)
Cvičící:
Jan Starý (gar.)
Předmět zajišťuje:
katedra aplikované matematiky
Anotace:

Klasická teorie rekursivních funkcí a efektivní vyčíslitelnosti.

Požadavky:

Elementární aritmetika, základní kurs matematické logiky.

Osnova přednášek:

1. Úvod a motivace. Elementárně rekursivní funkce.

2. Primitivně rekursivní funkce. Ackermannova funkce.

3. Obecně rekurzivní funkce. Universální funkce.

4. Částečně rekurzivní funkce.

5. Turingovy stroje.

6. Výpočetní síla Turingových strojů.

7. Universální stroj. Halting problem.

8. Ekvivalence Turingových strojů a rekursivních funkcí.

9. Aritmetika: kódování jazyka.

10. Rekursivní axiomatisovatelnost.

11. (Ne)úplnost a (ne)rozhodnutelnost.

12. Diagonální lemma, Gödelovy věty.

Osnova cvičení:

1. Elementárně rekursivní funkce.

2. Primitivně rekursivní funkce

3. Obecně rekurzivní funkce

4. Částečně rekurzivní funkce.

5. Turingovy stroje.

6. Programování Turingových strojů.

7. Programování Turingových strojů.

8. Programování Turingových strojů.

9. Gödelovo kódování a dekódování.

10. Rezhodnutelnost: příklady.

11. Nerozhodnutelnost: příklady.

12. Diagonalizace.

Cíle studia:

Získat přehled o základních formalizacích pojmu „algoritmu“ a elementárních otázkách vyčíslitelnosti.

Studijní materiály:

Church: An unsolvable problem of elementary number theory

Church: A note on the Entscheidungsproblem

Davis: Computability and unsolvability

Enderton: Elements of Recursion Theory

Kleene: Introduction to Metamathematics

Rogers: Theory of Recursive Functions and Effective Computability

Shoenfield: Mathematical Logic

Turing: On computable numbers

Černý: Výpočty I

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/MI-VYC/

Další informace:
https://courses.fit.cvut.cz/NI-VYC/
Rozvrh na zimní semestr 2022/2023:
Rozvrh není připraven
Rozvrh na letní semestr 2022/2023:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
místnost TH:A-1442
Starý J.
11:00–12:30
(přednášková par. 1)
Thákurova 7 (FSv-budova A)
místnost TH:A-1442
Starý J.
12:45–14:15
(přednášková par. 1
paralelka 101)

Thákurova 7 (FSv-budova A)
Út
St
Čt

Předmět je součástí následujících studijních plánů:
Platnost dat k 29. 1. 2023
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6163906.html