Vyčíslitelnost
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ů:
-
- 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)
- Bc. specializace Informační bezpečnost, 2024 (volitelný předmět)
- Bc. program, pro fázi studia bez specializace, 2024 (volitelný předmět)
- Bc. specializace Manažerská informatika, 2024 (volitelný předmět)
- Bc. specializace Počítačová grafika, 2024 (volitelný předmět)
- Bc. specializace Softwarové inženýrství, 2024 (volitelný předmět)
- Bc. specializace Webové inženýrství, 2024 (volitelný předmět)
- Bc. specializace Počítačové sítě a Internet, 2024 (volitelný předmět)
- Bc. specializace Počítačové inženýrství, 2024 (volitelný předmět)
- Bc. specializace Počítačové systémy a virtualizace, 2024 (volitelný předmět)
- Bc. specializace Umělá inteligence, 2024 (volitelný předmět)
- Bc. specializace Teoretická informatika, 2024 (volitelný předmět)