Дискретная математика, осень 2014

Курс: Дискретная математика.

Преподаватель: Павел Федотов.

Даты: Sep 2014 — Dec 2014.


Программа курса:

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

Зачетная оценка по курсу будет выставляться на основе выполненных домашних заданий, промежуточных тестов и лабораторных работ в течение семестра.