Название курса |
Источник / Организация |
Возраст |
Длина курса
|
Ликбез по дискретной математике (простой обзорный)
|
Линейная алгебра
- Линейная алгебра: линейное пространство, системы линейных уравнений
- Линейная алгебра: евклидово пространство, ортогональный базис, линейные операторы
Комбинаторика
- Основные понятия теории множеств и комбинаторики
- Принцип Дирихле, число сочетаний
- Число перестановок
- Подсчет отображений конечных множеств
- Рекуррентные соотношения
Теория графов
- Графы, связность, деревья
- Эйлеровы графы, двудольные графы, раскраски графов
- Паросочетания. Теорема Холла
- Основные понятия дискретной вероятности.
- Условная вероятность
- Основные характеристики случайных величин
|
|
Stepik / CSC
|
Старшая школа и студенты
|
10 часов видео, 100 тестов
|
Введение в дискретную математику (обзорный для программистов)
|
Теория множеств и комбинаторика'
- Теория множеств
- Сочетания и перестановки
Дискретная вероятность
- Случайные величины
- Распределения дискретной случайной величины
Теория графов и основы линейной алгебры
- Графы, определения и свойства.
- Эйлеровы пути и циклы в графе
- Теория Рамсея
Теория сложности
- Напоминание о суммах, логарифмах и экспонентах
- Скорость роста функций и алгоритмов
- O-нотация
|
|
Stepik / Институт Биоинформатики
|
Старшая школа и студенты
|
4 часа видео, 50 тестов
|
Комбинаторика для начинающих
|
Правило сложения и умножения. Принцип Дирихле'
- Правила сложения и умножения.
- Задачи о перелёте Москва-Сидней, о походе в театр, о пароле к компьютеру
- Принцип Дирихле.
Основные комбинаторные величины и их свойства
- Число перестановок, сочетаний, размещений
- Задачи 1: Капитан и боцман на пиратском корабле, поезд из вагонов
- Задачи 2: слова в языке, девушки выбирают одежду
Сочетания с повторениями и без
- Число сочетаний без повторений
- Задачи: мыши в лаборатории, коллекционеры, кости в домино, тренировочная группа
- Число сочетаний с повторениями, пример с сортами пирожных, букет из роз
Комбинаторные тождества
- Формула бинома Ньютона
- Комбинаторные тождества, треугольник Паскаля
- Сумма квадратов биномиальных коэффициентов
- Тождество с убывающими основаниями
- Разные суммы биномиальных коэффициентов
- Задачи: стаканы и чашки, наборы из чётного числа символов
Полиномиальные коэффициенты
- Полиномиальные коэффициенты
- Связь полиномиальных и биномиальных коэффициентов
- Задачи: перестановка букв в слове, шары и ящики, цветки и девочки
- Формулировка полиномиальной формулы в общем виде, сумма полиномиальных коэффициентов
Формула включений и исключений
- Формула включений и исключений
- Задачи 1: о путешественниках, отчет о школьниках, количество беспорядков
- Задачи 2: художники, празднование нового года,
Выравнивания
- Задача о выравнивании последовательностей
- Теорема о числе выравниваний
|
|
Coursera / МФТИ
|
Старшая школа и студенты
|
10 часов видео
|
Современная комбинаторика
|
Основные принципы комбинаторики'
- Основные принципы комбинаторики, Принцип Дирихле
- Последовательности векторов
- Задачи: шестизначные числа, первокурсники в кинотеатре
- Числа сочетаний, размещений и перестановок, Теоремы о числе размещений с повторениями и без
- Задачи: дежурство в столовой, карты из колоды, тома Пушкина на книжной полке
- Теорема о раскраске множества в два цвета
Комбинаторные тождества
- Бином Ньютона, полиномиальный коэффициент, полиномиальная формула
- Задачи: задачи и студенты, фигуры на шахматной доске, задача о НИИ, книги на полке
- Восемь комбинаторных тождеств
- Сумма биномиальных коэффициентов
Формула обращения Мёбиуса
- Определение циклической последовательности
- Простое число, бесконечность простых
- Основная теорема арифметики
- Функция Мебиуса, суммы по делителям, формула обращения Мебиуса
Циклические последовательности
- Количество циклических последовательностей
- Частично упорядоченное множество
- Обобщенная функция Мебиуса, теорема об формуле обращения Мебиуса на ч.у.м.
- Передоказательство формулы включений и исключений
Разбиения
- Разбиения чисел, упорядоченные и неупорядоченные разбиения
- Формула для числа упорядоченных разбиений
- Рекуррентное соотношение для числа неупорядоченных разбиений
- Теоремы Эйлера о равенстве количеств неупорядоченных разбиений
Линейные рекуррентные соотношения. Формальные степенные ряды.
- Линейные рекуррентные соотношения, Числа Фибоначчи
- Теорема о решении линейного рекуррентного соотношения второго порядка
- Формальные степенные ряды, операции над рядами
Производящие функции
- Производящие функции, Теорема о сходимости степенных рядов (б/д), примеры
- Сходимость на границе интервала
- Числа Фибоначчи и их производящая функция, суммы чисел Фибоначчи, чисел сочетания и пр.
- Числа Каталана
- Извлечение корней из степенных рядов
- Формула для числа Каталана: д-во через производящие функции
|
|
Coursera / МФТИ
|
Старшая школа и студенты
|
13 часов видео
|
Основы перечислительной комбинаторики
|
Элементарная комбинаторика'
- Основные понятия теории множеств и комбинаторики
- Принцип Дирихле, число сочетаний
- Число перестановок
- Подсчет отображений конечных множеств
- Перестановки с повторениями. Числа Стирлинга
Рекуррентные соотношения и производящие функции
- Рекуррентные соотношения и производящие функции
- Решение рекуррентных соотношений с помощью производящих функций
- Числа Каталана
Простейшие операции над производящими функциями
- Комбинаторный смысл операций над производящими функциями
- Понятие композиции обыкновенных производящих функций
- Разбиение числа на слагаемые. Диаграммная техника
Перечисление помеченных объектов
- Композиция экспоненциальных производящих функций
- Комбинаторика перестановок
- Формула Кэли для подсчета всех помеченных деревьев
- Перечисление деревьев
|
|
Stepik / CSC
|
Старшая школа и студенты
|
10 часов видео, 100 тестов
|
Основы теории графов (обычный)
|
Основные понятия теории графов'
- Основные понятия теории графов, виды графов
- Маршруты, пути, циклы, связность, подграфы
- Изоморфизм и автоморфизм графов
Деревья и циклы
- Деревья
- Циклы в графах: Эйлеровы графы, Гамильтоновы циклы
Связность в графах
- Связность графов: Вершинная и реберная связность, Структура двусвязных графов
- Связность графов: k-связные графы, Потоки и сети
Паросочетания в графах
- Независимые множества и покрытия графа
- Паросочетания в графах. Теорема Холла
Раскраска графов
- k-раскрашиваемые графы. Теорема Брукса, хроматическое число
- Хроматический многочлен графа
Планарные графы
- Планарные графы, формула Эйлера
- Раскраска планарных графов
|
|
Stepik / CSC
|
Старшая школа и студенты
|
11 часов видео, 100 тестов
|
Теория графов (расширенный)
|
Основные понятия теории графов'
- Основные понятия теории графов, виды графов
- Маршруты, пути, циклы, связность, подграфы
- Изоморфизм и автоморфизм графов
Деревья и их перечисление
- Деревья, Формула Кэли,
- Подсчет остовных деревьев в графе
Циклы
- Циклы в графах: Эйлеровы графы, Гамильтоновы циклы
- Графы Де Брейна
Связность в графах
- Связность графов: Вершинная и реберная связность, Структура двусвязных графов
- Связность графов: k-связные графы, Потоки и сети
Паросочетания в графах
- Независимые множества и покрытия графа
- Паросочетания в графах. Теорема Холла
- Совершенные и максимальные паросочетания
Раскраска графов
- k-раскрашиваемые графы. Теорема Брукса, хроматическое число
- Реберная раскраска, совершенные графы
- Хроматический многочлен графа
Планарные графы
- Планарные графы, формула Эйлера, Раскраска планарных графов
- Критерии планарности, карты на поверхностях
Теория Рамсея и экстремальная теория графов
- Принцип Дирихле, Начала теории Рамсея
- Экстремальная теория графов
|
|
Stepik / CSC
|
Старшая школа и студенты
|
18 часов видео, 100 тестов
|
Теория графов
|
Введение. Базовые понятия теории графов'
- Основные термины теории графов
- Деревья, число мультиграфов, путь в графе
- Перенумерация цикла, последовательности степеней
Эквивалентные определения дерева. Планарные графы
- Импликации
- Планарность, гипотеза о четырех красках
- Примеры непланарных графов, критерий Куратовского
- Плоские графы, грани и теорема Жордана, формула Эйлера
- Хроматическое число планарных графов, Двудольные планарные графы
Формула Кэли. Унициклические графы. Эйлеровы циклы
- Число деревьев, кодирование деревьев, коды Прюфера, декодирование
- Число унициклических графов, Эйлеровы циклы
- Центр дерева
- Число неизоморфных деревьев
Гамильтоновы циклы
- Гамильтоновы циклы, теорема Дирака
- Вершинная связность. Критерий Хватала
- Число гамильтоновых циклов в полном двудольном графе
- Признак Хватала. Оценка связности через общих соседей
- Примеры независимых множеств, теорема о числе независимости
Паросочетания. Теоремы Холла и Кёнига
- Паросочетания. Теорема Холла
- Вершинное покрытие, теорема Кёнига
- Теорема Холла из теоремы Кёнига и наоборот
- Паросочетания и степени вершин
- К-регулярный двудольный граф
Экстремальная теория графов. Теорема Турана
- Число независимости, кликовое число, теорема Турана
- Задача про графы на плоскости, Двудольный подграф
- Вершинное покрытие для графа без треугольников
- Граф без четных циклов
- Хроматическое число и его связь с другими величинами
Теория Рамсея
- Теория 6 рукопожатий
- Числа Рамсея, Значения R(s,t) для малых s
- Верхняя оценка чисел Рамсея с помощью рекурсии
- Подсчет графов с большими полными подграфами
- Обсуждение нижних оценок
|
|
Coursera / МФТИ
|
Старшая школа и студенты
|
15 часов видео
|
Случайные графы
|
Две модели случайного графа'
- Биномиальная модель случайного графа
- Равномерная модель случайного графа
- Пороговая вероятность для свойства связности
- Нижняя оценка вероятности связности
- Теорема о появлении гигантской компоненты в случайном графе
- Задачи
Теорема о пороговой вероятности для свойства связности
- Применение неравенства Чебышева
- Оценивание мат. ожидания, дисперсии
- Вероятность существования изолированной вершины
- Разложение случайного графа на компоненты связности, оценка мат. ожидания
- Задачи
Вероятностный метод
- Хроматическое число, число независимости и кликовое число.
- Обхват графа.
- Теорема о существовании графа с большим обхватом и большим хроматическим числом.
Хроматическое число случайного графа
- Оценки хроматического числа случайного графа G(n,p) при различных p=p(n).
Алгоритмы на случайном графе
- Жадный алгоритм раскраски.
- Жадное хроматическое число, жадное число независимости и жадное кликовое число.
- Теорема о жадном хроматическом числе и жадном числе независимости случайного графа.
Малые подграфы в случайном графе
- Распределение малых подрафов в случайном графе: пороговые вероятности и Пуассоновская предельная теорема на пороге.
|
|
Coursera / МФТИ
|
Старшая школа и студенты
|
15 часов видео
|