Дискретная математика

Бакалавриат 2021/2022

Статус: Курс обязательный (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

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

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 1-3 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Вялый Михаил Николаевич, Доброхотова-Майкова Наталья Сергеевна, Лукьяненко Никита Сергеевич, Максаев Артем Максимович, Фоменко Мария Михайловна, Хузиева Алина Эдуардовна

Язык: русский

Кредиты: 7

Контактные часы: 104

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

Дискретная математика-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
В измененных в 2021 г. правилах оценивания не используется. Остается из-за невозможности удалить элемент контроля из списка.
Коллоквиум 1
Коллоквиум 2
Промежуточный экзамен
В письменной форме после второго модуля. Предполагается очная форма сдачи экзамена. При невозможности проведения очного экзамена проводится дистанционный экзамен по правилам, которые дополнительно сообщаются студентам.
Итоговый экзамен
В письменной форме после третьего модуля. Предполагается очная форма сдачи экзамена. При невозможности проведения очного экзамена проводится дистанционный экзамен по правилам, которые дополнительно сообщаются студентам.

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

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

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

Авторы

Подольский Владимир Владимирович
Вялый Михаил Николаевич

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