Skip to main content

Algoritmy a zložitosť

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.

Lecturer


Instructor


Year


Bc. - II. LS

Extent


2P / 2CV

Credits


6

Recommended Literature


[1] Papadimitriou, Ch. - Steiglitz, K.: Combinatorial Optimization - Algorithms and Complexity.
[2] Plesník, J.: Grafové algoritmy, Veda VSAV Bratislava, 1983
[3] Učebný text (S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani)

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