Discrete Mathematics (Advanced Course)

2024/2025

Academic Year

RUS

Instruction in Russian

6

ECTS credits

Delivered at:

Big Data and Information Retrieval School

Course type:

Elective course

When:

1 year, 1-3 module

Instructors

Beldiev, Ivan

Ignatev, Mikhail

Maksaev, Artem

Promyslov, Valentin

Stasenko, Roman

Программа дисциплины

Аннотация

Дискретная математика-1 — базовый вводный курс, прививающий студентам азы математической культуры, нужные для последующего изучения как математических дисциплин, так и компьютерных наук. Курс знакомит с такими фудндаментальными понятиями как множества, алгебра логики, функции и отображения, булевы функции, отношения и графы. Они являются фундаментом как для изучения математики и для структур данных в программировании. Разделы введение в теорию чисел и мощность множеств готовит студентов к изучению алгебры и последующему изучению вычислимых функций в рамках курса дискретная математика-2.

Цель освоения дисциплины

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

Планируемые результаты обучения

• Знакомство с базовыми математическими понятиями.

Содержание учебной дисциплины

• Математическая индукция
• Множества и функции
• Комбинаторика
• Булевы функции и логика
• Полные системы связок, отношения
• Критерий Поста
• Счетные множества
• Мощности множеств, континуальные множества
• Частично упорядоченные множества
• Цепи и антицепи: теоремы Дилуорса и Шпернера
• Графы: основные понятия
• Ориентированные графы. Сильная связность, эйлеровы пути и циклы, топологическая сортировка
• Двудольные графы, паросочетания и вершинные покрытия, теорема Кёнига
• Теорема Холла, теорема Рамсея
• Раскраски графов, хроматическое число графа
• Вероятностное пространство, свойства вероятности
• Условная вероятность
• Математическое ожидание, вероятностный метод
• Оценки для биномиальных коэффициентов. Неравенство Чернова
• Производящие функции
• Линейные рекурентные соотношения с постоянными коэффициентами. Числа Каталана
• Комбинаторные игры с полной информацией. Теорема о цене игры
• Разрешающие деревья
• Булевы схемы
• Задачи выполнимости булевой схемы, КНФ и 3-КНФ
• Коды с исправлением ошибок

Элементы контроля

• Домашние задания
  Выдается после каждого семинара (кроме двух-трех последних семинаров курса) и содержит 5-9 задач по теме семинара.
• Контрольная работа
  Проводится в начале 2-го модуля и содержит 5-6 задач по темам лекций и семинаров 1-го модуля. Пользоваться можно лишь ручкой и стандартным калькулятором
• Коллоквиум-1
  Проводится в конце 2-го модуля. Студент получает билет с теоретическими вопросами и задачами по всем темам 1-2 модулей и отвечает его устно. Пользоваться можно лишь ручкой и стандартным калькулятором.
• Лабораторная работа-1
  Проводится во 2-м модуле. Состоит из нескольких практических задач по темам курса, в которых нужно написать код. На выполнение задач дается около двух недель.
• Экзамен-1
  Экзамен проводится в сессию после 2 модуля письменной форме в аудитории. Во время подготовки можно использовать любые печатные материалы, но запрещается использовать электронные средства коммуникации.
• Коллоквиум-2
  Проводится в конце 3-го модуля. Студент получает билет с теоретическими вопросами и задачами по всем темам 1-3 модулей и отвечает его устно. Пользоваться можно лишь ручкой и стандартным калькулятором
• Лабораторная работа-2
  Проводится в 3-м модуле. Состоит из нескольких практических задач по темам курса, в которых нужно написать код. На выполнение задач дается около двух недель
• Экзамен-2

Промежуточная аттестация

• 2024/2025 2nd module
  0.25 * Домашние задания + 0.25 * Коллоквиум-1 + 0.15 * Контрольная работа + 0.05 * Лабораторная работа-1 + 0.3 * Экзамен-1
• 2024/2025 3rd module
  0.25*ДЗ+0.1*Колл1+0.15*Экз1+0.2*Колл2+0.05*Лр2+0.25*Э2, где ДЗ -Домашние задания, Колл1 - Коллоквиум-1, Экз1 - Экзамен-1, Колл2 - Коллоквиум-2, Лр2 - Лабораторная работа-2, Э2 - Экзамен-2

Список литературы

Рекомендуемая основная литература

• Введение в дискретную математику : учеб. пособие для вузов, Яблонский, С. В., 2008

Рекомендуемая дополнительная литература

• Заметки по теории кодирования, Ромащенко, А. Е., 2017
• Лекции о производящих функциях, Ландо, С. К., 2007

Авторы

• Подольский Владимир Владимирович
• Сысоева Алевтина Александровна
• Рубцов Александр Александрович
• Максаев Артем Максимович