Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

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 [hours/week]
Capacity:	unlimited
Min. number of students:	unlimited
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. doc. RNDr. Martin Tancer, Ph.D.
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 Schedule Noticeboard

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).

Course completion requirements -

Last update: doc. Hans Raj Tiwary, M.Sc., Ph.D. (25.09.2020)

Hans Raj Tiwary:

For passing the tutorial it is necessary to obtain 50% from weekly homeworks.

Due to the nature of requirements, there will not be additional opportunities to pass the tutorial.

It is necessary to pass the tutorial to be able to take the exam for course credit. It is possible to take the final exam remotely.

Literature -

Last update: prof. 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. (25.09.2020)

Hans Raj Tiwary:

There will be a written exam at the end of the semester to test knowledge and understanding of the course material as well as problem solving. The exam will have three parts, one dedicated to each of the above. It is necessary to pass each part in order to pass the exam. There will be three opportunities to take the written exam whose dates will be announced in advance.

Detailed format of the exam can be found on the course webpage.

Syllabus -

Last update: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)

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. Estimates the factorial function and binomial

coefficients.

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.