| Course title | Discrete Mathematics 2 |
|---|---|
| Course code | KMI/DMII |
| Organizational form of instruction | Lecture + Lesson |
| Level of course | Bachelor |
| Year of study | 3 |
| Semester | Winter |
| Number of ECTS credits | 6 |
| Language of instruction | Czech |
| 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 properties and types of graphs, isomorphism of graphs and their representation; 2 - Degree sequence of graph, handshaking lemma, degree sequence theorem; 3 - Walking on the Graph, graph metric, search for the shortest path; 4 - Conectivity of a graph; 5 - Drawing of graphs, Euler's graphs; 6 - Trees, characterization of trees and their coding; 7 - Spaning Trees, minimal spanning problem; 8 - Planar graphs, Eulers formula, 4 colors problem; 9 - Generating functions and their applications in combinatorics; 10 - More application of generating functions; 11 - Random structures and expected complexity of algorithms; 12 - Recurrence Relations; 13 - Reserve (in case of residual time the topic may be chosen by students).
|
| Learning activities and teaching methods |
| Monologic (reading, lecture, briefing), Dialogic (discussion, interview, brainstorming) |
| Learning outcomes |
|
The course is a continuation of DMI. 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 the linear recurrence relations as well.
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. |
| 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 |
|
Oral examination, Written examination, Test
Active attendance on the seminars (two absences are allowed, more absences will be tolerated (for some extra homeworks) just for serious reasons). There are the assesment test during the semestr. Student has to collect at least 50 percent for them. The course is finished by final examination test. To pass the course succesfully student has to collect at least 50 percent from the examination test. |
| 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): Economic Informatics (4) | Category: Economy | 3 | Recommended year of study:3, Recommended semester: Winter |