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

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

Название курса	Источник / Организация	Возраст	Длина курса
Ликбез по дискретной математике (простой обзорный) Линейная алгебра Линейная алгебра: линейное пространство, системы линейных уравнений Линейная алгебра: евклидово пространство, ортогональный базис, линейные операторы Комбинаторика Основные понятия теории множеств и комбинаторики Принцип Дирихле, число сочетаний Число перестановок Подсчет отображений конечных множеств Рекуррентные соотношения Теория графов Графы, связность, деревья Эйлеровы графы, двудольные графы, раскраски графов Паросочетания. Теорема Холла Основные понятия дискретной вероятности. Условная вероятность Основные характеристики случайных величин	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 часов видео