460-2005/03 – Úvod do teoretické informatiky (UTI)

Garantující katedraKatedra informatikyKredity5
Garant předmětudoc. Ing. Zdeněk Sawa, Ph.D.Garant verze předmětudoc. Ing. Zdeněk Sawa, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostpovinný
Ročník2Semestrletní
Jazyk výukyčeština
Rok zavedení2019/2020Rok zrušení
Určeno pro fakultyFEIUrčeno pro typy studiabakalářské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
SNE10 Mgr. Pavla Dráždilová, Ph.D.
KOT06 Ing. Martin Kot, Ph.D.
MEN059 Mgr. Marek Menšík, Ph.D.
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+3
kombinovaná Zápočet a zkouška 0+21

Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi

Posluchač umí zacházet se základními pojmy teoretické informatiky a umí je používat v běžné programátorské praxi. Zároveň jsou předmětem podány teoretické základy nutné pro další studium informatiky na vyšším stupni.

Vyučovací metody

Přednášky
Cvičení (v učebně)

Anotace

Předmět je přehledovým úvodem do základních oblastí teoretické informatiky. Studenty seznámí se základy logiky, formálních jazyků, automatů, algoritmické složitosti, včetně některých jejich aplikací pro řešení praktických programátorských úkolů. Konkrétně se studenti seznámí se se základy výrokové a predikátové logiky. Naučí se formalizovat tvzení v jazyce těchto logik a naučí se používat několik metod logického vyvozování. Dozví se o použití konečných automatů, regulárních výrazů a bezkontextových gramatik při tvorbě překladačů (lexikální a syntaktická analýza) a při vyhledávání v textu. Studenti se seznámí se základy teorie vyčíslitelnosti a složitosti. Naučí se posuzovat výpočetní složitost algoritmu a používat asymptotickou notaci. Stručně se také seznámí se složitostí problémů a se třídami složitosti. Dozví se také, že některé problémy jsou algoritmicky nerozhodnutelné, a jakým způsobem se to dá dokázat.

Povinná literatura:

