Алгоритмы и анализ сложности (стр. 4 )

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

Трудоемкость алгоритма раскраски составляет .

Теория алгоритмов и -полные задачи

Цели:

- формальное сравнение и классификация алгоритмов,

- проверка возможности создания алгоритма решения задачи.

Пусть на некотором шаге алгоритма необходим выбор или обработка нескольких альтернатив. По способу выполнения данных операций можно выделить 2 типа алгоритмов:

Детерминированный алгоритм (ДА) проводит однозначный выбор конкретной альтернативы или обрабатывает все варианты последовательно.

Недетерминированный алгоритм (НА) копирует себя для одновременной обработки всех альтернатив: копии (экземпляры) алгоритма выполняются параллельно и независимо, каждая копия обрабатывает одну альтернативу.

Экземпляры НА полностью независимы: они используют копии данных и не обмениваются информацией.

Формирование и запуск экземпляров НА выполняет специальный оператор : выбор из множества альтернатив , один экземпляр НА на каждый элемент . Каждый из этих экземпляров при встрече очередного оператора выбора будет опять делиться на независимые копии.

Если какой-то из экземпляров сделал неправильный выбор и\или не может продолжать работу (тупик), то он завершается (говорит «нет»).

Если какой-то экземпляр нашел решение задачи, то он сообщает об этом (говорит «да»), все экземпляры завершают свою работу и считается, что НА решил задачу.

Максимальная из трудоемкостей отдельных экземпляров НА считается временной сложностью всего НА.

Аналогично, максимальные затраты памяти для одного экземпляра НА определяют емкостную сложность всего НА.

НА приспособлены для задач распознавания свойств: «существует ли решение (элемент), для к-рого выполняется некоторое свойство». При этом каждое возможное решение проверяется отдельным экземпляром НА, а полученные результаты не сравниваются.

Поэтому для задач, в к-рых нужно найти число допустимых решений или наилучшее решение, не существует НА.

НА – гипотетические, т. к. невозможно реализовать произвольное число одновременно работающих и независимых вычислителей.

Примеры задач, для решения к-рых можно использовать НА:

-коммивояжер – ли маршрут с весом ,

-клика графа – ли полный подграф с вершинами,

-раскраска графа – ли раскраска в цветов.

НА для -коммивояжера:

a[1] = 1; ves = 0; k = 1;

S = {2,…,n};

while (не_пусто(S)) {

       k++; a[k] = выбор(S);

       S = S – a[k]; ves += C[a[k-1]][a[k]];

}

ves += C[a[n]][a[1]];

if (ves <= b) сообщить(“да”);

else сообщить(“нет”);

Модели вычислений и машины Тьюринга

Алгоритмы решения некоторых задач были найдены давно: алгоритм Евклида, уравнения до 3-й степени, шахматные задачи.

В 20 в. появилось мн-во алгоритмов для компьютеров, и возникла проблема их формального сравнения и классификации по сложности.

Для некоторых задач вообще не удалось найти алгоритма:

- общий метод решения всех математ. задач (Лейбниц, 17 в.),

-  алгоритм док-ва теорем по любой системе аксиом (20 в.).

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

Для решения данных проблем необходимо абстрагироваться от деталей конкретных алгоритмов и по возможности формализовать объекты и выполняемые действия.

Входные и выходные объекты алгоритмов всегда кодируются строками символов некоторого алфавита (напр., двоичными).

  входная строка                                выходная строка

Можно считать, что все алгоритмы занимаются преобразованием строк: распознавание входных и формированием выходных.

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

Равнодоступная адресная машина (РАМ).

Бесконечная память: сумматор и регистры

Бесконечные входная и выходная ленты разделены на ячейки.

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

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

Неизменяемая программа, очередная выполняемая команда определяется по счетчику команд (СК).

Команды: load, store, add, … ,div, read, write, jump, jzero, halt.

Возможный операнд: (константа), (регистр), (косвенная адресация), метка.

РАМ близка к реальным языкам программирования (ЯП без численных ограничений реализации).

2 весовых критерия при оценке трудоемкости:

1. Равномерный – каждая команда выполняется за 1 шаг.

2. Логарифмический – время выборки и обработки целого числа составляет , т. е. зависит от значения.

РАМ с и полиномиально не связаны (отличаются в экспоненциальное число раз).

РАМ с сильно идеализирована для чисел произвольной длины.

Машина Тьюринга (1-МТ)

                                                                       алфавит

Бесконечная лента разделена на ячейки, в каждой ячейке м\б записан один из символов алфавита или пустой символ .

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

В начальном состоянии на ленте записана входная строка.

УУ может читать и писать в текущую ячейку какой-либо  символ входного алфавита , сдвигаться на одну ячейку влево или вправо или оставаться на месте, а также переходить в новое состояние.

Все указанные действия совершаются в соответствии с набором правил перехода конкретной МТ.