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

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

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

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

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

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

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

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

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

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

3. Графы

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

   Литература

   Р. Грэхем, Д. Кнут, О. Паташник "Конкретная математика: основание информатики"

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

   Элементы математики в задачах: через кружки и олимпиады к профессии, сборник под редакцией А. Заславского, А. Скопенкова и М. Скопенкова. Изд-во МЦНМО, 2016.

   ---