On Saturday 19th October 2024 there will be a shutdown of some components of the information system. Especially the work with files in Thesis modules will be particularly unavailable. Please postpone your requests for a later time.
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: Hric Jan, RNDr. (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.
Last update: Hric Jan, RNDr. (26.04.2019)
Aim of the course -
The course gives an introduction into the area of hypercube problems.
Last update: T_KTI (28.04.2015)
Seznámit se s problematikou hyperkrychlí.
Last update: T_KTI (03.05.2012)
Course completion requirements -
The course is finished by an exam.
Last update: Gregor Petr, doc. Mgr., Ph.D. (22.09.2020)
Předmět je ukončen zkouškou.
Last update: Gregor Petr, doc. Mgr., Ph.D. (22.09.2020)
Literature -
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.
Last update: T_KTI (28.04.2015)
Requirements to the exam -
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: Gregor Petr, doc. Mgr., 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.
Last update: Gregor Petr, doc. Mgr., Ph.D. (29.09.2022)
Syllabus -
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.
