Комбинаторика и теория вероятностей для математиков
Программа
Курс идет по средам в 18.30 в ИППИ.

Лекция 1. Множества, основные операция над множествами. Круги Эйлера. Комбинаторные объекты и комбинаторные числа. Основные правила комбинаторики: правило суммы и правило произведения. Факториал и убывающая факториальная степень. Базовые комбинаторные объекты: размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями. Их число и рекуррентные формулы для них. Теорема о числе сочетаний с повторениями.
Литература: [1, §2.1, 2.2, 2.3], [2, гл. 1, 2], [5, §1.1, 1.4, 2.1] [8, гл. 1].
Лекция
Семинар задачи
Решения задач
Видео (1, 2, 3)

Лекция 2. Биномиальные коэффициенты: основные свойства и отношения. Формула бинома Ньютона. Производящие функции, вычисление сумм и доказательство комбинаторных тождеств. Формула включений-исключений и ее производные случаи. Неравенство Бонферрони (б/д).
Литература: [1, §2.4], [2, гл. 4], [9].
Лекция
Семинар
Домашнее задание по лекциям 1-2

Лекция 3. Разбиение натуральных чисел на слагаемые. Примеры задач. Рекуррентные соотношения для количества разбиений. Диаграммная техника. Формула Харди-Рамануджана (б/д). Количество разбиений конечного множества. Числа Стирлинга и Белла.
Литература: [1, §2.4], [2, гл. 4], [9].
Лекция
Семинар
Видео

Лекция 4. Выравнивание последовательностей. Рекуррентные соотношения для числа выравниваний и . Решение задачи о выравнивании последовательностей при помощи динамического программирования.
Литература: [5, §7.1, 13.1].
Лекция

Лекция 5. Числа Фибоначчи: пример возникновения задачи, рекуррентное соотношение. Последовательности, задаваемые линейными рекуррентными соотношениями с постоянными коэффициентами (ЛРСПК). Частное решение ЛРСПК, лемма о линейной комбинации частных решений ЛРСПК. Общее решение ЛРСПК. Характеристический многочлен ЛРСПК. Теоремы об общем решении ЛРСПК. Линейные неоднородные рекуррентные соотношения с постоянными коэффициентами (ЛНРСПК), их частные и общие решения. Теорема об общем решении ЛНРСПК. Теорема о частном решении ЛНРСПК.
Литература: [2, гл. 7], [5, §6.1, 6.2].
Видео
Лекция
Домашнее задание по занятиям 3-5

Лекция 6. Графы: формальное определение и примеры. Основные подструктуры в графах (подграфы, порожденные подграфы, клики, независимые и доминирующие множества, паросочетания, цепи, циклы) и некоторые специальных классы графов (двудольные графы, полные графы, деревья). Изоморфизм графов. Связность графов, компоненты связности. Формула Кэли. Кодирование Прюфера. Теорема Рамсея (для графов для случая двух цветов). Числа Рамсея.
Видео
Лекция
Семинар

Лекция 7. Предмет теории вероятностей. Краткий повтор основных определений и концепций. Вероятностный метод в комбинаторике. Простая вероятностная нижняя оценка чисел Рамсея. Случайные графы. Понятие о «почти всех» объектах.
Видео (часть 1, 2)

Лекция 8. Применение вероятностного метода. Теорема Эрдёша о существовании графов с большим обхватом и одновременно большим хроматическим числом. Теорема о нижней оценке числа скрещиваний графа с большим числом рёбер.

Лекция 9. Локальная лемма Ловаса: общий и симметричный случаи. Применение для получения оценки диагональных чисел Рамсея.
Литература
[1] Н. Б. Алфутова, А. В. Устинов, Алгебра и теория чисел. Сборник задач для математических школ. — М.: МЦНМО, 2009.
[2] Н. Я. Виленкин, А. Н. Виленкин, П. А. Виленкин, Комбинаторика. — М.: ФИМА, МЦНМО, 2010.
[3] В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич, Лекции по теории графов. — М.: Либроком, 2009.
[4] Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн, Алгоритмы: построение и анализ. — М.: Вильямс, 2007.
[5] А. М. Райгородский, А. В. Савватеев, И. Д. Шкредов, Комбинаторика (методическое пособие для факультета биоинженерии и биоинформатики МГУ). — М.: Макс-пресс, 2005.
[6] Б. А.Севастьянов Курс теории вероятностей и математической статистики. М.: Наука. Гл. ред. физ.-мат. лит., 1982.— 256 с.
[7] Ф. Харари, Теория графов. — М.: Либроком, 2009.
[8] А. Х. Шахмейстер, Комбинаторика. Статистика. Вероятность. — М.: МЦНМО, 2010.
[9] Г. Эндрюс, Теория разбиений. — М.: Наука. 1982.
Преподаватель
К.ф.-м.н, ассистент
кафедры математической
кибернетики факультета вычислительной математики и кибернетики МГУ. Занимается исследованием математических моделей дискретных управляющих систем и интересуется разработкой алгоритмов и систем автоматизации проектирования интегральных схем.
Большой Каретный переулок, 19, ИППИ РАН,
м. Цветной Бульвар

hello@bioinfschool.ru

Реквизиты

Некоммерческое партнерство содействия развитию биоинформатики «Биоинформатический семинар»
Адрес: 119269 г.Москва ул.Вавилова д.60/1 офис 19
ИНН \ КПП 7716450074 \ 773601001
ОГРН 1117799008030
ОКПО \ ОКАТО 91570039 \ 45293558000
Банк: ОАО «Сбербанк России» г. Москва
Расчетный счет 40703810938110001685
БИК 044525225
Кор. счет 30101810400000000225
Made on
Tilda