DISCRETE MATHIMATICS

Abstract of the academic discipline

The purpose of studying the discipline: to provide basic training for fluency in the concepts and terminology of discrete mathematics, the use of discrete mathematics methods for solving applied problems, the formation of practical skills in students of higher education, which would enable the effective application of knowledge and methods of discrete mathematics in the future professional work
Practical significance and use of the acquired knowledge:
- formation of basic knowledge and mastery of concepts, terminology of discrete mathematics;
mastering the methods of solving applied problems and conducting research using the methods and means of discrete mathematics;
- creation of the necessary theoretical and practical foundation for successful mastering of disciplines related to theoretical research in the field of programming and information technologies.

Main learning outcomes
PRN#1. Apply knowledge of basic forms and laws of abstract logic
thinking, fundamentals of the methodology of scientific knowledge, forms and methods of extraction,
analysis, processing and synthesis of information in the subject area of computer science.
PRN#2. Use modern mathematical apparatus of continuous and
discrete analysis, linear algebra, analytical geometry, in professional
activities for solving problems of a theoretical and applied nature in
the process of designing and implementing informatization objects. (p
PRN#5. Design, develop and analyze algorithms for solving computational and logical problems, evaluate the efficiency and complexity of algorithms based on the application of formal models of algorithms and calculated functions.

Subjects and types of educational classes
1 week.
Lecture #1. 
"Definition of discrete mathematics. Digitization, quantization, discretization is a paradigm of modern computer technology. An example of sound digitization. Loss of information during digitization. A bridge between the description of the operation of the device and its implementation by logical functions implemented at the level of physics. Formal logic as a branch of mathematics".
Practical lesson 1. "Logical functions. A formal record of logical reasoning. Logical operations and their relative priority. Simplification of writing formulas. Basic identities of Boolean algebra".
2 week.
Lecture #2. 
"Problems of Boolean functions. Tabular method. Analytical method. Boolean functions of one and two variables. Interconversion of Boolean functions. Definition of degenerate and non-degenerate functions. Dependencies between Boolean functions and defining all functions of two variables through AND, OR, and NOT operations.
Practical lesson #2. 
"Zhegalkin algebra, definition, formulas of direct transition from Zhegalkin algebra to Boolean algebra and, conversely, from Boolean algebra to Zhegalkin algebra. Definition of canonical polynomial in the context of Zhegalkin Algebra. Classification of Boolean functions according to Post's theorem. Definition of functional completeness with respect to the superposition of functions".
3 week.
Lecture #3. 
"Synthesis of a complete binary adder as an example of the transition from a formal description to the implementation of a physical device using Boolean functions. Minimal forms and the canonical problem of synthesis of Boolean functions. Definition of complete disjunctive normal form (DDNF) and disjunctive normal form (DNF) as basic terms of the minimization algorithm".
Practical lesson #3. 
"Definition of absorption and gluing operations. Determination of dead-end forms as a result of minimization. Determination of Quine's price as a criterion for the minimum function. Minimization using Carnot maps".
Obtaining a task for the Calculation-Graphic Work.
4 week.
Lecture #4. "Automatic minimization of Boolean functions as an alternative to the Carnot method. Basic algorithms. Definition of a complex of cubes. The Quine-McClusky method".
Practical lesson 4. "Minimization of functions by the Quine-McCluska method."
Implementation of the first part of the Calculation-Graphic Work.
5 week.
Lecture #5. "Minimization of functions from three and four variables by the cube method. Comparison of various methods of minimization, justification of choosing one or another method. Minimization of partially defined functions".
Practical lesson #5. 
"Minimization of functions from three and four variables by the method of cubes."
Implementation of the first part of the Calculation-Graphic Work.
6 week.
Lecture # 6. 
"Theory of sets. Basic definitions. Methods of assignment of sets, subsets. Operations on sets, the addition operation and its correspondence to the inversion operation in Boolean algebra, Euler circles. Properties of operations on sets. The set of all subsets, boolean. Methods of proving the identities of the algebra of sets"
Practical lesson #6. 
"Simplification of set expressions through properties and the use of Euler's circles to obtain the result of operations on sets."
Implementation of the first part of the Calculation-Graphic Work
7 week.
Lecture #7. 
"Theory of sets. Definition of tuple, Cartesian product, ordered pair, cardinal number. Determination of correspondence, binary relations, composition of relations, matrix of relations and other methods of assignment of binary relations (tabular and in the form of graphs)".
Practical lesson #7.
"Building a relationship matrix."
Defense of the first part of the Calculation-Graphic Work.
8 week.
Lecture# 8. 
"Elements of graph theory. Definition of a graph, graph vertices, arcs and edges. Basic definitions: adjacency matrix and incidence matrix as a way to store information about a graph.
Practical exercise #8. 
"Construction of graphs by adjacency and incidence matrices."
Modular control work #1.
9 week.
Lecture #9. 
"Theory of graphs. Determining the weight of the arc, apex, edge. Definition of a variety of arc-loops and an undirected graph, weighted and unweighted. General types of graphs: pseudographs, multigraphs, simple graphs, null graphs, complete graphs, bipartite graphs, homogeneous graphs. Determination of the degree of the top of the graph. The composition of relations, representation of the composition of relations on a graph, methods of obtaining decisions regarding the composition of relations. Examples of using the relationship composition search algorithm".
Practical lesson #9. 
"Construction of directed and undirected graph, construction of weighted graph."
Implementation of the second part of the Calculation-Graphic Work.
10 week.
Lecture #10. 
"Algorithm for finding the minimum path on a discrete field - Lie's algorithm. Definition of the chromatic number of a graph, coloring algorithm, description, field of application, examples of using the coloring algorithm."
Practical lesson #10. 
"Determining the chromatic number using graph coloring algorithms, Lie's algorithm."
Implementation of the second part of the Calculation-Graphic Work.
11 week.
Lecture #11. 
"Theory of graphs. The concept of isomorphism. Definition of a route on a graph, definition of a chain, definition of a simple chain, definition of a cycle and a simple cycle on a graph. The classic problem about Königsberg bridges, the definition of the Euler cycle, the definition of the semi-Eulerian cycle. Necessary conditions for the existence of both of the above types of graphs. Definition of a Hamiltonian cycle, conditions for the existence of a Hamiltonian cycle on a graph".
Practical lesson #11. 
"Definition of the Euler and Hamilton cycle on graphs. Construction of isomorphic graphs".
Implementation of the second part of the Calculation-Graphic Work.
12 week
Lecture #12. 
"Trees and forest in graph theory, basic definitions. Types of trees. Definition of the core of the graph. Kruskal and Prim algorithms for building a spanning tree. Algorithms for finding the minimum path on a graph, features of use, expediency of this or that algorithm. The Floyd-Warshell algorithm for finding the minimum path between any two vertices of a graph.
Practical lesson #12 
"Building a spanning tree according to Prim and Kruskal algorithms. Finding the minimum path between the vertices of a graph using the Floyd-Warshell algorithm".
Implementation of the second part of the Calculation-Graphic Work.
13 week.
Lecture #13. 
"Finding the shortest and longest paths on a graph between two specific vertices: Dijkstra's algorithm, comparison with Floyd's algorithm in terms of speed and memory usage. Definition of flat (planar) graphs. Counts of Pontryagin-Kuratovsky".
Practical lesson #13
"Finding the minimum path between the vertices of a graph using Dijkstra's algorithm."
Implementation of the second part of the Calculation-Graphic Work.
14 week.
Lecture #14. 
"Determining the center and centroid on a graph. Search algorithms. Analysis of problems in which it is appropriate to use one or another algorithm. Determination of eccentricity for all vertices of the graph. Prüfer codes that allow you to store tree graphs in a one-dimensional array. Graph-tree packing, code and anticode".
Practical lesson #14. 
"Construction of a tree uniquely described by Prüfer codes in a one-dimensional array of size n-2 (n is the number of vertices of the graph)."
Implementation of the second part of the Calculation-Graphic Work.
15 week.
Lecture #15. 
"Combinatorics. Sum and product rules. Placements, permutations and combinations with and without repetition. Newton's binomial. The principle of inclusion and exclusion".
Practical lesson #15. 
"Solving combinatorics problems."
Defense of the second part of the Calculation-Graphic Work.
Modular control work #2.

Individual work of the applicant takes place during the semester and consists of preparation for classroom classes, control measures, individual tasks.
Consultations: are carried out by the teacher during the semester according to the schedule.

Assessment of learning outcomes
The evaluation of the results of studies in the discipline is carried out according to the cumulative system, which allows the student to receive a maximum of 100 points during the semester.
Module 1.  Practical classes - for active participation, 1 point per class (8 points in total)
The first part of the Calculation-Graphic Work was flawlessly completed and submitted to the teacher on time - maximum of 12 points.
Modular test 1 – perfect execution of 30 points (in each task of the modular test, maximum number of points for each task is given).
Module 2. Practical classes - for active participation, 1 point per class (7 points in total)
The second part of the calculation and graphic work was impeccably performed, submitted to the teacher on time - 13 points.
Modular test 2 – perfect execution of 30 points (in each task of the modular test, maximum number of points for each task is given).

Links to recommended sources of information
1. Конспект лекцій з дисципліни «Дискретна математика» для студентів денної форми навчання інституту комп’ютерних систем спеціальності 122 – «Комп’ютерні науки» / Укл.: Ю.В.Дрозд, М.О. Дрозд, – Одеса. ОНПУ, 2019. – 93с. 
2. Методичні вказівки та завдання для проведення практичних занять з дисципліни «Дискретна математика» для студентів денної форми навчання інституту комп’ютерних систем спеціальності 122 – «Комп’ютерні науки» / Укл.: Ю.В.Дрозд, М.О. Дрозд, – Одеса. ОНПУ, 2019. – 59с. 
3. Методичні вказівки та завдання для виконання розрахунково-графічної роботи з дисципліни «Дискретна математика» для студентів денної форми навчання інституту комп’ютерних систем спеціальності 122 – «Комп’ютерні науки» / Укл.: Ю.В.Дрозд, М.О. Дрозд, – Одеса. ОНПУ, 2019. – 14с. 
4. Балога С.І. Дискретна математика. Навчальний посібник. – Ужгород: ПП «АУТДОР-ШАРК», 2021. – 124 с. https://dspace.uzhnu.edu.ua/jspui/bitstream/lib/36740/1/Навчальний%20посібник%20Дискретна%20математика%20.pdf
5. Дискретна математика: Конспект лекцій (Частина 1) [Електронний ресурс]: навч. посіб. для студ. спеціальності 113 «Прикладна математика», освітньої програми «Наука про дані та математичне моделювання» / О.Л.Темнікова ; КПІ ім. Ігоря Сікорського. – Електронні текстові дані (1 файл: 2,97 Мбайт). – Київ : КПІ ім. Ігоря Сікорського, 2021. – 154 https://ela.kpi.ua/bitstream/123456789/42839/1/LectureDM1Temnikova.pdf