| Hlavná stránka |
| Domáce úlohy |
| Rasťo Královič |
Vitajte na stránke predmetu Teória algoritmov.
Predmet je zameraný na metódy riešenia "ťažkých" optimalizačných problémov.
Hlavným ťažiskom sú aproximatívne algoritmy: triedy PO, NPO, APX, PTAS, FPTAS,
techniky návrhu a analýzy aproximatívnych algoritmov, odhady aproximovateľnosti,
technika randomizácie.
Predmet predpokladá základné vedomosti z teórie formálnych jazykov a teórie
zložitosti.
Predmet je zakončený
skúškou, ktorá má písomnú (riešenie príkladov) a ústnu (teória) časť.
Literatúra:
(v prípade záujmu môžem požičať)
Lokálne prístupné materiály
Materiály na internete
(Rád privítam ďalšie zujímavé linky.)
D.R. Karger, P.N. Klein, R.E. Tarjan:
A Randomized Linear-Time Algorithm to Find Minimal Spanning Tree
(
iba pre účely tejto prednášky:
postscript+gzip - 634KB
)
Valerie King: A Simpler Minimal Spanning Tree Verification
Algorithm
(
postscript+gzip - 44KB
)
Sanjeev Arora: Polynomial Time Approximation Schemes for Euclidian
Traveling Salesman and other Geometric Problems
(
iba pre účely tejto prednášky:
postscript+gzip - 362KB
)
Sanjeev Arora: The Approximability of NP-hard Problems
(
iba pre účely tejto prednášky:
postscript+gzip - 218KB
)
(
http://148.247.2.21/~gmorales/logica/msatuap/msatuap.html, alebo
postscript+gz - 91KB)
(
postscript+gz - 297KB)
(
postscript+gz - 725KB)