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

Алгоритм – конечный набор правил, позволяющих чисто механически решать любую задачу из некоторого класса однотипных задач. Метод предложил Мухаммед бен Муса аль-Хорезми (Муса из Хорезма), имя которого с 12 века транслитерировалось как Algoritmi. Ясное понимание алгоритма в качестве самостоятельной сущности встречается в 1912 году в трудах великого французского математика Эмиля Бореля. Суть метода в следующем. Для каждой единичной задачи умножения исходным данным служит конкретная пара чисел, а для каждой единичной задачи на решение квадратного уравнения – конкретное квадратное уравнение. Решением же массовой задачи является общий метод, дающий решение для каждой из составляющих ее единичных задач. Если предложенный общий метод состоит в последовательности строго детерминированных операций, ведущих от исходных данных к результату, он называется конструктивным, или эффективным, или алгоритмическим, еще короче алгоритмом.

Говорят об алгоритме сложения столбиком, об алгоритме решения квадратных уравнений.

Простейшими примерами могут служить алгоритмы вычитания, сложения, умножения и деления целых чисел в арифметике с десятичной системой счисления. Осуществление алгоритмического процесса может быть передано машине, которая благодаря быстродействию может решать задачи, на которые человеку потребуется очень много времени. Прорыв в понимании этой возможности произошел в 1936 году, когда Алонзо Черч в США и Алан Тьюринг в Англии предложили математические уточнения понятия алгоритма и на этой основе предъявили первые примеры массовых проблем, неразрешимых алгоритмически, в числе которых оказалась проблема неразрешения. Дело в том, что массовая проблема считается алгоритмически неразрешимой, если не существует решающего ее алгоритма, т.е. такого единого алгоритма, который позволял бы находить решение для каждой из тех единичных проблем, которые и составляют рассматриваемую массовую проблему, или задачу.

В.Л.Успенский приводит один из наглядных примеров. Воспользуемся им. Допустим, мы участвуем в игре, подобной домино. У нас в руках пластинки, разделенные пополам, в каждой из половинок записывается цепочка из букв x и z. Цепочки длины один: x, z. А цепочки длины два: xx, xz, zx, zz. Тогда как цепочки длины три: xx, xzx, xzz, zxx, zxz, zzx, zzz. Возможна и цепочка длины ноль (в этом случае не записано ничего). Одна из цепочек длины семь будут выглядеть так: zxzxxxz. Допустим, у нас четыре пластинки, которые мы обозначим буквами A, B, C, D.

x x xz zzz

zx zzxx zz z

A B C D

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

В.Л.Успенский дает пояснение на примерах. Пусть объявленный набор содержит всего только одну пластину A из приведенного выше примера. Ясно, что решение невозможно, потому что, сколько раз ни прикладывай пластинку A к самой себе, нижняя строка всегда окажется длиннее верхней. По сходной причине решения не существует, если объявленный набор состоит из одной только пластинки D, только тут длиннее будет верхняя строка. Желающие могут попытаться доказать, что решения не существует и в том случае, когда объявленный набор состоит из двух пластинок A и D.

А вот если объявить набор из всех четырех пластинок, то решение существует. Действительно, если сложить пластинки в таком порядке: DBCDA, то и верхняя, и нижняя строка окажутся одинаковы: zzzxxzzzzx.

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

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