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 2022
• 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í
• Způsob výuky: prezenční
• Garant: Torsten Mütze, Ph.D.; doc. Mgr. Petr Gregor, Ph.D.
• Kategorizace předmětu: Informatika > Teoretická informatika

Anotace

čeština

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

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.

angličtina

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

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.

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

čeština

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

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

1 ústní zkouška (50%)

angličtina

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

2 marked homework assignments (50%)

1 oral exam (50%)

Literatura

čeština

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

• 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

Sylabus

čeština

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

• 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