Kombinatorické algoritmy - NDMI007

• Anglický název: Combinatorial Algorithms
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: letní
• E-Kredity: 5
• Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: nevyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• 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
• Je neslučitelnost pro: NDMI033
• Je záměnnost pro: NDMI033

Anotace

čeština

Poslední úprava: ()

Algoritmy pro řešení kombinatorických problěmů - optimální, přibližné a heuristické metody a jejich implementace.

angličtina

Poslední úprava: G_I (31.10.2001)

Algorithms for solving of combinatorial problems - optimal, approximation, and heuristic methods and their implementation.

Podmínky zakončení předmětu

Poslední úprava: prof. RNDr. Luděk Kučera, DrSc. (13.06.2019)

Požadavek pro zápočet:

Implementace některého z probíraných algoritmů dle pokynů vyučujícího a především experimentální vyhodnocení očekávaného chování algoritmu, aplikovaného na náhodně, ale realisticky, vytvářených vstupních datech; sepsání zprávy o experimentech a její přednesení v rámci cvičení předmětu.

Požadavky pro zkoušku:

Ústní zkouška z probrané látky

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