10. Алгоритмы

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

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

Каждый встречается с алгоритмами со школьной скамьи. Правила, по которым выполняются арифметические действия с многоразрядными числами являются простейшими примерами алгоритмов. Сам термин "алгоритм" происходит от имени средневекового узбекского математика Мухаммеда бен Муса аль Хорезми, который еще в IX веке сформулировал такие правила. В своем развитии математика накопила огромное количество различных алгоритмов. Получая соответствующую интерпретацию в конкретных приложениях, они составляют значительную и наиболее существенную часть математического аппарата, используемого в технике.

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

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

2. Численные алгоритмы. Алгоритмы, которые сводят решение поставленной задачи к арифметическим действиям над числами, называются численными алгоритмами. Традиционным примером является известный алгоритм Евклида для нахождения наибольшего общего делителя двух заданных целых положительных чисел a и b.

Алгоритм Евклида состоит из следующей системы последовательных указаний:

1) обозревай a и b и переходи к следующему;

2) сравни обозреваемые числа (a = b, или a b, или ) и переходи к следующему;

3) если обозреваемые числа равны, то каждое из них дает искомый результат, если нет — переходи к следующему;

4) если первое обозреваемое число меньше второго, переставь

- 621 -

их местами и переходи к следующему;

5) вычитай второе число из первого и обозревай два числа — вычитаемое и остаток; переходи к указанию 2.

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

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

!!!!

Рис. 257. Поиск пути в лабиринте от точки a к точке f.

3. Логические алгоритмы. Существует другой тип алгоритмов, которые содержат предписания, относящиеся не к цифрам, а к объектам любой природы. Типичным примером логических алгоритмов может служить алгоритм поиска пути в конечном лабиринте.

Лабиринт удобно изображать в виде графа, вершины которого соответствуют площадкам, а дуги — коридорам (рис. 257). Пусть требуется выяснить, достижима ли площадка f из площадки a, и если да, то найти путь из a в f, а если нет — вернуться в a. Конечно, предполагается, что заранее ничего не известно об устройстве данного лабиринта.

Лицо, ищущее путь в лабиринте, располагает нитью, конец которой закреплен на площадке a, и, двигаясь по лабиринту, может разматывать клубок (Р) или наоборот наматывать на него нить (Н). Можно делать отметки на проходимых коридорах и различать затем коридоры, еще ни разу не пройденные (зеленые — З), пройденные один раз (желтые — Ж) и пройденные дважды (красные — К). Метод поиска может быть задан следующей схемой:

1) площадка f — остановка (цель достигнута);

2) петля (П) — наматывание нити (от данной площадки расходятся, по крайней мере, два желтых коридора);

3) зеленая улица (ЗУ) — разматывание нити (от

- 622 -

данной площадки отходит хотя бы один зеленый коридор);

4) площадка a — остановка (исходный пункт);

5) отсутствие всех предыдущих признаков (ОП) — наматывание нити.

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

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

1) ЗУ — Р — ab — Ж;

2) ЗУ — Р — bc — Ж;

3) ЗУ — Р — cd — Ж;

4) ЗУ — Р — dg — Ж;

5) ЗУ — Р — gh — Ж;

6) ОР — Р — hg — K;

7) ОР — Р — gd — K;

8) ЗУ — Р — db — Ж;

9) П — Р - bd — K;

10) ЗУ — Р — df — Ж;

11) площадка f — остановка.

В данном случае площадка f оказалась достижимой (недостижимыми являются площадки i, k, l , m). Выделив коридоры, которые остались желтыми (ab, bc, cd, df), получим путь от a к f (abcdf, указанный на рис. 257 жирными дугами).

4. Общие свойства алгоритмов. Богатый опыт разработки и применения алгоритмов подсказывает ряд общих свойств, которые детализируют приведенное выше описание.

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

Детерминированность алгоритма. Совокупность величин, получаемых в какой-то (не начальный) момент времени, однозначно определяется совокупностью величин, полученных в предшествующие моменты времени. Например, алгоритм поиска пути в лабиринте допускает произвол в выборе коридора при наличии нескольких зеленых коридоров, отходящих от данной площадки. Чтобы сделать его строго детерминированным, необходимо добавить предписание о выборе зеленого коридора ( например, первый по часовой стрелке).

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

- 623 -

