Стратегии реализации алгоритма.

 

В теоретических подходах к построению строгого определения по­нятия алгоритма исторически выделились три основные направления.

Первое направление связано с рассмотрением алгоритмов, по­зволяющих вычислить значение числовых функций, зависящих от целочисленных значений аргументов - такие функции получили название вычислимых. Понятие вычислимой функции не является строгим, как и понятие алгоритма. Однако, благодаря работам А. Черча, К. Геделя, С. Клини, была обоснована тождественность класса всюду определенных вычислимых функций с классом час­тично рекурсивных функций, который определяется строго. Это позволило свести проблему алгоритмической разрешимости к

доказательству возможности (или невозможности) построения ре­курсивной функции, решающей задачу. Именно этим путем А. Черчу удалось доказать неразрешимость одной из проблем математиче­ской логики - исчисления истинности предикатов.

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

Третье направление связано с понятием нормальных алгорит­мов, введенным и разработанным российским математиком А. А. Марковым в начале 50-х гг. XX в.

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

1. Применение исполнителей, способных выполнять сложные команды. Определение термина «исполнитель алгоритма» достаточно очевидно:

Исполнитель алгоритма - это субъект или устройство способные правильно интерпретировать описание алго­ритма и выполнить содержащийся в нем перечень действий.

Указания по выполнению действий для каждого исполнителя формулируются посредством некоторого языка, включающего набор служебных слов, обозначающих действия (команды), а также синтаксические правила их объединения. Совокупность допустимых команд образует систему команд исполнителя (СКИ). Различаться СКИ разных исполнителей могут детальностью описания действий. Как будет показано ниже, элементарным (простейшим) действием при обработке дискретной информации является замена одного знака другим. Однако можно построить абстрактное или реальное устройство, которое будет способно выполнять целую цепочку подобных элементарных действий по заложенному в него правилу - некое комплексное (интегральное) действие. При построении алгоритма для такого исполнителя разработчику достаточно указать последовательность инте­гральных команд, а их преобразование в цепочку истинно эле­ментарных шагов будет производиться самим исполнителем. Та­кая «многоступенчатая» алгоритмизация широко применяется при управлении компьютером.

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

Перевод мнемоник в машинные команды осуществляет про­грамма - ассемблер; именно с ней имеет дело программист как с исполнителем. Команды, объединяющие ряд элементарных дейст­вий, появляются в языках программирования высокого уровня, на­пример, в тексте программы достаточно написать «Write», а уже транслятор языка переведет ее в последовательность элементар­ных шагов: прерываний, пересылок и пр. По отношению к програм­мисту исполнителем в этом случае оказывается транслятор языка программирования. Еще большую степень интеграции элементар­ных команд может обеспечить прикладная программа, которая яв­ляется исполнителем по отношению к конечному пользователю. СКИ такого исполнителя включает все команды управления, пред­ставленные в виде меню, экранных кнопок, окон настройки и других элементов интерфейса. Использование одной команды может вы­звать цепочку сложных действий, например, выравнивание многих строк текста.

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

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

Расширение применимости понятия алгоритма на последо­вательность любых дискретных действий. По определению алго­ритм должен быть обязательно связан с обработкой дискретной ин­формации. Однако этот же термин используется и для обозначения действий по управлению исполнителем, напрямую не производящим
преобразование информации. Например, в школьном курсе инфор­матики широко применяются учебные исполнители «Чертежник», «Паркетчик», «Черепашка», СКИ которых включает перемещение по экрану и выполнение некоторых операций («начертить линию», «положить плитку» и т.п.). То же относится к инструкциям по управлению какими-либо агрегатами и устройствами.