Kombinatorické generování: grafy, struktury a algoritmy - NTIN112

• Anglický název: Combinatorial generation: graphs, structures, and algorithms
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2024
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní s.:2/0, 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: vyučován
• Jazyk výuky: angličtina
• Způsob výuky: prezenční
• Další informace: http://not taught in 2024/25
• Garant: Torsten Mütze, Ph.D.; doc. Mgr. Petr Gregor, Ph.D.
• Vyučující: Torsten Mütze, Ph.D.
• Kategorizace předmětu: Informatika > Teoretická informatika

Anotace

čeština

V informatice a matematice se často setkáváme s různými druhy kombinatorických objektů jako jsou řetězce, permutace, rozklady, binární stromy, triangulace, kostry, perfektní párování atd. Zajímavým problémem je vygenerovat všechny objekty z dané třídy, každý objekt právě jednou. V tomto kurzu se budeme věnovat algoritmům pro tento problém a představíme techniky pro jejich vývoj a analýzu. Dotkneme se také souvisejících otázek jako je kombinatorické počítání a náhodné vzorkování. Tato oblast čerpá z metod několika oblastí jako je teorie grafů, teorie uspořádání, geometrie a algebra.

Poslední úprava: Hric Jan, RNDr. (23.03.2022)

angličtina

In computer science and mathematics we frequently encounter different kinds of combinatorial objects, such as bitstrings, permutations, partitions, binary trees, triangulations, spanning trees, perfect matchings etc. A recurring problem of interest is to exhaustively generate all the objects from a class, each object exactly once. We discuss algorithms for that task, and we will introduce the techniques for developing and analyzing them. We touch upon related questions, such as combinatorial counting and random sampling, including methods from graph theory, order theory, geometry and algebra.

Poslední úprava: Hric Jan, RNDr. (23.03.2022)

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

čeština

2 oznámkované domácí úkoly (50%)

1 ústní zkouška (50%)

Poslední úprava: Gregor Petr, doc. Mgr., Ph.D. (30.03.2022)

angličtina

2 marked homework assignments (50%)

1 oral exam (50%)

Poslední úprava: Gregor Petr, doc. Mgr., Ph.D. (30.03.2022)

Literatura

čeština

• Donald E. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Addison-Wesley, preprint versions are available online: http://www.cs.utsa.edu/~wagner/knuth/

• Frank Ruskey, Combinatorial generation, available online: http://www.1stworks.com/ref/ruskeycombgen.pdf

• Albert Nijenhuis and Herbert S. Wilf, Combinatorial algorithms, Academic Press, available online: https://www.math.upenn.edu/~wilf/website/CombinatorialAlgorithms.pdf

• Xavier Viennot, The Art of Bijective Combinatorics, online video lectures: http://www.viennot.org/abjc-course.html

• Torsten Mütze, Combinatorial Gray codes-an updated survey, https://arxiv.org/abs/2202.01280

• The Combinatorial Object Server Website: http://combos.org

Poslední úprava: Gregor Petr, doc. Mgr., Ph.D. (30.03.2022)

Sylabus

čeština

• Flip graphs

• Binary strings (binary reflected Gray code)

• Binary strings (monotone and balanced Gray codes)

• Combinations (transpositions and shifts)

• Catalan objects (parenthesis expressions)

• Middle levels theorem

• Permutations (transpositions, shifts and reversal)

• Permutations (linear extensions)

• Permutations (pattern-avoiding permutations)

• Geometric objects (triangulations, non-crossing matchings)

• De Bruijn sequences

• Spanning trees and bases of matroids

Poslední úprava: Gregor Petr, doc. Mgr., Ph.D. (30.03.2022)