Kombinatorické algoritmy a složitost

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

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.

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St
Čt	místnost Z4:B2-326 Demlová M. 11:00–12:30 (přednášková par. 1) Zikova ulice Konzultační místnostmístnost Z4:B2-326 Demlová M. 12:45–13:30 (paralelka 1) Zikova ulice Konzultační místnost
Pá

Předmět je součástí následujících studijních plánů:

• Doktorské studium, prezenční forma (povinně volitelný předmět)
• Doktorské studium, kombinovaná forma (povinně volitelný předmět)
• Doktorské studium, strukturované prezenční (povinně volitelný předmět)
• Doktorské studium, strukturované kombinované (povinně volitelný předmět)