Delivered at:: Big Data and Information Retrieval School

Course type:: Compulsory course

When:: 1 year, 1-3 module

Instructors

Raiko, Ilia

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

Аннотация

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

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

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

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

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

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

Множества и логика
Множества и операции над ними. Связь алгебры логики и алгебры множеств: предикаты, юнивёрсум и дополнение, законы де Моргана, кванторы, эквивалентность тождеств алгебры множеств и алгебры логики, импликация и включение множеств.
Комбинаторика
Правила суммы и произведения. Отображения и подсчёты. Правило суммы. Правило произведения — биекция с декартовым произведением множеств. Число двоичных слов длины n. Число подмножеств n-элементного множества. Размещения. Перестановки. Подсчёт количества слов длины k с разными буквами. Подсчёты с кратностью: сколько различных слов можно составить из слова «Математика»? Число сочетаний. Количество k-элементных подмножеств n-элементного множества. Дискретная вероятность. Биномиальные коэффициенты. Количество путей по узлам клеток (вправо и вверх) из (0,0) в (i,j) есть (i+ji). Треугольник Паскаля и его свойства: симметрия, возрастание биномиальных коэффициентов к середине, оценка. Бином Ньютона и биномиальные коэффициенты. Рекуррентное соотношение. Сумма биномиальных коэффициентов и её комбинаторный смысл. Знакопеременная сумма биномиальных коэффициентов. Комбинаторные доказательства. Рекуррентное соотношение на биномиальные коэффициенты в треугольнике Паскаля. Задача о командире и солдатах: n×2n−1=∑k=1nk(nk). Формула ∑k=1n(nk)2=(2nn). Метод точек и перегородок. Число решений уравнения x1+x2+…+xk=n в неотрицательных целых числах есть (n+k−1k−1) (Формула Муавра). Число мономов степени d. Число сочетаний с повторениями. Числа Фибоначчи. Числа Каталана (доказательство явной формулы). Формула включений-исключений. Характеристические функции. Доказательство формула включений-исключений. Примеры: количество чисел от 1 до 1000 не делящихся ни на 3, ни на 5, ни на 7; связь со знакопеременной суммой биномиальных коэффициентов; подсчёт сюръекций. Подсчёт числа отображений (всюду определённых функций), функций, инъекций, биекций из n-элементного множества в n-элементное множество Множества и функции. Смысл обозначений 2A для множества всех подмножеств и YX для множества отображений из X в Y. Принцип Дирихле: при m>n нет инъекции из {1,…,m} в {1,…,n}.
Математические определения, утверждения и доказательства
Определение, утверждение, теорема, критерий. Запись утверждений в кванторах (формулы первого порядка). Логический вывод, Modus Ponnens. Методы доказательств: контрапозиция, индукция, от противного, конструктивные (примеры и контрпримеры), неконструктивные.
Алгебра логики
Высказывания и логические связки. Булевы функции и способы их задания: таблицы истинности, формулы, вектор значений. Законы коммутативности, ассоциативности и дистрибутивности, приоритет операций. Законы поглощения. Равенство булевых функций (и булевых формул). Существенные и фиктивные переменные.
Графы
Неориентированные графы. Определение неориентированных графов Степень вершины. Сумма степеней вершин~"--- удвоенное количество рёбер. Число людей, сделавших нечётное число рукопожатий, чётно. Теоретико множественные операции с графами. Определение подграфа Определение путей и циклов (через подграфы). Связные графы и компоненты связности (через подграфы). Деревья. Связность. Теорема «\#компонент связности ≥|V|−|E|». Маршруты и замкнутые маршруты. Между двумя вершинами графа есть путь, если между ними есть маршрут. Деревья. Теорема об эквивалентности четырёх свойств. Расстояние между вершинами, диаметр графа. Диаметр любого связного графа не превосходит |V|−1. Двураскрашиваемый граф. Граф двураскрашиваемый тогда и только тогда, когда нет циклов нечётной длины.
Основы теории чисел
Арифметика остатков, вычеты, обратимые элементы. Основная теорема арифметики. Алгоритм Евклида для решения линейных диофантовых уравнений с двумя неизвестными, поиск обратных элементов. Малая теорема Ферма. Китайская теорема об остатках. Функция Эйлера, теорема Эйлера.
Двудольные графы, паросочетания и функции
Двудольные графы и паросочетание. Теорема Холла (без доказательства). Функции (область определения, множество значений, образ, полный прообраз). Отображения (всюду определённые функции): инъекции, сюръекции, биекции. Отображения и задача о назначениях. Изоморфизм графов. Доказательство теоремы Холла*.
Ориентированные графы и отношения порядка.
Определение ориентированного графа. Исходящие и входящие степени — аналог формулы суммы степененй для неориентированного графа. Компоненты сильной связности. Т.: Следующие условия для ориентированного графа равносильны: — Каждая компонента сильной связности тривиальна (состоит из одной вершины). — Граф ациклический. — Вершины графа можно занумеровать так, что рёбра идут только от вершин с меньшим номером к вершинам с большим номером. Примеры отношений (частичного) порядка, формальное определение. Линейный порядок. Отношение непосредственного следования и его граф (диаграмма Хассе). Покоординатный порядок. Булев куб — двоичные слова, упорядоченные покоординатно.
Бинарные отношения. Отношения эквивалентности.
Формальное определение отношений и их свойств: рефлексивность, транзитивность, симметричность, антисимметричность. Задание бинарного отношения таблицей, двудольным графом, перечислением пар. Примеры отношений эквивалентности: рациональные числа, равные и подобные треугольники, неопределённые интегралы. Формальное определение. Т.: Классы эквивалентности не пересекаются или совпадают. Теоретико-множественные операции с отношениями. Операция обращения. Описание с помощью булевых матриц. Композиция отношений (связь с базами данных).
Булевы функции
Алгоритм построения ДНФ (и КНФ) по таблице истинности Определение булевых схем, реализующих булевы функции, через последовательности присваиваний и графов (стандартный базис). Задание функции булевой схемой (последовательностью присваиваний) Формулы — схемы специального вида Общее определение схем (для произвольного базиса) Базис — полный базис Монотонные функции: неполнота монотонного базиса {∧,∨}, связь с множествами (монотонность по включению), раскраска булева куба, монотонных булевых функций от 2n переменных не меньше чем 2х((2 в степени 2n) /2n+1). Многочлены Жегалкина. Классы Поста: T0 — функции, сохраняющие ноль; T1— функции, сохраняющие единицу; M — монотонные функции; L — линейные функции; S — самодвойственные функции. Формулировка теоремы Поста. Булевы схемы: определение через последовательность присваиваний и графы. Построение схем для сложения и умножения чисел, проверки графа на связность.
Вероятность
Вероятностное пространство и вероятностная модель (для случая конечного множества элементарных исходов). Схема последовательного выбора. Условная вероятность, формула Байеса, формула полной вероятности. Случайная величина, математическое ожидание случайной величины, лемма о среднем (математическое ожидание не больше максимума и не меньше минимума). \textbf{Т.:} всякий граф имеет разрез не меньше |E|/2. Неравенство Маркова.
Мощность множеств
Счётные множества. Всякое подмножество счётного множества конечно или счётно. Замкнутость счётных множеств относительно конечного и счётного объединения, декартого произведения. Счётность множества рациональных чисел, несчётность множества действительных чисел. Континуальные множества. Равномощность отрезков, интервалов, лучей и множества действительных чисел. Отрезок [0,1] равномощен множеству действительных чисел. Теорема Кантора-Бернштейна.
Разрешающие деревья и нижние оценки
Задача об угадывании числа. Модель разрешающих деревьев. Поиск самой тяжёлой монеты. Нижняя оценка на число операций сортировки сравнениями. Метод противника.

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

Домашнее задание 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) форма для сканов/фото решений объёмных задач (одна). То есть в итоге студенты должны будут отправить не один файл с решениями, а форму.

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

Промежуточная аттестация (2 модуль)
0.15 * Домашнее задание 1 + 0.15 * Домашнее задание 2 + 0.3 * Коллоквиум 1 + 0.4 * Промежуточный экзамен
Промежуточная аттестация (3 модуль)
0.083 * Домашнее задание 1 + 0.083 * Домашнее задание 2 + 0.084 * Домашнее задание 3 + 0.3 * Итоговый экзамен + 0.15 * Коллоквиум 1 + 0.15 * Коллоквиум 2 + 0.15 * Промежуточный экзамен

Bachelor’s Programme 'Applied Mathematics and Information Science'

Discrete Mathematics

Instructors

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

Аннотация

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

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

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

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

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

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

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

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