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

2021/2022

Учебный год

RUS

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

7

Кредиты

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Кто читает:

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

Статус:

Курс обязательный

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

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

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

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

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

Подольский Владимир Владимирович

Таламбуца Алексей Леонидович

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

Аннотация

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

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

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

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

• Владеть арифметикой остатков (вычетов). Уметь проверять элемент на обратимость, находить обратный элемент, решать линейные диофантовы уравнения от двух переменных с помощью алгоритма Евклида, знать базовые теоремы
• Владеть определениями и математическим аппаратом, связанным с функциями: образы, прообразы, инъекция, сюръекция, биекция
• Владеть определениями и математическим аппаратом, связанным с функциями: образы, прообразы, инъекция, сюръекция, биекция.
• Выработать базовую математическую культуру (культуру доказательств)
• Знать базовые комбинаторные числа: число перестановок, сочетаний, размещений, сочетаний с повторениями
• Знать базовые свойства бинарных отношений: рефлексивность, симметричность, транзитивность, антисимметричность, антирефлексивность, линейность; отношения эквивалентности, отношения частичного порядка
• Знать основные определения теории вероятности: вероятностное пространство, вероятностная модель, элементарный исход, событие, условная вероятность, случайная величина, математическое ожидание. Уметь решать задачи.
• Знать основы теории графов
• Знать основы теории множеств, владеть формулами алгебр множеств и логики
• Изучить доказательство нижних оценок для алгоритмов поиска максимума в массиве и сортировки.
• Уметь различать счётные множества и множества мощности континуум. Усилить куль Овладеть диагональным методом на примере теоремы Кантора.
• Уметь решать базовые комбинаторные задачи: пользоваться правилами суммы и произведения, формулой включений-исключений
• Уметь строить разложениями в ДНФ и КНФ, проверять на полноту базис. Уметь строить булевы схемы, реализующие арифметические операции, уметь использовать их при решении задач. Уметь оценивать асимптотический размер булевых схем.

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

• Множества и логика
• Комбинаторика
• Алгебра логики
• Математические определения, утверждения и доказательства
• Графы
• Основы теории чисел
• Двудольные графы, паросочетания и функции
• Ориентированные графы и отношения порядка.
• Бинарные отношения. Отношения эквивалентности.
• Булевы функции
• Вероятность
• Мощность множеств
• Разрешающие деревья и нижние оценки

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

• Домашнее задание 1
  В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. При выставлении итоговой и промежуточных оценок используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3, 5,48 – до 5, 5,54 – до 6, 7,12 – до 8.
• Домашнее задание 2
  В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. При выставлении итоговой и промежуточных оценок используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3, 5,48 – до 5, 5,54 – до 6, 7,12 – до 8.
• Домашнее задание 3
  В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. При выставлении итоговой и промежуточных оценок используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3, 5,48 – до 5, 5,54 – до 6, 7,12 – до 8.
• Коллоквиум 1
• Коллоквиум 2
• Промежуточный экзамен
  В письменной форме после второго модуля.
• Итоговый экзамен
  Для пилотного потока: Письменный экзамен. Студенты пишут на бумаге. В конце экзамена отправляют скан/фото работы. В течение экзамена за ними ведется наблюдение через zoom. Можно пользоваться распечатанными или заранее скачанными материалами. Во время экзамена преподаватель может попросить студента включить звук или поделиться экраном. Допускается два разрыва связи по пять минут. Если лимит превышен, вторая попытка через неделю, формат будет изменен на устный. Для основного потока: Экзамен проводится в форме теста на компьютере с применением проткоринга. Студенты получают задания в Moodle. Вариант с формами трёх типов: 1) вопросы с множественным выбором вариантов ответа (checkbox); 2) формы ввода текста; 3) форма для сканов/фото решений объёмных задач (одна). То есть в итоге студенты должны будут отправить не один файл с решениями, а форму.

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

• 2021/2022 учебный год 2 модуль
  0.15 * Домашнее задание 2 + 0.15 * Домашнее задание 1 + 0.4 * Коллоквиум 1 + 0.3 * Домашнее задание 3
• 2021/2022 учебный год 3 модуль
  0.3 * Итоговый экзамен + 0.083 * Домашнее задание 2 + 0.15 * Промежуточный экзамен + 0.15 * Коллоквиум 2 + 0.15 * Коллоквиум 1 + 0.083 * Домашнее задание 1 + 0.084 * Домашнее задание 3

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

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

• Lovász, L., Pelikán, J., & Vsztergombi, K. (2003). Discrete Mathematics : Elementary and Beyond. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=108108
• Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., доп. — Москва : МЦНМО, [б. г.]. — Часть 2 : Языки и исчисления — 2008. — 288 с. — ISBN 978-5-94057-322-7. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9307 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
• Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., стер. — Москва : МЦНМО, [б. г.]. — Часть 1 : Начала теории множеств — 2008. — 128 с. — ISBN 978-5-94057-321-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9306 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

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

• Дискретная математика. Углубленный курс: Учебник / Соболева Т.С.; Под ред. Чечкина А.В. - М.:КУРС, НИЦ ИНФРА-М, 2017. - 278 с.: - (Бакалавриат) - Режим доступа: http://znanium.com/catalog/product/851215

Авторы

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