• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
2020/2021

Вероятностные алгоритмы

Статус: Дисциплина общефакультетского пула
Когда читается: 1, 2 модуль
Охват аудитории: для своего кампуса
Язык: русский
Кредиты: 2

Программа дисциплины

Аннотация

При определенных обстоятельства использование случайных бит позволяет построить для задачи значительно более простой алгоритм, чем детерминированные алгоритмы для той же задачи. Более того использование случайных бит может даже существенно ускорить время выполнения алгоритма. В курсе будут приведены основные методы построения вероятностных алгоритмов, а также приведены классические примеры алгоритмов. Отдельная часть курса будет посвящена способам конвертации случайного алгоритма в детерминированный с некоторой потерей в быстродействии.
Цель освоения дисциплины

Цель освоения дисциплины

  • формирование у студентов теоретических знаний и практических навыков в области построения алгоритмов, чья работа может зависеть от случайных бит. А также освоения стандартных методов дерандомизации вероятностных алгоритмов.
Планируемые результаты обучения

Планируемые результаты обучения

  • Знает основные классы вероятностных алгоритмов
  • Знает основные способы модификации базовых вероятностных алгоритмов, применяемые для различных задач.
  • Знает основные методы дерандомизации случайных алгоритмов
  • Подбирает оптимальный алгоритм для конкретной практической задачи, анализирует его эффективность.
  • Умеет использовать базовые алгоритмы и подходы и модифицирует их, исходя из специфики решаемой задачи
Содержание учебной дисциплины

Содержание учебной дисциплины

  • Минимальный разрез. Параметризованный алгоритм для наибольшего дерева.
  • Неравенство Маркова и Чебышева. Задача о стабильных браках
  • Задача о собирателях купонов.
  • Оценки Чернова, покраска гиперграфов.
  • Методы дерандомизации.
  • Кодирование цветом. d - кластеризация
  • Мотонный локальный поиск
  • Расширяющиеся графы.
  • Вероятностные методы в применении к MAXSAT.
  • Оценки Чернова, округление решений.
  • Метод условной вероятности.
  • Ядро для MAX-R-SAT
  • Локальная лемма Ловаса
  • Алгебраические методы
Элементы контроля

Элементы контроля

  • неблокирующий Домашнее задание №1
  • блокирующий Письменный экзамен №1
Промежуточная аттестация

Промежуточная аттестация

  • Промежуточная аттестация (2 модуль)
    0.59 * Домашнее задание №1 + 0.41 * Письменный экзамен №1
Список литературы

Список литературы

Рекомендуемая основная литература

  • Алгоритмы и структуры данных : учеб.пособие, Гагарина Л. Г., Колдаев В. Д., 2009
  • Алгоритмы и структуры данных, Вирт Н., Подшивалова Д. Б., 2001

Рекомендуемая дополнительная литература

  • Probability and computing : randomization and probabilistic techniques in algorithms and data analysis, Mitzenmacher, M., Upfal, E., 2017
  • The probabilistic method, Alon N., Spencer J. H., 2008