SubjectsSubjects(version: 944)
Course, academic year 2023/2024
   Login via CAS
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 -
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.
Literature -
Last update: prof. Mgr. Milan Hladík, Ph.D. (17.04.2013)

Literature according to the recommendation of the teacher.

Syllabus - Czech
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.

Charles University | Information system of Charles University |