Логотип

В корзине нет товаров
Книги> Дискретная, прикладная и вычислительная математика

Комбинаторика и теория вероятностей

  • Комбинаторика и теория вероятностей Райгородский А.М.  2013
    • Автор Райгородский А.М.
    • Раздел: Дискретная, прикладная и вычислительная математика
    • Страниц: 104
    • Переплёт: Мягкий
    • Год: 2013
    • ISBN: 978-5-91559-147-8
    • В продаже
    • Цена: 330 руб.
    • В корзину

Введение

   Книга представляет собой учебное пособие по комбинаторике и теории вероятностей. Она возникла на основе лекций по комбинаторике, информатике, теории вероятностей, которые ее автор в разные годы читал и продолжает читать на факультете биоинженерии и биоинформатики МГУ им. М.В. Ломоносова, в Школе Анализа Данных Яндекса, в Московском Физико-Техническом Институте и в совместном бакалавриате Российской Экономической Школы и Высшей Школы Экономики.
   Предметы, которым посвящена книга, изложены в ней достаточно неформально, что позволяет читателю быстро понять их суть. Более детально в книге изложены те разделы, которые редко в подробностях обсуждаются в литературе. И наоборот, те разделы, которые легко изучать по стандартным  учебникам, в книге расписаны конспективно - со ссылками на класические источники.
   Учебное пособие будет полезно студентам, начинающим специалистам и всем, кто интересуется основами комбинаторики и вероятности.

 

Введение

   Настоящая книга возникла как методическое пособие к курсам лекций, которые автор в разные годы читал и до сих пор читает на факультете биоинженерии и биоинформатики МГУ, на факультете инноваций и высоких технологий МФТИ, в совместном бакалавриате Российской экономической школы и Высшей школы экономики, в Школе анализа данных Яндекса. Все эти курсы объединены наличием в них базовой составляющей по комбинаторике и теории вероятностей. Иными словами, в основе каждого из них лежит некоторое количество простых понятий и фактов, которые возникают в указанных дисциплинах и без которых невозможно понимание более специфических — так сказать, «продвинутых» — результатов.
   Многие из этих фактов и понятий есть в классических учебниках и монографиях. Однако, во-первых, они разбросаны по разным книгам, а во-вторых, помимо них, эти книги содержат и массу другой информации. Как следствие, оказывается, что нет удобного источника, где были бы собраны и надлежащим образом позиционированы эти и только эти факты и понятия. По сути предлагаемая книга заполняет этот пробел.
   В книге сжато, лаконично и достаточно неформально вводятся все необходимые объекты и даются все необходимые утверждения о них. Если доказательство теоремы имеется в стандартном учебнике, то, как правило, оно не воспроизводится; на него лишь ставится удобная ссылка. Зато если доказательство мало доступно или нигде популярно не изложено, то ему уделяется значительное внимание. Например, так сделано в отношении формулы обращения Мёбиуса, которую мало где подробно обсуждают, или в отношении задач об оценках комбинаторных величин, которые крайне важны, но обычно возникают «сами собой» в чисто профессиональной литературе, и читатель вынужден догадываться, какие идеи за этим стоят.
   Есть в книге и достаточно нетривиальные вещи, характерные для курсов автора. Например, в той части, которая посвящена теории вероятностей, обсуждаются формулы обращения, позволяющие выразить распределения дискретных величин через их моменты (это очень важно в приложениях: например, для случайных графов), а также мартингалы (в дискретном случае) и некоторые связанные с ними неравенства концентрации меры. Эти вещи описаны так же неформально и без чрезмерного углубления в детали, как и все остальное. Однако так и проще не потеряться в дебрях материала.
   По аналогичному принципу устроены задачи, которые предлагаются в конце каждой темы.
   Таким образом, книга позволит четко систематизировать информацию, разбросанную по разным учебникам и задачникам (а зачастую и просто недоступную), и даст тот ее минимум, который необходим для адекватного восприятия курсов по комбинаторике, информатике, теории графов, теории алгоритмов, теории вероятностей и др.


Оглавление


Введение


Глава 1.
Базовые принципы комбинаторики


1.1. Основные правила комбинаторики
1.2. Принцип Дирихле
1.3. Формула включений и исключений
1.4. Факториал. Размещения, перестановки и сочетания. Бином Ньютона
Задачи по теме


Глава 2.
Числа сочетаний и простейшие тождества


2.1. Сочетания с повторениями
2.2. Полиномиальная формула
2.3. Свойства чисел сочетания: доказательство знакопостоянных тождеств. Треугольник Паскаля
Задачи по теме


Глава 3.
Еще тождества и элементы комбинаторного анализа


3.1. Частный случай формулы включений и исключений. Доказательство знакопеременных тождеств
3.2. Оценки для факториалов и биномиальных коэффициентов. Формула Стирлинга
Задачи по теме


Глава 4.
Обращение Мёбиуса


4.1. Функция Мёбиуса. Формула обращения Мёбиуса
4.2. Применение формулы Мёбиуса для подсчета числа циклических последовательностей
Задачи по теме


Глава 5. Разбиения


5.1. Основы комбинаторики разбиений: примеры задач
5.2. Разбиение чисел на слагаемые
Задачи по теме


Глава 6.
Фибоначчи и выравнивания


6.1. Несколько общих слов о рекуррентных соотношениях
6.2. Числа Фибоначчи
6.3. Выравнивание последовательностей
Задачи по теме


Глава 7.
Рекурсия и степенные ряды


7.1. Линейные рекуррентные соотношения с постоянными коэффициентами
7.2. Степенные ряды и производящие функции
7.3. Ряд Ньютона и числа Каталана
Задачи по теме


Глава 8.
Графы


8.1. Основы теории графов
8.2. Деревья и унициклические графы
8.3. Основы теории гиперграфов
Задачи по теме


Глава 9.
Простейшие вероятностные модели


9.1. Классическая вероятность
9.2. Схема Бернулли
9.3. Схема серий
Задачи по теме


Глава 10.
Общая вероятностная модель и понятие независимости


10.1. Общее конечное вероятностное пространство
10.2. Условные вероятности и независимость событий
10.3. Несколько слов о бесконечных вероятностных пространствах
Задачи по теме


Глава 11.
Распределения


11.1. Случайные величины и их распределения
11.2. Моменты распределений
11.3. Формула обращения и предельные теоремы пуассоновского типа
11.4. Нормальная аппроксимация
Задачи по теме


Глава 12.
Неравенства и законы больших чисел


12.1. Неравенства Чебышёва и Маркова
12.2. Уточнение неравенства Чебышёва в случае схемы Бернулли
12.3. Законы больших чисел
Задачи по теме


Глава 13.
Усиленный закон больших чисел и центральная предельная теорема


13.1. Виды сходимости последовательностей случайных величин
13.2. Неравенство Колмогорова
13.3. Усиленные законы больших чисел
13.4. Центральная предельная теорема
Задачи по теме


Глава 14.
Мартингал


14.1. Условные вероятности и математические ожидания относительно разбиений
14.2. Понятие о мартингале
14.3. Неравенство Азумы
Задачи по теме


Литература


Комментарии: (авторизуйтесь, чтобы оставить свой)