PředmětyPředměty(verze: 806)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Kombinatorické algoritmy - NDMI007
Anglický název: Combinatorial Algorithms
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2008
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Garant: prof. RNDr. Luděk Kučera, DrSc.
Třída: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Matematická lingvistika
Kategorizace předmětu: Informatika > Diskrétní matematika
Anotace -
Poslední úprava: ()

Algoritmy pro řešení kombinatorických problěmů - optimální, přibližné a heuristické metody a jejich implementace.
Literatura
Poslední úprava: RNDr. Pavel Zakouřil, Ph.D. (05.08.2002)

L. Kučera, Kombinatorické algoritmy, SNTL 1983, 1991 (Praha)

Sylabus
Poslední úprava: ()

Datové struktury.

Základní programovací techniky pro návrh kombinatorických algoritmů.

Nejkratší a extremální cesty.

Minimalní kostra grafu.

Toky v sítích a párování v grafu.

Rovinné grafy.

Heuristické algoritmy pro kombinatorické problémy (isomorfismus, barvení, klika a nezavislá množina, Hamiltonovský cykl a obchodní cestující), jejich analýza.

Optimální algoritmy pro těžké kombinatorické algoritmy (branch and bound a pod.), jejich možnosti a omezení.

Paralelní implementace kombinatorických algoritmů.

 
Univerzita Karlova | Informační systém UK