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
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
Opinion survey results   Examination dates   Schedule   Noticeboard   
Annotation -
Overview of basics of computational complexity and NP-completeness. Then graph theory and combinatorics as in DMI011 and DMI012.
Last update: T_MUUK (31.01.2001)
Literature -

Literature according to the recommendation of the teacher.

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

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.

Last update: ()