Skip to main content

Teoretická informatika

Content


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

Lecturer


Instructor


Year


Bc. - II. LS

Extent


3P / 3CV

Credits


6

Recommended Literature


[1[ Bučko M. – Klešč, M.: Diskrétna matematika, Elfa, Košice, 1999.
[2] Matoušek J. – Nešetřil J.: Kapitoly z diskrétní matematiky, Matfyzpress, Praha 1996.
[3] Kolář, J. – Štěpánková, O. – Chytil, M.: Logika algebry a grafy. SNTL, ALFA, Praha 1989.
[4] Kvasnička V. – Pospíchal J.: Algebra a diskrétna matematika, STU Press, Bratislava, 2008, ISBN: 9788022729345.
[5] 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.
[6] Draženská E.: Diskrétna matematika - Zbierka riešených a neriešených príkladov, KMTI FEI TUKE, Košice 2014.
[7] Draženská E. – Myšková H.: Matematická logika, KMTI FEI TUKE, Košice 2014, ISBN: 978-80-553-1821-9.
[8] Kovář Petr: Teorie grafů, skriptá, Vysoká škola báňská - Technická univerzita Ostrava a Západočeská univerzita v Plzni, 2016.
[9] 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".

Examples and Templates


Conditions for obtaining prerequisites/examination

Credit test:

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

***
Úč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.

Exam:

získanie minimálne 51 bodov zo 100 možných
- semestrálna skúška - príklady + teória <= 60 bodov
- semester <= 40 bodov

Attachments


Drupal theme by Adaptivethemes - Design by Kodamera