Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

Kombinatorické algoritmy a složitost

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
XP01KAS ZK 4 2+1 česky
Přednášející:
Marie Demlová (gar.)
Cvičící:
Marie Demlová (gar.)
Předmět zajišťuje:
katedra matematiky
Anotace:

Algoritmy a měření jejich složitosti, třídy P a NP. Lineární algoritmus pro zjištění planarity grafu. FFT - rychlá Fourierova transformace. Lineární

programování a simplexová metoda. NP-úplné úlohy a jejich převody. Metoda větví a mezí a jejich využití pro řešení NP-úloh. Aproximační algoritmy.

Problém obchodního cestujícího. Testování prvočíselnosti, Millerův algoritmus. Poznámka: Jednotlivé konkrétní algoritmy mohou být změněny a to na základě zájmu přihlášených doktorandů.

Výsledek studentské ankety předmětu je zde: http://www.fel.cvut.cz/anketa/aktualni/courses/XP01KAS

Požadavky:
Osnova přednášek:
Osnova cvičení:
Cíle studia:
Studijní materiály:

1. G. Ausiello, P. Croscenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi: Complexity and Approximztion Combinatorial Optimization Problems and Their Approximability Properties. Springer, 1999.

2. Jozef Gruska: Foundations of Computing. International Thomson Computer Press, 1997.

Poznámka:

Předmět je nabízen jednou za dva roky.

Další informace:
http://math.feld.cvut.cz/demlova/teaching/kas.html
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 12. 12. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet11505704.html