Combinatorial generation: graphs, structures, and algorithms - NTIN112

• Title: Kombinatorické generování: grafy, struktury a algoritmy
• Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2024
• Semester: winter
• E-Credits: 3
• Hours per week, examination: winter s.:2/0, Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: English
• Teaching methods: full-time
• Additional information: http://not taught in 2024/25
• Guarantor: Torsten Mütze, Ph.D.; doc. Mgr. Petr Gregor, Ph.D.
• Teacher(s): Torsten Mütze, Ph.D.
• Classification: Informatics > Theoretical Computer Science

Annotation

English

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.

Last update: Hric Jan, RNDr. (23.03.2022)

Czech

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.

Last update: Hric Jan, RNDr. (23.03.2022)

Course completion requirements

English

2 marked homework assignments (50%)

1 oral exam (50%)

Last update: Gregor Petr, doc. Mgr., Ph.D. (30.03.2022)

Czech

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

1 ústní zkouška (50%)

Last update: Gregor Petr, doc. Mgr., Ph.D. (30.03.2022)

Literature

English

• 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

Last update: Gregor Petr, doc. Mgr., Ph.D. (30.03.2022)

Syllabus

English

• 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

Last update: Gregor Petr, doc. Mgr., Ph.D. (30.03.2022)