PředmětyPředměty(verze: 845)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Problémy na hyperkrychlích - NTIN097
Anglický název: Hypercube Problems
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2018 do 2018
Semestr: zimní
E-Kredity: 3
Rozsah, examinace: zimní s.:2/0 Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
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: Mgr. Petr Gregor, Ph.D.
Třída: Informatika Mgr. - Teoretická informatika
Kategorizace předmětu: Informatika > Teoretická informatika
Anotace -
Poslední úprava: RNDr. Jan Hric (26.04.2019)
Mnohé otázky v různých oblastech teoretické informatiky lze formulovat jako problémy v hyperkrychlích. Přednáška nabízí přehled vybraných problémů studovaných na hyperkrychlích s důrazem na aplikace v teoretické 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.
Cíl předmětu -
Poslední úprava: T_KTI (03.05.2012)

Seznámit se s problematikou hyperkrychlí.

Podmínky zakončení předmětu -
Poslední úprava: Mgr. Petr Gregor, Ph.D. (07.06.2019)

Předmět je zakončen složením zkoušky. Požadavky a formát zkoušky jsou uvedeny níže.

Literatura -
Poslední úprava: 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.

Požadavky ke zkoušce -
Poslední úprava: Mgr. Petr Gregor, Ph.D. (09.10.2017)

Zkouška se skládá z písemného řešení tří sad domácích úloh v průběhu semestru a zpracování rešeršního textu na vybrané téma, např. zápisu přednášky. Výsledná známka je určena ze 70% hodnocením řešení domácích úloh a z 30% hodnocením rešeršního textu.

Sylabus -
Poslední úprava: T_KTI (28.04.2015)
  • 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.

 
Univerzita Karlova | Informační systém UK