Дискретная математика, осень 2014
Курс: Дискретная математика.
Преподаватель: Павел Федотов.
Даты: Sep 2014 — Dec 2014.
Программа курса:
- Основы математической логики и теории множеств.
- Неопределяемые понятия в математике, аксиомы и утверждения.
- Логические операции. Таблица истинности.
- Множества. Операции над множествами.
- Декартово произведение. Бинарное отношение. Свойства отношений.
- Бонус: доказательства от противного.
- Комбинаторика.
- Мощность множеств. Дискретность.
- Число подмножеств, перестановок, сочетаний.
- Формула включений-исключений.
- Рекуррентные соотношения. Числа Фибоначчи (число способов подняться по лестнице).
- Бонус: Метод математической индукции.
- Теория вероятности.
- Вероятностное пространство, элементарный исход, событие.
- Независимые события.
- Условная вероятность.
- Формула Байеса.
- Формула полной вероятности.
- Бонус: Случайная величина.
- Алгоритм.
- Основные алгоритмические конструкции. Следование, ветвление, повторение.
- Алгоритмы без массивов.
- Анализ алгоритмов. Сложность по времени и по памяти.
- "O-большое" нотация.
- Алгоритмы с массивами.
- Поиск элемента в массиве.
- Счетчик числа элементов.
- Число различных элементов в неубывающем массиве.
- Слияние массивов.
- Перестановка элементов в обратном порядке.
- Поиск и сортировка.
- Поиск минимума в массиве.
- Квадратичные сортировки.
- Сортировка слиянием.
- Двоичный поиск.
- Промежуточный тест.
- Структуры данных.
- Очередь, стек, список, динамически расширяющийся массив, хеш.
- Динамическое программирование.
- Динамическое программирование – 2.
- Строки.
- Поиск подстроки в строке: наивный алгоритм, алгоритм Рабина-Карпа.
- Редакционное расстояние.
- Фильтр Блума.
- Граф, дерево.
- Основные понятия и способы представления.
- Алгоритмы на графах.
- Обходы в глубину и ширину.
- Кратчайшие пути.
Зачетная оценка по курсу будет выставляться на основе выполненных домашних заданий, промежуточных тестов и лабораторных работ в течение семестра.