- doc. Ing. Zdeněk Sawa, Ph.D.: Úvod do teoretické informatiky - slidy (k dispozici na adrese http://www.cs.vsb.cz/sawa/uti/slides/uti-cz.pdf, anglická verze na adrese http://www.cs.vsb.cz/sawa/uti/slides/uti-en.pdf) - doc. Ing. Zdeněk Sawa, Ph.D.: Úvod do teoretické informatiky - logika a algoritmy, (k dispozici na adrese http://www.cs.vsb.cz/sawa/uti/materialy/uti-2014.02.09.pdf) - prof. RNDr. Petr Jančar, CSc.: Úvod do teoretické informatiky - učební text, 2007, (k dispozici na adrese http://www.cs.vsb.cz/sawa/uti/materialy/uti.pdf). - doc. RNDr. Marie Duží, CSc.: Matematická logika, (k dispozici na adrese http://www.cs.vsb.cz/sawa/uti/materialy/Matlogika.pdf).

Doporučená literatura:

- Sipser, M.: Introduction to the Theory of Computation, PWS Publishing Company, 1997. - Kozen, D.: Automata and Computability. Undergraduate Text in Computer Science, Springer Verlag, 1997. - Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993. - Hopcroft, J.E., Motwani, R., Ullman, J, D.: Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison Wesley, 2006. - Gruska, J.: Foundation of Computing. International Thomson Computer Press, 1997. - Huth, M., Ryan, M.: Logic in Computer Science: Modelling and Reasoning about Systems, Cambridge University Press, 2004. - Švejdar, V.: Logika - neúplnost, složitost a nutnost, Academia, 2002. - Suppes, P.: Introduction to Logic, Dover Publications, 1999. - Tarski, A.: Introduction to Logic and to the Methodology of Deductive Sciences, Dover Publications, 1995. - Devlin, K.: Introduction to Mathematical Thinking, Keith Devlin, 2012.

Forma způsobu ověření studijních výsledků a další požadavky na studenta

V průběhu semestru budou studenti psát jednu větší zápočtovou písemku a také několik kratších testů. Předmět je zakončen zkouškou, která má písemnou podobu.

E-learning

Další požadavky na studenta

Na studenta nejsou kladeny žádné další požadavky.

Prerekvizity

Předmět nemá žádné prerekvizity.

Korekvizity

Předmět nemá žádné korekvizity.

Osnova předmětu

Náplň přednášek: 1. Úvod. Čím se zabývá teoretická informatika (algoritmy, algoritmické problémy, formální jazyky, ...). 2. Formální jazyky - základní pojmy (abeceda, slovo, jazyk). Operace na jazycích. Regulární výrazy. 3. Deterministické konečné automaty (DKA). Konstrukce konečných automatů. Některé jazykové operace na DKA. 4. Nedeterministické konečné automaty (NKA). Převod NKA na DKA. Jazykové operace na NKA. Vztah mezi regulárními výrazy a konečnými automaty. 5. Bezkontextové gramatiky a jazyky. 6. Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám. Chomského hierarchie. 7. Algoritmické problémy. Modely výpočtu (Turingovy stroje a stroje RAM). Churchova-Turingova teze. 8. Korektnost algoritmů. Dokazování korektnosti algoritmů. 9. Výpočetní složitost algoritmů. Asymptotická notace. Analýza výpočetní složitosti konkrétních algoritmů (iterativních i rekurzivních). 10. Různé obecné techniky návrhu algoritmů - řešení hrubou silou, rozděl a panuj, prohledávání s návratem, greedy algoritmy, dynamické programování. 11. Složitost problémů. Třídy složitosti (především třídy P a NP). Převody mezi problémy. NP-úplné problémy. 12. Konkrétní příklady NP-úplných problémů a převodů mezi problémy. 13. Algoritmicky nerozhodnutelné problémy (např. halting problem). Náplň cvičení: (Pozn.: Témata cvičení odpovídají tématům přednášek.) 1. Zopakování základů logiky, teorie množin, relací, funkcí a teorie grafů. 2. Operace na jazycích. Regulární výrazy. 3. Konstrukce deterministických konečných automatů (DKA). Operace na těchto automatech. 4. Konstrukce nedeterministických konečných automatů (NKA). Převod NKA na DKA. Převody mezi regulárními výrazy a konečnými automaty. 5. Konstrukce bezkontextových gramatik. Různé operace na těchto gramatikách. 6. Zásobníkové automaty. 7. Algoritmické problémy. Turingovy stroje a stroje RAM. 8. Dokazování korektnosti algoritmů. 9. Asymptotická notace. Analýza výpočetní složitosti algoritmů. 10. Techniky návrhů algoritmů. 11. Složitost problémů. Třídy složitosti. Převody mezi problémy. 12. Dokazování NP-úplnosti problémů. 13. Dokazování algoritmické nerozhodnutelnosti problémů.

Podmínky absolvování předmětu

Kombinovaná forma (platnost od: 2019/2020 zimní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodůMax. počet pokusů
Zápočet a zkouška Zápočet a zkouška 100 (100) 51
        Zápočet Zápočet 30 (30) 15
                Zápočtová písemka Písemka 24  12
                Aktivita na tutoriálech Jiný typ úlohy 6  3
        Zkouška Zkouška 70 (70) 30 3
                Jazyky a automaty Písemná zkouška 35  12
                Vyčíslitelnost a složitost Písemná zkouška 35  12
Rozsah povinné účasti: Účast na cvičeních je povinná a je kontrolována. S rozsahem povinné účastí seznámí studenty garant předmětu na začátku semestru.

Zobrazit historii

Podmínky absolvování předmětu a účast na cvičeních v rámci ISP: Splnění všech povinných úkolů v individuálně dohodnutých termínech.

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2023/2024 (B0613A140014) Informatika TZI K čeština Ostrava 2 povinný stu. plán
2023/2024 (B0613A140014) Informatika TZI P čeština Ostrava 2 povinný stu. plán
2023/2024 (B0541A170008) Výpočetní a aplikovaná matematika P čeština Ostrava 2 povinný stu. plán
2023/2024 (B0541A170008) Výpočetní a aplikovaná matematika K čeština Ostrava 2 povinný stu. plán
2022/2023 (B0613A140014) Informatika TZI K čeština Ostrava 2 povinný stu. plán
2022/2023 (B0613A140014) Informatika TZI P čeština Ostrava 2 povinný stu. plán
2022/2023 (B0541A170008) Výpočetní a aplikovaná matematika K čeština Ostrava 2 povinný stu. plán
2022/2023 (B0541A170008) Výpočetní a aplikovaná matematika P čeština Ostrava 2 povinný stu. plán
2021/2022 (B0613A140014) Informatika TZI P čeština Ostrava 2 povinný stu. plán
2021/2022 (B0613A140014) Informatika TZI K čeština Ostrava 2 povinný stu. plán
2021/2022 (B0541A170008) Výpočetní a aplikovaná matematika P čeština Ostrava 2 povinný stu. plán
2021/2022 (B0541A170008) Výpočetní a aplikovaná matematika K čeština Ostrava 2 povinný stu. plán
2021/2022 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2021/2022 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2021/2022 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2021/2022 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2020/2021 (B0613A140014) Informatika TZI K čeština Ostrava 2 povinný stu. plán
2020/2021 (B0613A140014) Informatika TZI P čeština Ostrava 2 povinný stu. plán
2020/2021 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2020/2021 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2020/2021 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2020/2021 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2020/2021 (B0541A170008) Výpočetní a aplikovaná matematika P čeština Ostrava 2 povinný stu. plán
2020/2021 (B0541A170008) Výpočetní a aplikovaná matematika K čeština Ostrava 2 povinný stu. plán
2019/2020 (B0541A170008) Výpočetní a aplikovaná matematika P čeština Ostrava 2 povinný stu. plán
2019/2020 (B0541A170008) Výpočetní a aplikovaná matematika K čeština Ostrava 2 povinný stu. plán
2019/2020 (B0613A140014) Informatika TZI P čeština Ostrava 2 povinný stu. plán
2019/2020 (B0613A140014) Informatika TZI K čeština Ostrava 2 povinný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku

Hodnocení Výuky



2021/2022 letní
2020/2021 letní