Discrete Mathematics
Description: Basic concepts of set theory. The most important types of binary relations. Introduction to propositional logic. Introduction to predicate logic, quantifiers. Boolean functions, their properties. The most important closed classes of Boolean functions. Complete systems of Boolean functions. Minimization of boolean functions. Introduction to graph theory.
Amount of credits: 5
Пререквизиты:
- Linear Algebra & Analytical Geometry
Course Workload:
| Types of classes | hours |
|---|---|
| Lectures | 15 |
| Practical works | 30 |
| Laboratory works | |
| SAWTG (Student Autonomous Work under Teacher Guidance) | 30 |
| SAW (Student autonomous work) | 75 |
| Form of final control | Exam |
| Final assessment method |
Component: University component
Cycle: Base disciplines
Goal
- Training of specialists for the design of architecture, elements of mathematical, informational and software support for hardware and software complexes and systems and other types of design and engineering activities.
Objective
- The acquisition by students of basic knowledge of graph theory, the theory of Boolean functions, set theory, formal calculus.
- In practical classes, it is necessary to develop the skills of compiling and analyzing mathematical models of simple applied problems related to the future activities of an engineer.
Learning outcome: knowledge and understanding
- Possess basic knowledge in the field of discrete mathematics, contributing to the formation of a highly educated personality with a broad outlook and a culture of thinking.
- Understand the fundamental basis of modern mathematics and its logical structure.
Learning outcome: applying knowledge and understanding
- Apply modern mathematical methods in solving various problems of science and technology. Be able to assess the reliability and security of computing systems and networks.
- Know and be able to use mathematical models, methods, information technologies in scientific research and other activities
Learning outcome: formation of judgments
- Set new scientific tasks in the field of applications of mathematics to solving problems in professional activities.
Learning outcome: communicative abilities
- Математика саласында теориялық және қолданбалы ғылыми зерттеулер жүргізу үшін жеке және топпен жұмыс істей білу; математика және оны қолдану саласындағы халықаралық ынтымақтастық
Learning outcome: learning skills or learning abilities
- Based on an understanding of the fundamental foundations of modern mathematics and its logical structure, the student must be able to master special disciplines and have the skill of independent work.
Teaching methods
Lectures and online lectures, practical exercises using slides and other multimedia tools, in particular, the use of the Open edX platform.
search and research (students' own research activities in the learning process);
Assessment of the student's knowledge
Teacher oversees various tasks related to ongoing assessment and determines students' current performance twice during each academic period. Ratings 1 and 2 are formulated based on the outcomes of this ongoing assessment. The student's learning achievements are assessed using a 100-point scale, and the final grades P1 and P2 are calculated as the average of their ongoing performance evaluations. The teacher evaluates the student's work throughout the academic period in alignment with the assignment submission schedule for the discipline. The assessment system may incorporate a mix of written and oral, group and individual formats.
| Period | Type of task | Total |
|---|---|---|
| 1 rating | oral survey | 0-100 |
| ИДЗ | ||
| ИДЗ | ||
| Intermediate control | ||
| 2 rating | oral survey | 0-100 |
| ИДЗ | ||
| ИДЗ | ||
| Intermediate control | ||
| Total control | Exam | 0-100 |
The evaluating policy of learning outcomes by work type
| Type of task | 90-100 | 70-89 | 50-69 | 0-49 |
|---|---|---|---|---|
| Excellent | Good | Satisfactory | Unsatisfactory | |
| Interview (colloquium) on control questions | Demonstrates systematic theoretical knowledge, masters terminology, logically and consistently explains the essence of phenomena and processes, draws substantiated conclusions and generalizations, gives examples, speaks fluently in monologue speech, and can quickly answer clarifying questions. | 1. Demonstrates good theoretical knowledge, knows the terminology, logically and consistently explains the essence, phenomena and processes, makes substantiated conclusions and generalizations. 2. Gives examples, demonstrates fluency in monological speech, but makes minor errors that can be corrected independently or with minor corrections from the teacher. | 1. Demonstrates poor theoretical knowledge, poorly developed skills in analyzing phenomena and processes, inability to draw substantiated conclusions and give examples. 2. Does not have sufficient knowledge of monologue speech, terminology, logic and presentation consistency, makes mistakes that can only be corrected by the teacher. | Demonstrates systematic theoretical knowledge, masters terminology, logically and consistently explains the essence of phenomena and processes, draws substantiated conclusions and generalizations, gives examples, speaks fluently in monologue speech, and can quickly answer clarifying questions. |
| Homework (individual homework) or written work / exam | 1. Performs practical work in full, observing the necessary sequence of actions. 2. Correctly and accurately performs all notes, tables, pictures, drawings, graphs, calculations in the answer. 3. Correctly performs error analysis. 4. When answering questions, he correctly understands the meaning of the question, accurately defines and explains the main concepts. 5. Accompany the answer with new examples, can apply knowledge in a new situation. 6. Can establish connections between the studied and previously studied material, as well as material obtained when studying other subjects. | The requirements for the grade "5" are met, but 2-3 shortcomings are made. 2. The student's answer to the questions meets the basic requirements for the answer to grade 5, but is given without applying knowledge in a new situation, without using the connection with previously studied material and material mastered during the study of other subjects. 3. One error or no more than two shortcomings are made, the student can correct them independently or with a little help from the teacher. | 1. The work was not completed in full, but at least 50% of the volume of practical work was completed, which allows obtaining correct results and conclusions. 2. Mistakes were made during the work. 3. When answering the questions, the student correctly understands the meaning of the question, but the answer contains individual problems in mastering course questions that do not interfere with further mastering the program material. 4. No more than one gross error and two shortcomings were made. | 1. Performs practical work in full, observing the necessary sequence of actions. 2. Correctly and accurately performs all notes, tables, pictures, drawings, graphs, calculations in the answer. 3. Correctly performs error analysis. 4. When answering questions, he correctly understands the meaning of the question, accurately defines and explains the main concepts. 5. Accompany the answer with new examples, can apply knowledge in a new situation. 6. Can establish connections between the studied and previously studied material, as well as material obtained when studying other subjects. |
Evaluation form
The student's final grade in the course is calculated on a 100 point grading scale, it includes:
- 40% of the examination result;
- 60% of current control result.
The final grade is calculated by the formula:
| FG = 0,6 | MT1+MT2 | +0,4E |
| 2 |
Where Midterm 1, Midterm 2are digital equivalents of the grades of Midterm 1 and 2;
E is a digital equivalent of the exam grade.
Final alphabetical grade and its equivalent in points:
The letter grading system for students' academic achievements, corresponding to the numerical equivalent on a four-point scale:
| Alphabetical grade | Numerical value | Points (%) | Traditional grade |
|---|---|---|---|
| A | 4.0 | 95-100 | Excellent |
| A- | 3.67 | 90-94 | |
| B+ | 3.33 | 85-89 | Good |
| B | 3.0 | 80-84 | |
| B- | 2.67 | 75-79 | |
| C+ | 2.33 | 70-74 | |
| C | 2.0 | 65-69 | Satisfactory |
| C- | 1.67 | 60-64 | |
| D+ | 1.33 | 55-59 | |
| D | 1.0 | 50-54 | |
| FX | 0.5 | 25-49 | Unsatisfactory |
| F | 0 | 0-24 |
Topics of lectures
- Множества
- Бинарные отношения, их основные свойства
- Важнейшие типы бинарных отношений: эквивалентности, частичные порядки, функции
- Логика высказываний и основные булевы функции
- Исчисление высказываний
- Предикаты и кванторы
- Применения матлогики в математике и информатике
- Нормальные формы и многочлен Жегалкина
- Полнота и замкнутость систем булевых функций
- Проблема минимизации булевых функций
- Методы нахождения сокращённых и тупиковых ДНФ
- Методы нахождения минимальных ДНФ
- Определения, начальные понятия теории графов
- Метрические характеристики графов
- Некоторые оптимизационные алгоритмы на графах
Key reading
- С.В. Яблонский Введение в дискретную математику.– М., Наука, 2009.
- С.В. Судоплатов, Е.В. Овчинникова Дискретная математика, Новосибирск, 2007.
- И.В. Латкин Дискретная математика с элементами математической логики. Усть-Каменогорск: ВКГТУ, 2016
- Ф.А. Новиков Дискретная математика для программистов.–СПб: Питер, 2011.
- М.О. Асанов, В.А. Баранский, В.В. Расин Дискретная математика: графы, матроиды, алгоритмы. – Москва, Ижевск: НИЦ «Регулярная и хаотическая динамика», 2011.
- В.А. Емеличев и др. Лекции по теории графов.– М.: Наука. 2012.
Further reading
- Л.Ю. Березина Графы и их применение. М.: Просвещение, 1979
- С.Г. Горбатов Основы дискретной математики. М.: Высшая школа, 1977г.
- Г.П. Гаврилов, А.А. Сапоженко Задачи и упражнения по курсу дискретной математики.– М.: Наука, 1992
- С.Г. Горбатов Фундаментальные основы дискретной математики.– М.: Наука, 2000
- И.В. Латкин Дискретная математика. – Методические указания и задания по выполнению контрольных работ заочной формы обучения. Усть-Каменогорск, ВКТУ, 2003
- И.В. Латкин Конспект лекций по дискретной математике. – Усть-Каменогорск: ВКГТУ, 2010.
