Vyčíslitelnost

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 2023/2024:

Rozvrh není připraven

Rozvrh na letní semestr 2023/2024:

	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
Út	místnost T9:301 Starý J. 14:30–16:00 (přednášková par. 1) Dejvice NBFIT učebnamístnost T9:301 Starý J. 16:15–17:45 (přednášková par. 1 paralelka 101) Dejvice NBFIT učebna
St
Čt
Pá

Předmět je součástí následujících studijních plánů:

• Bc. program Informatika, pro fázi studia bez oboru, 2015-2020 (volitelný předmět)
• Bc. obor Bezpečnost a informační technologie, 2015-2020 (volitelný předmět)
• Bc. obor Teoretická informatika, 2015-2020 (volitelný předmět)
• Bc. obor Počítačové inženýrství, 2015-2020 (volitelný předmět)
• Bc. obor Informační systémy a management, 2015-2020 (volitelný předmět)
• Bc. obor Webové a softwarové inženýrství, zaměření Softwarové inženýrství, 2015-2020 (volitelný předmět)
• Bc. obor Webové a softwarové inženýrství, zaměření Webové inženýrství, 2015-2020 (volitelný předmět)
• Bc. obor Webové a softwarové inženýrství, zaměření Počítačová grafika, 2015-2020 (volitelný předmět)
• Bc. obor Znalostní inženýrství, 2018-2020 (volitelný předmět)
• Mgr. specializace Počítačová bezpečnost, 2020 (volitelný předmět)
• Mgr. specializace Návrh a programování vestavných systémů, 2020 (volitelný předmět)
• Mgr. specializace Počítačové systémy a sítě, 2020 (volitelný předmět)
• Mgr. specializace Manažerská informatika, 2020 (volitelný předmět)
• Mgr. specializace Softwarové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2020 (volitelný předmět)
• Mgr. specializace Webové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Znalostní inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2020 (volitelný předmět)
• Mgr. program, pro fázi studia bez specializace, ver. pro roky 2020 a vyšší (volitelný předmět)
• Bc. specializace Informační bezpečnost, 2021 (volitelný předmět)
• Bc. specializace Manažerská informatika, 2021 (volitelný předmět)
• Bc. specializace Počítačová grafika, 2021 (volitelný předmět)
• Bc. specializace Počítačové inženýrství, 2021 (volitelný předmět)
• Bc. program, pro fázi studia bez specializace, 2021 (volitelný předmět)
• Bc. specializace Webové inženýrství, 2021 (volitelný předmět)
• Bc. specializace Umělá inteligence, 2021 (volitelný předmět)
• Bc. specializace Teoretická informatika, 2021 (volitelný předmět)
• Bc. specializace Softwarové inženýrství, 2021 (volitelný předmět)
• Bc. specializace Počítačové systémy a virtualizace, 2021 (volitelný předmět)
• Bc. specializace Počítačové sítě a Internet, 2021 (volitelný předmět)
• Study plan for Ukrainian refugees (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2023 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2023 (volitelný předmět)