VSFS:B_DMa Discrete mathematics - Course Information

B_DMa Discrete mathematics

Extent and Intensity

2/1/0. 5 credit(s). Type of Completion: zk (examination).

Teacher(s)

RNDr. Ivan Havlíček, CSc. (lecturer)

Guaranteed by

RNDr. Ivan Havlíček, CSc.
Department of Computer Science and Mathematics – Departments – University of Finance and Administration
Contact Person: Ivana Plačková

Timetable of Seminar Groups

B_DMa/cAPH: each odd Tuesday 10:30–11:14 E129, each odd Tuesday 11:15–12:00 E129; and Wed 6. 12. 14:00–14:45 E230, I. Havlíček
B_DMa/pAPH: Tue 12:15–12:59 E129, Tue 13:00–13:45 E129, I. Havlíček
B_DMa/vAPH: Fri 10. 11. 15:45–17:15 E222, Sat 2. 12. 9:45–11:15 E122, 11:30–13:00 E122, Fri 15. 12. 14:00–15:30 E122, 15:45–17:15 E122, I. Havlíček

Prerequisites

There are no prerequisites for this course

Course Enrolment Limitations

The course is also offered to the students of the fields other than those the course is directly associated with.

fields of study / plans the course is directly associated with

• Applied Informatics (programme VSFS, B-INF) (2)

Course objectives

At the end of this course students will be able to: - Understand the proofs of logical formulae. - Apply the proofs of mathematical relations, especially proofs using contradiction and/or mathematical induction. - Understand binary relations: ordering and equivalence. Functions onto and one-to-one. - Combinatorial counting, - Remember the definition of unoriented graph, basic terminology of graphs. - Search for the shortest paths using Dijkstra‘s algorithm, matching in graph and its change. - Apply the score of graph and its conversions, solve the Euler trail and the task of a Chinese Mailman. - Explain properties of the special class of graphs, i.e. trees. Utilize different algorithms of the lightest spanning tree of an evaluated graph. - Apply Kruscal, Jarník/Prim and Borůvka algorithms finding the lightest spanning trees and discuss their effectivity. - Draw plannar graphs, construct and describe dual graphs. Try to color maps, verticie and edges, the four-color problem. - Oriented graph and its symetrisation, acyclic graph, condensation of graph, De Bruijn sequences. - Search in a network for the maximum flow and the minimum cut.

Syllabus

• 1. Introduction to mathematical logic.
• 2. Mathematical proofs, sets.
• 3. Binary relations and functions.
• 4. Combinatorial counting and discrete probability.
• 5. The definition and basic types of undirected graph.
• 6. The lightest path in graph (Dijstra algorithm) and matching in graph.
• 7. Euler graphs and connectivity of graphs.
• 8. Special class of graphs - trees.
• 9. The algorithms for finding the lightest spanning tree of a graph, plannar graphs.
• 10. Coloring of a map, the four color theorem.
• 11. The oriented graphs.
• 12. Flows in a network.

Literature

required literature
• HAVLÍČEK, I., Sbírka příkladů z diskrétní matematiky, umístěná v IS VŠFS"Učební materiály"
• Náhradní obsah: Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky. Nakladatelství Karolinum: Praha, 2009.
• DEMEL, J., Grafy a jejich aplikace, Libčice nad Vltavou 2015
• HAVLÍČEK, I., Powerpointová prezentace k přednášce, umístěná v IS VŠFS "Učební materiály"
• Havlíček, I.: Diskrétní matematika. Praha: VŠFS - Eupress, 2007.

Teaching methods

Lectures and seminars in full-time study; tutorials in part-time study; compulsory seminar participation is 75% in full-time study, compulsory tutorial participation is 50% in part-time study

Assessment methods

Credit (75% participation in the exercise), written exam (50% correct answers) and oral examen.

Language of instruction

Czech

Further comments (probably available only in Czech)

The course can also be completed outside the examination period.
General note: pouze prezenční forma.
Information on the extent and intensity of the course: 10 hodin KS/semestr.

• Enrolment Statistics (Winter 2017, recent)
  
• Permalink: https://is.vsfs.cz/course/vsfs/winter2017/B_DMa