Course: Discrete Mathematics II

« Back
Course title Discrete Mathematics II
Course code KIN/DM2A
Organizational form of instruction Lecture + Lesson
Level of course Bachelor
Year of study 2
Semester Winter
Number of ECTS credits 5
Language of instruction Czech
Status of course Compulsory
Form of instruction unspecified
Work placements unspecified
Recommended optional programme components None
Lecturer(s)
  • Dobiáš Václav, Mgr. Ph.D.
  • Beránek Ladislav, doc. Ing. CSc.
Course content
1. Graph Definition 2. Operations on Graphs 3. Walking on the Graph 4. Graph homomorphisms 5. Trees 6. Tree Coding 7. Spaning Trees 8. Greedy Algorithm 9. Shortest Path Problem 10. Generating Functions 11. Pólya Theorem 12. Recurrence Relations 13. Word Problems

Learning activities and teaching methods
Monologic (reading, lecture, briefing)
Learning outcomes
The course is a continuation of KIN/DM1A. Its first part is targeted at the graph theory, including some chosen graph algorithms. Further, the theory of generating functions is performed with applications on word problems (the Pólya theorem) and the technique of solving the linear recurrence relations as well.
Student understands the fundamental concepts of the graph theory. He/she performs the basic graph operations and determines some typical parameters of the graph. He/she masters the Prüfer coding of the trees, the greedy, the Dijkstra and the Floyd algorithms, and, on a variety of word problems, demonstrates the use of the generating functions and the linear recurrence relations.
Prerequisites
KIN/DM1A
KIN/DM1A

Assessment methods and criteria
Written examination

Active attendance at seminars (100 %). Two credited tests - minimum 55% of points each. Written exam test at minimum 55% of points.
Recommended literature
  • Diestel, R. Graph Theory. electronic edition [online]. [cit. 1. 9. 2008].. New York: Springer-Verlag, 2000.
  • Matoušek, J., Nešetřil, J. Kapitoly z diskrétní matematiky.. Praha: Karolinum, 2007. ISBN 978-80-246-1411-3.
  • Nýdl, V. Diskrétní matematika v příkladech, díl 2.. České Budějovice: PF JU, 2007.
  • Rosen, K., H. Discrete Mathematics and Its Applications.. New York: McGraw-Hill, 1988.


Study plans that include the course
Faculty Study plan (Version) Category of Branch/Specialization Recommended year of study Recommended semester
Faculty: Faculty of Education Study plan (Version): Introductory teacher training course in information technology (3) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Winter
Faculty: Faculty of Education Study plan (Version): Introductory teacher training course in information technology (2) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Winter
Faculty: Faculty of Education Study plan (Version): Introductory teacher training course in information technology (4) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Winter
Faculty: Faculty of Education Study plan (Version): Introductory teacher training course in information technology (3) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Winter
Faculty: Faculty of Education Study plan (Version): Introductory teacher training course in information technology (4) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Winter
Faculty: Faculty of Education Study plan (Version): information technology and e-learning (2) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Winter
Faculty: Faculty of Education Study plan (Version): Introductory teacher training course in information technology (2) Category: Pedagogy, teacher training and social care 2 Recommended year of study:2, Recommended semester: Winter