 | The course contains 10 parts. Part one is focused on fundamentals of set theory which is indispensable for all mathematical disciplines. We present here basic concepts and knowledge related to set theory and Venn diagrams. Part two is dedicated to propositional calculus, we explain the principle of evaluating propositional formulas, we define various terms related to propositions and we present the principle of algebraic simplification of propositional formulas to finite normal disjunctive and conjunctive form. Part three consists of Boolean algebra, which directly follows propositional calculus. The main parts of the part are algebraic simplification of Boolean expressions and the use of B-algebra in the design of computer electronic circuits. Part four explains, with the use of various applications, binomial and multinomial theorem and the principle of inclusion and exclusion with a link to number theory. In the following fifth part we define the basic concepts of combinatorics and we explain the principle of using combinatorial structures in problem solving. Divisibility, as one of the basic concepts of discrete mathematics, is discussed in part six. In this section, terms such as the divides relationship, the greatest common divisor or the least common multiple, Dirichlet’s principle and partitions are explained. Part seven includes basic knowledge of prime numbers and explains the nature of their use in the encryption process and the algorithm for their generation. The part contains a number of key terms related to prime numbers such as the fundamental theorem of arithmetic or canonical decomposition of an integer. The content of the eighth part contains solving of linear Diophantine equations in two unknowns and Fermat's Last Theorem. The part also explains the principle of division with a remainder, the so called Euclidean algorithm. Modular arithmetic, which along with prime numbers plays an important role in cryptography, is the subject of part nine. We focused mainly on the basic properties of congruences, residue classes and solutions to linear congruences. In this part, we also present the principle of solving linear congruences and we explain the necessary and sufficient condition for solvability of a system, the so called Chinese remainder theorem. A special section of this part is the section focused on the constraint satisfaction problem which is one of the possibilities for solving systems of linear congruences by algorithm, as well as for solving other problems related to modular arithmetic. Every problem that we are trying to solve within mathematics or computer science (whether it is a combinatorial, algorithmic or encryption problem) is characterized by its complexity and it is important to know at least the basic terms of complexity theory. Therefore, in the last, tenth part of our course, we include basic knowledge of complexity and we explain complexity classes and characterize the so called NP-completeness. |
