Спецкурс «Теория сложности вычислений»




Скачать 42.91 Kb.
Дата10.03.2016
Размер42.91 Kb.

Спецкурс «Теория сложности вычислений»


(Лектор — А. А. Татузов)

Осенний семестр, полугодовой спецкурс

Аннотация

В курсе изучаются способы классификация вычислительных задач относительно их вычислительной сложности. Разбирается понятие эффективного вычисления, приводится и доказывается ряд теорем об иерархии и ускорении. Приводятся различные нижние оценки сложности вычислений. Вводится понятие релятивизации (вычисления с оракулом) и доказываются теоремы о невозможности разрешения ряда сложностных проблем (в том числе P=NP) с помощью релятивизируемых методов. В курсе рассматриваются основные сложностные классы и доказываются теоремы об их взаимосвязи, в том числе рассматриваются классы полиномиальной иерархии, классы языков, имеющих интерактивные доказательства, экспоненциальные классы сложностей, функциональные классы сложностей, классы, связанные с понятиями параллельной и коммуникационной сложности.


Программа


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

  2. Теоремы об иерархии и ускорении. Универсальные машины Тьюринга.

  3. Однородная и неоднородная модели. Понятие эффективного вычисления. Тезис Эдмондса (полиномиальный тезис Тьюринга). Классы P и P∕poly. Вычисление с оракулом. Релятивизация.

  4. Недетерминированные вычисления. Класс NP. Класс UP. Сводимость по Карпу. Сводимость по Куку. Полные задачи. Самосводимость.

  5. Полиномиальная иерархия.

  6. Класс PSPACE.

  7. Экспоненциальные классы сложностей.

  8. Вероятностная машина Тьюринга. Классы RP, BPP и BP ⋅ NP. Рандомизированная самосводимость.

  9. Интерактивные доказательства. Классы IP и AM.

  10. Сложность по объему памяти. Классы L, NL.

  11. Параллельная сложность. Классы NC, AC. Проблема распараллеливания алгоритма. Распараллеливаемость задачи. P-полнота.

  12. Коммуникационная сложность. Классы PCC, NPCC и соотношения между ними.

  13. Нижние оценки сложности.

  14. Зоопарк сложностных классов.

Список рекомендуемой литературы


  1. Кузюрин Н. Н., Фомин С. А. Эффективные алгоритмы и сложность вычислений: Учебное пособие. - М.: МФТИ, 2007. - 312 с.

  2. Гэри М., Джонcон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ. - М.: Мир, 1982. - 416 с.

  3. Китаев А., Шень А., Вялый М.. Классические и квантовые вычисления. - М.: МЦНМО, 1999. - 192 с.

  4. Christos H. Papadimitiou. Computational Complexity. - Addison-Wesley, 1994. - 523 с.

  5. S. Arora, B. Barak. Computational Complexity: A Modern Approach. - Cambridge University Press, 2009. - 594 с.

  6. O. Goldreich. Computational Complexity: A Conceptual Perspective. - Cambridge University Press, 2008. - 632 с.

ПОЛУГОДОВОЙ СПЕЦКУРС ДЛЯ АСПИРАНТОВ


«ДИСКРЕТНЫЕ ФУНКЦИИ В СИМВОЛИЧЕСКОЙ ДИНАМИКЕ»

(с приложениями в теории кодирования и криптографии)

Несмотря на то, что символическая динамика (symbolic dynamics) является разделом общей теории динамических систем, в отечественной научной литературе этот раздел математики представлен недостаточно. В частности, отсутствуют учебники(учебные пособия) и монографии на русском языке. Вместе с тем, основные идеи символической динамики сущностно связаны с теорией информации, теорией кодирования, теорией автоматов, теорией графов и другими разделами дискретной математики. Кроме того, математические методы, применяемые в символической динамике, позволяют выявить новые подходы к решению задач теории кодирования и криптографии.

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

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

ПЛАН ЛЕКЦИЙ


(осенний семестр — 32 часа )

Автор курса, лектор — доцент кафедры ИБ ВМК О.А.Логачев.

1.Сдвиговые пространства ( s-пространства или сдвиги). Языки. Неприводимые s-пространства. Скользящие блоковые коды. Сопряженность s-пространств. Понятие фактора s-пространства.
2.Сверточные коды и их свойства.
3.S-пространства конечного типа. Графы и ассоциированные с ними s-пространства. Представление s-пространств конечного типа с помощью графов. Расщепление.
4.Софические s-пространства. Характеризация софических s-пространств и их rr-представления.
5.Энтропия и ее основные свойства. Теорема Перрона-Фробениуса. Вычисление энтропии.
6.Метрические пространства. Компактность. Теоремы Больцано- Вейерштрасса и Гейне — Бореля.
7.Динамические системы. Инварианты динамических систем. Гомоморфизмы и сопряжннность динамических систем. Теорема Куртиса-Линдона- Хедлунда.
8.Дзета-функция динамической системы и примеры ее вычисления.
9.Разбиения Маркова динамических систем. Примеры.
10.Символическая динамика и криптографические примитивы. Задачи частичного и локального обращения эндоморфизмов s-систем. Примеры. Локальная обратимость и синхронизируемость.

ЛИТЕРАТУРА

1.Michael Brin and Gurret Stuck. Introduction to Dynamical Systems. Cambridge University Press, 2003, pp.240.

2.Douglas Lind and Brian Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, 1995, pp.495.

3.Bruce P. Kitchens. Symbolic Dynamics. One-Sided, Two-Sided and Countable State Markov Shifts. Springer, 1997, 262.

4.G.A. Hedlund. Endomorphisms and Automorphisms of the Shift Dynamical System. Math. Systems Theory, 3 (1969), pp. 320-375.



5.П.Биллингслей. Эргодическая теория и информация. МИР, Москва 1969, С.238.


База данных защищена авторским правом ©uverenniy.ru 2016
обратиться к администрации

    Главная страница