556
правок
Изменения
Перейти к навигации
Перейти к поиску
<!-- ****************************** -->
<!-- Table ending - do not touch -->
|}
<!-- ****************************** -->
==Дискретная математика==
<!-- ****************************** -->
<!-- Table Format - do not touch -->
{| class="a" style="width:100%;" border="1" style="width:100%; border-collapse:collapse"|+
<!-- Table name -->
'''Дискретная математика'''
<!-- Table headers - do not touch -->
! style="background: #EAECF0;"| Название курса||style="background: #EAECF0;"|Источник / Организация||style="background: #EAECF0;"|Возраст||style="background: #EAECF0;"|Длина курса
<!-- ****************************** -->
<!-- Course 1 -->
|-
|
<!-- Course format do not touch -->
{| role="presentation" class="a mw-collapsible mw-collapsed" style="border:1px solid white;"
| style="border:1px solid white;"|<strong>[https://stepik.org/course/91/promo Ликбез по дискретной математике (простой обзорный)]</strong>
|-
<!-- Course content format do not touch -->
| style="border:1px solid white;"|
<!-- Course content -->
'''Линейная алгебра'''
* Линейная алгебра: линейное пространство, системы линейных уравнений
* Линейная алгебра: евклидово пространство, ортогональный базис, линейные операторы
'''Комбинаторика'''
* Основные понятия теории множеств и комбинаторики
* Принцип Дирихле, число сочетаний
* Число перестановок
* Подсчет отображений конечных множеств
* Рекуррентные соотношения
'''Теория графов'''
* Графы, связность, деревья
* Эйлеровы графы, двудольные графы, раскраски графов
* Паросочетания. Теорема Холла
* Основные понятия дискретной вероятности.
* Условная вероятность
* Основные характеристики случайных величин
|}
<!-- Formating do not touch -->
|style="text-align:center;"|
[[Stepik]] / [[CSC]]
|style="text-align:center;"|
[[Материалы для старшей школы и студентов| Старшая школа и студенты]]
|style="text-align:center;"|
10 часов видео, 100 тестов
<!-- ****************************** -->
<!-- Course 4 -->
|-
|
<!-- Course format do not touch -->
{| role="presentation" class="a mw-collapsible mw-collapsed" style="border:1px solid white;"
| style="border:1px solid white;"|<strong>[https://stepik.org/course/902/promo Введение в дискретную математику (обзорный для программистов)]</strong>
|-
<!-- Course content format do not touch -->
| style="border:1px solid white;"|
<!-- Course content -->
'''Теория множеств и комбинаторика'''
* Теория множеств
* Сочетания и перестановки
'''Дискретная вероятность'''
* Случайные величины
* Распределения дискретной случайной величины
'''Теория графов и основы линейной алгебры'''
* Графы, определения и свойства.
* Эйлеровы пути и циклы в графе
* Теория Рамсея
'''Теория сложности'''
* Напоминание о суммах, логарифмах и экспонентах
* Скорость роста функций и алгоритмов
* O-нотация
|}
<!-- Formating do not touch -->
|style="text-align:center;"|
[[Stepik]] / [[Институт Биоинформатики]]
|style="text-align:center;"|
[[Материалы для старшей школы и студентов| Старшая школа и студенты]]
|style="text-align:center;"|
4 часа видео, 50 тестов
<!-- ****************************** -->
<!-- Course 5 -->
|-
|
<!-- Course format do not touch -->
{| role="presentation" class="a mw-collapsible mw-collapsed" style="border:1px solid white;"
| style="border:1px solid white;"|<strong>[https://www.coursera.org/learn/kombinatorika-dlya-nachinayushchikh Комбинаторика для начинающих]</strong>
|-
<!-- Course content format do not touch -->
| style="border:1px solid white;"|
<!-- Course content -->
'''Правило сложения и умножения. Принцип Дирихле'''
* Правила сложения и умножения.
* Задачи о перелёте Москва-Сидней, о походе в театр, о пароле к компьютеру
* Принцип Дирихле.
'''Основные комбинаторные величины и их свойства'''
* Число перестановок, сочетаний, размещений
* Задачи 1: Капитан и боцман на пиратском корабле, поезд из вагонов
* Задачи 2: слова в языке, девушки выбирают одежду
'''Сочетания с повторениями и без'''
* Число сочетаний без повторений
* Задачи: мыши в лаборатории, коллекционеры, кости в домино, тренировочная группа
* Число сочетаний с повторениями, пример с сортами пирожных, букет из роз
'''Комбинаторные тождества'''
* Формула бинома Ньютона
* Комбинаторные тождества, треугольник Паскаля
* Сумма квадратов биномиальных коэффициентов
* Тождество с убывающими основаниями
* Разные суммы биномиальных коэффициентов
* Задачи: стаканы и чашки, наборы из чётного числа символов
'''Полиномиальные коэффициенты'''
* Полиномиальные коэффициенты
* Связь полиномиальных и биномиальных коэффициентов
* Задачи: перестановка букв в слове, шары и ящики, цветки и девочки
* Формулировка полиномиальной формулы в общем виде, сумма полиномиальных коэффициентов
'''Формула включений и исключений'''
* Формула включений и исключений
* Задачи 1: о путешественниках, отчет о школьниках, количество беспорядков
* Задачи 2: художники, празднование нового года,
'''Выравнивания'''
* Задача о выравнивании последовательностей
* Теорема о числе выравниваний
|}
<!-- Formating do not touch -->
|style="text-align:center;"|
[[Coursera]] / [[МФТИ]]
|style="text-align:center;"|
[[Материалы для старшей школы и студентов| Старшая школа и студенты]]
|style="text-align:center;"|
10 часов видео
<!-- ****************************** -->
<!-- Course 6 -->
|-
|
<!-- Course format do not touch -->
{| role="presentation" class="a mw-collapsible mw-collapsed" style="border:1px solid white;"
| style="border:1px solid white;"|<strong>[https://www.coursera.org/learn/modern-combinatorics Современная комбинаторика]</strong>
|-
<!-- Course content format do not touch -->
| style="border:1px solid white;"|
<!-- Course content -->
'''Основные принципы комбинаторики'''
* Основные принципы комбинаторики, Принцип Дирихле
* Последовательности векторов
* Задачи: шестизначные числа, первокурсники в кинотеатре
* Числа сочетаний, размещений и перестановок, Теоремы о числе размещений с повторениями и без
* Задачи: дежурство в столовой, карты из колоды, тома Пушкина на книжной полке
* Теорема о раскраске множества в два цвета
'''Комбинаторные тождества'''
* Бином Ньютона, полиномиальный коэффициент, полиномиальная формула
* Задачи: задачи и студенты, фигуры на шахматной доске, задача о НИИ, книги на полке
* Восемь комбинаторных тождеств
* Сумма биномиальных коэффициентов
'''Формула обращения Мёбиуса'''
* Определение циклической последовательности
* Простое число, бесконечность простых
* Основная теорема арифметики
* Функция Мебиуса, суммы по делителям, формула обращения Мебиуса
'''Циклические последовательности'''
* Количество циклических последовательностей
* Частично упорядоченное множество
* Обобщенная функция Мебиуса, теорема об формуле обращения Мебиуса на ч.у.м.
* Передоказательство формулы включений и исключений
'''Разбиения'''
* Разбиения чисел, упорядоченные и неупорядоченные разбиения
* Формула для числа упорядоченных разбиений
* Рекуррентное соотношение для числа неупорядоченных разбиений
* Теоремы Эйлера о равенстве количеств неупорядоченных разбиений
'''Линейные рекуррентные соотношения. Формальные степенные ряды.'''
* Линейные рекуррентные соотношения, Числа Фибоначчи
* Теорема о решении линейного рекуррентного соотношения второго порядка
* Формальные степенные ряды, операции над рядами
'''Производящие функции'''
* Производящие функции, Теорема о сходимости степенных рядов (б/д), примеры
* Сходимость на границе интервала
* Числа Фибоначчи и их производящая функция, суммы чисел Фибоначчи, чисел сочетания и пр.
* Числа Каталана
* Извлечение корней из степенных рядов
* Формула для числа Каталана: д-во через производящие функции
|}
<!-- Formating do not touch -->
|style="text-align:center;"|
[[Coursera]] / [[МФТИ]]
|style="text-align:center;"|
[[Материалы для старшей школы и студентов| Старшая школа и студенты]]
|style="text-align:center;"|
13 часов видео
<!-- ****************************** -->
<!-- Course 7 -->
|-
|
<!-- Course format do not touch -->
{| role="presentation" class="a mw-collapsible mw-collapsed" style="border:1px solid white;"
| style="border:1px solid white;"|<strong>[https://stepik.org/course/125/promo Основы перечислительной комбинаторики]</strong>
|-
<!-- Course content format do not touch -->
| style="border:1px solid white;"|
<!-- Course content -->
'''Элементарная комбинаторика'''
* Основные понятия теории множеств и комбинаторики
* Принцип Дирихле, число сочетаний
* Число перестановок
* Подсчет отображений конечных множеств
* Перестановки с повторениями. Числа Стирлинга
'''Рекуррентные соотношения и производящие функции'''
* Рекуррентные соотношения и производящие функции
* Решение рекуррентных соотношений с помощью производящих функций
* Числа Каталана
'''Простейшие операции над производящими функциями'''
* Комбинаторный смысл операций над производящими функциями
* Понятие композиции обыкновенных производящих функций
* Разбиение числа на слагаемые. Диаграммная техника
'''Перечисление помеченных объектов'''
* Композиция экспоненциальных производящих функций
* Комбинаторика перестановок
* Формула Кэли для подсчета всех помеченных деревьев
* Перечисление деревьев
|}
<!-- Formating do not touch -->
|style="text-align:center;"|
[[Stepik]] / [[CSC]]
|style="text-align:center;"|
[[Материалы для старшей школы и студентов| Старшая школа и студенты]]
|style="text-align:center;"|
10 часов видео, 100 тестов
<!-- ****************************** -->
<!-- Course 8 -->
|-
|
<!-- Course format do not touch -->
{| role="presentation" class="a mw-collapsible mw-collapsed" style="border:1px solid white;"
| style="border:1px solid white;"|<strong>[https://stepik.org/course/126 Основы теории графов (обычный)]</strong>
|-
<!-- Course content format do not touch -->
| style="border:1px solid white;"|
<!-- Course content -->
'''Основные понятия теории графов'''
* Основные понятия теории графов, виды графов
* Маршруты, пути, циклы, связность, подграфы
* Изоморфизм и автоморфизм графов
'''Деревья и циклы'''
* Деревья
* Циклы в графах: Эйлеровы графы, Гамильтоновы циклы
'''Связность в графах'''
* Связность графов: Вершинная и реберная связность, Структура двусвязных графов
* Связность графов: k-связные графы, Потоки и сети
'''Паросочетания в графах'''
* Независимые множества и покрытия графа
* Паросочетания в графах. Теорема Холла
'''Раскраска графов'''
* k-раскрашиваемые графы. Теорема Брукса, хроматическое число
* Хроматический многочлен графа
'''Планарные графы'''
* Планарные графы, формула Эйлера
* Раскраска планарных графов
|}
<!-- Formating do not touch -->
|style="text-align:center;"|
[[Stepik]] / [[CSC]]
|style="text-align:center;"|
[[Материалы для старшей школы и студентов| Старшая школа и студенты]]
|style="text-align:center;"|
11 часов видео, 100 тестов
<!-- ****************************** -->
<!-- Course 9 -->
|-
|
<!-- Course format do not touch -->
{| role="presentation" class="a mw-collapsible mw-collapsed" style="border:1px solid white;"
| style="border:1px solid white;"|<strong>[https://stepik.org/course/5608/promo Теория графов (расширенный)]</strong>
|-
<!-- Course content format do not touch -->
| style="border:1px solid white;"|
<!-- Course content -->
'''Основные понятия теории графов'''
* Основные понятия теории графов, виды графов
* Маршруты, пути, циклы, связность, подграфы
* Изоморфизм и автоморфизм графов
'''Деревья и их перечисление'''
* Деревья, Формула Кэли,
* Подсчет остовных деревьев в графе
'''Циклы'''
* Циклы в графах: Эйлеровы графы, Гамильтоновы циклы
* Графы Де Брейна
'''Связность в графах'''
* Связность графов: Вершинная и реберная связность, Структура двусвязных графов
* Связность графов: k-связные графы, Потоки и сети
'''Паросочетания в графах'''
* Независимые множества и покрытия графа
* Паросочетания в графах. Теорема Холла
* Совершенные и максимальные паросочетания
'''Раскраска графов'''
* k-раскрашиваемые графы. Теорема Брукса, хроматическое число
* Реберная раскраска, совершенные графы
* Хроматический многочлен графа
'''Планарные графы'''
* Планарные графы, формула Эйлера, Раскраска планарных графов
* Критерии планарности, карты на поверхностях
'''Теория Рамсея и экстремальная теория графов'''
* Принцип Дирихле, Начала теории Рамсея
* Экстремальная теория графов
|}
<!-- Formating do not touch -->
|style="text-align:center;"|
[[Stepik]] / [[CSC]]
|style="text-align:center;"|
[[Материалы для старшей школы и студентов| Старшая школа и студенты]]
|style="text-align:center;"|
18 часов видео, 100 тестов
<!-- ****************************** -->
<!-- Course 10 -->
|-
|
<!-- Course format do not touch -->
{| role="presentation" class="a mw-collapsible mw-collapsed" style="border:1px solid white;"
| style="border:1px solid white;"|<strong>[https://www.coursera.org/learn/teoriya-grafov Теория графов]</strong>
|-
<!-- Course content format do not touch -->
| style="border:1px solid white;"|
<!-- Course content -->
'''Введение. Базовые понятия теории графов'''
* Основные термины теории графов
* Деревья, число мультиграфов, путь в графе
* Перенумерация цикла, последовательности степеней
'''Эквивалентные определения дерева. Планарные графы'''
* Импликации
* Планарность, гипотеза о четырех красках
* Примеры непланарных графов, критерий Куратовского
* Плоские графы, грани и теорема Жордана, формула Эйлера
* Хроматическое число планарных графов, Двудольные планарные графы
'''Формула Кэли. Унициклические графы. Эйлеровы циклы'''
* Число деревьев, кодирование деревьев, коды Прюфера, декодирование
* Число унициклических графов, Эйлеровы циклы
* Центр дерева
* Число неизоморфных деревьев
'''Гамильтоновы циклы'''
* Гамильтоновы циклы, теорема Дирака
* Вершинная связность. Критерий Хватала
* Число гамильтоновых циклов в полном двудольном графе
* Признак Хватала. Оценка связности через общих соседей
* Примеры независимых множеств, теорема о числе независимости
'''Паросочетания. Теоремы Холла и Кёнига'''
* Паросочетания. Теорема Холла
* Вершинное покрытие, теорема Кёнига
* Теорема Холла из теоремы Кёнига и наоборот
* Паросочетания и степени вершин
* К-регулярный двудольный граф
'''Экстремальная теория графов. Теорема Турана'''
* Число независимости, кликовое число, теорема Турана
* Задача про графы на плоскости, Двудольный подграф
* Вершинное покрытие для графа без треугольников
* Граф без четных циклов
* Хроматическое число и его связь с другими величинами
'''Теория Рамсея'''
* Теория 6 рукопожатий
* Числа Рамсея, Значения R(s,t) для малых s
* Верхняя оценка чисел Рамсея с помощью рекурсии
* Подсчет графов с большими полными подграфами
* Обсуждение нижних оценок
|}
<!-- Formating do not touch -->
|style="text-align:center;"|
[[Coursera]] / [[МФТИ]]
|style="text-align:center;"|
[[Материалы для старшей школы и студентов| Старшая школа и студенты]]
|style="text-align:center;"|
15 часов видео
<!-- ****************************** -->
<!-- Course 11 -->
|-
|
<!-- Course format do not touch -->
{| role="presentation" class="a mw-collapsible mw-collapsed" style="border:1px solid white;"
| style="border:1px solid white;"|<strong>[https://www.coursera.org/learn/sluchajnye-graphy Случайные графы]</strong>
|-
<!-- Course content format do not touch -->
| style="border:1px solid white;"|
<!-- Course content -->
'''Две модели случайного графа'''
* Биномиальная модель случайного графа
* Равномерная модель случайного графа
* Пороговая вероятность для свойства связности
* Нижняя оценка вероятности связности
* Теорема о появлении гигантской компоненты в случайном графе
* Задачи
'''Теорема о пороговой вероятности для свойства связности'''
* Применение неравенства Чебышева
* Оценивание мат. ожидания, дисперсии
* Вероятность существования изолированной вершины
* Разложение случайного графа на компоненты связности, оценка мат. ожидания
* Задачи
'''Вероятностный метод'''
* Хроматическое число, число независимости и кликовое число.
* Обхват графа.
* Теорема о существовании графа с большим обхватом и большим хроматическим числом.
'''Хроматическое число случайного графа'''
* Оценки хроматического числа случайного графа G(n,p) при различных p=p(n).
'''Алгоритмы на случайном графе'''
* Жадный алгоритм раскраски.
* Жадное хроматическое число, жадное число независимости и жадное кликовое число.
* Теорема о жадном хроматическом числе и жадном числе независимости случайного графа.
'''Малые подграфы в случайном графе'''
* Распределение малых подрафов в случайном графе: пороговые вероятности и Пуассоновская предельная теорема на пороге.
|}
<!-- Formating do not touch -->
|style="text-align:center;"|
[[Coursera]] / [[МФТИ]]
|style="text-align:center;"|
[[Материалы для старшей школы и студентов| Старшая школа и студенты]]
|style="text-align:center;"|
15 часов видео
Математика для старших классов и студентов (просмотреть исходный код)
Версия 21:49, 28 марта 2020
, 21:49, 28 марта 2020→Дискретная математика
|style="text-align:center;"|
6 часов видео, 100 тестов
<!-- ****************************** -->
<!-- Table ending - do not touch -->
