Наука и искусство алгоритмизации

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

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

Давайте посмотрим, что это за случаи. Это, пожалуй, те случаи, в которых алгоритм решения уже получен кем-нибудь другим. Например, существует метод Эйлера для численного интегрирования дифференциальных уравнений. Нетрудно для конкретного дифференциального уравнения составить алгоритм его решения методом Эйлера. Но метод Эйлера как раз и представляет собой сделанное в общем виде описание этого алгоритма! В § 2 гл. 2 мыуже говорили о том, как получают алгоритмы. Теперь мы xoтим \ снова вернуться к этому вопросу, имея значительно 6oльшее вооружение, для того чтобы к нему подступиться. Мы можем изложить даже некоторую теорию алгоритмизации.

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

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

Конечно, может быть, мы не сумеем доказать ни воз­можность, ни невозможность алгоритма. Что делать в этом случае — неизвестно. Автор полагает, что нужно жать исследования.

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

Хотя автор и сказал: «Построение хотя бы какого-ни­будь алгоритма», но, конечно, нужно стремиться получить сразу «хороший» алгоритм, если это удается. Если же ни один из известных приемов не позволит получить «хороший» алгоритм, возникает вопрос: нельзя ли, отправляясь от «плохого», улучшить его настолько, чтобы он стал прием­лемым?

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

Некоторые преобразования связаны с видоизменением алгоритмического и операндного языков, другие преобразо­вания оставляют нас в рамках прежних языков[29]. К сожа­лению, метода направленных преобразований нет. Если мы хотим с помощью равносильных преобразований улуч­шить алгоритм, то должны при этом руководствоваться ин­туицией, а в ряде случаев действовать наудачу. Преобра­зовав алгоритм, мы проверяем: стал ли он лучше? Смотрим, нельзя ли его еще улучшить?

При этом мы встречаемся с одной трудностью. Слова «лучше», «хуже», «хороший», «плохой» применительно к ал­горитмам не имеют точного смысла. Когда алгоритм очень «плох», нам это ясно. Когда он очень «хорош», мы тоже ка­ким-то шестым, а может быть, и седьмым чувством это вос­принимаем. Но в «средних» случаях наше седьмое чувство молчит.

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

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

Если допустимый максимум объема обозначить V*, то коль скоро алгоритм таков, что V ≤ V*, где V — потребный объем, то стремиться к дальнейшему уменьшению потреб­ного объема уже незачем. Этот критерий перестает дей­ствовать.

Теперь начинает действовать новый критерий: потреб­ное время. Для оценки времени нужно учесть физические характеристики исполнителя. Очень грубо можно оцени­вать время, если известно «среднее быстродействие» ис­полнителя. Каждую операцию при каждом значении опе­ранда исполнитель производит за определенное время. Но таких точных сведений об исполнителе мы обычно не име­ем. Нам бывает известно некоторое среднее быстродействие, подсчитанное в предположении, что каждый вид операций и каждый вид исходного для нее данного в процессе выпол­нения алгоритма встречается с определенной известной вероятностью. За неимением других характеристик при­ходится пользоваться этой очень неточной характеристикой исполнителя. Определяя количество последовательно вы­полняемых операций и умножая их число на среднее быст­родействие, получаем условное время выполнения алго­ритма.

Сделаем допущение, что условное время является дей­ствительным временем выполнения. И тогда из двух алго­ритмов, удовлетворяющих условию V ≤ V*, лучше тот, для которого время выполнения меньше. Сам метод оценки неточен, и потому стремиться к получению наилучшего алгоритма — дело бессмысленное. Такой «наилучший» ал­горитм может быть хуже многих других. Обычно нам из­вестно максимальное допустимое время Т и, коль скоро мы нашли алгоритм, время выполнения которого удовлетво­ряет условию t<T, проблема считается решенной.

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

ЗАКЛЮЧЕНИЕ

Может ли машина мыслить?