Předměty

Váš prohlížeč nepodporuje JavaScript nebo je jeho podpora vypnutá. Některé funkce nemusejí být dostupné.

Teorie grafů a algoritmy pro matematiky 1 - NDMA001

Anglický název:	Graph Theory and Algorithms for Mathematicians 1
Zajišťuje:	Katedra aplikované matematiky (32-KAM)
Fakulta:	Matematicko-fyzikální fakulta
Platnost:	od 2022
Semestr:	letní
E-Kredity:	5
Rozsah, examinace:	letní s.:2/2, Z+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:	zrušen
Jazyk výuky:	čeština
Způsob výuky:	prezenční
Způsob výuky:	prezenční

Garant:	prof. RNDr. Jan Kratochvíl, CSc.
Kategorizace předmětu:	Informatika > Diskrétní matematika Matematika > Diskrétní matematika
Záměnnost :	NDMI011, NMIN331
Je neslučitelnost pro:	NDMI031, NMIN331, NDMI011, NDMX011
Je záměnnost pro:	NMIN331

Výsledky anket Termíny zkoušek Rozvrh Nástěnka

Anotace -

Poslední úprava: ()

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.

Literatura -

Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (17.04.2013)

Literatura dle doporučení učitele.

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.