Массовость алгоритма. Алгоритм служит для решения целого класса задач, причем начальная совокупность величин может выбираться из некоторого множества. Например, в алгоритме Евклида числа a и b выбираются из бесконечного (счетного) множества целых числе, а в алгоритме поиска пути в лабиринте начальная и конечная площадки выбираются из конечного множества площадок лабиринта. В математике проблема считается решенной, если для нее найден общий алгоритм.

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

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

Напомним, что алфавит представляет собой любую конечную систему различных символов, называемых буквами. Любая конечная последовательность n букв некоторого алфавита является словом длины n в этом алфавите. Например, в алфавите из трех букв {a, b, c} словами будут последовательности b, ac, bac, abba, cbcccacabca и т.д. Пустое слово, не содержащее ни одной буквы, обычно обозначается через ∧. если слово L является частью слова M, то говорят о вхождении слова L в слово M. Например, в слове abcbcbab имеются два вхождения слова bcb и одно вхождение слова ba.

В качестве операций ассоциативного исчисления определяется система допустимых подстановок, с помощью которых одни слова преобразуются в другие. Подстановка вида L-M, где L и M — слова в том же алфавите, означает замену вхождения левой части правой, равно как и замену правой части левой. Иначе говоря, если в некотором слове R имеется одно или несколько вхождений слова L, то каждое из этих вхождений может заменяться словом M, и наоборот, если имеется вхождение слова М, то его можно заменить словом L. Например, подстановка ab-bcb применима четырьмя способами к слову abcbcbab. Замена каждого из двух вхождений bcb даст слова aabcbab и abcabab, а замена каждого из двух вхождений ab дает слова bcbcbcbsb, abcbcbbcb. В то же время к слову bacb эта подстановка не применима. Подстановка вида Р-∧ означает, что из преобразуемого слова выбрасывается вхождение слова Р,

- 624 -

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

Итак, ассоциативное исчисление — это множество всех слов в некотором алфавите вместе с какой-нибудь конечной системой допустимых подстановок. Очевидно, чтобы задать ассоциативное исчисление, достаточно определить алфавит и систему допустимых подстановок (например, алфавит {a, b, c, d, e} и система подстановок ac-ca, ad-da, bc-cb, bd-db, abac-abacc, eca-ae, edb-be).

6. Эквивалентность слов. Два слова называются эквивалентными, если одно из них можно получить из другого последовательным применением допустимых подстановок. Так, в приведенном выше (5) исчислении эквивалентными являются, например, слова abcde cadedb, что видно из следующих последовательных преобразований: abcde, acbde, cabde, cadbe, cadedb. Последовательность слов R₁, R₂, ..., R_n, когда каждое следующее слово является результатом однократного применения допустимой подстановки к предыдущему слову, образует дедуктивную цепочку, причем соседние слова в этой цепочке называют смежными. Очевидно, любые два слова в дедуктивной цепочке являются эквивалентными.

Эквивалентность слов L и M обозначается L ~ M и обладает всеми свойствами отношения эквивалентности (рефлексивность, симметричность и транзитивность). Если L ~ M, то при наличии в каком-либо слове R вхождения L в результате подстановки L-M получается слово, эквивалентное R. Например, воспользовавшись эквивалентностью abcde~cadbe, из слова bbabcdec получаем эквивалентное ему слово bbcadbec.

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

С помощью алгоритма перебора решается ограниченная проблема слов: требуется установить, можно ли одно из заданных слов преобразовать в другое применением допустимых подстановок не более, чем k раз, где k — произвольное, но фиксированное число. Для этого достаточно построить все слова, смежные с одним из заданных слов,

- 625 -

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

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

В некоторых случаях могут быть обнаружены и использованы свойства, остающиеся неизменными для всех слов дедуктивной цепочки (дедуктивные инварианты). Так, в каждой из допустимых подстановок исчисления из (5) левая и правая части содержат одно и то же число вхождений буквы а. Следовательно, в любой дедуктивной цепочке все слова также должны содержать одно и то же число вхождений буквы а. На основе этого дедуктивного инварианта можно установить, какие слова не могут быть эквивалентными (например, слова abacdac и abaadac — не эквивалентны).

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

- 626 -

