Нестрогое определение алгоритма

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

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

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

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

3. Элементарность шагов: закон получения последующей системы величин из предыдущей должен быть простым и локальным. Какой шаг (действие) можно считать элементарным, определяется особенностями исполнителя алгоритма.

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

5. Массовость алгоритма: начальная система величин может выбираться из некоторого множества.

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

Понятие алгоритма, в какой-то мере определяемое перечислением свойств 1-5, также нельзя считать строгим, поскольку в формулировках свойств использованы термины «величина», «способ», «простой», «локальный» и другие, точный смысл которых не установлен. В дальнейшем данное определение будем называть нестроги/и (иногда его называют интуитивным) понятием алгоритма.

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

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

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

Таким образом, возникла необходимость в точном определении понятия «любой алгоритм», т.е. максимально общем определении, под которое подходили бы все мыслимые виды алгоритмов. В 20-е гг. XX в. построение определения алгоритма стало одной из центральных математических проблем. Определение это, с одной стороны, должно было соответствовать сущности интуитивного понятия алгоритма, а с другой стороны, быть формально строгим. Попытки формулировки такого понятия привели к появлению в 30-х гг. XX века теории алгоритмов как самостоятельной науки, которая вместе с математической логикой изучает основные средства математики - методы доказательств, способы построения аксиоматических теорий, свойства математических процедур и пр. Когда же в 40-е - 50-е гг. началось бурное развитие вычислительной техники и наук, связанных с ее функционированием и использованием, то выяснилось, что в основе этих наук также должна лежать теория алгоритмов, поскольку компьютер может реализовать только такие процедуры, которые представимы в виде алгоритмов. Любая программа есть ни что иное, как запись алгоритма на языке, который может «понять» исполнитель - компьютер. Таким образом, с практической точки зрения также представляется важным уточнение понятия алгоритма.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Понятие экономичности системы счисления

Общая идея моделирования

Значение формализации

Пример 7.5

Пример 4.12

Вернуться в оглавление: Теоретические основы информатики