FPF:UINSB01 Theoretical Computer Science - Course Information
UINSB01 Theoretical Computer Science
Faculty of Philosophy and Science in OpavaWinter 2018
- Extent and Intensity
- 0/0. 0 credit(s). Type of Completion: -.
- Guaranteed by
- Institute of Computer Science – Faculty of Philosophy and Science in Opava
- Course Enrolment Limitations
- The course is also offered to the students of the fields other than those the course is directly associated with.
- fields of study / plans the course is directly associated with
- Computer Science and Technology (programme FPF, B1801 Inf) (2)
- Computer science in combination with another discipline (programme FPF, B1803 InDO)
- Syllabus (in Czech)
- A1. Teorie formálních jazyků a automatů
1. Gramatika, typy gramatik - Chomského hierarchie.
2. Konečné automaty, ekvivalence deterministických a nedeterministických
konečných automatů.
3. Vztah mezi regulárními gramatikami a konečnými automaty.
4. Zásobníkové automaty. Akceptování prázdným zásobníkem a koncovými stavy.
5. Deterministické a nedeterministické zásobníkové automaty.
6. Vztah zásobníkových automatů a bezkontextových gramatik.
7. Bezkontextové gramatiky, normální tvary gramatik.
8. Turingovy stroje a jazyky typu 0.
A2. Teorie vyčíslitelnosti a složitosti
1. Turingův stroj: definice, přijímání jazyků a výpočet funkcí. Univerzální Turingův stroj.
2. Rekurzívní a rekurzívně spočetné jazyky. Souvislost s rozhodovacími problémy a jejich (ne)rozhodnutelností.
3. Metoda diagonalizace a metoda redukce pro dokazování nerozhodnutelnosti, příklady jejich užití.
4. Metoda redukce pro dokazování nerozhodnutelnosti, příklad jejího užití.
5. Riceho věta a její důsledky.
6. Časová a prostorová složitost výpočtu, třídy DTIME(f(n)), NTIME(f(n)), DSPACE(f(n)), NSPACE(f(n)) a jejich vzájemné vztahy.
7. Stroj RAM, porovnání složitosti výpočtů na RAM a Turingově stroji.
8. Základní složitostní třídy DLOG, NLOG, P, NP atd., definice a vzájemné vztahy.
9. Třída NP, NP-úplnost, polynomiální redukce. NP úplné problémy.
A3. Logika
1. Výroková logika, syntax a sémantika jazyka výrokové logiky.
2. Ekvivalence výrokových formulí. Normální formy výrokových formulí.
3. Splnitelnost a platnost formule ve výrokové logice, rozhodování pomocí sémantického stromu, Quienův algoritmus, reduction ad absurdum, tablová metoda, rezoluční metoda, dedukce ve výrokové logice.
4. Predikátová logika 1. řádu - jazyk predikátové logiky, term, formule, substituce, sémantika, splnitelná formule v interpretaci, pravdivá formule v interpretaci, splnitelná formule, tautologie, kontradikce.
5. Obecná rezoluční metoda v predikátové logice - obecna? rezoluc?ni? metoda, klauzulární (Skolemova) forma, Skolemova funkce, Skolemova konstanta, prenexní tvar formule, Herbrandova procedura, Robinsonův unifikační algoritmus, Herbrandovo universum, zobecněné rezoluční odvozovací pravidlo.
A4. Teorie grafů
1. Grafy a jednoduché grafy, vrchol, hrana, stupeň vrcholu. Podgrafy, faktor, indukovaný podgraf, incidenční matice a matice sousednosti grafu.
2. Sled, tah, cesta, cyklus, dosažitelnost, souvislost a vzdálenost v grafu, izomorfismus grafů
3. Strom, kostra, les, bipartitní grafy, úplné bipartitní grafy, algoritmus nalezení minimální kostry grafu.
4. Vrcholová a hranová souvislost grafů
5. Párování a pokrytí grafů, úplné párování, popište nalezení úplného párování pomocí algoritmu hledající nesaturované alternující cesty.
6. Hranové a vrcholové barvení grafů, dobré hranové a vrcholové barvení, chromatický index a chromatické číslo a jejich meze, skladovací problém.
7. Planární a neplanární grafy, Eulerův vzorec, věta o 4 barvách, průsečíkové číslo
8. Eulerovské a hamiltonovské grafy, problém obchodního cestujícího.
9. Orientované grafy, ohodnocené grafy, prohledávání grafu, značkování, prohledávání do šířky, do hloubky, konstrukce cest.
- A1. Teorie formálních jazyků a automatů
- Teaching methods
- Interactive lecture
Lecture with a video analysis - Assessment methods (in Czech)
- Závěrečná ústní zkouška
- Language of instruction
- Czech
- Further comments (probably available only in Czech)
- The course can also be completed outside the examination period.
- Enrolment Statistics (Winter 2018, recent)
- Permalink: https://is.slu.cz/course/fpf/winter2018/UINSB01