Vijesti

STUDY: Computer Systems Maintenance

Course: Discrete Mathematics

Semester:

Lectures + Exercises:

Total:

ECTS Credits:

Elective

2

1

45

4

Course Objective: Acquiring more precise manner of expression and reasoning, understanding basic mathematical structures as well as basic structures and techniques of discrete mathematics, and their application in computer sciences.

Course Contents: MATHEMATICAL LANGUAGE. Symbolisation and use of variables. Definitions and proofs. SETS. The definition of set. Basic operations with sets. Partitive set. Set partition. RELATIONS. The definition of relation. Representing relation by graph and matrix. Equivalence relations. Ordering relations. Topological sorting. FUNCTIONS. The definition of function. Function representation by graph and program. Domain and set of values. Injectivity, surjectivity and bijectivity. Composition and inverse functions. MATHEMATICAL STRUCTURES. Mathematical structures and data structures. Structure of natural numbers. Algebra modulo n. INDUCTION AND RECURSION. Inductive proofs. Recursive definitions and recursive data types. COMBINATORICS. Basic counting principles. Permutations. Selections. COMPLEXITY OF ALGORITHMS. The definition of algorithm complexity. Asymptotic comparison of complexity. Effective and ineffective algorithms. Cryptography. GRAPHS. The definition of non-directional and directional graphs. Euler and Hamilton problems. The problem of shortest path and Dijkstra’s algorithm. The problem of minimum spanning tree and Prim’s algorithm.

General and Specific Competencies (Knowledge and Skills): Making use of basic mathematical vocabulary. Argumenting by induction and defining by recursion. Solving basic problems of counting. Estimate of algorithm complexity. Graph modelling of discrete problems. Use of basic algorithms with graphs.