Informativní přehled o základech teoret. informatiky (výpočetní složitost, NP-úplnost) a algoritmech (lineární programování, grafové algoritmy). Prezentace teoret. partií kombinatoriky a teorie grafů (toky v sítích, faktory grafů, množinové systémy a systémy reprezentantů, Ramseyova teorie). Jako pokračování je v letním semestru doporučeno DMI012. Shodné s DMI011.
Poslední úprava: T_MUUK (31.01.2001)
Overview of basics of computational complexity and NP-completeness. Then
graph theory and combinatorics as in DMI011 and DMI012.
Literatura -
Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (17.04.2013)
Literatura dle doporučení učitele.
Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (17.04.2013)
Literature according to the recommendation of the teacher.
Sylabus
Poslední úprava: ()
Základy NP-úplnosti - nedeterministické Turingovy stroje, Cookova věta, základní NP-úplné problémy (3-splnitelnost, Hamiltonovská kružnice, nezávislá množina, exaktní pokrytí). Dále viz I173 a I174.