Hlavní stránka | Seznam oborů/specializací | Seznam všech skupin předmětů | Seznam všech předmětů | Seznam rolí                Návod

Předmět je základní jednotka výuky, jejímž prostřednictvím si student osvojí ucelenou část souboru znalostí a dovedností, potřebnou pro zvládnutí studijního oboru/specializace. Za věcný obsah předmětu zodpovídá garant předmětu. Časovou náročnost předmětu zhruba vyjadřuje atribut předmětu rozsah kontaktní výuky. Například rozsah = 2+2  značí, že předmět bude mít týdně dvě hodiny přednášek a dvě hodiny cvičení týdně. Na závěr semestru musí vyučující provést vyhodnocení, nakolik si ten který student osvojil poznatky a dovednosti, kterých měl během výuky nabýt. Jakým způsobem toto hodnocení vyučující provedou určuje atribut způsob zakončení. U předmětu lze definovat, že předmět je zakončen pouze zápočtem(Z), klasifikovaným zápočtem(KZ), pouze zkouškou(ZK), nebo zápočtem a zkouškou(Z,ZK). Náročnost úspěšného absolvování předmětu je vyjádřena ECTS kreditními body. Výuka předmětu probíhá během semestru. Opakovaně se předmět vyučuje vždy v zimním(Z), nebo v letním(L) semestru každého akademického roku. Výjimečně může předmět být nabízen studentům v obou semestrech(Z,L). Za organizační zajištění výuky zodpovídá přiřazená katedra, která zejména vytvoří časový rozvrh předmětu a zajistí pro předmět vyučující. Někteří přednáší a zkouší, jiní vedou cvičení a udělují zápočty.
Obsahová náplň a další organizační informace, týkající se předmětu je popsána pomocí různých popisných textů(anotace, týdenní osnova, literatura, apod.)
$DODATEK_POPIS
MI-VYC Vyčíslitelnost Rozsah kontaktní výuky: 2P+2C
Vyučující: Způsob zakončení: Z,ZK
Zodpovědná katedra: 18105 ECTS Kredity: 4 Semestr: L

Anotace:
Klasická teorie rekursivních funkcí a efektivní vyčíslitelnosti, s aplikacemi ve formální dokazatelnosti.

Osnovy 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.

Osnovy 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.

Literatura:
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

Požadavky:
Elementární aritmetika, základní kurs logiky.

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

Předmět je zahrnut do těchto studijních plánů:
Plán Obor Role Dop. semestr
MI-ZI.2016 Znalostní inženýrství V Není
MI-ZI.2018 Znalostní inženýrství V Není
MI-SP-TI.2016 Systémové programování V Není
MI-SP-SP.2016 Systémové programování V Není
MI-SPOL.2016 Nespecifikovaný/á obor/specializace studia - Unspecified Branch/Specialisation of Study V Není
MI-WSI-WI.2016 Webové a softwarové inženýrství V Není
MI-WSI-SI.2016 Webové a softwarové inženýrství V Není
MI-WSI-ISM.2016 Webové a softwarové inženýrství V Není
MI-NPVS.2016 Návrh a programování vestavných systémů V Není
MI-PSS.2016 Počítačové systémy a sítě V Není
MI-PB.2016 Počítačová bezpečnost V Není
NI-TI.2018 Teoretická informatika V 2
MI-WSI-ISM.2016 Webové a softwarové inženýrství V 4


Stránka vytvořena 29. 3. 2024, semestry: Z/2020-1, L/2023-4, Z/2022-3, Z,L/2021-2, Z/2023-4, L/2019-20, L/2022-3, Z/2019-20, L/2020-1, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: J. Novák, I. Halaška