Teoretická informatika

Ročník, rozsah, kredity

Stupeň	Stupeň Bc.
Semester	Číslo semestra II. LS

Rozsah	Rozsah 3P / 3CV
Kredity	Počet kreditov 6

Obsah

Algoritmy a ich zložitosť:

Vypočítateľnosť a časové hranice algoritmov.
Turingove stroje. Veľkosť vstupu konkrétnej realizácie optimalizačnej úlohy.
Analýza algoritmov. Polynomiálne algoritmy.
Optimalizačný problém. Triedy NP. Triedy NP-úplné.
Polynomiálna redukcia. Cookova veta. Trieda co-NP.
Pseudopolynomiálne algoritmy.
NP-ťažké problémy.
Aproximatívne algoritmy. Heuristiky.

Algebraické štruktúry a výroková logika:

Niektoré vlastnosti množín, množina celých čísel, kongruencie.
Binárne relácie a zobrazenia. Čiastočne usporiadané množiny.
Zväzy. Boolovské algebry. Boolovské funkcie.
Výroková logika, formuly výrokovej logiky.
Ekvivalencia formúl. Relácia vyplývania. Realizácia formúl.

Teória grafov:

Grafy (definícia, typy grafov, súvislosť, maticové vyjadrenie).
Stromy a kostra grafu. Eulerovské, hamiltonovské grafy.
Planárne grafy. Farbenie grafov.
Digrafy (definícia, typy, silná súvislosť, maticové vyjadrenie).
Acyklické digrafy. Orientované stromy, kostra digrafu a binárne stromy
Niektoré aplikácie grafov. Grafové algoritmy.
Toky v sieťach.

Prednášajúci:

prof. RNDr. Ján Plavka, CSc.

Cvičiaci:

prof. RNDr. Ján Plavka, CSc.

Odporúčaná literatúra

[01[ Bučko M. – Klešč, M.: Diskrétna matematika, Elfa, Košice, 1999.
[02] Matoušek J. – Nešetřil J.: Kapitoly z diskrétní matematiky, Matfyzpress, Praha 1996.
[03] Kolář, J. – Štěpánková, O. – Chytil, M.: Logika algebry a grafy. SNTL, ALFA, Praha 1989.
[04] Kvasnička V. – Pospíchal J.: Algebra a diskrétna matematika, STU Press, Bratislava, 2008, ISBN: 9788022729345.
[05] Berežný Štefan – Draženská Emília – Kravecová Daniela: Zbierka úloh z Diskrétnej matematiky, KM FEI TUKE, Košice 2005, ISBN: 80-8073-364-3.
[06] Draženská E.: Diskrétna matematika - Zbierka riešených a neriešených príkladov, KMTI FEI TUKE, Košice 2014.
[07] Draženská E. – Myšková H.: Matematická logika, KMTI FEI TUKE, Košice 2014, ISBN: 978-80-553-1821-9.
[08] Kovář Petr: Teorie grafů, skriptá, Vysoká škola báňská - Technická univerzita Ostrava a Západočeská univerzita v Plzni, 2016.
[09] Kovář Petr: Úvod do teorie grafů, skriptá, Vysoká škola báňská - Technická univerzita Ostrava a Západočeská univerzita v Plzni, 2012.
[10] Papadimitriou, Ch. - Steiglitz, K.: Combinatorial Optimization - Algorithms and Complexity.
[11] Plesník, J.: Grafové algoritmy, Veda VSAV Bratislava, 1983
[12] Učebný text (S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani)
[13] Jiří Demel: GRAFY a jejich aplikace, Academia Praha 2002, ISBN: 80-200-0990-6

Učebnice a skriptá v elektronickej podobe sú k dispozícii v okne "Prílohy".

Doplňujúce materiály k cvičeniam určené na samoštúdium, vytvorené v rámci projektu IT4KT, sú na stránke: IT4KT - Grafové algoritmy a zložitosť.