Комбинаторика и теория вероятностей для биологов
Курс в Школе биоинформатики
Программа
Курс идет по понедельникам в 18.30 в ИППИ.
Программа курса
Лекция 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. Выравнивание последовательностей. Рекуррентные соотношения для числа выравниваний и . Решение задачи о выравнивании последовательностей при помощи динамического программирования.
Литература: [5, §7.1, 13.1].
Презентация
Семинар
Видео
Лекция 4. Числа Фибоначчи: пример возникновения задачи, рекуррентное соотношение. Последовательности, задаваемые линейными рекуррентными соотношениями с постоянными коэффициентами. Характеристический многочлен рекуррентного соотношения. Общий вид решения.
Литература: [2, гл. 7], [5, §6.1, 6.2].
Презентация
Видео
Домашнее задание
Лекция 5. Графы: формальное определение и примеры. Основные подструктуры в графах (подграфы, порожденные подграфы, клики, независимые и доминирующие множества, паросочетания, цепи, циклы) и некоторые специальных классы графов (двудольные графы, полные графы, деревья). Изоморфизм графов. Связность графов, компоненты связности. Задача Эйлера о кёнигсбергских мостах. Гамильтоновы циклы. Универсальные последовательности и графы Де Брёйна.
Литература: [3, гл. 1], [5, §13.3], [7, гл. 2, 4].
Презентация
Видео
Семинар
Лекция 6. Основные понятия асимптотического анализа. Символы . Сравнение скоростей роста функций. Примеры.
Литература: [4, гл. 3].
Видео
Презентация
Семинар
Лекция 7. Предмет теории вероятностей. Случайные события и их свойства. Вероятность и способы её определения (классическое определение, геометрическая вероятность, частотное определение). Свойства вероятности. Условная вероятность и независимые события. Формула Байеса, формула полной вероятности. Схема испытаний Бернулли. Случайные графы. Понятие о «почти всех» объектах.
Литература: [6, гл. 1, 2].
Видео
Презентация
Семинар
Домашнее задание
Лекция 8. Случайные величины, примеры. Математическое ожидание, дисперсия и моменты случайной величины. Неравенства Маркова и Чебышева. Основные законы распределения случайных величин. Функция распределения случайных величин. Совместное распределение и независимость случайных величин.
Литература: [6, гл. 3].
Видео
Презентация
Семинар
Лекция 9. Закон больших чисел. Теорема Пуассона о схеме испытаний Бернулли. Теорема Муавра-Лапласа. Центральная предельная теорема. Метод Монте-Карло и примеры его применения.
Литература: [6, гл. 4, 10].
Презентация
Видео
Программа курса
Лекция 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. Выравнивание последовательностей. Рекуррентные соотношения для числа выравниваний и . Решение задачи о выравнивании последовательностей при помощи динамического программирования.
Литература: [5, §7.1, 13.1].
Презентация
Семинар
Видео
Лекция 4. Числа Фибоначчи: пример возникновения задачи, рекуррентное соотношение. Последовательности, задаваемые линейными рекуррентными соотношениями с постоянными коэффициентами. Характеристический многочлен рекуррентного соотношения. Общий вид решения.
Литература: [2, гл. 7], [5, §6.1, 6.2].
Презентация
Видео
Домашнее задание
Лекция 5. Графы: формальное определение и примеры. Основные подструктуры в графах (подграфы, порожденные подграфы, клики, независимые и доминирующие множества, паросочетания, цепи, циклы) и некоторые специальных классы графов (двудольные графы, полные графы, деревья). Изоморфизм графов. Связность графов, компоненты связности. Задача Эйлера о кёнигсбергских мостах. Гамильтоновы циклы. Универсальные последовательности и графы Де Брёйна.
Литература: [3, гл. 1], [5, §13.3], [7, гл. 2, 4].
Презентация
Видео
Семинар
Лекция 6. Основные понятия асимптотического анализа. Символы . Сравнение скоростей роста функций. Примеры.
Литература: [4, гл. 3].
Видео
Презентация
Семинар
Лекция 7. Предмет теории вероятностей. Случайные события и их свойства. Вероятность и способы её определения (классическое определение, геометрическая вероятность, частотное определение). Свойства вероятности. Условная вероятность и независимые события. Формула Байеса, формула полной вероятности. Схема испытаний Бернулли. Случайные графы. Понятие о «почти всех» объектах.
Литература: [6, гл. 1, 2].
Видео
Презентация
Семинар
Домашнее задание
Лекция 8. Случайные величины, примеры. Математическое ожидание, дисперсия и моменты случайной величины. Неравенства Маркова и Чебышева. Основные законы распределения случайных величин. Функция распределения случайных величин. Совместное распределение и независимость случайных величин.
Литература: [6, гл. 3].
Видео
Презентация
Семинар
Лекция 9. Закон больших чисел. Теорема Пуассона о схеме испытаний Бернулли. Теорема Муавра-Лапласа. Центральная предельная теорема. Метод Монте-Карло и примеры его применения.
Литература: [6, гл. 4, 10].
Презентация
Видео
Литература
[1] Н. Б. Алфутова, А. В. Устинов, Алгебра и теория чисел. Сборник задач для математических школ. — М.: МЦНМО, 2009.
[2] Н. Я. Виленкин, А. Н. Виленкин, П. А. Виленкин, Комбинаторика. — М.: ФИМА, МЦНМО, 2010.
[3] В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич, Лекции по теории графов. — М.: Либроком, 2009.
[4] Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн, Алгоритмы: построение и анализ. — М.: Вильямс, 2007.
[5] А. М. Райгородский, А. В. Савватеев, И. Д. Шкредов, Комбинаторика (методическое пособие для факультета биоинженерии и биоинформатики МГУ). — М.: Макс-пресс, 2005.
[6] Б. А.Севастьянов Курс теории вероятностей и математической статистики. М.: Наука. Гл. ред. физ.-мат. лит., 1982.— 256 с.
[7] Ф. Харари, Теория графов. — М.: Либроком, 2009.
[8] А. Х. Шахмейстер, Комбинаторика. Статистика. Вероятность. — М.: МЦНМО, 2010.
[9] Г. Эндрюс, Теория разбиений. — М.: Наука. 1982.
[2] Н. Я. Виленкин, А. Н. Виленкин, П. А. Виленкин, Комбинаторика. — М.: ФИМА, МЦНМО, 2010.
[3] В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич, Лекции по теории графов. — М.: Либроком, 2009.
[4] Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн, Алгоритмы: построение и анализ. — М.: Вильямс, 2007.
[5] А. М. Райгородский, А. В. Савватеев, И. Д. Шкредов, Комбинаторика (методическое пособие для факультета биоинженерии и биоинформатики МГУ). — М.: Макс-пресс, 2005.
[6] Б. А.Севастьянов Курс теории вероятностей и математической статистики. М.: Наука. Гл. ред. физ.-мат. лит., 1982.— 256 с.
[7] Ф. Харари, Теория графов. — М.: Либроком, 2009.
[8] А. Х. Шахмейстер, Комбинаторика. Статистика. Вероятность. — М.: МЦНМО, 2010.
[9] Г. Эндрюс, Теория разбиений. — М.: Наука. 1982.
Преподаватель
К.ф.-м.н, ассистент
кафедры математической
кибернетики факультета вычислительной математики и кибернетики МГУ. Занимается исследованием математических моделей дискретных управляющих систем и интересуется разработкой алгоритмов и систем автоматизации проектирования интегральных схем.
кафедры математической
кибернетики факультета вычислительной математики и кибернетики МГУ. Занимается исследованием математических моделей дискретных управляющих систем и интересуется разработкой алгоритмов и систем автоматизации проектирования интегральных схем.
Большой Каретный переулок, 19, ИППИ РАН,
м. Цветной Бульвар
hello@bioinfschool.ru
м. Цветной Бульвар
hello@bioinfschool.ru
Реквизиты
Некоммерческое партнерство содействия развитию биоинформатики «Биоинформатический семинар»
Адрес: 119269 г.Москва ул.Вавилова д.60/1 офис 19
ИНН \ КПП 7716450074 \ 773601001
ОГРН 1117799008030
ОКПО \ ОКАТО 91570039 \ 45293558000
Банк: ОАО «Сбербанк России» г. Москва
Расчетный счет 40703810938110001685
БИК 044525225
Кор. счет 30101810400000000225
Адрес: 119269 г.Москва ул.Вавилова д.60/1 офис 19
ИНН \ КПП 7716450074 \ 773601001
ОГРН 1117799008030
ОКПО \ ОКАТО 91570039 \ 45293558000
Банк: ОАО «Сбербанк России» г. Москва
Расчетный счет 40703810938110001685
БИК 044525225
Кор. счет 30101810400000000225
