Программа курса Комбинаторика и теория вероятностей(для математиков)


Комбинаторика и теория вероятностей
Дайняк А.Б., Шуплецов М.С.
Лекция 1.
Комбинаторные объекты и комбинаторные числа. Основные правила комбинаторики: правило суммы и правило произведения. Факториал и убывающая факториальная степень. Базовые комбинаторные объекты: размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями. Их число и рекуррентные формулы для них. Формула бинома Ньютона и биномиальные коэффициенты. Теорема о числе сочетаний с повторениями.
Литература: [1, §2.1, 2.2, 2.3], [2, гл. 1, 2], [5, §1.1, 1.4, 2.1] [8, гл. 1].
Лекция 2.
Биномиальные коэффициенты: основные свойства и отношения. Производящие функции, вычисление сумм и доказательство комбинаторных тождеств. Формула включений-исключений и ее производные случаи. Неравенство Бонферрони (б/д).
Литература: [1, §2.4], [2, гл. 4], [9].
Лекция 3.
Разбиение натуральных чисел на слагаемые. Примеры задач. Рекуррентные соотношения для количества разбиений. Диаграммная техника. Формула Харди-Рамануджана (б/д). Количество разбиений конечного множества. Числа Стирлинга и Белла.
Литература: [1, §2.4], [2, гл. 4], [9].
Лекция 4.
Выравнивание последовательностей. Рекуррентные соотношения для числа выравниваний f(n,m) и g(m,n). Решение задачи о выравнивании последовательностей при помощи динамического программирования.
Литература: [5, §7.1, 13.1].
Лекция 5.
Числа Фибоначчи: пример возникновения задачи, рекуррентное соотношение. Последовательности, задаваемые линейными рекуррентными соотношениями с постоянными коэффициентами (ЛРСПК). Частное решение ЛРСПК, лемма о линейной комбинации частных решений ЛРСПК. Общее решение ЛРСПК. Характеристический многочлен ЛРСПК. Теоремы об общем решении ЛРСПК. Линейные неоднородные рекуррентные соотношения с постоянными коэффициентами (ЛНРСПК), их частные и общие решения. Теорема об общем решении ЛНРСПК. Теорема о частном решении ЛНРСПК.
Литература: [2, гл. 7], [5, §6.1, 6.2].
Лекция 6.
Графы: формальное определение и примеры. Основные подструктуры в графах (подграфы, порожденные подграфы, клики, независимые и доминирующие множества, паросочетания, цепи, циклы) и некоторые специальных классы графов (двудольные графы, полные графы, деревья). Изоморфизм графов. Связность графов, компоненты связности. Формула Кэли. Кодирование Прюфера. Теорема Рамсея (для графов для случая двух цветов). Числа Рамсея.
Лекция 7.
Предмет теории вероятностей. Краткий повтор основных определений и концепций. Вероятностный метод в комбинаторике. Простая вероятностная нижняя оценка чисел Рамсея. Случайные графы. Понятие о «почти всех» объектах.
Лекция 8.
Применение вероятностного метода. Теорема Эрдёша о существовании графов с большим обхватом и одновременно большим хроматическим числом. Теорема о нижней оценке числа скрещиваний графа с большим числом рёбер.
Лекция 9.
Локальная лемма Ловаса: общий и симметричный случаи. Применение для получения оценки диагональных чисел Рамсея.
Литература
Н. Б. Алфутова, А. В. Устинов, Алгебра и теория чисел. Сборник задач для математических школ. — М.: МЦНМО, 2009.
Н. Я. Виленкин, А. Н. Виленкин, П. А. Виленкин, Комбинаторика. — М.: ФИМА, МЦНМО, 2010.
В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич, Лекции по теории графов. — М.: Либроком, 2009.
Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн, Алгоритмы: построение и анализ. — М.: Вильямс, 2007.
А. М. Райгородский, А. В. Савватеев, И. Д. Шкредов, Комбинаторика (методическое пособие для факультета биоинженерии и биоинформатики МГУ). — М.: Макс-пресс, 2005.
Б. А.Севастьянов Курс теории вероятностей и математической статистики. М.: Наука. Гл. ред. физ.-мат. лит., 1982.— 256 с.
Ф. Харари, Теория графов. — М.: Либроком, 2009.
А. Х. Шахмейстер, Комбинаторика. Статистика. Вероятность. — М.: МЦНМО, 2010.
Г. Эндрюс, Теория разбиений. — М.: Наука. 1982.

Приложенные файлы

  • docx 8930786
    Размер файла: 20 kB Загрузок: 0

Добавить комментарий