Опубликована: 22.04.2015 | Уровень: для всех | Стоимость: 1.00 руб. | Длительность: 
В рамках курса рассматриваются основные понятия и методы комбинаторного, дискретного и асимптотического анализа, теории вероятностей, статистики и на примере решения классических задач демонстрируется их применение.

План занятий

ЗанятиеЗаголовок <<Дата изучения
-
Лекция 1
Основы перечислительной комбинаторики
Числа сочетания (с повторениями и без повторений), числа размещения (с повторениями и без повторений), перестановки. Бином Ньютона и биномиальные коэффициенты. Полиномиальная формула и полиномиальные коэффициенты. Формула включений и исключений.
Оглавление
    -
    Тест 1
    36 минут
    -
    Лекция 2
    Обобщенная функция Мёбиуса и асимптотики
    Простейшие комбинаторные тождества. Знакопеременные тождества. Использование формулы включений и исключений для доказательства тождеств. Функция Мёбиуса и формула обращения Мёбиуса. Подсчет числа циклических последовательностей. Элементарные оценки факториалов, биномиальных коэффициентов и пр. Понятие об энтропии. Неравенство Чернова. Формула Стирлинга (б/д). Асимптотики для биномиальных коэффициентов и пр.
    Оглавление
      -
      Тест 2
      36 минут
      -
      Лекция 3
      Деревья и унициклические графы
      Основные понятия теории графов. Перечисление деревьев на n вершинах (формула Кэли): подход с производящими функциями; подход с использованием биекции между множеством деревьев и множеством размещений с повторениями (коды Прюфера). Изоморфизмы и автоморфизмы графов. Сводка результатов по перечислению графов.
      Оглавление
        -
        Тест 3
        36 минут
        -
        Лекция 4
        Разбиение чисел на слагаемые
        Задачи о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения. Рекуррентные соотношения для функций разбиения. Харди-Рамануджана (б/д).
        Оглавление
          -
          Тест 4
          36 минут
          -
          Лекция 5
          Производящие функции и линейные рекуррентные соотношения
          Линейные рекуррентные соотношения с постоянными коэффициентами. Степенные ряды и производящие функции. Применение степенных рядов и производящих функций для доказательства комбинаторных тождеств. Применение степенных рядов и производящих функций для решения рекуррентных соотношений. Числа Каталана, Стирлинга, Бернулли и др. Их применения.
          Оглавление
            -
            Тест 5
            36 минут
            -
            Лекция 6
            Хроматические числа графов и Кнезеровский граф
            Хроматические числа графов. Гипотеза Кнезера. Теорема Ловаса.
            Оглавление
              -
              Тест 6
              36 минут
              -
              Лекция 7
              Классическое определение вероятности, схема Бернулли и их применение к числам Рамсея
              Классическое определение вероятности. Геометрические вероятности. Парадокс Бертрана. Условные вероятности. Независимость событий. Формулы полной вероятности и Байеса. Схема Бернулли. Полиномиальная схема. Схема серий. Случайные блуждания. Понятие о случайном графе. Перколяция. Метод Монте-Карло.
              Оглавление
                -
                Тест 7
                36 минут
                -
                Лекция 8
                Локальная лемма Ловаса. Начала теории вероятностей
                Числа Рамсея. Раскраски гиперграфов.
                Оглавление
                  -
                  Лекция 9
                  Локальная лемма Ловаса. Теория вероятностей
                  Покрытие графов линейными лесами.
                  Оглавление
                    -
                    Тест 8
                    36 минут
                    -
                    Лекция 10
                    Распределения случайных величин
                    Дискретные и абсолютно непрерывные распределения. Основные виды распределений: биномиальное, геометрическое, пуассоновское, гипергеометрическое, равномерное, нормальное, показательное, гамма-распределение, хи-квадрат, Стьюдента, Фишера и пр. Числовые характеристики распределений: математическое ожидание, дисперсия, моменты, факториальные моменты. Совместные распределения. Ковариация и корреляция. Независимость и некоррелированность случайных величин. Понятие о вариационном ряде. Распределения, математические ожидания, дисперсии и ковариации порядковых статистик.
                    Оглавление
                      -
                      Тест 9
                      36 минут
                      -
                      Лекция 11
                      Предельные теоремы
                      Неравенства Маркова и Чебышёва. Закон больших чисел для схемы Бернулли. Закон больших чисел в форме Чебышёва. Закон больших чисел в форме Хинчина. Неравенство Колмогорова. Усиленный закон больших чисел. Предельные теоремы Муавра-Лапласа для схемы Бернулли (локальная и интегральная).
                      Оглавление
                        -
                        Лекция 12
                        Предельные теоремы (продолжение)
                        Предельная теорема Пуассона для схемы серий. Производящие и характеристические функции. Центральная предельная теорема (различные формулировки; доказательство только для случая независимых одинаково распределенных случайных величин).
                        Оглавление
                          -
                          Тест 10
                          36 минут
                          -
                          Лекция 13
                          Размерность Вапника-Червоненкиса
                          Понятие о выборке и выборочном пространстве. Точечное оценивание параметров. Несмещенность, состоятельность и пр. Методы моментов и максимального правдоподобия. Доверительное оценивание. Методы построения доверительных интервалов.
                          Оглавление
                            -
                            Тест 11
                            36 минут
                            -
                            5 часов
                            -