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

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
Garant předmětu:
Jan Starý
Přednášející:
Jan Starý
Cvičící:
Jan Starý
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 2024/2025:
Rozvrh není připraven
Rozvrh na letní semestr 2024/2025:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 10. 11. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet6163906.html