SubjectsSubjects(version: 807)
Course, academic year 2017/2018
   Login via CAS
Discrete Mathematics - NDMI002
Czech title: Diskrétní matematika
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2017
Semester: winter
E-Credits: 5
Hours per week, examination: winter s.:2/2 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: RNDr. Martin Tancer, Ph.D.
Mgr. Jan Kynčl, Ph.D.
doc. Hans Raj Tiwary, M.Sc., Ph.D.
Class: Informatika Bc.
Classification: Informatics > Discrete Mathematics
Incompatibility : NDMA005
Annotation -
Last update: T_KAM (06.05.2001)

Introduction to combinatorics and graph theory. We lay stress on active knowledge of basic definitions and methods (relation, mapping, graph, exact formulation of mathematical theorems, problem solving and proofs of simple statements).
Terms of passing the course -
Last update: doc. Hans Raj Tiwary, M.Sc., Ph.D. (12.10.2017)

Hans Raj Tiwary:

There will be two small tests for the credit for the tutorial.

It is required to obtain 50% of the points to pass the tutorial.

The material for the tests will be the one covered during the lectures.

Obtaining the credit is necessary before the final exam.

There is provision for repeated attempts for the credit.

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

J. Matousek, J. Nesetril: Invitation to Discrete Mathematics, Oxford University Press, 2008, 2nd edition.

Requirements to the exam -
Last update: doc. Hans Raj Tiwary, M.Sc., Ph.D. (12.10.2017)

Hans Raj Tiwary:

There will be one written exam for the main course, with oral part where the students explain

their solutions at the end of the exam. The material for the exam will be the same as taught in the lecture.

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

  • Basic notation, motivating examples, the concept of a proof, proof by induction.
  • Mappings, relations, equivalences. Permutations.
  • Basic combinatorial counting (the number of subsets, of subsets of size k, of all mappings, of all injective mappings, of permutations). The binomial theorem.
  • Inclusion-exclusion formula, applications (hatcheck lady).
  • Probability space (at most countable, all subsets are events). Independent events, conditional probability. Random variable, distribution function. Expectation, examples of calculation.
  • Basic notions of graph theory, path/circuit/walk, isomorphism, etc.
  • Characterisation of Eulerian graphs (including directed case; strong and weak connectedness).
  • Trees (various characterisations, existence of a leaf).
  • Planar graphs, Euler's formula, maximum number of edges.
  • The chromatic number of a graph, characterisation of bipartite graphs, chromatic number of a d-degenerate graph is at most d+1; 5-colorability of planar graphs (using Kempe's chains).
  • Partial orderings, chains and antichains, large implies tall or wide, Erdös-Szekeres lemma on monotone subsequences.

Additional topics: the HEX game, score theorem.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html