ČeskyEnglish

Popis předmětu - XP01KAS

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
XP01KAS Kombinatorické algoritmy a složitost Rozsah výuky:2+1
Garanti:Demlová M. Role:S Zakončení:ZK
Vyučující:Demlová M.
Zodpovědná katedra:13101 Kreditů:4 Semestr:L

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: XP01KAS

Osnovy přednášek:

Osnovy cvičení:

Literatura:

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.

Požadavky:

Poznámka:

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

Webová stránka:

http://math.feld.cvut.cz/demlova/teaching/kas.html

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
DOKK Před zařazením do oboru S
DOKP Před zařazením do oboru S


Stránka vytvořena 20.9.2017 17:47:17, semestry: L/2016-7, Z,L/2017-8, Z/2018-9, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.