Combinatorial Algorithms - NDMI007

• Title: Kombinatorické algoritmy
• Guaranteed by: Department of Applied Mathematics (32-KAM)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2020
• Semester: summer
• E-Credits: 5
• Hours per week, examination: summer s.:2/2, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: not taught
• Language: Czech
• Teaching methods: full-time
• Guarantor: prof. RNDr. Luděk Kučera, DrSc.
• Class: Informatika Mgr. - Teoretická informatika; Informatika Mgr. - Matematická lingvistika
• Classification: Informatics > Discrete Mathematics
• Is incompatible with: NDMI033
• Is interchangeable with: NDMI033

Annotation

English

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

Last update: G_I (31.10.2001)

Czech

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

Last update: ()

Course completion requirements

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

Last update: Kučera Luděk, prof. RNDr., DrSc. (13.06.2019)

Literature

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

Last update: Zakouřil Pavel, RNDr., Ph.D. (05.08.2002)

Syllabus

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

Last update: ()