Алгоритм— это точное предписание, задающее вычислительный процесс, или, другими словами, точное изложение последовательности действий над исходными данными, выполнение которой обеспечивает получение искомого результата, полностью определяе-мого исходными данными. В качестве примеров простейших алгоритмов могут служить правила выполнения арифметических действий, извлечение квадратного корня, решения системы алгебраических уравнений и т. д.К более сложным можно отнести создание сайтов .К важнейшим свойствам алгоритма относятся: определенность — однозначность предписываемой последовательности действий, не допускающая произвольного ее толкования; массовость — пригодность для решения многих или даже всех задач данного типа при различных исходных данных — расчлененность алгоритма на отдельные элементарные акты; результативность — возможность получения решения за конечное число шагов; инвариантность по отношению к вычислителю, означающая, что алгоритм может оставаться неизменным при выполнении предписываемых им вычислений человеком или машиной любого типа.
Существует несколько способов записи алгоритмов. Прежде всего алгоритм можно записать в терминах обычного разговорного языка. Однако это неудобно, так как запись получается громоздкой, не наглядной, может возникнуть разноречивость толкования алгоритма. Более четка запись в виде формулы, и наконец, наиболее наглядно и удобно представление алгоритма в виде логической блок-схемы.
В случае необходимости эта блок-схема может быть и более детализирована и таким образом приближена к блок-схеме программы. Однако разработка и вычерчивание блок-схемы для больших и сложных задач — весьма трудоемкий и длительный процесс. Этого недостатка лишены способы записи алгоритмов на искусственных алгоритмических языках, представляющих четко определенные совокупности специальных символов (алфавита) и правил построения алгоритмов.
Раздел математики, изучающий общие свойства алгоритмов, называется теорией алгоритмов. Хотя отдельные исследования, положенные впоследствии в основу теории алгоритмов, проводились еще в 20-х годах нашего века, началом систематической раз-работки этой теории можно считать 1936 г., когда американский математик А. Черч четко сформулировал понятие вычислимой функции как функции, вычисление значений которой осуществимо с помощью некоторой эффективной процедуры или алгоритма.
В том же 1936 г. английским ученым А. Тьюрингом и независимо от него американским ученым Э. Постом была выдвинута идея абстрактного цифрового автомата с бесконечной памятью, известного как машина Тьюринга. Ее можно определить как абстрактное понятие вычислительной машины, принципиально пригодной для реализации любого вычислительного алгоритма (программы вычислений).
Представим некоторую задачу в виде совокупности данных, перерабатываемых по определенному алгоритму, и совокупности возможных результатов. Если задача разрешима, то, очевидно, существует такая функция ср, что j = cp (i), где j — номер результата, a i — номер совокупности исходных данных.
Машину Тьюринга представляют в виде бесконечной ленты Л с пронумерованными ячейками, управляющего устройства УУ и головки Г, которая обозревает одну из ячеек ленты, может изменять запись в ячейке, а также сдвигаться на одну ячейку вправо или влево. Функционирование машины Тьюринга полностью определяется исходной информацией, записанной в ячейках ленты, и оператором преобразования УУ, заданного записанной в нем таблицей переходов.
Л. Тьюринг теоретически доказал, что при достаточно большой таблице переходов и достаточно большом количестве шагов (тактов) работы машины ею может быть разрешена сколь угодно сложная задача. Машина Тьюринга никогда не была построена, а если бы подобное устройство и было реализовано, то решение сколько-нибудь сложных задач на нем было бы нецелесообразно, так как для этого понадобилось бы очень большое количество шагов и, следовательно, очень длительное время. Однако разработка соответствующих теоретических вопросов стала важным этапом развития теории цифровых вычислительных машин (ЦВМ) и послужила доказательством принципиальной возможности решения на них любых алгоритмически разрешимых задач.
Большой вклад в теорию лагоритмов внес советский математик А. А. Марков, который, в частности, ввел понятие нормального алгоритма, применимого к словам некоторого алфавита и полностью определяемого*указанием этого алфавита и схемой алгоритма, ко-торая представляет список конечного числа так называемых формул подстановок. Важным результатом исследований А. А. Маркова стало доказательство неразрешимости ряда алгебраических проблем, т. е. массовых проблем, для которых не существует эффективных методов разрешения.
Теория алгоритмов имеет большое прикладное значение, так как она явилась основой для разработки алгоритмических языков, ряда положений теории автоматов, современных методов программирования и решения задач на ЦВМ, а также разработок в области кибернетики.