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í
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.
Třída: Informatika Mgr. - Teoretická informatika
Kategorizace předmětu: Informatika > Teoretická informatika
Výsledky anket   Termíny zkoušek   Rozvrh ZS   Nástěnka   
Anotace -
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)
Cíl předmětu -

Seznámit se s problematikou hyperkrychlí.

Poslední úprava: T_KTI (03.05.2012)
Podmínky zakončení předmětu -

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

Poslední úprava: Gregor Petr, doc. Mgr., Ph.D. (22.09.2020)
Literatura -
  • 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)
Požadavky ke zkoušce -

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)
Sylabus -
  • 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)