Teorie grafů a algoritmy pro matematiky 2 - NDMA002

• Anglický název: Graph Theory and Algorithms for Mathematicians 2
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2004
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, 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.
• Třída: Předměty bloku A
• Neslučitelnost : NDMI012, NDMI032
• Záměnnost : NDMI012, NDMI032
• Je neslučitelnost pro: NDMI032

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). Ve š.r.1996/97 spojeno s M398 a M400. Shodné s I173 a I174.

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.