Дискретная математикаSyllabus

Subject code

İF-61433y-RU

Credits

5

Student workload

90

Semester

Autumn semester

Academic year

2

Subject type

Mandatory

Form of education

Full-time

Language of instruction

Russian

In-class hours

a) 30 часов — лекции b) 30 часов — семинары

Out-of-class hours

a) 89 часов — самостоятельная работа b) 1 час — проектная работа или консультационные часы

Дисциплина «дискретная математика» изучает математические структуры и методы, используемые для решения задач информатики, программирования и информационных технологий. в рамках курса рассматриваются теория множеств, математическая логика, отношения и функции, комбинаторика, теория графов, деревья, булева алгебра, элементы теории чисел и основы дискретных вероятностных моделей. особое внимание уделяется применению математических методов для анализа алгоритмов, моделирования информационных систем, решения задач программирования и построения логических схем. дисциплина способствует развитию логического, алгоритмического и аналитического мышления, необходимого для изучения компьютерных наук и кибербезопасности.

• lecture
• seminar
• interactive discussion
• presentations

1. 1

   CLO 1: Изучить основные понятия комбинаторики, декартова произведения множеств и булева множества, научиться решать практические задачи.

2. 2

   CLO 2: Освоить понятия бинарного отношения, отношения эквивалентности и их свойств.

3. 3

   CLO 3: Изучить основные логические операции, научиться строить таблицы истинности и применять логические операции

4. 4

   CLO 4: Научиться представлять булевы функции в виде сднф и скнф, а также выполнять разложение по переменным

5. 5

   CLO 5: Изучить основные понятия теории кодирования.

6. 6

   CLO 6: Изучить основные понятия теории графов, научиться находить эйлеров цикл и применять алгоритм дейкстры для поиска кратчайшего пути.

1. 1.
   Элементы комбинаторики. декартово произведение. булевы множества.Lecture

   Рассматриваются основные понятия и методы комбинаторики, правила суммы и произведения, элементы подсчёта комбинаций. изучаются декартово произведение множеств, булевы множества и основные операции над ними.

2. 2.
   Отношение. бинарное отношение. отношение эквивалентности.Lecture

   Изучаются понятия отношения и бинарного отношения между множествами. рассматриваются свойства бинарных отношений, отношения эквивалентности, классы эквивалентности и их основные характеристики.

3. 3.
   Функции. композиция функций. мощность множества.Lecture

   Рассматриваются понятие функции, способы её задания и основные свойства. изучается композиция функций, взаимно однозначные соответствия и понятие мощности конечных и бесконечных множеств.

4. 4.
   Основные логические операции и их применения.Lecture

   Изучаются основные логические операции, логические выражения и таблицы истинности. рассматривается применение логических операций при построении и анализе сложных высказываний и логических функций.

5. 5.
   Понятие формулы. двойственная функция. принцип двойственности.Lecture

   Рассматривается понятие формулы в алгебре логики и способы её представления. изучаются двойственные булевы функции, операции двойственности и принцип двойственности, а также их применение при преобразовании логических выражений.

6. 6.
   Разложение булевых функций по переменным. совершенные дизъюнктивные и конъюнктивные нормальные формы (сднф, скнф). многочлен жегалкина.Lecture

   Изучаются методы разложения булевых функций по переменным и представления функций в нормальных формах. рассматриваются совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы, а также представление булевых функций в виде многочлена жегалкина.

7. 7.
   Теория групп. понятие кольца и поля.Lecture

   Рассматриваются основные алгебраические структуры и понятие группы, её элементы, операции и свойства. изучаются кольца и поля, их основные характеристики и взаимосвязь с дискретной математикой и теорией чисел.

8. 8.
   Вычисления по модулю. класс вычетов ℤm.Lecture

   Изучаются арифметические операции по модулю и основные свойства сравнений. рассматривается кольцо классов вычетов \(\mathbb{z}_m\), операции над классами вычетов и их применение в задачах теории чисел и криптографии.

9. 9.
   Некоторые числовые функции.Lecture

   Рассматриваются основные числовые функции и их свойства. изучаются функции эйлера, мёбиуса и другие арифметические функции, их определения, основные свойства и способы вычисления. рассматривается применение числовых функций при решении задач теории чисел и дискретной математики.

10. 10.
    Конечные циклические группы. примитивные элементы. задача дискретного логарифмирования.Lecture

    Изучаются конечные циклические группы, их структура и свойства. рассматриваются примитивные элементы и порядок элементов группы, а также задача дискретного логарифмирования и её значение в современной криптографии.

11. 11.
    Конечное поле. простое конечное поле. расширенные конечные поляLecture

    Рассматривается понятие конечного поля и его основные свойства. изучаются простые конечные поля, расширения полей, операции над элементами конечных полей и их применение в криптографических алгоритмах.

12. 12.
    Построение конечных полей.Lecture

    Рассматриваются основные принципы построения конечных полей и их алгебраические свойства. изучаются простые конечные поля, расширения конечных полей, операции над их элементами и методы представления элементов конечных полей.

13. 13.
    Примитивные многочлены.Lecture

    Рассматривается понятие примитивного многочлена и его основные свойства. изучаются примитивные многочлены над конечными полями, условия их существования и методы определения. рассматривается использование примитивных многочленов при построении расширений конечных полей и выполнении операций над их элементами.

14. 14.
    Элементы теории графов. алгоритм дейкстрыLecture

    Рассматриваются основные понятия теории графов: графы, вершины, рёбра, степени вершин, пути, циклы и связность. изучаются ориентированные и неориентированные, взвешенные графы. рассматривается алгоритм дейкстры для нахождения кратчайших путей во взвешенном графе и его применение при решении задач теории графов.

15. 15.
    Итоговое оценивание по дисциплинеLecture

    Проводится итоговая проверка знаний и практических навыков студентов по основным разделам дисциплины. оценивается степень освоения теоретических понятий, методов и алгоритмов, изученных в течение семестра, а также способность применять полученные знания при решении практических задач.

1. Новиков ф.а. – "дискретная математика для программистов"
2. Яблонский с.в. – "введение в дискретную математику"
3. Романовский и.в. – "дискретный анализ"
4. Алексеев в.е., таланов в.а. – "графы и алгоритмы"