| Course title | Discrete Mathematics 2 |
|---|---|
| Course code | KMI/DMIIA |
| Organizational form of instruction | Lecture + Lesson |
| Level of course | Bachelor |
| Year of study | not specified |
| Semester | Winter and summer |
| Number of ECTS credits | 6 |
| Language of instruction | English |
| Status of course | Compulsory-optional |
| Form of instruction | unspecified |
| Work placements | unspecified |
| Recommended optional programme components | None |
| Lecturer(s) |
|---|
|
| Course content |
|
1 - Graph Definition, basic examples and types of graphs, graph isomorphism, representation of a graph; 2 - Score of a graph, score theorem; 3 - Walking on the Graph, graph metric, searching of the shortest path; 4 - Connected graphs, trees; 5 - Euler graphs; 6 - Tree Coding, tree characterization; 7 - Spaning Trees, Jarnik, Boruvka and Kruskal algorithms; 8 - Plane graphs, Eulers formula; 9 - Generating functions and applications; 10 - Generating Functions (further applications in combinatorics); 11 - Random schemes and mean complexity of a graph; 12 - Recurrence Relations; 13 - Word Problems.
|
| Learning activities and teaching methods |
| Monologic (reading, lecture, briefing), Dialogic (discussion, interview, brainstorming) |
| Learning outcomes |
|
The course is a continuation of DMIA. 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 linear recurrence relations as well. The course is performed in English.
The 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. The students fulfill all their duties in English. |
| Prerequisites |
|
Discrete mathematics I (DMI, DMIA).
KMI/CDMI ----- or ----- KMI/DMI ----- or ----- KMI/DMIA ----- or ----- KMI/KDMI ----- or ----- KMI/KDMIA ----- or ----- KMI/YDMI |
| Assessment methods and criteria |
|
Combined exam, Test
Active attendance on the seminars (100 %). Two credit tests - minimum 55% of points each. Written exam test at minimum 55% of points. |
| Recommended literature |
|
| Study plans that include the course |
| Faculty | Study plan (Version) | Category of Branch/Specialization | Recommended semester | |
|---|---|---|---|---|
| Faculty: Faculty of Economics | Study plan (Version): Engineering and Informatics (1) | Category: Economy | 3 | Recommended year of study:3, Recommended semester: Winter |
| Faculty: Faculty of Economics | Study plan (Version): Economic Informatics (4) | Category: Economy | 3 | Recommended year of study:3, Recommended semester: Winter |