Дискретная математика (углубленный курс)

2023/2024

Учебный год

RUS

Обучение ведется на русском языке

6

Кредиты

Кто читает:

Департамент больших данных и информационного поиска

Статус:

Курс по выбору

Когда читается:

1-й курс, 1-3 модуль

Преподаватели

Игнатьев Михаил Викторович

Лукьяненко Никита Сергеевич

Максаев Артем Максимович

Промыслов Валентин Валерьевич

Соколов Павел Павлович

Стасенко Роман Олегович

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

Аннотация

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

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

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

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

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

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

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

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

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

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

• 2023/2024 учебный год 2 модуль
  0.25 * Домашние задания + 0.25 * Коллоквиум-1 + 0.15 * Контрольная работа + 0.05 * Лабораторная работа-1 + 0.3 * Экзамен-1
• 2023/2024 учебный год 3 модуль
  0.25 * Домашние задания + 0.1 * Коллоквиум-1 + 0.2 * Коллоквиум-2 + 0.05 * Лабораторная работа-2 + 0.15 * Экзамен-1 + 0.25 * Экзамен-2

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

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

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

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

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

Авторы

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