SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Graph Theory and Algorithms for Mathematicians 1 - NDMA001
Title in English: Teorie grafů a algoritmy pro matematiky 1
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2017
Semester: summer
E-Credits: 5
Hours per week, examination: summer s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: not taught
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: NDMI011, NMIN331
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: doc. 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 | http://www.cuni.cz/UKEN-329.html