7. Нормальный алгоритм Маркова. Система допустимых подстановок в некотором алфавите, снабженная точным предписанием о порядке и способе их использования, позволяет осуществить детерминированный процесс, который последовательно преобразует некоторое слово в новые слова, эквивалентные исходному. Говорят, что задан алгоритм в алфавите А, который применим к слову L и перерабатывает его в слово М, если, отправляясь от L и действуя согласно предписанию, в конце концов получают М, на котором процесс обрывается. Множество слов, к которым применим данный алгоритм, называют его областью применимости. Два алгоритма в некотором алфавите называются эквивалентными, если области их применимости совпадают и результаты переработки или любого слова из общей области применимости также совпадают.

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

Задается алфавит А и фиксируется в определенном порядке система ориентированных подстановок. Исходя из произвольного слова R в алфавите А, просматриваются подстановки в том порядке, в каком они заданы. Первая встретившаяся подстановка с левой частью входящей в R, используется для преобразования R, в которое вместо первого вхождения ее левой части подставляется ее правая часть, в результате чего получаем новое слово R₁. Далее процесс повторяется, исходя из слова R₁, R₂ и т.д. до тех пор, пока этот процесс не останавливается. Признаками остановки процесса служат два случая: во-первых, когда получается такое слово R_n, что ни одна из левых частей допустимых подстановок в него не входят, и во-вторых, когда при получении R_n приходится применять последнюю подстановку.

Пусть, например, задан алфавит A = {1, +} и система подстановок + → ∧, 1→ 1 (∧ - пустое слово). Слово 111+11+1111+1 этот алгоритм перерабатывает так:

111+11+1111+1

11111+1111+1

111111111+1

1111111111

1111111111

Процесс оканчивается применением заключительной подстановки, которая перерабатывает слово само в себя. Как видим, алгоритм суммирует количество единиц, т.е. осуществляет операцию сложения. Эквивалентный ему алгоритм можно задать с помощью системы подстановок: 1+ → +1; +1→1; 1→1.

- 627 -

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

8. Машина Тьюринга. Другой стандартной формой представления любого алгоритма являются функциональные схемы, реализуемые в машинах Тьюринга (рис. 258). Слова, перерабатываемые в данном алфавите {ξ₁, ξ₂, ..., ξ_m}, называемом внешним алфавитом машины, изображаются в ячейках неограниченной ленты (НЛ), причем в каждой в ячейке может храниться только один символ.

Работа машины происходит в дискретном времени. На каждом такте обозревается единственная ячейка и считываемый символ ξ_i заменяется другим ξ_j (i = j означает, что символ не изменяется), который определяется состоянием машины s_k в данный тактовый момент из множества ее возможных состояний {s₁, s₂, ..., s_n}. Кроме того, вырабатывается последующее состояние машины и команда, управляющая перемещением по ленте, которая подготавливает очередную ячейку для обозрения на следующем такте. Таких команд в машине Тьюринга только три: П — обозревать соседнюю справа ячейку, Л — обозревать соседнюю слева ячейку и Н — продолжать обозревать прежнюю ячейку. Совокупность {s₁, s₂, ..., s_n} и {П, Л, Н} образует внутренний алфавит машины.

Функциональная схема, соответствующая какому-либо алгоритму, задается подобно общей таблице переходов конечного автомата (6.4) с некоторыми несущественными отличиями. Обычно строки таблицы соответствуют символам внешнего алфавита ξ₁, ξ₂, ..., ξ_m, а столбца — состояниям машины s₁, s₂, ..., s_n. В каждой клетке записывается тройка символов, обозначающих замещающих символ из внешнего алфавита, управляющую команду и последующее состояние. Например, функциональная схема, соответствующая алгоритму сложение (числа представляются совокупностью единиц или просто «палочек», общее количество которых равно данному числу, причем они расположены в ячейках без пропусков) имеет вид:

Знак «!» используется для обозначения стоп-состояния, при наступлении которого процесс останавливается и результирующее слово считывается по ленте, а через ∧ обозначается пустой символ.

Функциональная таблица полностью определяет функционирование машины и реализуется в ней логическим блоком (ЛБ). На

- 628 -

два его входа подаются считываемые символы, над которыми совершаются операции (замена другими символами), и состояния, играющие роль команд, определяющих эти операции. На одном из выходов логического блока образуется символ, который в данном такте замещает на ленте обозреваемый символ, а на остальных двух выходах — команды, определяющие функционирование машины на следующем такте (перемещение по ленте и новое состояние). Для запоминания этих команд вводятся задержки З₁ и З₂ представляющие собой внутреннюю память машины.

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

