456-0511/01 – Úvod do teoretické informatiky (UTI)

Garantující katedraKatedra informatikyKredity6
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í1999/2000Rok zrušení2009/2010
Určeno pro fakultyFEIUrčeno pro typy studiabakalářské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
CIP016 Ing. Nikola Ciprich
CIH053 PhDr. Martina Číhalová, Ph.D.
SNE10 Mgr. Pavla Dráždilová, Ph.D.
FRY057 Ing. Tomáš Frydrych
KOT06 Ing. Martin Kot, Ph.D.
KUC275 Ing. Štěpán Kuchař, Ph.D.
MEN059 Mgr. Marek Menšík, Ph.D.
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
TAK003 Ing. Ondřej Takács
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2
kombinovaná Zápočet a zkouška 10+0

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

Cílem je naučit posluchače zacházet se základními pojmy teoretické informatiky a používat je 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ě)
Projekt

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:

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

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

Průběžná kontrola studia: - Dvě písemky v průběhu semestru (každá za 10 bodů). - Písemně vypracovaný referát, který musí být poté odprezentován cvičícímu (15 bodů) (témata budou studentům přidělena na začátku semestru). Požadavky na zápočet: Pro udělení zápočtu musí student získat z obou písemek a referátu dohromady nejméně 20 bodů. Zkouška: - Zkouška bude písemná a případně může být doplněna o volitelnou ústní část, která slouží zejména k vyjasnění případných nejasností v písemné části. Zkouška se bude skládat ze tří částí věnovaných následujícím oblastem: - teorie formálních jazyků a automatů - vyčíslitelnost a složitost - úvod do logiky Celkem je možné získat za zkoušku až 65 bodů. Pro absolvování zkoušky je nutné získat z každé z jejích tří částí minimálně 5 bodů.

E-learning

Další požadavky na studenta

Prerekvizity

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

Korekvizity

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

Osnova předmětu

Náplň přednášek: - Základy výrokové a predikátové logiky. - Analýza vět přirozeného jazyka v jazyce výrokové a predikátové logiky. - Odvozování důsledků. Množinové / sémantické důkazy. - Základy rezoluční metody.Přednášky: - Formální jazyky - základní pojmy (abeceda, slovo, jazyk). Operace na jazycích. Konečné automaty. - Konstrukce konečných automatů. Nedeterministické konečné automaty. - Převod nedeterministických konečných automatů na deterministické. Regulární výrazy. - Bezkontextové gramatiky a jazyky. - Algoritmické problémy. Modely výpočtu (Turingovy stroje a stroje RAM). - Asymptotická notace. Složitost algoritmů. - Složitost problémů. Třídy složitosti. Převody mezi problémy. NP-úplné problémy. - Algoritmicky nerozhodnutelné problémy. Cvičení: - Zopakování základů teorie množin, relací a funkcí a teorie grafů. - Výroková a predikátová logika. - Analýza vět přirozeného jazyka v jazyce výrokové a predikátové logiky. - Odvozování důsledků. Množinové / sémantické důkazy. - Rezoluční metoda. - Operace s jazyky. - Konstrukce konečných automatů. - Převod nedeterministických automatů na deterministické. - Regulární výrazy. - Bezkontextové gramatiky. - Turingovy stroje a stroje RAM. - Asymptotická notace. Složitost algoritmů. - Složitost problémů. Třídy složitosti.

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

Prezenční forma (platnost od: 2003/2004 letní semestr, platnost do: 2009/2010 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (100) 51
        Zkouška Zkouška 65 (65) 15
                Matematická logika Písemná zkouška 22  5
                Jazyky a automaty Písemná zkouška 22  5
                Vyčíslitelnost a složitost Písemná zkouška 21  5
        Zápočet Zápočet 35 (35) 20
                1. zápočtová písemka Písemka 10  0
                2. zápočtová písemka Písemka 10  0
                Referát Projekt 15  0
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2009/2010 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2009/2010 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 2 povinný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2009/2010 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2009/2010 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 2 povinný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2009/2010 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2009/2010 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 2 povinný stu. plán
2009/2010 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 2 povinný stu. plán
2008/2009 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 2 povinný stu. plán
2008/2009 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 2 povinný stu. plán
2008/2009 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2008/2009 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2008/2009 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2008/2009 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 2 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 2 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2008/2009 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2007/2008 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 2 povinný stu. plán
2007/2008 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 2 povinný stu. plán
2007/2008 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2007/2008 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2007/2008 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2007/2008 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 2 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 2 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2007/2008 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2006/2007 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 2 povinný stu. plán
2006/2007 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 2 povinný stu. plán
2006/2007 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2006/2007 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2006/2007 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2006/2007 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika P čeština Ostrava 2 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (1103R031) Výpočetní matematika K čeština Ostrava 2 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika P čeština Ostrava 2 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2601R013) Telekomunikační technika K čeština Ostrava 2 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2006/2007 (B2647) Informační a komunikační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2005/2006 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2005/2006 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 2 povinný stu. plán
2005/2006 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2005/2006 (N2646) Informační technologie (1103T021) Počítačová matematika P čeština Ostrava 1 povinný stu. plán
2005/2006 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2005/2006 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 2 povinný stu. plán
2005/2006 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2005/2006 (N2646) Informační technologie (1103T021) Počítačová matematika K čeština Ostrava 1 povinný stu. plán
2005/2006 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2005/2006 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2004/2005 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2004/2005 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 2 povinný stu. plán
2004/2005 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2004/2005 (N2646) Informační technologie (1103T021) Počítačová matematika P čeština Ostrava 1 povinný stu. plán
2004/2005 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2004/2005 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 2 povinný stu. plán
2004/2005 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2004/2005 (N2646) Informační technologie (1103T021) Počítačová matematika K čeština Ostrava 1 povinný stu. plán
2004/2005 (B2646) Informační technologie (2612R059) Mobilní technologie P čeština Ostrava 2 povinný stu. plán
2004/2005 (B2646) Informační technologie (2612R059) Mobilní technologie K čeština Ostrava 2 povinný stu. plán
2003/2004 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2003/2004 (B2646) Informační technologie (1103R021) Počítačová matematika P čeština Ostrava 2 povinný stu. plán
2003/2004 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2003/2004 (N2646) Informační technologie (1103T021) Počítačová matematika P čeština Ostrava 1 povinný stu. plán
2003/2004 (B2646) Informační technologie (2612R025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2003/2004 (B2646) Informační technologie (1103R021) Počítačová matematika K čeština Ostrava 2 povinný stu. plán
2003/2004 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2003/2004 (N2646) Informační technologie (1103T021) Počítačová matematika K čeština Ostrava 1 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