Many objects in various areas of theoretical computer science may be formulated as problems in hypercubes. The
lecture offers an overview of selected problems studied in hypercubes with emphasis on applications in
theoretical computer science. It assumes only elementary knowledge and it is suitable for students in the M.Sc.
programme.
Last update: RNDr. Jan Hric (26.04.2019)
Mnohé objekty v různých oblastech jako je teorie booleovských funkcí, extremální kombinatorika, teorie kódování,
paralelní výpočty, atd. je přirozené reprezentovat jako struktury v hyperkrychlích. Přednáš�ka nabízí přehled vybraných
struktur studovaných na hyperkrychlích s důrazem na aplikace v informatice. Nabízí i otevřené otázky pro případný
vlastní výzkum. Předpokládá pouze elementární znalosti a je vhodná pro studenty magisterského cyklu.
Aim of the course -
Last update: T_KTI (28.04.2015)
The course gives an introduction into the area of hypercube problems.
Last update: T_KTI (03.05.2012)
Seznámit se s problematikou hyperkrychlí.
Course completion requirements -
Last update: doc. Mgr. Petr Gregor, Ph.D. (22.09.2020)
The course is finished by an exam.
Last update: doc. Mgr. Petr Gregor, Ph.D. (22.09.2020)
Předmět je ukončen zkouškou.
Literature -
Last update: T_KTI (28.04.2015)
B. Bollobás, Combinatorics: set systems, hypergraphs, families of vectors, and combinatorial probability, Cambridge University Press, Cambridge, 1986.
R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition, CRC Press, 2011.
S. Jukna, Extremal Combinatorics with Applications in Computer Science, Springer, Berlin, 2001.
F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, 1992.
selected journal papers.
Last update: T_KTI (28.04.2015)
B. Bollobás, Combinatorics: set systems, hypergraphs, families of vectors, and combinatorial probability, Cambridge University Press, Cambridge, 1986.
R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition, CRC Press, 2011.
S. Jukna, Extremal Combinatorics with Applications in Computer Science, Springer, Berlin, 2001.
F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, 1992.
vybraná časopisecká literatura.
Requirements to the exam -
Last update: doc. Mgr. Petr Gregor, Ph.D. (29.09.2022)
The exam consists of solving three sets of exercises during the semester and an oral exam. Average exercise grade will cover 60% of the final mark, and the other 40% will be given for the oral exam.
Last update: doc. Mgr. Petr Gregor, Ph.D. (29.09.2022)
Zkouška se skládá z písemného řešení tří sad domácích úloh v průběhu semestru a ústní zkoušky. Výsledná známka je určena ze 60% hodnocením řešení domácích úloh a z 40% hodnocením ústní zkoušky.
Syllabus -
Last update: T_KTI (28.04.2015)
Hypercube characterizations, basic properties.
Orbit and stabilizer theorem, group of automorphisms.
Parcial cubes, median graphs, convex expansion.
Nonexpansive maps, correspondence to 2-SAT.
Matchings, Gray codes, Hamiltonian decomposition.
Independent spanning trees, robustness of communication.
