Graph Theory and Algorithms for Mathematicians 2 - NDMA002

• Title: Teorie grafů a algoritmy pro matematiky 2
• Guaranteed by: Department of Applied Mathematics (32-KAM)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2004
• Semester: summer
• E-Credits: 3
• Hours per week, examination: summer s.:2/0, Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: cancelled
• Language: Czech
• Teaching methods: full-time
• Teaching methods: full-time
• Guarantor: prof. RNDr. Jan Kratochvíl, CSc.
• Class: Předměty bloku A
• Incompatibility : NDMI012, NDMI032
• Interchangeability : NDMI012, NDMI032
• Is incompatible with: NDMI032

Annotation

Last update: ()

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.

Syllabus

Last update: ()

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.