Sylabus
- 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
Anotace
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.