Дискретные структуры

Александр Дайняк

Stepic.org

Это базовый курс дискретной математики и комбинаторики. Он для всех, кто хочет развить математическую интуицию, помогающую в работе с дискретными объектами и алгоритмами на них

Программа

1. Введение и знакомство с базовыми понятиями

1.1 Приветствие
1.2 Множества, отображения
1.3 Суммы и произведения с параметром
1.4 Целые части
1.5 Принцип Дирихле
1.6 Индукция
1.7 Основные дискретные объекты комбинаторики
1.8 Задачи на подсчёт
1.9 Биномиальные коэффициенты
1.10 Формула включений-исключений
1.11 Рекуррентные соотношения и метод выделенного элемента
1.12 Повторение материала первого модуля

2. Основные понятия теории графов

2.1 Азбука теории графов I: графы, подграфы, степени вершин
2.2 Азбука теории графов II: специальные графы, путешествия по графу
2.3 Одинаковые графы: изоморфизм
2.4 Задачи, задачи, задачи…
2.5 Деревья
2.6 Как нарисовать граф
2.7 Раскраски графов
2.8 Эйлеровы и гамильтоновы циклы
2.9 Повторение материала второго модуля

3. Асимптотики дискретных величин

3.1 Кто побеждает в битве на бесконечности: рассудят O, Ω, Θ, o, ~
3.2 Оценки для факториала и биномиальных коэффициентов
3.3 Суммы, быстро растущие функции, и другие насущные вещи

4. Вероятностный метод

4.1 Теорема Рамсея, числа Рамсея
4.2 Ликбез по теории вероятностей + случайные графы на десерт
4.3 Вероятностный метод на примере нижней оценки чисел Рамсея
4.4 Продолжение ликбеза: случайные величины, Марков и Чебышёв
4.5 Теорема о числе скрещиваний
4.6 Теорема Эрдёша о нелокальности хроматического числа

5. Алгебра на службе дискретной математики

5.1 Ликбез по алгебре: простые числа, равенство по модулю
5.2 Ликбез по алгебре: поля вычетов, многочлены
5.3 Nullstellensatz: обобщение теоремы Лагранжа и его следствия
5.4 Комбинаторика алгебры: аддитивная комбинаторика
5.5 Ликбез по алгебре: линейные пространства
5.6 Скалярные произведения и теорема Фишера
5.7 Конструктивная нижняя оценка чисел Рамсея

6. Избранные сюжеты комбинаторики и теории графов

6.1 Потоки в сетях и паросочетания в двудольных графах
6.2 Решённая задача Турана и открытая проблема Заранкевича
6.3 Решаем частный случай проблемы Заранкевича при помощи алгебры
6.4 Две замечательные теоремы о раскрасках: теоремы Брукса и Кёнига
6.5 Подводим итоги курса

Ключевые слова

Дискретная математика
Комбинаторика
Алгоритмы
Графы
Асимптотический анализ


Характеристики курса

Направление в конкурсе
Естественные и технические науки
Вид образования
Внеформальное
Язык обучения
Русский
Дисциплина
Математика, Естественные науки, математика и статистика
Авторы курса
Александр Дайняк
Реквизиты авторов
Доцент кафедры дискретной математики ФИВТ МФТИ, кандидат физико-математических наук.
Организация
Stepic.org
Реквизиты организации
Stepic.org – платформа для массовых открытых онлайн-курсов по техническим дисциплинам, а также онлайн-конструктор для создания и распространения образовательных материалов.
Входные требования по уровню знаний
Курс рассчитан на студентов 1-2 курсов технических вузов и всех интересующихся.
Входной тест
Формирование групп по уровню подготовленности
Присутствие преподавателей
Присутствие тьюторов
Присутствие фасилитаторов
Форма представления учебных материалов
тексты, мультимедиа, видеолекции, презентации, онлайн общение с преподавателем, тестовый экзамен
Наличие обратной связи в материалах
Наличие совместного обучения
Наличие практических занятий
лабораторные
Наличие форумов, дискуссий
Наличие вебинаров, видеоконференций
Наличие неформального общения, meetup
Интеграция с LMS
Учебная аналитика
Наличие сертификации
Виды сертификации
Stepic-сертификат
Наличие временных границ
Продолжительность
4 (месяцы)
Тип занятий (синхронность)
асинхронные
Виды оценивания
тест, творческое задание
Единица модуля
неделя
Количество модулей в курсе
6
Возможность формирования собственной траектории, индивидуализации на курсе
Поддерживаемые браузеры
Минимальные версии поддерживаемых браузеров: IE / Edge 10 Firefox 38 Chrome 31 Safari 8 Opera 30 iOS Safari 9 Android Browser 4.4 Chrome for Android 44
Поддержка лиц с ограниченными возможностями
Сайт курса

Комментарии