Содержание пакета (5 курсов)
1. Доказательства 4.67
О курсе
1 урок
1.
Добро пожаловать!
↗
Доказательства существования и оптимальности
7 уроков
1.
Конструктивные доказательства существования
↗
2.
Трудные и открытые задачи в теории чисел (опционально)
↗
3.
Доказательства несуществования
↗
4.
Неконструктивные доказательства существования
↗
5.
Больше неконструктивных доказательств (опционально)
↗
6.
Доказательства оптимальности
↗
7.
Применение: коды, исправляющие ошибки (опционально)
↗
Доказательства универсальных утверждений: индукция
6 уроков
1.
Метод математической индукции
↗
2.
База индукции
↗
3.
Полная индукция
↗
4.
Метод минимального контрпримера
↗
5.
Усиление утверждения
↗
6.
Вложенные утверждения (опционально)
↗
Доказательства корректности алгоритмов и оценок на время работы
5 уроков
1.
Многочлен, экспонента и логарифм
↗
2.
Скорость роста функций
↗
3.
Инварианты и алгоритмы
↗
4.
Отгадывание числа
↗
5.
Приложение: сжатие данных (опционально)
↗
Доказательства в компьютерных науках (опционально)
6 уроков
1.
Сертификаты
↗
2.
Теория вычислимости
↗
3.
Теория сложности вычислений
↗
4.
Интерактивные доказательства
↗
5.
Доказательства с нулевым разглашением
↗
6.
Вероятностно проверяемые доказательства
↗
2. Комбинаторика 5.00
О курсе
1 урок
1.
Добро пожаловать!
↗
Размещения и сочетания
11 уроков
1.
Размещения и сочетания
↗
2.
Базовые правила
↗
3.
Размещения
↗
4.
Сочетания
↗
5.
Сочетания с повторениями
↗
6.
Тождества
↗
7.
Оценки биномиальных коэффициентов (опционально)
↗
8.
Размещения с повторениями
↗
9.
Числа Каталана: введение
↗
10.
Числа Каталана: доказательство формулы
↗
11.
Числа Каталана: разные проявления
↗
Генерация комбинаторных объектов
9 уроков
1.
Генерация подмножеств
↗
2.
Коды Грэя
↗
3.
Генерация перестановок
↗
4.
Скобочные последовательности
↗
5.
Перебор с возвратом
↗
6.
Метод ветвей и границ
↗
7.
Применение: Динамическое программирование (опционально)
↗
8.
ILP-солверы (опционально)
↗
9.
Номера объектов (опционально)
↗
Рекуррентные соотношения
6 уроков
1.
Комбинаторика разбиений
↗
2.
Рекуррентные определения
↗
3.
Рекурсивные алгоритмы
↗
4.
Финансовые вычисления
↗
5.
Применение: Метод <<разделяй и властвуй>>
↗
6.
Линейные рекуррентные соотношения
↗
Производящие функции
6 уроков
1.
Производящие функции
↗
2.
Операции с производящими функциями
↗
3.
Ряд Маклорена
↗
4.
Дробно-рациональные функции
↗
5.
Линейные рекуррентные соотношения
↗
6.
Числа Каталана
↗
3. Логика и теория множеств 5.00
О курсе
1 урок
1.
Добро пожаловать!
↗
Пропозициональная логика
5 уроков
1.
Предикаты
↗
2.
Нормальные формы
↗
3.
Тавтологии
↗
4.
Кванторы
↗
5.
Критерий Поста
↗
Задача выполнимости
6 уроков
1.
Формулировка задачи
↗
2.
SAT-солверы
↗
3.
Полиномиально разрешимые частные случаи
↗
4.
Алгоритмы для задачи выполнимости (опционально)
↗
5.
Формальная верификация и системы доказательств
↗
6.
Применение: условные нижние оценки на вычислительную сложность
↗
Булевы схемы
4 урока
1.
Прямолинейные программы и булевы схемы
↗
2.
Синтез булевых схем
↗
3.
Максимальная сложность
↗
4.
Нижние оценки
↗
Теория множеств
8 уроков
1.
Введение
↗
2.
Равномощность
↗
3.
Счётные множества
↗
4.
Диагональный аргумент Кантора
↗
5.
Сравнение мощностей
↗
6.
Аксиоматический метод (необязательно)
↗
7.
Применение: неразрешимость задачи остановки
↗
8.
Первая теорема Гёделя о неполноте (необязательно)
↗
Частично упорядоченные множества
5 уроков
1.
Частичные порядки
↗
2.
Диаграммы Хассе
↗
3.
Операции над частично упорядоченными множествами
↗
4.
Порядки и индукция
↗
5.
Теорема Дилуорса
↗
4. Теория вероятностей 5.00
О курсе
1 урок
1.
Добро пожаловать!
↗
События и вероятностные пространства
5 уроков
1.
События и вероятностные пространства
↗
2.
Дерево процесса
↗
3.
Парадокс дней рождения
↗
4.
Вероятность объединения
↗
5.
Рекуррентное вычисление вероятностей (опционально)
↗
Условная вероятность
6 уроков
1.
Пропорции
↗
2.
Условная вероятность
↗
3.
Независимые события
↗
4.
Формула Байеса
↗
5.
Странная игра
↗
6.
Локальная лемма (опционально)
↗
Случайные величины
7 уроков
1.
Случайные величины
↗
2.
Распределения
↗
3.
Математическое ожидание
↗
4.
Геометрическое распределение
↗
5.
Распределение Пуассона
↗
6.
Линейность математического ожидания
↗
7.
Условное математическое ожидание (опционально)
↗
Уклонения
7 уроков
1.
Неравенство Маркова
↗
2.
Дисперсия
↗
3.
Неравенство Чебышёва
↗
4.
Закон больших чисел
↗
5.
Центральная предельная теорема (опционально)
↗
6.
Выборочный метод
↗
7.
Неравенство Чернова (опционально)
↗
Вероятностный метод (опционально)
5 уроков
1.
Парадокс турнира
↗
2.
Числа Рамсея
↗
3.
Свободные от сумм множества
↗
4.
Задача максимальной выполнимости
↗
5.
Коды
↗
5. Теория графов 5.00
О курсе
1 урок
1.
Добро пожаловать!
↗
Что такое граф?
5 уроков
1.
Графы
↗
2.
Определения
↗
3.
Базовые графы
↗
4.
Формула суммы степеней
↗
5.
Компоненты связности
↗
Деревья
5 уроков
1.
Введение
↗
2.
Минимальное остовное дерево
↗
3.
Динамическое программирование
↗
4.
Формула Кэли
↗
5.
Матричная теорема о деревьях (опционально)
↗
Циклы
6 уроков
1.
Ациклические графы
↗
2.
Компоненты сильной связности
↗
3.
Эйлеровы графы
↗
4.
Гамильтоновы графы
↗
5.
Задача коммивояжёра
↗
6.
Применение: Сборка генома
↗
Потоки и связность
7 уроков
1.
Связность
↗
2.
Потоки
↗
3.
Теорема Форда--Фалкерсона
↗
4.
Теорема Менгера
↗
5.
Паросочетания в двудольных графах
↗
6.
Применение: Выбор проектов
↗
7.
Применение: Сегментация изображений
↗
Паросочетания
5 уроков
1.
Независимые множества и покрытия: определения и соотношения
↗
2.
Независимые множества
↗
3.
Двудольные графы
↗
4.
Вершинное покрытие
↗
5.
Применение: Устойчивое паросочетание
↗
Раскраски
6 уроков
1.
Введение
↗
2.
Раскраски и степень
↗
3.
Раскраски и клики
↗
4.
Нелокальность хроматического числа (опционально)
↗
5.
Хроматический многочлен
↗
6.
Применение: Алгоритмы нахождения раскраски (опционально)
↗
Планарные графы
7 уроков
1.
Планарные графы
↗
2.
Формула Эйлера
↗
3.
Непланарные графы
↗
4.
Число пересечений
↗
5.
Раскраска планарных графов
↗
6.
Теоремы Куратовского и Вагнера
↗
7.
Специальные укладки
↗