3.2. Алгоритмы [1976 Арбиб М. - Метафорический мозг]

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

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

Более глубокая причина успеха вычислительных машин никак не связана с их схемами, а обусловлена основными логическими свойствами алгоритмов, и именно тем, что алгоритм может задаваться гораздо меньшим числом шагов, чем нужно для его осуществления (т. е. для проведения всех операций с конкретными данными). На первый взгляд это кажется парадоксальным, поскольку легко понять, что можно упустить какие-то команды при выполнении, но трудно представить себе, откуда появятся дополнительные! На самом деле все очень просто: в алгоритмы часто входят последовательности команд, суть которых может быть выражена словами: "Повторяйте следующий шаг до тех пор, пока этого не окажется достаточным". Чтобы внести полную ясность в этот вопрос, рассмотрим следующий алгоритм отыскания двери в абсолютно темной комнате. (Для простоты предположим, что всю мебель с нашего пути любезно убрали и что дверь закрыта.) Устные наставления, которые мы могли бы дать человеку, звучали бы так: "Идите к стене, потом идите вдоль стены, пока не дойдете до двери". Это можно представить в виде следующей последовательности элементарных операций:

3. Сделайте небольшой шаг вперед и затем приставьте другую ногу.

5. Касаясь стены или двери левой рукой впереди себя, поворачивайтесь до тех пор, пока она окажется слева от вас.

7. Сделайте небольшой шаг вперед и затем приставьте другую ногу.

9. СТОП (или переход к следующей программе действия после того, как вы отыскали дверь).

Из этой программы ясно видно, что задание такого алгоритма обычно короче его исполнения. Если человек, когда он начинает идти, находится в 12 шагах от стены и ему нужно сделать 8 шагов вдоль нее, чтобы отыскать дверь, то он должен в целом выполнить 63 команды, т. е. в 7 раз больше, чем потребовалось для описания программы. (Внимательный читатель может заметить, что программа "работает" только в том случае, если дверь расположена на первой стене. А что делать, если дверь может быть на любой стене прямоугольной комнаты? Какие нужны дополнительные команды, если комната имеет необычную форму?) Следует добавить, что этот пример, демонстрирующий сравнительную краткость задания алгоритма относительно его исполнения, не может служить примером того, как можно обеспечить максимальную скорость решения поставленной задачи. Робот, как и человек, не может сделать миллион шагов в секунду. Так что в полной мере воспользоваться преимуществами быстродействия вычислительной машины можно лишь тогда, когда элементарные операции, из которых слагается поведение, могут выполняться внутри машины, в ее схемах, а не требуют "натурного" взаимодействия со средой.

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

1) в нее можно ввести программу и данные и этому не препятствует быстродействие ее устройств ввода и вывода;

2) у нее есть блоки, способные выполнить любую базовую" операцию;

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

4) она умеет считывать данные со своих рецепторов и посылать команды своим эффекторам.

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

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

Л. Зафиксировав положение Правого колеса, повернуть Левое на один оборот.

П. Зафиксировав положение Левого колеса, повернуть Правое на один оборот.

О. Повернуть одновременно Оба колеса на один оборот.

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

Однако нам хотелось бы иметь возможность пользоваться командами типа "вперед на пять футов" или "поворот на 30° вправо". Предположим, что, зафиксировав одно колесо, робот .делает полный оборот на 360° за 72 оборота другого колеса, а одновременный оборот обоих колес продвинет робота на 5 см вперед.

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

Поворот на θ° вправо. 1. Положить x=θ/5 (округленный до ближайшего целого).

Прежде чем закончить этот раздел, заметим, что все эти алгоритмы последовательные, т. е. все они способны выполнять одновременно лишь одну операцию. Мозг, напротив, работает в параллельном режиме: каждый нейрон непрерывно производит тесты над нейронами, с которыми он образует синапсы, в результате чего одновременно происходят миллиарды операций. Тем не менее описание связей в схеме, выполняющей задание, определяет алгоритм не хуже, чем последовательность команд. Большая часть работ по искусственному интеллекту направлена на поиски какого-либо алгоритма, который бы позволял реализовать некоторую функцию "разумного" поведения, но при этом обычно останавливаются на алгоритмах последовательного типа, поскольку именно для таких алгоритмов предназначено большинство современных вычислительных машин. Однако, когда мы обратимся в третьей части к теории мозга, нас будут интересовать параллельные алгоритмы, структура которых больше напоминает структуру мозга. Но как это ни смешно, свои теории мы будем обычно проверять, воспроизводя наши модели на вычислительной машине, другими словами, переводя параллельный алгоритм в последовательный. Эта стратегия поясняется на тривиальном примере на рис. 40. Для того чтобы описать события, происходящие на одном-единственном шаге параллельного алгоритма, нам приходится записать целую последовательность команд, и если смотреть лишь на те результаты наших последовательных расчетов, которые относятся к концам каждого такого цикла, то мы получим как бы "замедленную съемку" параллельных расчетов.

Рис. 40. Пример параллельного алгоритма, который можно моделировать с помощью последовательного алгоритма, введя дополнительный параметр состояния и замедлив процедуру в четыре раза (ср. с рис. 34)

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