| Course Unit Code | 470-2301/03 |
|---|
| Number of ECTS Credits Allocated | 5 ECTS credits |
|---|
| Type of Course Unit * | Compulsory |
|---|
| Level of Course Unit * | First Cycle |
|---|
| Year of Study * | Second Year |
|---|
| Semester when the Course Unit is delivered | Winter Semester |
|---|
| Mode of Delivery | Face-to-face |
|---|
| Language of Instruction | Czech |
|---|
| Prerequisites and Co-Requisites | Course succeeds to compulsory courses of previous semester |
|---|
| Name of Lecturer(s) | Personal ID | Name |
|---|
| KUB59 | RNDr. Michael Kubesa, Ph.D. |
| KOV16 | doc. 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: |
|---|
P. Kovář: Lecture slides online http://homel.vsb.cz/~kov16/files/dim_kapitoly_all_en.pdf
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 http://homel.vsb.cz/~kov16/files/algoritmizace_diskretnich_struktur.pdf
P.Kovář, Úvod do teorie grafů, elektronický učební text, 2011, on-line http://homel.vsb.cz/~kov16/files/uvod_do_teorie_grafu.pdf
|
| Recommended Reading: |
|---|
K.H.Rosen, Discrete Mathematics and Its Applications - 6th ed., McGraw-Hill, New York NY, (2007), ISBN-10 0-07-288008-2.
P. Kovář: Lecture slides online http://homel.vsb.cz/~kov16/files/dim_kapitoly_all_en.pdf
P. Kovář, T. Kovářová: Solved exercises http://homel.vsb.cz/~kov16/files/dim_solved_exercises.pdf |
P. Kovář, Řešené přı́klady k procvičenı́, cvičebnice, 2022, on-line http://homel.vsb.cz/~kov16/files/dim_priklady_resene.pdf
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.)
P. Kovář: Lecture slides online http://homel.vsb.cz/~kov16/files/dim_kapitoly_all_en.pdf
P. Kovář, T. Kovářová: Solved exercises http://homel.vsb.cz/~kov16/files/dim_solved_exercises.pdf |
| Planned learning activities and teaching methods |
|---|
| Lectures, Individual consultations, Tutorials, Project work |
| Assesment methods and criteria |
|---|
| Task Title | Task Type | Maximum Number of Points
(Act. for Subtasks) | Minimum Number of Points for Task Passing |
|---|
| Credit and Examination | Credit and Examination | 100 (100) | 51 |
| Credit | Credit | 30 (30) | 10 |
| Project DiM | Project | 10 | 0 |
| Weekly Quizes | Written test | 20 | 0 |
| Examination | Examination | 70 | 21 |