Delivered at:: Big Data and Information Retrieval School

Course type:: Compulsory course

When:: 1 year, 1-3 module

Instructors

Валинкин Михаил Валерьевич

Оноприенко Анастасия Александровна

Khuzieva, Alina

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

Аннотация

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

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

Знать основы теории множеств, владеть формулами алгебр множеств и логики.
Уметь различать счётные множества и множества мощности континуум. Овладеть диагональным методом на примере теоремы Кантора.
Знать базовые свойства бинарных отношений: рефлексивность, симметричность, транзитивность, антисимметричность, антирефлексивность, линейность; отношения эквивалентности, отношения частичного порядка.
Знать основы элементарной теории вероятностей: вероятностное пространство, условные вероятности, формула Байеса, математическое ожидание.
Знать основы теории чисел: арифметика остатков, НОД и НОК, алгоритм Евклида, основная теорема арифметики.

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

Владеть определениями и математическим аппаратом, связанным с функциями: образы, прообразы, инъекция, сюръекция, биекция.
Ознакомиться с базовыми математическими понятиями.
Выработать математическую культуру (культуру доказательств).
Знать базовые комбинаторные числа: число перестановок, сочетаний, размещений, сочетаний с повторениями.
Уметь решать базовые комбинаторные задачи: пользоваться правилами суммы и произведения, формулой включений-исключений.
Знать основы теории графов.

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

Способы доказательств, булевы связки, высказывания, тавтологии. Множества, операции, связь с булевыми связками.
Натуральные числа и конечные множества.
Формальное определение функций.
Подсчеты слов и функций.
Монотонные пути.
Мультиномиальные коэффициенты. Сочетания с повторениями.
Формула включений и исключений. Симметрия в подсчетах: примеры.
Сравнение бесконечных множеств. Обратная функция. Счетные множества.
Мощность континуум. Примеры. Доказательство несчетности. Теорема Кантора--Бернштейна.
Бинарные отношения, простые неориентированные графы. Отношения эквивалентности. Связность. Компоненты связности.
Деревья. Остовные деревья. Деревья поиска в глубину.
Клики и независимые. Теорема Рамсея. Нижняя оценка чисел Рамсея.
Раскраски, критерий 2-раскрашиваемости. Раскраски во много цветов. Двудольные графы. Паросочетания.
Теорема Холла. Вершинные покрытия. Теорема Кёнига.
Ориентированные графы. Сильная связность, компоненты сильной связности. Ациклические графы.
Порядки, основные определения и свойства. Изоморфизм порядков.
Теорема Дилуорса. Цепи и антицепи в бесконечных порядках. Фундированные множества, индукция по фундированному множеству.
Элементарная теория вероятностей.
Условные вероятности. Формула полной вероятности, формула Байеса. Парадокс Симпсона.
Случайная величина, математическое ожидание случайной величины. Лемма о среднем (математическое ожидание не больше максимума и не меньше минимума). Неравенство Маркова.
Деление с остатком. Арифметика остатков, вычеты, свойства арифметики остатков. Признаки делимости.
Наибольший общий делитель. Алгоритм Евклида. Линейные диофантовы уравнения. Основная теорема арифметики.
Малая теорема Ферма. Функция Эйлера, теорема Эйлера. Китайская теорема об остатках. Оценки количества простых чисел.
Разрешающие деревья. Основные определения и примеры. Мощностные нижние оценки.

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

Домашнее задание 1
Домашнее задание 2
Коллоквиум 1
Коллоквиум 2
Промежуточный экзамен
Предполагается очная форма сдачи экзамена. При невозможности проведения очного экзамена проводится дистанционный экзамен (при условии согласования с учебным офисом) по правилам, которые дополнительно сообщаются студентам. Экзамен проводится в письменной форме после второго модуля. Письменный экзамен служит для проверки умения творчески использовать полученные знания при решении новых для студента задач. Задания в промежуточном письменном экзамене возможны по всем темам, которые изучались в первых двух модулях.
Итоговый экзамен
Проводится после третьего модуля. Правила проведения полностью аналогичны правилам промежуточного экзамена, только задачи возможны по всем темам курса.

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

2023/2024 2nd module
0.299 * Домашнее задание 1 + 0.299 * Коллоквиум 1 + 0.402 * Промежуточный экзамен
2023/2024 3rd module
Оценка 3 модуля = 0.2*Оценка 2 модуля + 0.2*Домашнее задание 2 + 0.2*Коллоквиум 2 + 0.4*Итоговый экзамен

Bachelor’s Programme 'Economics and Data Science'

Address

Discrete Mathematics

Instructors

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

Аннотация

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

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

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

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

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

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

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

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