Poslední úprava: prof. RNDr. Jiří Podolský, CSc., DSc. (15.05.2017)
Přednáška představuje úvod do oblasti, kde se stýká statistická fyzika a informatika. Ukážeme, jak
algoritmická složitost souvisí s kritickým chováním v okolí fázového přechodu. Vysvětlíme metody, které se
používají ve statistické fyzice neuspořádaných systémů a nacházejí aplikaci při modelování složitých sítí
náhodnými grafy, při kombinatorické optimalizaci a návrhu algoritmů.
Určeno pro studenty magisterského a doktorského studia.
Poslední úprava: prof. RNDr. Jiří Podolský, CSc., DSc. (15.05.2017)
The lecture represents an introduction into an area where statistical physics and computer science meet. We show
how the algorithmic complexity relates to critical behavior close to phase transition. We explain the methods used
in statistical physics of complex systems and applied in modelling complex networks by random graphs, in
combinatorial optimization and algorithm design.
For master and PhD students.
Podmínky zakončení předmětu
Poslední úprava: doc. RNDr. Karel Houfek, Ph.D. (11.06.2019)
Ústní zkouška
Literatura -
Poslední úprava: prof. RNDr. Jiří Podolský, CSc., DSc. (15.05.2017)
M. Mézard, G. Parisi, and M.A. Virasoro, Spin Glass Theory and Beyond, World Scientific, 1986.
H. Nishimori, Statistical Physics of Spin Glasses and Information Processing, Oxford University Press, 2001.
S. N. Dorogovtsev and J. F. F. Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW, Oxford University Press, 2003.
Poslední úprava: prof. RNDr. Jiří Podolský, CSc., DSc. (15.05.2017)
M. Mézard, G. Parisi, and M.A. Virasoro, Spin Glass Theory and Beyond, World Scientific, 1986.
H. Nishimori, Statistical Physics of Spin Glasses and Information Processing, Oxford University Press, 2001.
S. N. Dorogovtsev and J. F. F. Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW, Oxford University Press, 2003.
Požadavky ke zkoušce
Poslední úprava: doc. RNDr. Karel Houfek, Ph.D. (11.06.2019)
Zkouška je ústní, požadavky odpovídají sylabu, v detailech pak tomu, co bylo během semestru odpřednášeno.
Sylabus -
Poslední úprava: prof. RNDr. Jiří Podolský, CSc., DSc. (15.05.2017)
Kritické jevy
Fenomenologie kritických jevů, singulární chování termodynamických veličin v okolí kritického bodu, kritické exponenty, univerzalita a pojem tříd univerzality
Algoritmická složitost
P, NP, NP-úplné úlohy, souvislost s pomalou dynamikou v okolí kritického bodu, celulární automaty, samoorganizované kritické jevy
Teorie sítí a náhodné grafy
Erdös-Rényiho model, bezškálové sítě
Kombinatorická optimalizace
simulované žíhání, metoda replik, spinová skla, neuronové sítě, problém obchodního cestujícího, K-SAT
Poslední úprava: prof. RNDr. Jiří Podolský, CSc., DSc. (15.05.2017)
Critical phenomena
Phenomenology of critical phenomena, singular behavior near critical point, critical exponents, universality, universality classes.
Algorithmic complexity
P, NP, NP-complete problems, relation to slow dynamics close to critical point, cellular automata, self-organized criticality
Network theory and random graphs
Erdös-Rényi model, scale-free networks