Дискретная математика

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

1. Математические обозначения и математический язык

• Утверждения
• Логические операторы
• Следствия
• Кванторы

2. Доказательства

• Доказательство от противного
• Доказательство утверждений с условиями
• Доказательство утверждений с кванторами
• Доказательство по индукции

3. Элементы теории множеств и комбинаторика

• Множества
• Число подмножеств, перестановок, сочетаний
• Формула включений-исключений
• Комбинаторика и вычислительная биология

4. Теория вероятности

• Алгебра событий
• Вероятность
• Независимость
• Теорема Байеса
• Случайная величина

5. Алгоритмы

• Поиск подстроки в строке
• Анализ алгоритмов
• O-нотация

6. Простейшие алгоритмы на массивах

• Сумма и среднее массива
• Поиск элемента в массиве
• Разворот массива
• Слияние массивов

7. Поиск и сортировки

• Поиск элемента в отсортированном массиве
• Квадратичные сортировки
• Сортировка слиянием

8. Структуры данных

• Очередь
• Стек
• Список
• Динамически расширяющийся массив
• Хэш таблица

9. Структуры данных-2

• Дерево поиска
• Бор
• Куча
• Фильтр Блума

10. Динамическое программирование

• Задача о размене купюры
• Выравнивания

11. Теория графов

• Граф
• Дерево
• Пути и циклы

12. Алгоритмы на графах

• Поиск в ширину/глубину
• Поиск кратчайшего пути
• Выделение компонент связности

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

Итоговая аттестация: оценка

Материалы