| Study program / study programs: Advanced data analytics |
| Course: Discrete structures |
| Teacher(s): Vesna P. Todorčević, Nebojša T. Nikolić |
| Course status: Elective |
| ECTS points: 10 |
| Prerequisites: none |
| Course objective: Mastering some standard topics of discrete mathematics as basics of mathematical logic and graph theory, relational structures, finite automata and formal languages. |
| Learning outcomes: The subject matter of this course is to teach the students the ways of formal deductions, to make them familiar with important applications of mathematical formalizations in the organization and the search of a large data basis as an important foundation for advanced analysis of data. |
| Course structure and content: Lectures Basic notions. Propositional calculus. Rules of inference in propositional calculus. First order logic. Truth value of a first order formula. Valid sentences. Relational structures. Partially ordered set, chain and lattice. Elementary graph theory. Trees. Coding and recognition of music melodies using graph theory. Music data base. Finite machines and finite automata. Minimization of automata. Formal languages and grammars. Labs Properties of the logical connectives. Elimination of certain logical operations. Properties of quantifiers. Truth values of propositional formulas. Relations on finite sets. Suprema, infima, lattices. Relations on infinite sets. Representing graphs, paths in graphs. Trees. Application of trees in computability theory. Finite automata. Minimization of finite automata. Regular grammars. |
| Literature/Readings Basic literature: Čangalović M., Todorčević V., Baltić V. Discrete mathematical structures, textbook, FOS, 2019. Todorčević V., Čangalović M., Baltić V. Book of problems from Discrete mathematical structures, FOS, 2016. Additional literature: D. Cvetković, S. Simić, Discrete Mathematics, Mathematics for computer sciences,Libra, Belgrade, 2000. A.J. Anderson, Discrete Mathematics with Combinatorics, Pearson Education,2004. D. Cvetković, V. Manojlović, Spectral recognition of music melodies, SYM-OP-IS 2013, 269-271. D. Cvetković, Т. Drobni, V. Тоdorčević, Recognition of music melodies in spectral graph theory, Phlogiston, 26 (2018), 165-180. |
| The number of class hours per week: Lectures: 4 Labs: 0 Workshops: 0 Research study: 3 Other classes: 0 |
| Teaching methods: Classical teaching method using blackboards, overhead projectors and computer presentations. |
| Evaluation/Grading (maximum 100 points): Pre-exam requirements: 40 (Activity during classes – 5, Practical classes – 5, Lab test(s) – 20, Seminar(s) – 10) Final exam: 60 (Written exam – 20, Oral exam – 40) |
