Course description

Purpose. Studying of the main concepts and methods of discrete mathematics and their applications in computer sciences.

Short description. In a course theoretical provisions of mathematical logic, the combinatory analysis, the theory of counts and the relations, theories of codes, Boolean functions and the theory of calculations with the proofs of theorems, the formulations of algorithms of the solution of discrete tasks are studied.

Problem. To seize the basic theoretical provisions of discrete mathematics and their applications in computer sciences.

As a result of studying of this course the student
Has to know
• Basic provisions of mathematical logic;
• Main definitions and theorems of the theory of counts;
• The main algorithms on columns;
• Applications of trees in informatics;
• Relations and their applications;
• Main concepts of the theory of codes;
• Boolean functions and their applications;
• Modeling computation.

Has to be able
• To formulate basic provisions of mathematical logic and to apply them in proofs of theorems;
• To carry out the main operations over sets, using computer representation of sets;
• To work with columns, in particular, to use the main algorithms on columns;
• To use algorithms of work with trees;
• To use the device of the relations;
• To build Fano, Huffman and Hamming codes;
• To build normal forms of Boolean functions, the minimal forms and logic gates;
• To estimate computation complexity of algorithms.