Skip to main content
Skip header

ECTS Course Overview



Discrete Mathematics

* Exchange students do not have to consider this information when selecting suitable courses for an exchange stay.

Course Unit Code470-2301/04
Number of ECTS Credits Allocated5 ECTS credits
Type of Course Unit *Optional
Level of Course Unit *First Cycle
Year of Study *
Semester when the Course Unit is deliveredWinter Semester
Mode of DeliveryFace-to-face
Language of InstructionCzech, English
Prerequisites and Co-Requisites Course succeeds to compulsory courses of previous semester
Name of Lecturer(s)Personal IDName
KOV74Mgr. Tereza Kovářová, Ph.D.
KOV16doc. Mgr. Petr Kovář, Ph.D.
Summary
In this course the students learn the basic terms and concepts and basic constructions used in Discrete mathematics, especially in Combinatorics and Graph theory.
The word "discrete" refers to the opposite of "continuous". In this course we deal almost exclusively with finite sets and finite objects.
Learning Outcomes of the Course Unit
The goals of this subject are to introduce basic terms and methods of discrete mathematics and graph theory and to teach students to use them to formulate real life problems using mathematical terminology and to solve these related practical problems.

The students should learn to
- comprehend and generalize given definitions,
- distinguish which theoretical approach is suitable for a particular practical problem,
- classify given objects based on given properties and summarize the results,
- summarize each chapter.

In class students should practice to
- state a real life problem in the terms of Discrete mathematics or Graph theory
- apply theoretical approaches in solving real life problem, choose proper methods,
- choose and compare various methods of solution and pick the most suitable,
- verify the validity of each partical method,
- reuse the same theoretical approach in similar problems.
Course Contents
Lectures and discussions:

Part I - Introduction to discrete mathematics.

The scope and goals of Discrete mathematics. Counting selections and arrangements, related problems. Pidgeon-hole principle.
Geometric and arithmetic progressions. Inclusion-exclusion principle, binomial theorem and its applications.
Discrete probability: tossing coins, random choice, shuffling cards. Probability space and random event.
Integers and mathematical induction, the concept of proofs. Proving the formulas for numbers of subsets, k-combinations, k-permutations.
Recurrence relations, their applications and examples.
Modular arithmetics.
Algorithmic aspects: practical implementation of sets and relations. Obtaining a full list of all possible subsets k-combinations, and k-permutations.

Part II - Introduction to graph theory

Graphs and relations. Subgraphs, isomorphism, degrees, implementation. Directed graphs.
Graph connectivity, algorithms for searching. Higher degrees of connectivity, edge-connectivity. Eulerian graphs and their applications.
Distance in graphs, Dijkstra's algorithm, graph metric and its enumeration.
Trees and their characterizations, rooted trees, tree isomorphism.
Spanning trees, MST problem. Basic algorithms for MST.
Planar embeddings of graphs, Euler's formula and its applications.
Graph coloring, bipartite graphs, recognition.
Network flows: formulation and application to real life problems. Ford-Fulkerson's algorithm for maximum flow. Further applications to matching and system of representatives.
Recommended or Required Reading
Required Reading:
J.Matoušek, J.Nešetřil. Invitation to Discrete Mathematics, Oxford University Press, ISBN 0-19-850208-7.
M.Kubesa, Základy diskrétní matematiky, elektronický učební text, 2011, on-line.
P.Kovář, Algoritmizace diskrétních struktur, elektronický učební text, 2016, on-line.
P.Kovář, Úvod do teorie grafů, elektronický učební text, 2011, on-line.
Recommended Reading:
K.H.Rosen, Discrete Mathematics and Its Applications - 6th ed., McGraw-Hill, New York NY, (2007), ISBN-10 0-07-288008-2.
J.Matoušek, J.Nešetřil. Kapitoly z diskrétní matematiky, Karolinum Praha 2000.
(Konkrétně: Kapitoly 1,2 a část kapitoly 9 pro Část I přednášky. Kapitoly 3,4,5 pro Část II přednášky.)
Planned learning activities and teaching methods
Lectures, Individual consultations, Tutorials, Project work
Assesment methods and criteria
Tasks are not Defined