Характерные черты алгоритма

Теория алгоритмов.

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

В соответсвтии с ГОСТ 19781-74 «Машины вычислительные. Программное обеспечение. Термины и определения» алгоритм – это точное предписание, определяющий вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату. При этом предполагается наличие исполнителя алгоритма – такого объекта, который «умеет» выполнять эти действия.

Слово алгоритм происходит, как предполагают, от мени среднеазиатского (узбекского) математика IX в. Аль Хорезми (Абу Абдалла Мухаммед ибн Муса ал Хорезми ал Меджуси) – “Algorithmi” в латинской транскрипции, впервые сформулировавшего правила (процедуру) выполнения четырех арифметических действий в десятичной системе счисления.

Пока вычисления были не сложными, особой необходимость в алгоритмах не было. Когда появилась потребность в многократных пошаговых процедурах, тогда и появилась теория алгоритмов. Но при еще большем усложнениии задач оказалось, что часть их невозможно решить алгоритмическим путем. Таковы, например, многие задачи, решаемые головным мозгом человека. Решение таких задач основано на других принципах. Эти принципы использует новая наука – нейроматематика и соответствующие технические средства – нейрокомпьютеры.

Качество алгоритма определяется его свойствами (характеристиками). К основным свойствам алгоритма относятся следующие.

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

2. Результативность. Это свойство означает, что алгоритм должен приводить к получению результата за конечное число шагов.

3. Определенность. Предписания, входящие в алгоритм, должны быть точными и понятными. Эта характеристика обеспечивает однозначность результата вычислительного процесса при хаданных исходных данных.

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

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

В последствии было установлено, что эти и другие модели эквивалентны в том смысле, что классы решаемых ими задач совпадают. Этот факт носит название тезиса А. Черча.