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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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