Приглашаем посетить сайт
Алгоритм
АЛГОРИТМ (алгорифм; от лат. формы имени ученого 9 в. аль-Хорезми - Algorithmi) - точное предписание о порядке выполнения некоторой системы операций над исходными данными для получения желаемого результата, которое исполняется вычислителем (человеком, вычислительной машиной). Примерами А. являются «школьные» правила обращения с целыми числами, записанными в десятичной системе счисления: сложение, вычитание и умножение «столбиком», деление с остатком «уголком». А. является одним из основных неопределяемых понятий математики и близких наук, напр. кибернетики, информатики. К основным параметрам А. относят: 1) совокупность возможных исходных данных; 2) совокупность возможных результатов; 3) совокупность возможных промежуточных данных; 4) совокупность возможных инструкций (команд) для преобразования данных; 5) условия начала и завершения работы А. Совокупности из пп. 1-3 предполагаются состоящими из конструктивных объектов, т.е. из конечных слов, возможно, устроенных нелинейно (пример: столбики в действиях над числами), в фиксированных конечных алфавитах. Совокупность из п. 4 конечна. При заданных исходных данных А. задает вычислительный (алгоритмический) процесс: последовательность, начинающаяся исходными данными; т.е. каждый член этой последовательности, кроме первого, получается из предыдущего в результате применения инструкции в соответствии с предписанием, с указанием этой инструкции. Если эта последовательность конечна и последний ее член удовлетворяет условию завершения работы (в частности, последний член последовательности принадлежит совокупности возможных результатов), то считается, что А. завершил свою работу результативно (А. применим к заданным исходным данным) и ее результатом является последний член последовательности; в противном случае (т.е. когда вычислительный процесс бесконечен или конечен, но не удовлетворяет описанному условию) считается, что А. не применим к заданным исходным данным. К основным свойствам А. относят: дискретность - отчетливость каждого шага всякого вычислительного процесса; детерминированность - каждые конкретные исходные данные А. определяют ровно один вычислительный процесс; массовость - совокупность возможных исходных данных бесконечна; элементарность шагов вычислительного процесса - на каждом шаге процесса вычислитель в состоянии выполнить соответствующую инструкцию.
Иногда к А. относят процедуры, имеющие дело с объектами, не являющимися конструктивными. Таковы, напр., геометрические процедуры нахождения середины отрезка с помощью циркуля и линейки, нахождения наибольшей общей меры двух отрезков и т.п. Возможны и другие ослабления требований, напр., отказ от детерминированности.
Каждый А. определяет вычислимую функцию (функцию, вычислимую данным А.): аргумент функции принимает значения из совокупности возможных исходных данных, а значениями являются соответствующие результаты работы А. Одна вычислимая функция может определяться разными А.
Начиная с 30-х гг. 20 в. математики выработали многочисленные формальные аналоги понятия А. и вычислимой функции: машина Поста; машина Тьюринга; нормальный алгорифм Маркова; частично рекурсивная функция; А.-определимая функция и др. В дальнейшем были предложены и другие формализации; в частности, программы, написанные на любом языке программирования из применяемых на практике, задают А. Все предложенные до сих пор формализации понятия А. оказались эквивалентными: классы определяемых ими функций совпадают. Это подтверждает так называемый тезис Черча: класс вычислимых функций, задаваемых (неформальными) А., совпадает с вычислимыми функциями, задаваемыми А., описанными в одной (любой) из указанных формализации. Поскольку А., заданный в фиксированной формализации, является точно описанным математическим объектом, тезис Черча позволил создать математическую теорию алгоритмов.
А.В. Чагров
Лит.: Катленд Н. Вычислимость: Введение в теорию рек у р с и в н ы х функций. М., 1983; Мальцев А.И. Алгоритмы и рекурсивные функции. М., 1986; Марков А.А., Нагорный Н.М. Теория алгорифмов. М., 1996; Роджерс X. Теория рекурсивных функций и эффективная вычислимость. М., 1972.