Struktury v hyperkrychlích - NTIN097

• Anglický název: Hypercube structures
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2019
• 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: čeština, angličtina
• Způsob výuky: prezenční
• Další informace: http://ktiml.mff.cuni.cz/~gregor/hypercube/hypercube-course.htm
• Garant: doc. Mgr. Petr Gregor, Ph.D.
• Vyučující: doc. Mgr. Petr Gregor, Ph.D.
• Třída: Informatika Mgr. - Teoretická informatika
• Kategorizace předmětu: Informatika > Teoretická informatika

Anotace

čeština

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.

Poslední úprava: Hric Jan, RNDr. (26.04.2019)

angličtina

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.

Poslední úprava: Hric Jan, RNDr. (26.04.2019)

Cíl předmětu

čeština

Seznámit se s problematikou hyperkrychlí.

Poslední úprava: T_KTI (03.05.2012)

angličtina

The course gives an introduction into the area of hypercube problems.

Poslední úprava: T_KTI (28.04.2015)

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

čeština

Předmět je ukončen zkouškou.

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

angličtina

The course is finished by an exam.

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

Literatura

čeština

• 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.

Poslední úprava: T_KTI (28.04.2015)

angličtina

• 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.

Poslední úprava: T_KTI (28.04.2015)

Požadavky ke zkoušce

čeština

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.

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

angličtina

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.

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

Sylabus

čeština

• Charakterizace hyperkrychlí, základní vlastnosti.

• Věta o orbitě a stabilizátoru, grupa automorfismů.

• Parciální krychle, mediánové grafy, konvexní expanze.

• Neexpanzivní zobrazení, korespondence s 2-SAT.

• Párování, Grayovy kódy, Hamiltonovská dekompozice.

• Nezávislé kostry, stromy, komunikační robustnost.

• Stíny, protínající se systémy, isoperimetrické problémy.

• Problémy lineárních rozvržení, šířkové parametry.

• Vliv proměnných booleovských funkcí, harmonická analýza.

• Pakování a pokrývání, využití samoopravných kódů.

• Turánovské a související extremální problémy.

Poslední úprava: T_KTI (28.04.2015)

angličtina

• 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.

• Shadows, intersecting systems, isoperimetric problems.

• Linear layout problems, width parameters.

• Influence of variables of boolean functions, harmonic analysis.

• Packing and covering, applications of self-correcting codes.

• Turán numbers and other extremal problems.

Poslední úprava: T_KTI (28.04.2015)