Graph Theory and Algorithms for Mathematicians 1 - NDMA001

• Title: Teorie grafů a algoritmy pro matematiky 1
• Guaranteed by: Department of Applied Mathematics (32-KAM)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2022
• Semester: summer
• E-Credits: 5
• Hours per week, examination: summer s.:2/2, C+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.
• Classification: Informatics > Discrete Mathematics; Mathematics > Discrete Mathematics
• Interchangeability : NDMI011, NMIN331
• Is incompatible with: NDMI031, NMIN331, NDMI011, NDMX011
• Is interchangeable with: NMIN331

Annotation

English

Last update: T_MUUK (31.01.2001)

Overview of basics of computational complexity and NP-completeness. Then graph theory and combinatorics as in DMI011 and DMI012.

Czech

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). Jako pokračování je v letním semestru doporučeno DMI012. Shodné s DMI011.

Literature

English

Last update: prof. Mgr. Milan Hladík, Ph.D. (17.04.2013)

Literature according to the recommendation of the teacher.

Czech

Last update: prof. Mgr. Milan Hladík, Ph.D. (17.04.2013)

Literatura dle doporučení učitele.

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.