litceysel.ru
добавить свой файл
1
РОССИЙСКАЯ АКАДЕМИЯ НАУК


Федеральное государственное бюджетное учреждение науки

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

Сибирского отделения Российской академии наук


ПРИНЯТО

Ученым советом Института

Протокол № 5 от 21.06.2012 г.

Председатель Ученого совета

______________ак. И.В. Бычков


РАБОЧАЯ ПРОГРАММА


ТЕОРИЯ СЛОЖНОСТИ АЛГОРИТМОВ


ФД.А.05


Специальность 05.13.11

«Математическое и программное обеспечение вычислительных машин,

комплексов и компьютерных сетей»


г. Иркутск


2012


  1. Цели и задачи дисциплины

Цель дисциплины: рассмотреть базовые понятия и концепции теории алгоритмической сложности.

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


2. Место дисциплины в структуре ООП

Данная дисциплина относится к группе факультативных дисциплин образовательной составляющей ООП ППО (в соответствии с Федеральными государственными требованиями (ФГТ)).

Содержание дисциплины опирается на знания, приобретенные ранее при изучении дисциплин «Дискретная математика», «Математическая логика». Для выполнения практических заданий аспиранты должны владеть базовыми понятиями перечисленных курсов.


3. Требования к уровню освоения содержания дисциплины

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


  • Владеть базовыми принципами сводимости одних комбинаторных задач к другим.

  • Освоить принципы построения приближенных алгоритмов для решения NP-трудных комбинаторных задач поиска.

  • Освоить принципы построения эвристических алгоритмов для решения NP-трудных комбинаторных задач.


4. Структура и содержание дисциплины


Общая трудоемкость дисциплины составляет 3 зачетных единицы - 108 часов.

4.1. Структура дисциплины



Наименование дисциплины

Объем учебной работы (в часах)

Вид итогового контроля

Всего

Всего аудит.

Из аудиторных

Сам. работа

Лекции

Лаб.

Прак.

КСР

1.

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

108

72

48




24




36





4.2. Содержание дисциплины

4.2.1. Разделы дисциплины и виды занятий



Раздел дисциплины

Виды учебной работы и трудоемкость (в часах)

Самост. работа

Лекции

Лаб.

Прак.

КСР

1

Основные классы вычислительной (временной) сложности

4




2




4

2

Сводимость по Карпу и понятие NP-полноты. Теорема Кука

8




4




4

3

Базовые NP-полные задачи

8




4




4

4

Понятие NP-трудности и некоторые NP-трудные задачи

8




4




4

5

Приближенные алгоритмы

4





2




4

6

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

8




2




4

7

Теорема Рамсея и вероятностный метод в теории графов

2




2




4

8

Полиномиальная иерархия и схемная сложность

2




2




4

9

Структурная теория сложности алгоритмов и современная криптография

4




2




4


4.2.2 Содержание разделов дисциплины




Наименование раздела дисциплины


Содержание раздела

Форма проведения



Основные классы вычислительной (временной) сложности

Задачи распознавания двоичных языков. Класс P. Полиномиальные недетерминированные вычисления и классы NP и co-NP. Основная гипотеза теории вычислительной сложности.

Лекции, практ. занятия,самост. работа



Сводимость по Карпу и понятие NP-полноты. Теорема Кука

Понятие сводимости по Карпу для двоичных языков и проблем распознавания. Свойства сводимости по Карпу, примеры. Преобразования Цейтина для булевых уравнений. Теорема Кука.

Лекции, практ. занятия,самост. работа



Базовые NP-полные задачи

NP-полнота ряда комбинаторных задач (3-ВЫПОЛНИМОСТЬ, совместность квадратичных систем над полем GF(2), 0-1-целочисленное линейное программирование, задачи на графах, задачи о сочетаниях и покрытиях, задачи 0-1-РЮКЗАК и РАЗБИЕНИЕ). Псевдополиномиальные алгоритмы и сильная NP-полнота.

Лекции, практ. занятия,

самост. работа



Понятие NP-трудности и некоторые NP-трудные задачи

Оракульная машина Тьюринга и полиномиальная сводимость по Тьюрингу. Понятие NP-трудности и некоторые NP-трудные задачи. Примеры NP-трудных задач, не являющихся алгоритмически разрешимыми.

Лекции, практ. занятия, самост. работа



Приближенные алгоритмы

NP-трудная задача об упаковке контейнеров и приближенный алгоритм ее решения. Понятие погрешности приближенного алгоритма. Приближенные алгоритмы для задачи поиска минимального вершинного покрытия. Пример алгоритма, не являющегося дельта-приближенным ни для какого дельта.

Лекции, практ. занятия,самост. работа



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

Вероятностная машина Тьюринга и полиномиальное вероятностное время. Классы RP, co-RP, BPP и ZPP. Задача проверки простоты натуральных чисел и полиномиальный вероятностный алгоритм ее решения (тест Соловея-Штрассена).

Лекции, практ. занятия,

самост. работа



Теорема Рамсея и вероятностный метод в теории графов

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

Лекции, практ. занятия,

самост. работа



Полиномиальная иерархия и схемная сложность

Схемы из функциональных элементов над различными базисами. Возможность «распознавания» произвольного двоичного языка семейством схем экспоненциальной сложности. Класс P/poly. Полиномиальная иерархия. Теорема Стокмейера. Теорема Карпа-Липтона. Теорема Адлмана о включении BPP в P/poly. Теорема Шеннона о схемной сложности почти всех булевых функций.

