PředmětyPředměty(verze: 901)
Předmět, akademický rok 2022/2023
  
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 2017
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: nevyučován
Jazyk výuky: čeština
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.

 
Univerzita Karlova | Informační systém UK