Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Дискретная оптимизация и моделирование в условиях неопределенности данных

Перепелица В. А., Тебуева Ф. Б.,

1.3. Понятие сложности вычисления и порождения. Время и емкость

Прикладная комбинаторика строится на следующих принципах.

1⁰. Вместо задач существования, определения количества и перечисления рассматриваются задачи отыскание конфигураций, обладающих определенными свойствами. Чаще всего – это задачи комбинаторной оптимизации [65].

2⁰. Большое внимание уделяется парной формулировке задач. Сначала приводится содержательное словесное описание задачи. Затем вводятся формальные обозначения, с помощью которых представляется математическая постановка или модель задачи.

3⁰. Подчеркивается, что основная проблема прикладной комбинаторики – это проблема построения достаточно эффективного алгоритма, гарантирующего для данной математической постановки нахождение искомого (оптимального) решения конкретной (индивидуальной) задачи [78].

Вначале условимся, что термин «вычислительная модель» означает то или иное вычислительное устройство, например, машину Тьюринга, нормальный алгорифм Маркова, машину Колмогорова и т.д. В представленном ниже реферативном изложении используемые понятия, определения и утверждения можно найти в [14], [27], [42], [55].

Сформулируем два постулата:

а) каждое реальное вычисление осуществляется в физическом времени, имея определенную длительность;

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

Для того, чтобы формализовать и измерить используемые время и пространство, мы должны, прежде всего, фиксировать некоторую вычислительную модель. Затем мы должны указать способ измерения длительности вычисления на этой модели и способ измерения занимаемого им места. Меру длительности называют термином «время», а меру места – «емкость». Время и емкость являются функциями от входа, т.е. от исходных данных вычисления [27]. Область значений этих функций – натуральный ряд .

Указанные функции, а также их значения существенно зависят от выбранной вычислительной модели. Большая часть всех исследований времени и емкости осуществлена для многоленточных машин Тьюринга (ММТ) [55]. В ММТ имеется одна или несколько рабочих лент и по одной читающей головке для каждой ленты. Эти головки могут двигаться в обе стороны, читать и писать.

Пусть дан натуральный алгоритм [55], описание которого представлено в терминах ММТ. При данном входе временем работы называется число шагов, выполняемых машиной до получения результата. Емкостью работы машины называется максимальная длина использованного участка на рабочих лентах, т.е. максимум берется по всем рабочим лентам.

В связи с данными определениями возникает первый вопрос: существуют ли какие-нибудь связи между временем и емкостью ? Обозначим через  длину входа. Тогда для любой ММТ существует такое натуральное , что выполняются неравенства:

 и (1.1)

Второй вопрос: велики ли различия во времени вычисления на машинах с разным числом лент? Оказывается, эти различия невелики. Справедлива

Теорема 1.1.Любая функция, вычисляемая на какой-либо ММТ за время, не превосходящее , может быть вычислена на машине с одной рабочей лентой за время, не превосходящее , где  – независящая от константа. При этом, если функция вычислялась на ММТ с емкостью, не превосходящей , то на машине с одной лентой она вычисляется с емкостью, не превосходящей .

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

Теорема 1.2.Пусть какой либо предикат вычисляется на некоторой ММТ за время  при исходном данном . Тогда он может быть вычислен на некоторой машине (возможно, другой) с емкостью .

Примечание 1.3. Соотношения (1.1) связывают время и емкость вычисления на одной и той же ММТ. В теореме 1.2 эта связь относится, вообще говоря, к двум различным машинам.

Третий вопрос: как изменится время вычисления, если вместо ММТ для реализации данного алгоритма изберем другую вычислительную модель? Например, нормальный алгорифм Маркова или машину с произвольным доступом к памяти (МПДП), которую рассматривали Ахо, Хопрофт, Ульман [14]. Для ответа на этот вопрос сначала заметим, что во всех известных вычислительных моделях процесс вычисления состоит из отдельных шагов. Тогда самый простой ответ на третий вопрос заключается в следующем допущении.

Допущение 1.1.Время есть число шагов в процессе вычисления (Цейтин Г.С., 1956 г.) [55].

Однако, используя допущение 1.1, необходимо учитывать, что различные шаги имеют различную длительность. Укажем еще один нежелательный эффект: можно перестроить вычисление, т.е. работу данного алгоритма, объединяя некоторые последовательные шаги в один макрошаг, и получить «новое» вычисление, которое на самом деле является старым, но имеет как бы меньшее число шагов. Например, при поиске максимального элемента в данной последовательности  требуется осуществлять  шагов – операций попарного сравнения чисел. Объединив последовательность этих однотипных операций, получим один шаг «выбор максимального элемента в данной последовательности». Ясно, что длительность  шагов сравнения и длительность полученного шага «выбор максимума» одна и та же. Поэтому более правильным является

Допущение 1.2.Время – это сумма длительностей шагов.

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

Рассмотрим теперь определение емкости.

Допущение 1.3.Емкость (данного вычисления) – это максимальный размер памяти, используемой при вычислении.

Уточним смысл использованных терминов и понятий. Понятие «память» в одних случаях употребляется ко всему состоянию данного вычисления, включая память, затрачиваемую на запись исходных данных и результатов работы алгоритма. В других случаях подразумевается только рабочая память. Например, в последнем случае не учитывается память  ячеек, затрачиваемая на запись всех данных о графе для задач, которые формулируются на графах (задача о кратчайшем остовном дереве, задача о кратчайшей цепи между парой вершин и др.).

До конца неясным пока остается вопрос: должна ли емкость зависеть от алфавита? Например, одинаков ли размер 10-ти буквенного слова, записанного в 2-х буквенном алфавите и 10-ти буквенном алфавите ? Иными словами, как изменится емкость, если построим новый алфавит, объявив новыми буквами длинные комбинации прежних букв.

Более сложные вопросы относительно измерения емкости возникают при переходе от одномерной памяти (какой является лента ММТ) к многомерной памяти.

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

Напомним теперь, что параллельно с понятием «алгоритм» мы рассматриваем процесс, называемый термином «исчисление» [42]. Исчисление предполагает реализацию процесса порождения. Понятие времени и емкости (порождения) можно пытаться определить и для исчислений. При этом время порождения (при фиксированном выводе) есть число шагов вывода, а емкость – максимальный размер встречающихся в этом выводе объектов. Напомним принципиальную отличительную характеристику исчисления: в отличие от алгоритма исчисление допускает, вообще говоря, много способов порождения одного и того же объекта для одних и тех же исходных данных. Тогда для исчисления за сложность принимается минимум по всем способам порождения.

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

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

В этом случае говорят о доказательстве эффективности того или иного алгоритма.