Předmět Problémy na hyperkrychlích (NTIN097)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NTIN097 - Problémy na hyperkrychlích, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Seznámit se s problematikou hyperkrychlí.
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.
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.
Garant
Mgr. Petr Gregor, Ph.D.