Лекции, практ. занятия,

самост. работа




Структурная теория сложности алгоритмов и современная криптография

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

Лекции, практ. занятия,

самост. работа


5. Образовательные технологии

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


6. Учебно-методическое обеспечение самостоятельной работы аспирантов

Используются виды самостоятельной работы аспиранта: в читальном зале библиотеки, на рабочих местах с доступом к ресурсам Internet и в домашних условиях. Порядок выполнения самостоятельной работы соответствует программе курса и контролируется в ходе лекционных занятий. Самостоятельная работа подкрепляется учебно-методическим и информационным обеспечением, включающим рекомендованные учебники и учебно-методические пособия.


7. Учебно-методическое обеспечение дисциплины

а) Основная литература

  1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ. – «Вильямс», 2007. – 1290 с.

  2. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. – «Вильямс», 2002. – 528 с.

  3. Goldreich O. Computational Complexity: A Conceptual Perspective. – Cambridge University Press, 2008. – 606 p.
  4. Коблиц Н. Курс теории чисел и криптографии. – М.: «ТВП», 2001. – 254 с.



б) Дополнительная литература

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

  2. Papadimitriou C.H. Computational complexity. – Addison Wesley, 1994. – 523 p.

  3. Wegener I. Complexity Theory. Exploring the Limits of Efficient Algorithms.– Springer, 2003. – 308 p.

  4. Агибалов Г.П. Избранные теоремы начального курса криптографии. – Томск: Изд-во ТГУ, 2005. – 112 с.

в) Интернет-источники

  1. Методические и учебные пособия на сайте Иркутского суперкомпьютерного центра СО РАН hpc.icc.ru/

  2. Интернет-университет информационных технологий www.intuit.ru.

  3. Интернет-университет суперкомпьютерных технологий www.hpcu.ru.

  4. Сайт лаборатории Параллельных информационных технологий НИВЦ МГУ www.parallel.ru.

  5. Межведомственный суперкомпьютерный центр РАН www.jscc.ru.

  6. Электронная библиотека механико- математического факультета МГУ lib.mexmat.ru.

  7. Электронные ресурсы издательства Springer http://link.springer.com/search?facet-content-type=%22Book%22&showAll=false .

  8. Электронные ресурсы издательства Elsevier http://link.springer.com/search?facet-content-type=%22Book%22&showAll=false.
  9. Национальный Открытый Университет "ИНТУИТ"- текстовые и видеокурсы по различным наукам http://www.intuit.ru/

  10. Общероссийский математический портал Math-Net.Ru

  11. Видеотека лекций по математике http://www.mathnet.ru/php/presentation.phtml?eventID=15&option_lang=rus#PRELIST15

  12. Единая коллекция цифровых образовательных ресурсов http://school-collection.edu.ru/catalog/rubr/75f2ec40-e574-10d2-24eb-dc9b3d288563/25892/?interface=themcol

  13. Видеолекции ведущих ученых мира http://www.academicearth.org/subjects/algebra.


  14. MPI. www.mpi-forum.org

  15. OpenMP. www.openmp.org

  16. DVM-система. www.keldysh.ru/dvm

  17. NVIDIA CUDA Zone. www.nvidia.ru/object/cuda_home_new_ru.html

  18. NVIDIA Developer Zone. http://developer.nvidia.com/cuda-downloads
  19. NVIDIA Tesla. www.nvidia.ru/page/tesla_computing_solutions.html


  20. NVIDIA Tesla. Инструменты разработчика. www.nvidia.ru/object/tesla_software_ru.html

  21. CUDA Documents. http://docs.nvidia.com/cuda/index.html.

8. Материально-техническое обеспечение дисциплины



Наименование

Кол- во

1

Библиотечный фонд ИДСТУ СО РАН




2

Библиотечный фонд научной библиотеки ИНЦ СО РАН




3

Учебные классы ИДСТУ СО РАН

С общим количеством:

- посадочных мест

- рабочих мест (компьютер+монитор)

- проекторов, экранов

4


100

12

3

4

Рабочие места с выходом в интернет

31

5

Вычислительные системы коллективного пользования ИДСТУ СО РАН


Из них:

Вычислительных кластеров с архитектурой x86

Вычислительных кластеров с архитектурой x86_64

Вычислительных кластеров с архитектурой x86_64+GPU


3


1

1

1

Программа составлена в соответствии с требованиями следующих нормативных документов:

  1. Федеральные государственные требования к структуре основной профессиональной образовательной программы послевузовского профессионального образования (аспирантура): - приказ Минобрнауки России от 16.03.2011 № 1365.

  2. Паспорт научной специальности 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», разработанный экспертами ВАК Минобрнауки России в рамках Номенклатуры специальности научных работников (утверждена приказом Минобрнауки РФ от 25.02.2009 №59, в ред. Приказом Минобрнауки РФ от 11.08.2009 №294, от 10.01.2012 №5).

  3. Программа - минимум кандидатских экзаменов по специальности 05.13.11 - «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», утвержденная приказом Минобрнауки РФ от 08.10.2007 № 274 «Об утверждении программы кандидатских экзаменов».


Автор:

к.т.н. ______________________ А.А. Семенов


Ответственный за специальность

д.т.н. ______________________ Г.А. Опарин