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

 

Podmienky zápočtu:

Podmienky zápočtu

získanie minimálne 21 bodov zo 40 možných

  • písomný test <= 20 bodov (10. týždeň)
  • každý odovzdá 2 zadania:
  • 1. zadanie <= 10 bodov
  • 2. zadanie <= 10 bodov

Upozornenie:

Študent má v zmysle študijného poriadku nárok na opravu zápočtovej písomnej práce. Účasť na cvičeniach je povinná a je potrebné sa riadiť pokynmi, ktoré sú v dokumentoch: Informovanie o neúčasti na výuke, priebežnom a záverečnom hodnotení a Osobná zodpovednosť študentov za študijné výsledky.

 

Podmienky skúšky:

Podmienky skúšky

získanie minimálne 51 bodov zo 100 možných

  • semestrálna skúška - príklady + teória <= 60 bodov
  • semester <= 40 bodov