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

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

Stepic.org

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

Syllabus

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 Подводим итоги курса

key words, tags

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


Course properties

Competition track
Science and engineering
Form of education
Informal
Learning language
Russian
Discipline
Mathematics, Natural sciences, mathematics and statistics
Course authors
Александр Дайняк
Author’s characterization
Доцент кафедры дискретной математики ФИВТ МФТИ, кандидат физико-математических наук.
Organization
Stepic.org
Organization characterization
Stepic.org – платформа для массовых открытых онлайн-курсов по техническим дисциплинам, а также онлайн-конструктор для создания и распространения образовательных материалов.
Knowledge level entrance requirements
Курс рассчитан на студентов 1-2 курсов технических вузов и всех интересующихся.
Entrance test
Groups formation by readiness level
Teachers presence
Tutors presence
Facilitators presence
Training materials forms
texts, multimedia, video lecture, presentation, synchronous video, sample exam
Interactivity in training materials
Collaborative learning presence
Practical activities
labs
Discussions, forums presence
Webinars, video conferences presence
meetup presence
LMS integration
Learning Analytics
Certification presence
Certification types
Stepic-сертификат
Course time limits
Duration
4 (months)
Learning types (sync/async)
asynchronous
Assessment types
test, creative work
Module unit
неделя
Course modules number
6
Personal learning path possibility, course individualization
Supported browsers
Минимальные версии поддерживаемых браузеров: IE / Edge 10 Firefox 38 Chrome 31 Safari 8 Opera 30 iOS Safari 9 Android Browser 4.4 Chrome for Android 44
Special needs support
Course site

Comments