Компания
376,43
рейтинг
4 января 2014 в 14:49

Разработка → Лекции от Яндекса для тех, кто хочет провести каникулы с пользой. Дискретный анализ и теория вероятностей tutorial

Для тех, кому одного курса на праздники мало и кто хочет больше, продолжаем нашу серию курсов от Школы анализа данных Яндекса. Сегодня подошла очередь курса «Дискретный анализ и теория вероятностей» – даже более фундаментального, чем предыдущий. Но без него нельзя представить ещё большую часть современной обработки данных.

В рамках курса рассматриваются основные понятия и методы комбинаторного, дискретного и асимптотического анализа, теории вероятностей, статистики и на примере решения классических задач демонстрируется их применение.



Читает курс Андрей Райгородский. Доктор физико-математических наук. Профессор кафедры математической статистики и случайных процессов механико-математического факультета МГУ им. М. В. Ломоносова. Заведующий кафедрой Дискретной математики ФИВТ МФТИ. Профессор и научный руководитель бакалавриата кафедры «Анализ данных» факультета инноваций и высоких технологий МФТИ. Руководитель отдела теоретических и прикладных исследований компании «Яндекс». (Ещё больше можно узнать в статье о нём на Википедии).



Лекция 1. Основы перечислительной комбинаторики


Числа сочетания (с повторениями и без повторений), числа размещения (с повторениями и без повторений), перестановки. Бином Ньютона и биномиальные коэффициенты. Полиномиальная формула и полиномиальные коэффициенты. Формула включений и исключений.

Лекция 2. Обобщенная функция Мёбиуса и асимптотики


Простейшие комбинаторные тождества. Знакопеременные тождества. Использование формулы включений и исключений для доказательства тождеств. Функция Мёбиуса и формула обращения Мёбиуса. Подсчет числа циклических последовательностей. Элементарные оценки факториалов, биномиальных коэффициентов и пр. Понятие об энтропии. Неравенство Чернова. Формула Стирлинга (б/д). Асимптотики для биномиальных коэффициентов и пр.

Лекция 3. Деревья и унициклические графы


Основные понятия теории графов. Перечисление деревьев на n вершинах (формула Кэли): подход с производящими функциями; подход с использованием биекции между множеством деревьев и множеством размещений с повторениями (коды Прюфера). Изоморфизмы и автоморфизмы графов. Сводка результатов по перечислению графов.

Лекция 4. Разбиение чисел на слагаемые


Задачи о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения. Рекуррентные соотношения для функций разбиения. Харди-Рамануджана (б/д).

Лекция 5. Производящие функции и линейные рекуррентные соотношения


Линейные рекуррентные соотношения с постоянными коэффициентами. Степенные ряды и производящие функции. Применение степенных рядов и производящих функций для доказательства комбинаторных тождеств. Применение степенных рядов и производящих функций для решения рекуррентных соотношений. Числа Каталана, Стирлинга, Бернулли и др. Их применения.

Лекция 6. Хроматические числа графов и Кнезеровский граф


Хроматические числа графов. Гипотеза Кнезера. Теорема Ловаса.

Лекция 7. Классическое определение вероятности, схема Бернулли и их применение к числам Рамсея


Классическое определение вероятности. Геометрические вероятности. Парадокс Бертрана. Условные вероятности. Независимость событий. Формулы полной вероятности и Байеса. Схема Бернулли. Полиномиальная схема. Схема серий. Случайные блуждания. Понятие о случайном графе. Перколяция. Метод Монте-Карло.

Лекции 8-9. Локальная лемма Ловаса. Теория вероятностей (часть 1, часть 2)


Числа Рамсея. Раскраски гиперграфов. Покрытие графов линейными лесами.

Лекция 10. Распределения случайных величин


Дискретные и абсолютно непрерывные распределения. Основные виды распределений: биномиальное, геометрическое, пуассоновское, гипергеометрическое, равномерное, нормальное, показательное, гамма-распределение, хи-квадрат, Стьюдента, Фишера и пр. Числовые характеристики распределений: математическое ожидание, дисперсия, моменты, факториальные моменты. Совместные распределения. Ковариация и корреляция. Независимость и некоррелированность случайных величин. Понятие о вариационном ряде. Распределения, математические ожидания, дисперсии и ковариации порядковых статистик.

Лекции 11-12. Предельные теоремы (часть 1, часть 2)


