|
|
Main menu for Browse IS/STAG
Course info
KMA / DMA
:
Course description
Department/Unit / Abbreviation
|
KMA
/
DMA
|
Academic Year
|
2023/2024
|
Academic Year
|
2023/2024
|
Title
|
Discrete Mathematics
|
Form of course completion
|
Exam
|
Form of course completion
|
Exam
|
Accredited / Credits
|
Yes,
4
Cred.
|
Type of completion
|
Combined
|
Type of completion
|
Combined
|
Time requirements
|
Lecture
3
[Hours/Week]
Tutorial
1
[Hours/Week]
|
Course credit prior to examination
|
Yes
|
Course credit prior to examination
|
Yes
|
Automatic acceptance of credit before examination
|
No
|
Included in study average
|
YES
|
Language of instruction
|
Czech
|
Occ/max
|
|
|
|
Automatic acceptance of credit before examination
|
No
|
Summer semester
|
267 / -
|
15 / -
|
0 / -
|
Included in study average
|
YES
|
Winter semester
|
0 / -
|
0 / -
|
0 / -
|
Repeated registration
|
NO
|
Repeated registration
|
NO
|
Timetable
|
Yes
|
Semester taught
|
Summer semester
|
Semester taught
|
Summer semester
|
Minimum (B + C) students
|
1
|
Optional course |
Yes
|
Optional course
|
Yes
|
Language of instruction
|
Czech
|
Internship duration
|
0
|
No. of hours of on-premise lessons |
|
Evaluation scale |
1|2|3|4 |
Periodicity |
každý rok
|
Evaluation scale for credit before examination |
S|N |
Periodicita upřesnění |
|
Fundamental theoretical course |
Yes
|
Fundamental course |
Yes
|
Fundamental theoretical course |
Yes
|
Evaluation scale |
1|2|3|4 |
Evaluation scale for credit before examination |
S|N |
Substituted course
|
None
|
Preclusive courses
|
KMA/DMA-A
|
Prerequisite courses
|
N/A
|
Informally recommended courses
|
KMA/LA or KMA/ME2
|
Courses depending on this Course
|
N/A
|
Histogram of students' grades over the years:
Graphic PNG
,
XLS
|
Course objectives:
|
The course provides a knowledge of basics of discrete mathematics.
|
Requirements on student
|
Credit requirements: written test.
Exam: written test, orals.
For requirements see http://portal.zcu.cz - CourseWARE
|
Content
|
1. Basic set theory. Relations and mappings. Combinatorics.
2. Basic algebraic structures. Modular arithmetic.
3. Orderings, properties. Hasse diagram.
4. Lattices. Distributive and complementary lattices.
5. Boolean algebras. Boolean calculus. Direct product of Boolean algebras, Stone representation theorem.
6. Boolean functions, Boolean polynomials, disjunctive and conjunctive normal form. Minimal form.
7. Directed and undirected graphs. Basic graph theory concepts. Graph homomorphisms.
8. Graph connectivity. Trees and spanning trees. Eulerian graphs. Directed graphs. Weak and strong connectivity. Acyclic graphs, condensation.
9. Matrix representation of a graph: adjacency, incidence and Laplace matrix. Basics of algebraic and spectral graph theory.
10. Number of spanning trees. Number of walks. Applications.
11. Weighted graphs. Gentle introduction to algorithms and computational complexity.
12. Applications: minimum spanning tree, distance and shortest paths, critical path, Chinese postman problem.
13. Introduction to further areas: planar graphs, Hamiltonian graphs, graph coloring, network flows, complex networks, coding, cryptography.
|
Activities
|
|
Fields of study
|
|
Guarantors and lecturers
|
-
Guarantors:
Doc. Ing. Roman Čada, Ph.D. ,
-
Lecturer:
Doc. Ing. Roman Čada, Ph.D. (100%),
-
Tutorial lecturer:
RNDr. Jan Ekstein, Ph.D. (100%),
Doc. RNDr. Přemysl Holub, Ph.D. (100%),
RNDr. Adam Kabela, Ph.D. (100%),
RNDr. Milena Šebková (100%),
RNDr. Mgr. Jakub Teska, Ph.D. (100%),
|
Literature
|
-
Basic:
Čada, Roman; Kaiser, Tomáš; Ryjáček, Zdeněk. Diskrétní matematika. Plzeň : Západočeská univerzita, 2004. ISBN 80-7082-939-7.
-
Basic:
Matoušek, Jiří; Nešetřil, Jaroslav. Kapitoly z diskrétní matematiky. Čtvrté, upravené a doplněné vydání. 2019. ISBN 978-80-246-1740-4.
-
Extending:
Biggs, Norman L. Discrete Mathematics. Oxford Univ. Press, 2002. ISBN 9780198507178.
-
Extending:
Discrete Mathematics - An Open Introduction
(Levin, Oscar)
-
Recommended:
Keller, M.T.; Trotter, W.T. Applied Combinatorics. CreateSpace Independent Publishing Platform. 2017.
-
Recommended:
Gross, Jonathan L.; Yellen, Jay; Anderson, Mark. Graph Theory and Its Applications. Chapman and Hall/CRC, New York, 2018. ISBN 9781482249484.
-
Recommended:
Kopka, Jan. Svazy a Booleovy algebry. Univerzita J.E.Purkyně v Ústí nad Labem, 1991. ISBN 80-7044-025-2.
-
On-line library catalogues
|
Time requirements
|
All forms of study
|
Activities
|
Time requirements for activity [h]
|
Contact hours
|
52
|
Preparation for an examination (30-60)
|
58
|
Preparation for formative assessments (2-20)
|
18
|
Total
|
128
|
|
Prerequisites
|
Knowledge - students are expected to possess the following knowledge before the course commences to finish it successfully: |
to formulate basic concept of linear algebra and explain their basic properties |
Skills - students are expected to possess the following skills before the course commences to finish it successfully: |
to apply basic methods of linear algebra |
Competences - students are expected to possess the following competences before the course commences to finish it successfully: |
N/A |
|
Learning outcomes
|
Knowledge - knowledge resulting from the course: |
to describe matrix representation of a graph and explain relations among properties of graphs and algebraic properties of relevant matrices |
to explain algorithmic aspects of solving of some basic applicable graph problems |
to explain basic notions of the theory of relation structures: binary relation, equivalence (including a special case of arithmetics modulo 2), linear a partial orderings, Boolean algebra and Boolean functions and polynoms |
to express basic notions of the graph theory and explain their basic properties, including connections among them |
Skills - skills resulting from the course: |
to apply basics of of Boolean algebras including an expression of Bollean functions (polynomials) in canonical conjunctive and disjunctive normal forms |
to design algorithms for solving of basic graph problems, analyze their theoretical and algorithmical attributes, and use the designed algorithms on examples |
to know the concept of equivalence and partition of a set into equivalence classes |
to represent a graph structure by a matrix including understanding of relations between properties of graphs and algebraic properties of relevant matrices |
to solve simple problems in arithmetic modulo k |
Competences - competences resulting from the course: |
aktivně využívá získané znalosti a dovednosti při řešení praktických problémů |
|
Assessment methods
|
Knowledge - knowledge achieved by taking this course are verified by the following means: |
Combined exam |
Test |
Skills demonstration during practicum |
Skills - skills achieved by taking this course are verified by the following means: |
Combined exam |
Skills demonstration during practicum |
Test |
Competences - competence achieved by taking this course are verified by the following means: |
Combined exam |
Skills demonstration during practicum |
Test |
|
Teaching methods
|
Knowledge - the following training methods are used to achieve the required knowledge: |
Lecture |
Practicum |
Skills - the following training methods are used to achieve the required skills: |
Lecture |
Practicum |
Competences - the following training methods are used to achieve the required competences: |
Lecture |
Practicum |
|
|
|
|