Theory of Algorithms

2018/2019

Academic Year

ENG

Instruction in English

3

ECTS credits

Delivered at:

Department of Informatics

Course type:

Compulsory course

When:

2 year, 4 module

Instructor

Bliznets, Ivan

Course Syllabus

Abstract

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

Learning Objectives

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

Expected Learning Outcomes

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

Course Contents

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

Assessment Elements

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

Interim Assessment

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

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