Понятие об алгоритме и теории алгоритмов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Схемы алгоритмов

Предписание о последовательности действий алгоритма может быть представлено схемой — логической схемой алгоритма, матричной схемой алгоритма, граф-схемой алгоритма.

Логическая схема алгоритма (ЛСА) впервые была предложена советским математиком А.А. Ляпуновым ( 1911–1973 гг.), профессором кафедры математики военной артиллерийской (в те годы) академии им. Ф.Э. Дзержинского.

ЛСА — это выражение, состоящее из символов операторов, логических условий, следующих в определенном порядке, а также нумерованных стрелок, расставленных особым образом.

Матричная схема алгоритма (МСА) — это квадратная матрица, элементы которой указывают условия передачи управления от i -г o оператора строки к j -му оператору столбца. Строки матрицы нумеруются от первого оператора до предпоследнего, столбцы — от второго до последнего.

Граф-схема алгоритма (ГСА) — это ориентированный граф особого вида. Он содержит вершины четырех типов: 1) операторные, обозначаемые прямоугольниками; 2) условные, обозначаемые ромбами; 3) начальную вершину и 4) конечную вершину, обозначаемые овалами. Вершины соединяются дугами.

Граф-схемы алгоритмов называют просто схемами и выполняют по ГОСТ 701-90 «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения».

Таблица 69