Delivered at:: Big Data and Information Retrieval School

Course type:: Compulsory course

When:: 1 year, 1-3 module

Instructors

Vyalyi, Michael

Dobrokhotova-Maykova, Natalia

Lukianenko, Nikita

Maksaev, Artem

Fomenko, Maria

Khuzieva, Alina

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

Аннотация

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

Bachelor’s Programme 'Applied Mathematics and Information Science'

Discrete Mathematics

Instructors

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

Аннотация

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

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

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

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

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

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

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

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