Course objectives:
|
The goal is to introduce basics of discrete mathematics and its relation with other fields of mathematics and applications.
|
Requirements on student
|
Credit: two tests.
Exam: written part, oral part.
|
Content
|
1. Combinatorics.
2. Advanced combinatorics. Difference equations.
3. Discrete dynamical systems.
4. Basic algebraic structures. Modular counting. Latin squares.
5. Detecting primes. Code theory and cryptography.
6. Boolean algebras. Boolean functions. Minimisation.
7. Basic concepts of graph theory. Graph connectivity. Minimum spanning tree. Eulerian graphs.
8. Planar graphs. 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.
11. Critical path. Cycle and cut spaces.
12. Hamiltonian graphs. Graph colouring. Basics of Ramsey theory.
13. Graph problems as optimisation tasks. Computational complexity.
|
Activities
|
|
Fields of study
|
|
Guarantors and lecturers
|
|
Literature
|
|
Time requirements
|
All forms of study
|
Activities
|
Time requirements for activity [h]
|
Contact hours
|
39
|
Preparation for comprehensive test (10-40)
|
11
|
Preparation for an examination (30-60)
|
30
|
Total
|
80
|
|
Prerequisites
|
Knowledge - students are expected to possess the following knowledge before the course commences to finish it successfully: |
popsat pojem množiny |
popsat pojem funkce |
vymezit pojem vektoru a matice |
Skills - students are expected to possess the following skills before the course commences to finish it successfully: |
řešit soustavy rovnic |
vypočítat vlastní čísla a vektory matice |
využívat derivace a integrály |
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: |
ovládat metody řešení jednodušších kombinatorických úloh |
definovat základní pojmy z oblasti Booleovských funkcí |
definovat základní pojmy teorie grafů |
znát algoritmy k řešení základních grafových úloh |
Skills - skills resulting from the course: |
řešit soustavy rovnic v aritmetice modulo k |
vyčíslovat a zjednodušovat Booleovské funkce |
řešit eulerovské problémy teorie grafů |
zjistit vzdálenost v grafech pomocí Dijkstrova algoritmu |
řešit úlohu minimální kostry grafu |
určit prostor kružnic a řezů grafu |
Competences - competences resulting from the course: |
N/A |
N/A |
|
Assessment methods
|
Knowledge - knowledge achieved by taking this course are verified by the following means: |
Oral exam |
Skills - skills achieved by taking this course are verified by the following means: |
Written exam |
Competences - competence achieved by taking this course are verified by the following means: |
Oral exam |
Written exam |
|
Teaching methods
|
Knowledge - the following training methods are used to achieve the required knowledge: |
Interactive lecture |
Lecture |
Practicum |
Skills - the following training methods are used to achieve the required skills: |
Practicum |
Interactive lecture |
Competences - the following training methods are used to achieve the required competences: |
Interactive lecture |
Practicum |
|