Рис. 258. Машина Тьюринга.

Пусть, например, требуется сложить числа 4 и 6. исходное слово на ленте запишется в виде 1111+111111. В соответствии с приведенной выше схемой сложения начальные условия определяются ячейкой с крайней левой единицей и состоянием s₁. На первом такте единица стирается, выдается команда сдвига вправо и перехода в состояние s₃(∧Пs₃ ). Последующие такты сводятся к сдвигам направо сквозь все единицы (1Пs₃ ) и знак + (+Пs₃ ) до тех пор, пока не будет достигнута первая пустая ячейка. Тогда в эту пустую ячейку вписывается единица и машина переходи в состояние s₂ (1Нs₂) При состоянии s₂ происходят сдвиги в обратном направлении через все символы 1 и + до первой пустой ячейки слева. После этого происходит сдвиг вправо, левая крайняя единица стирается, и машина переходит в состояние s₁ (∧Пs₁). В результате этого цикла единица левого слагаемого оказалась перенесенной в правое слагаемое, что соответствует слову 111+1111111 (сумма не изменяется). Очевидно, через четыре таких цикла исходное слово преобразуется к виду +1111111111. К началу пятого цикла обозревается символ + при состоянии s₁, который стирается и происходит остановка (∧Н!). В результате получим слово 1111111111, соответствующее числу 10.

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

- 629 -

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

9. Алгоритмическая разрешимость. После того как понятие алгоритма получило точное определение, вопрос об алгоритмической разрешимости того или иного класса задач ставится совершенно определенно: существует ли какая-либо стандартная форма алгоритма, решающая данный класс задач? В ряде случаев на этот вопрос теория алгоритмов дает отрицательный ответ.

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

Пробным камнем теории алгоритмов явилась проблема распознавания выводимости: для любых двух формул R и S в логическим исчислении узнать, существует ли дедуктивная цепочка, ведущая от R к S, или же такой цепочки не существует. Оказалось, что эта проблема алгоритмически неразрешима. Отрицательный ответ получен и для проблемы распознавания эквивалентности слов в любом ассоциативном исчислении. Были построены конкретные примеры ассоциативных исчислений, в которых- не существует алгоритма, позволяющего для любой пары слов установить, эквиваленты они или нет. Простейший пример такого исчисления приведен в (5).

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

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

- 630 -

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

Аналогичный подход выработала практика и к задачам, которые относятся к нерешенным проблемам. Например, до сих пор не найден общий алгоритм раскраски граней любого плоского графа не больше чем четырьмя различными цветами так, чтобы никакие соседние грани не были окрашены одинаковым цветом (в 1976 г. появилось сообщение о решении этой проблемы с помощью вычислительных машин, которое еще подлежит проверке). В то же время в реальных условиях еще не встречалось случаев, когда такая раскраска оказалась бы невозможной (эта задача возникает, например, при изготовлении географических карт). Можно предложить много различных способов, облегчающих решение конкретных задач этого типа. Однако ни один из них нельзя назвать алгоритмом, если он не гарантирует раскраску любого графа. В отличие от алгоритмов, практические способы, используемые для решения таких задач, относящихся к нерешенным проблемам, называют псевдоалгоритмами.

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

Прикладная теория алгоритмов мало озабочена собственно существованием алгоритмов (обычно это просто подразумевается),

- 631 -

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

Для описания алгоритмов используются различные методы, отличающиеся степенью детализации и формализации. Теоретическое описание обычно дается в повествовательно-формульном изложении, цель которого — обосновать без излишних подробностей процедуру, предлагаемую в качестве алгоритма. Для наглядного представления структуры алгоритмов широко применяются графические средства: графы, блок-схемы, сети. Формальное и полное описание алгоритмов осуществляется на специально разработанных для этой цели алгоритмических языках; оно содержит всю необходимую для реализации алгоритма информацию, но не связано непосредственно со специфическими особенностями вычислительных машин. Машинная реализация алгоритма требует перевода его на язык, свойственный данной машине, в виде программы. Роль автоматических переводчиков с алгоритмических языков играют специальные программы, называемые трансляторами. Часто общее описание алгоритма непосредственно переводится на машинный язык путем расшифровки операторов алгоритма в операции вычислительной машины.

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