SubjectsSubjects(version: 837)
Course, academic year 2018/2019
   Login via CAS
Foundations of Algorithms and Graph Theory - NMIN331
Title in English: Základy kombinatoriky a teorie grafů
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2014
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: taught
Language: Czech
Teaching methods: full-time
Guarantor: doc. RNDr. Pavel Valtr, Dr.
Class: M Bc. MMIB
M Bc. MMIB > Doporučené volitelné
M Bc. OM
M Bc. OM > Zaměření MSTR
M Bc. OM > Povinně volitelné
Classification: Informatics > Discrete Mathematics
Mathematics > Discrete Mathematics
Incompatibility : NDMA001
Interchangeability : NDMA001
Annotation -
Last update: G_M (16.05.2012)
Basics of graph theory and systems of sets. Recommended for specialization Mathematical Structures within General Mathematics and for bachelor's program in Information security.
Course completion requirements -
Last update: prof. RNDr. Jan Kratochvíl, CSc. (18.02.2018)

The credit for the exercise is given after obtaining at least 20 points for solving home problems, which is roughly a quarter of all points that can be obtained. The deadline for solutions is approximately until the end of the semester and it is possible to hand in the solutions repeatedly, only the best solutions are counted in for each problem. The nature of the conditions does not allow repeated attempts for obtaining the credit. Obtaining the credit is necessary before the exam.

Literature -
Last update: doc. Mgr. Milan Hladík, Ph.D. (17.04.2013)

Literature according to the recommendation of the teacher.

Requirements to the exam -
Last update: prof. RNDr. Jan Kratochvíl, CSc. (18.02.2018)

The exam is oral. The knowledge and skills examined correspond to the sylabus in extent presented during the lectures. Common understanding to all notions and their relationship, theorems including proofs and ability to apply the aquired skills to simple situations related to the topics of the class are subject of the examination. Credit from the recitations must be obtained prior to enroling to an exam.

Syllabus -
Last update: G_M (16.05.2012)

Overview of basics of computational complexity and NP-completeness. Inclusion-exclusion principle and its applications. Generating functions. Finite projective planes, latin squares. Hall theorem and its applications. Flows in digraphs. k-connectivity of graphs. Ramsey theory.

Charles University | Information system of Charles University |