Методические указания к курсу ”Сложность вычислений” (стр. 1 )

МЕТОДИЧЕСКИЕ УКАЗАНИЯ  К  КУРСУ  ”СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ”

  Гамова  А. Н.

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

Введение. Определение  сложности  вычислений.  Вычислительные модели.  Меры  сложности.  Сложностные  классы  P  и  NP. 

Тема  1.  Машина  Тьюринга  как  вычислительная  модель.

§ 1.  Детерминированная  машина  Тьюринга.

§ 2.  Языки, допускаемые  машиной  Тьюринга.

§ 3.  Многоленточная  машина  Тьюринга.

§ 4.  Недетерминированная  машина  Тьюринга.

§ 5.  Имитация  машины  Тьюринга  на  компьютере  и  компьютера  на  машине  Тьюринга.

Тема  2.  Проблемы,  решаемые  за  полиномиальное  время

Теория

[1],  стр.94 - 122 (алгоритмы  сортировок)

[1],  стр.255 - 279 (умножение матриц)

[1],  стр.128 - 161 (операции  над  множествами)

[1],  стр.197 - 251 (алгоритмы  на  графах).

Тема 3.  Труднорешаемые  проблемы.

§ 1.  Классы  P  и  NP.

§ 3.  Полиномиальное  сведение.

§ 4.  NP – полные  проблемы.

  4.1.  Проблема  выполнимости  булевой  функции (ВЫП).

  4.2.  NP – полнота  проблемы  выполнимости  КНФ  (КНФ).

  4.3.  NP – полнота  проблемы  выполнимости  3-КНФ  (3-КНФ).

  4.4.  Проблемы, к  которым  сводится  проблема  3-КНФ:

Проблема  независимого  множества  (НМ).

Проблема  узельного  покрытия (УП).

Проблема  ориентированного  гамильтонова  цикла (ОГЦ).

Проблемы,  к  которым  сводится  проблема  ОГЦ:

Проблема  неориентированного  гамильтонова  цикла (НГЦ).

Проблема  коммивояжера (ПК)

  Теория

[2],  стр. 423 – 472.

[1], стр. 404 – 440.

[2], стр. 473-477.

Тема 4.  Другие  сложностные  классы.

§ 1  Классы  PS  и  NPS.  PS -  полнота.  Булевы  фукнкции  с  кванторами (КБФ).

§ 2.  Классы  языков,  основанных  на  рандомизации.

Быстрая сортировка  как  пример  рандомизированного  алгоритма. Язык  рандомизированной  машины  Тьюринга. Класс  RP. Класс  ZPP.

Теория

[1], стр. 440 – 445.

[2],  стр. 499 – 509.

Тема 5.  Сложность  арифметических  проблем.

§ 1.  Сложность  проверки  простоты  числа.

§ 2.  Сложность  вычислений  в  модулярной  арифметике.

  § 3.  Рандомизированная  полиномиальная  проверка  простоты.

  § 4.  Недетерминированные  проверки  простоты.

Теория

[3],  проверка  простоты.

[3],  построение  больших  простых  чисел.

[3],  алгоритмы  факторизации.

[2], стр. 509-519.

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

Теория

  [1], приближенные вычисления. 

  Методические указания к самостоятельной  работе

  по курсу  “Сложность вычислений”

Введение. Определение  сложности  вычислений.  Вычислительные модели.  Меры  сложности.  Сложностные  классы  P  и  NP. 

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

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

Третий  путь аксиоматический, здесь Блюмом  были  предложены  две  аксиомы  меры сложности.  Из  доказанных  в  этой  теории  теорем  следует, что существуют  вычислимые  функции, не  имеющие  “наилучшей ”  программы  вычислений.

Наиболее  употребимые  меры  сложности – время  работы  машины  M (число шагов, переходов) на  входе ω  до  окончания  работы, обозначается tM (n), где  n – длина  слова ω. Другой, часто применяемой  мерой  сложноcти,  является  емкость, обозначается  SM (n),  т. е.  максимальная  длина  используемого  участка  ленты  на  всех  рабочих  лентах,  по  всем  шагам  вычисления.  Если  вычисление  не  заканчивается,  время  и  емкость  считаются  бесконечными.

Тема  1.  Машина  Тьюринга  как  вычислительная  модель.

§ 1.  Детерминированная  машина  Тьюринга.

§ 2.  Языки, допускаемые  машиной  Тьюринга.

§ 3.  Многоленточная  машина  Тьюринга.

§ 4.  Недетерминированная  машина  Тьюринга.

§ 5.  Имитация  машины  Тьюринга  на  компьютере  и  компьютера  на  машине  Тьюринга.

Самостоятельные  занятия 

Примеры  вычислений  на  детерминированной  одноленточной  машине  Тьюринга.[3], раздел 2, глава1. [1], глава 8.

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

  Машина  Тьюринга  представляет  собой  абстрактную  вычислительную  машину,  состоящую  из  управления  с  конечным  числом  состояний  и  бесконечной  ленты,  разделенной  на  ячейки,  в  каждой  из  которых  хранится  один  ленточный  символ,  и  одна  из  ячеек  является  текущей  позицией  ленточной  головки.  Формальная  запись  машины  Тьюринга  - это упорядоченный  набор  M =  (X, Q, q 0, F, I),  где

X – внешний алфавит  символов  (букв  на  ленте), включающий символ  Λ;

Q – конечный  алфавит  внутренних  состояний;

q0 – инициальное состояние (начало работы), q0 ∈ Q;

F– множество  заключительных  состояний, F⊂ Q;

I  -  множество  инструкций,  или  машинных  команд,  каждая  из  которых  принадлежит  множеству  (Q \ F) × X × {→} × Q × X × {R, L,S}.

  Переходы  осуществляются  на  основе  текущего  состояния  и  обозреваемого  считывающей  головкой  символа  к  следующему  состоянию, переписыванию символа  и  сдвигу  головки  (вправо R, влево L, на месте S).

Можно  определить  функцию  переходов

δ :  (Q \ F) ×  X*  →  Q × X* × {R, L,S},  где  X* - слова  в  алфавите  X.

В  случае  однозначной  функции  δ  машина  Тьюринга  называется  детерминированной  машиной  Тьюринга.

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

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

  В  качестве  примера  рассмотрим  работу  детерминированной  машины  Тьюринга,  вычисляющей  функцию  ⎪m - n⎪.  Упорядоченную  пару  натуральных  чисел  (m, n)  представляем  как  слово  0m10n  в  алфавите  X \ {Λ} = {0,1}, ячейки  слева  и  справа  от  которого  содержат  символ  Λ.