SubjectsSubjects(version: 945)
Course, academic year 2023/2024
   Login via CAS
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
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 -
Last update: G_I (31.10.2001)
Algorithms for solving of combinatorial problems - optimal, approximation, and heuristic methods and their implementation.
Course completion requirements - Czech
Last update: 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

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

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

Syllabus - Czech
Last update: ()

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

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html