Delivered at:: Big Data and Information Retrieval School

Course type:: Elective course

When:: 1 year, 1-3 module

Instructors

Ignatev, Mikhail

Lukianenko, Nikita

Maksaev, Artem

Promyslov, Valentin

Sokolov, Pavel

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
Экзамен проводится в сессию после 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

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

Авторы

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

Bachelor’s Programme 'Applied Mathematics and Information Science'

Discrete Mathematics

Instructors

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