• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2018/2019

Теория алгоритмов

Статус: Курс обязательный (Прикладная математика и информатика)
Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 2-й курс, 4 модуль
Формат изучения: без онлайн-курса
Язык: английский
Кредиты: 3

Course Syllabus

Abstract

Целью данной дисциплины является освоение студентами основ теории сложности и различных типов алгоритмов, таких как вероятностные и параметризованные. В результате освоения дисциплины студент должен: знать: − основные классы языков в теории сложности; − основные примеры вероятностных алгоритмов; − некоторые примеры параметризованных алгоритмов; − связи между различными классами языков. уметь: − применять неравенство Чернова; − строить вероятностные алгоритмы; − доказывать PSPACE-полноту различных задач; − доказывать NP-полноту различных задач; − доказывать NL-полноту различных задач. владеть: − основными методами и инструментами теории сложности; − основами техниками построения вероятностных алгоритмов
Learning Objectives

Learning Objectives

  • освоение студентами основ теории сложности и различных типов алгоритмов, таких как вероятностные и параметризованные.
Expected Learning Outcomes

Expected Learning Outcomes

  • Знает основные современные алгоритмы, актуальные оценки их оптимальности. Умеет анализировать существующие материалы и ресурсы, в том числе англоязычные, для выбора оптимального алгоритма и фреймворка для решения практических задач. Решает проблемы, используя современные алгоритмы и фреймворки.
  • Знает основные классы теории сложности, связи между различными классами языков. Доказывает полноту различных задач. Владеет основными навыками и инструментами теории сложности.
  • Знает основные вероятностные и параметризованные алгоритмы. Использует алгоритмы при решении прикладных задач. Разрабатывает собственные библиотеки, необходимые для решения различных прикладных задач.
Course Contents

Course Contents

  • Машина Тьюринга. Иерархия по времени. Теорема Ладнера. Сложность по памяти
  • Класс NL. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. Полиномиальная иерархия.
  • Вероятностные алгоритмы. Оценки Чернова. Схемы. Теорема ВэлиантаВазирани.
Assessment Elements

Assessment Elements

  • non-blocking Домашнее задание №1
  • non-blocking Домашнее задание №2
  • non-blocking Контрольная работа
  • blocking Письменный экзамен
Interim Assessment

Interim Assessment

  • Interim assessment (4 module)
    0.125 * Домашнее задание №1 + 0.125 * Домашнее задание №2 + 0.25 * Контрольная работа + 0.5 * Письменный экзамен
Bibliography

Bibliography

Recommended Core Bibliography

  • Крупский В. Н. - ТЕОРИЯ АЛГОРИТМОВ. ВВЕДЕНИЕ В СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ 2-е изд., испр. и доп. Учебное пособие для бакалавриата и магистратуры - М.:Издательство Юрайт - 2019 - 117с. - ISBN: 978-5-534-04817-9 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/teoriya-algoritmov-vvedenie-v-slozhnost-vychisleniy-444131

Recommended Additional Bibliography

  • Tourlakis, G. J. (2012). Theory of Computation. Hoboken, N.J.: Wiley. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=451360