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
Přednášející (garant):Demlová M. Typ předmětu:S Zakončení:ZK
Zodpovědná katedra:301 Kreditů:3 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ů.

Literatura Č:

Literatura A:

Plán Obor Role Dop. semestr
XDOKP Elektrotechnika a informatika S Není
XDOKK Elektrotechnika a informatika S Není

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


Stránka vytvořena 14. 2. 2002, semestry: Z/2001-2, Z/2002-3, L/2001-2, L/2002-3, 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)