На главную страницу НМУ

Михаил Борисович Скопенков

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

Мы изучим основы дискретной математики, которые необходимо знать каждому математику, независимо от специализации.

Для каждой изучаемой теории, каждого нового понятия мы постараемся показать, как они естественно возникают при решении практических задач, к каким задачам применяются дальше. Благодаря этому большинство объектов становятся наглядными.

Теория будет изучаться в виде решения задач участниками, с подробными указаниями и последующим разбором на занятии. Многие занятия доступны школьникам.

Примерная программа

  1. Комбинаторика.

    Подсчёт и комбинаторные тождества
    Формула включений и исключений
    Числа Каталана
    Производящие функции
    Разбиения*
    Булев куб
    Перестановки
    Порядок, тип, сопряженность
    Чётность перестановок
    Комбинаторика классов эквивалентности*

  2. Вероятность

    Классическое определение вероятности
    Более общее определение вероятности
    Независимость и условная вероятность
    Случайные величины
    Испытания Бернулли*

  3. Графы

    Основные определения
    Подсчеты в графах
    Пути в графах
    Перечисление деревьев
    Графы с точностью до изоморфизма
    Плоские графы*
    Раскраски графов*
    Хроматические число и индекс*

    Литература

    Р. Грэхем, Д. Кнут, О. Паташник "Конкретная математика: основание информатики"
    Элементы дискретной математики в задачах, А.А. Глибичук, А.Б. Дайняк, Д.Г. Ильинский, А.Б. Купавский, А.М. Райгородский, А.Б. Скопенков, А.А. Чернов, Изд-во МЦНМО, 2016
    Элементы математики в задачах: через кружки и олимпиады к профессии, сборник под редакцией А. Заславского, А. Скопенкова и М. Скопенкова. Изд-во МЦНМО, 2016.

    Rambler's Top100