|
|
Main menu for Browse IS/STAG
Course info
KMA / DMA-A
:
Course description
Department/Unit / Abbreviation
|
KMA
/
DMA-A
|
Academic Year
|
2023/2024
|
Academic Year
|
2023/2024
|
Title
|
Discrete Mathematics
|
Form of course completion
|
Exam
|
Form of course completion
|
Exam
|
Accredited / Credits
|
Yes,
5
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
|
English
|
Occ/max
|
|
|
|
Automatic acceptance of credit before examination
|
No
|
Summer semester
|
0 / -
|
0 / -
|
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
|
English
|
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 |
No
|
Fundamental course |
No
|
Fundamental theoretical course |
No
|
Evaluation scale |
1|2|3|4 |
Evaluation scale for credit before examination |
S|N |
Substituted course
|
None
|
Preclusive courses
|
KMA/DMA
|
Prerequisite courses
|
N/A
|
Informally recommended courses
|
N/A
|
Courses depending on this Course
|
N/A
|
Histogram of students' grades over the years:
Graphic PNG
,
XLS
|
Course objectives:
|
The aim is to provide students with basic discrete mathematical structures, their properties and respective algorithms.
|
Requirements on student
|
Credit: two tests.
Exam: written and oral parts.
|
Content
|
1. Combinatorics. Advanced combinatorics.
2. Difference equations. Discrete dynamical systems.
3. Basic algebraic structures. Modular counting. Latin squares.
4. Detecting primes. Code theory and cryptography.
5. Block designs. Steiner triple systems.
6. Orderings. Lattices. Boolean algebra. Boolean functions. Minimisation.
7. Basic concepts of graph theory. Graph connectivity. Minimum spanning tree. Eulerian graphs.
8. Planar graphs. Graphs on surfaces. Digraphs. Strong connectivity. k-connectivity.
9. Matrices assigned to graphs. Algebraic properties of matrices. Spectra of matrices and graph properties.
10. Distance in graphs. Dijkstra algorithm. Floyd-Warshall algorithm. Dynamic programming.
11. Critical path. Cycle and cut spaces.
12. Hamiltonian graphs. Graph colouring. Extremal graph theory. Basics of Ramsey theory.
13. Graph problems as optimisation tasks. Computational complexity.
|
Activities
|
|
Fields of study
|
|
Guarantors and lecturers
|
|
Literature
|
-
Recommended:
Van Lint, J. H.; Wilson, R. M. A course in combinatorics. Cambridge : Harvard University Press, 2001. ISBN 0-521-00601-5.
-
Recommended:
Gross, Jonathan; Yellen, Jay. Graph theory and its applications. Boca Raton : CRC Press, 1999. ISBN 0-8493-3982-0.
-
Recommended:
Matoušek, Jiří; Nešetřil Jaroslav. Invitation to discrete mathematics. Oxford University Press, USA, 1998. ISBN 978-0198502081.
-
Recommended:
Scheinerman, Edward R. Mathematics: A discrete introduction. Brooks Cole, 2005. ISBN 978-0534398989.
-
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)
|
56
|
Preparation for formative assessments (2-20)
|
30
|
Total
|
138
|
|
Prerequisites
|
Knowledge - students are expected to possess the following knowledge before the course commences to finish it successfully: |
An active knowledge of linear algebra in a range of the course KMA/LA-A or KMA/LA-A and of combinatorics at high school level is assumed.
|
|
Learning outcomes
|
Knowledge - knowledge resulting from the course: |
A student will be able to:
- solve basic problems of combinatorics,
- use actively the concept of a relation and a function,
- apply basic facts of group theory,
- solve linear congruence equations,
- identify partial ordering relation,
- define lattices and Boolean algebras,
- deal with Boolean functions,
- use actively basic concepts of graph theory,
- describe a graph with help of matrices and use them to determine properties of the graph,
- apply linear algebra in graph theory,
- solve critical path problem.
|
|
Assessment methods
|
Knowledge - knowledge achieved by taking this course are verified by the following means: |
Combined exam |
Test |
Skills demonstration during practicum |
|
Teaching methods
|
Knowledge - the following training methods are used to achieve the required knowledge: |
Lecture |
Interactive lecture |
Practicum |
|
|
|
|