Просмотр кода страницы Дискретная математика

<!-- ****************************** -->
<!-- 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 часов видео
<!-- ****************************** -->
<!-- Table ending - do not touch -->
|}
<!-- ****************************** -->