We use cookies in order to improve the quality and usability of the HSE website. More information about the use of cookies is available here, and the regulations on processing personal data can be found here. By continuing to use the site, you hereby confirm that you have been informed of the use of cookies by the HSE website and agree with our rules for processing personal data. You may disable cookies in your browser settings.

  • A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Discrete Mathematics (Advanced Course)

2024/2025
Academic Year
RUS
Instruction in Russian
6
ECTS credits
Course type:
Elective course
When:
1 year, 1-3 module

Instructors


Maksaev, Artem


Promyslov, Valentin

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

Аннотация

Дискретная математика-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

Авторы

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