Discrete Mathematics - NDMI002
Title: Diskrétní matematika
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2022
Semester: winter
E-Credits: 5
Hours per week, examination: winter s.:2/2, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Additional information: http://mj.ucw.cz/vyuka/dm/
Guarantor: doc. RNDr. Jiří Fiala, Ph.D.
prof. RNDr. Martin Tancer, Ph.D.
Teacher(s): Mgr. Todor Antić
Sudatta Bhattacharya, M.Sc.
Bc. Barbora Dohnalová
Bc. Vojtěch Gaďurek
Bc. Klára Grinerová
Mgr. Tomáš Hons
Ida Kantor, M.Sc., Ph.D.
Bc. Petr Martinek
Lluís Sabater Rojas
prof. RNDr. Martin Tancer, Ph.D.
doc. Hans Raj Tiwary, M.Sc., Ph.D.
Bc. Josef Tkadlec, Ph.D.
Mgr. Mikuláš Zindulka
Class: Informatika Bc.
Classification: Informatics > Discrete Mathematics
Incompatibility : NDMA005
Is incompatible with: NDMA006, NDMI030
Is pre-requisite for: NDMI021
Is interchangeable with: NDMI030, NDMA005
Opinion survey results   Examination dates   WS schedule   Noticeboard   
Annotation -
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).
Last update: T_KAM (06.05.2001)
Course completion requirements -

For credit you need to get 100 points out of at least 150 possible continuously awarded for tests, homework and other activities.

The ongoing nature of the inspection does not imply a right to request corrective tests nor alternative homework assignments.

In justified cases (long-term illness, stay abroad, etc.) the lecturer may set individual conditions for credit granting.

Credit is a condition for taking the exam.

The exam can be written, oral or combined. The exam may be arranged in contact or distant form.

The exam format is decided by the educator(s).

Result of tests accomplished during the teaching period may be taken into account at the exam.

Last update: Fiala Jiří, doc. RNDr., Ph.D. (26.07.2022)
Literature -

J. Matoušek, J. Nešetřil: Invitation to Discrete Mathematics, Oxford University Press, 2008, 2nd edition.

Last update: Fiala Jiří, doc. RNDr., Ph.D. (05.08.2022)
Requirements to the exam -

The requirements for the exam correspond to the syllabus of the subject to the extent that it was covered in lectures, tutorials and self-study.

The ability to apply the acquired knowledge in problem solving is also required.

Credit is a condition for taking the exam.

Last update: Fiala Jiří, doc. RNDr., Ph.D. (26.07.2022)
Syllabus -

Notation, motivating problems, the concept of a proof, proof by induction.

Combinatorics:

  • Relation: mapping (function, permutation), equivalence.
  • Partial ordering: chains and antichains, large implies tall or wide.
  • Combinatorial counting: the number of subsets, of subsets of size k, of all mappings, of all injective mappings, of permutations.
  • The binomial theorem. Estimates the factorial function and binomial coefficients.
  • Inclusion-exclusion formula, applications (hatcheck lady).

Probability:

  • Probability space (at most countable, all subsets are events).
  • Independent events, conditional probability.
  • Random variable: distribution function, expectation, linearity, most common distributions.

Graph theory:

  • Elementary notions: complete graph, complete bipartite graph, path, cycle, vertex degree, subgraph, isomorphism.
  • Handshaking lemma.
  • Eulerian graphs: trail, walk, characterisation, including directed case, strong and weak connectivity.
  • Trees: various characterisations, existence of a leaf.
  • Planar graphs: Euler's formula, maximum number of edges.
  • Graph coloring: characterisation of bipartite graphs, d-degenerate graphs, 5-color theorem for planar graphs (Kempe's chains).

Optional topics:

  • Erdős-Szekeres lemma on monotone subsequences.
  • Probabilistic proofs (e.g. existence of a 3-paradoxical tournament).
  • Graph score.
  • Platonic solids.
  • Sperner's lemma, application on the HEX game.

Last update: Tancer Martin, prof. RNDr., Ph.D. (28.02.2023)