2.2.2. Алгоритмическая сводимость задач

Пусть существует алгоритм A, который, будучи применимым ко всякому входному слову  задачи , строит некоторое входное словозадачи. Если при этом слово дает ответ «да» тогда и только тогда, когда ответ «да» дает слово , то говорят что задача (полиномиально) сводится к задаче, и пишут .

Нетрудно показать, что если иP, то P.

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

Подведем итоги. Мы определили два класса задач P и NP. Причем имеет место включение PNP.

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

Кроме того, имеется обширный класс нерешимых задач, которые нельзя решить алгоритмически.

Таким образом, имеются 4 основных класса массовых задач: P. NP, труднорешаемых задач и нерешаемых задач.

3. Алгоритмы и их сложность

3.1. Представление абстрактных объектов (последовательностей)

При описании понятия алгоритма вводится важное понятие конструктивного объекта данных. Без данных не существует алгоритмов. Под конструктивным объектом данных в программировании понимается модель данных. В большинстве языков программирования понятие модели данных совпадает с понятием абстрактных типов данных.

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

Главные соображения, которыми нужно руководствоваться при таком выборе, состоят в следующем.

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

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