Неравенства Маркова и Чебышёва. Закон больших чисел для схемы Бернулли. Закон больших чисел в форме Чебышёва. Закон больших чисел в форме Хинчина. Неравенство Колмогорова. Усиленный закон больших чисел. Предельные теоремы Муавра-Лапласа для схемы Бернулли (локальная и интегральная). Предельная теорема Пуассона для схемы серий. Производящие и характеристические функции. Центральная предельная теорема (различные формулировки; доказательство только для случая независимых одинаково распределенных случайных величин).

Лекция 13. Размерность Вапника-Червоненкиса


Понятие о выборке и выборочном пространстве. Точечное оценивание параметров. Несмещенность, состоятельность и пр. Методы моментов и максимального правдоподобия. Доверительное оценивание. Методы построения доверительных интервалов.

Update: все лекции курса «Дискретный анализ и теория вероятностей» в виде открытой папки на Яндекс.Диске.
Автор: @anton
Яндекс
рейтинг 376,43

Комментарии (21)

  • +9
    Очень хотелось бы увидеть курс «Цифровая обработка сигналов» с современными методами.
    • 0
      А какие методы там современные?:)
      Базовый курс всегда одинаковый, а что-то новенькое там на таких глубинах, до которых копать уже только спецом став. В 95% задачах ничего из новинок не используется. Или вы под «ЦОС» подразумеваете методы распознавания изображений?
      • +2
        Лично меня интересует обработка звука, распознавание речи и определение частоты основного тона. Есть разные подходы и было бы интересно именно в академическом стиле увидеть их изложение, т.е. цельным курсом.
        • 0
          Хмм. Всё-таки обычно в общих курсах заточенных подходов не дают, разве что какая-нибудь компания специально для себя курс пишет. Методов такого уровня десятки, а каждому посвятить нужно 1-2 лекции. Тот же фильтр Калмана, если его честно выводить со всей математикой растягивается на 2 лекции, а без него никакой курс с обработкой данных представить нельзя.
          Конкретно про обработку аудио, я слышал, ОТиПЛ сам иногда хорошие курсы проводит, или под его патронатом они идут.
    • +3
      На Coursera было два курса по ЦОС:
      Digital Signal Processing
      Image and video processing: From Mars to Hollywood with a stop at the hospital

      И планируется еще один:
      Fundamentals of Digital Image and Video Processing

      Но именно на ваши вопросы — я не уверен, что это именно фундаментальный университетский курс.
    • 0
      Поищите книги Юкио Сато
    • +1
      Записано в пожелания.
  • +9
    Так держать ЯНДЕКС!
  • 0
    Ну скорее Лекции от Яндекса, а не курс.
    • +2
      Ну ок, согласен. Переименовал пост.
  • +7
    Мой уровень математики, после прослушивания лекций, показал, что он вовсе не уровень.
  • 0
    тут с именами файлов по-лучше, чем в Машинном обучении, но тоже не очень-то.

    Кто-то из сотрудников пробовал скачивать эти лекции по приведенным ссылкам, а потом смотреть, до того, как публиковать их на хабре? Ни у кого никаких вопросов не возникло?

    у меня три простых вопроса:
    1. неужели дата в виде dd.mm.yyyy (ddmmyyyy) удобнее в имени файла, чем yyyymmdd (или через точки)?
    2. неужели сложно, везде выдерживать один формат имени файла?
    3. а если кто-то ошибся — исправить, привести к единому?
    • 0
      Спасибо за все ваши замечания, приведём после праздников всё к единому виду.
  • +2
    А лекции этого года не выложили по причине искрометных шуток Райгора на тему «Есть два типа задач: задача о том как набрать и задача о том, как набраться» (так он называл задачи о разбиениях чисел на слагаемые)?)
    • 0
      Не поэтому. Но версия хорошая :)
  • +3
    Очень хотелось бы увидеть задачи, которые разбираются на семинарах по дискретному анализу в ШАД.
    • 0
      Ок, записано.
  • +1
    Большое спасибо за видео, однако, смею заметить, что плохо видна доска, это на будущее (что-то вроде пожеланий).
  • 0
    Лектор добротный. Спасибо за лекции.
    А задачи с этого курса есть? Или после лекций идет чисто теоретический семинар?
    • 0
      Задачи были и на семинарах, а также и убийственные домашки, которые мы ТЕХали днями).
      • +2
        А задачи можно где-то посмотреть?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка