АЛГОРИТМ, алгорифм
АЛГОРИТМ (АЛГОРИФМ)
[от algorithmi, algorismus, первоначально – латинская транслитерация имени математика аль-Хорезми] – 1) способ (программа) решения вычислительных и др. задач, точно предписывающий, как и в какой последовательности получить результат, однозначно определяемый исходными данными. Алгоритм – набор инструкций, задающих последовательность действий по преобразованию некоторой совокупности исходных данных для получения определенного результата. Алгоритм является одной из основных категорий математики, в рамках которой с ним связано задание вычислительных процедур. В вычислительной технике для описания алгоритма используют языки программирования. Вариант алгоритмов – система операций, выполняемых последовательно и по определенным правилам для решения конкретной проблемы или задачи; 2) заранее заданное понятное и точное предписание возможному исполнителю научной темы совершить определенную последовательность действий для получения решения исследования за конечное число шагов. Понятие алгоритма не имеет формального определения в терминах более простых понятий, абстрагируется непосредственно из опыта.
Источник: Словарь науки. Общенаучные термины и определения. 2008 г.
АЛГОРИТМ, алгорифм
от лат. algorithmi, algorismus, n имени арабского ученого 9 в. ал-Хорезми)—точное предписание, задающее потенциально осуществимый (см. Абстракция потенциальной осуществимости) вычислительный процесс (процесс исполнения алгоритма), ведущий от исходных данных, которые могут варьировать, к конечному результату. Овладение общим методом решения точно поставленной задачи по сути дела означает знание алгоритма. Так, умение складывать два числа означает владение алгоритмом сложения чисел (напр., сложением столбиком, которому учат в школе). Необходимо различать алгоритм и алгоритмическое предписание, имеющее внешнюю форму алгоритма, но включающее не до конца определенные шаги. Так, для перевода текста с одного естественного языка на другой нельзя дать алгоритм, поскольку придется апеллировать к таким неточным понятиям, как смысл и контекст. При попытке же применения точного алгоритма получается то, что в более откровенной форме выдают машинные переводчики и в более мягкой, но от этого не менее вредной—профессиональные переводчики в тот момент, когда выходят за рамки полностью освоенных ими понятий и действий. Поскольку процесс исполнения потенциально осуществим, в теоретическом определении алгоритма отвлекаются от реальных ограничений на ресурсы и следят лишь за тем, чтобы в любой момент вычисления требуемая информация и другие ресурсы были конечными. При создании практических алгоритмов проблемы сложности выходят на первый план.
Хотя неформально математики все время занимались поиском алгоритмов, данное понятие было уточнено лишь в 30-х гг. 20 в. Первыми уточнениями были абстрактные определения частично-рекурсивных и представимых функций в формальной теории чисел, появившиеся в связи с задачами доказательств теории. В 1936 Э. Пост и А. Тьюринг независимо друг от друга предложили понятия абстрактных вычислительных машин и подметили, что любой алгоритм в интуитивном смысле слова может быть реализован на данных машинах, несмотря на кажущуюся примитивность их элементарных действий. Так, памятью машины Тьюринга является потенциально бесконечная лента, в каждой клетке которой записан символ из заранее заданного конечного алфавита. Более того, достаточно рассматривать ленту, каждая клетка которой содержит один бит информации, т. е. либо пуста, либо содержит символ |. Процессор машины Тьюринга состоит из головки, которая в любой момент обозревает одну клетку, и программы, состоящей из конечного числа команд, обычно нумеруемых натуральными числами. Каждая команда представляет собой условное действие, зависящее от символа, записанного в клетке. Это действие имеет вид совокупности элементарных инструкций формы ab(L, R, S)i, в которой присутствует лишь одна из букв L, R, S. — приказ сдвинуться на следующем такте на одну клетку влево, R—враво, S— остаться на месте. Элементарная инструкция означает следующее: если машина видит а, записать в клетку Ь, передвинуться в соответствии с командой и перейти к исполнению команды /. Такая элементарность действий машины явилась результатом проведенного Тьюрингом методологического анализа элементарных действий человека по исполнению алгоритмов. Команды машины Поста предвосхитили систему команд современных вычислительных машин. В машине имеются регистры, содержащие натуральные числа, элементарные операции увеличения и уменьшения числа на 1 и условный переход, если число в регистре равно 0. Одновременно А. Черч и X. Б, Карри создали одно из самых абстрактных понятий алгоритма: gamma-определимость, выразимость с помощью терма комбинаторной логика.
И ранее созданные теоретические понятия, и самые элементарные, и самые абстрактные из вновь появившихся уточнений алгоритма оказались эквивалентны. Этот факт, подтвержденный в дальнейшем для всех вновь появлявшихся точных определений алгоритма, послужил основой утверждения, скромно называемого в математике тезисом Черча, хотя степень его подтвержденности ныне выше, чем у любого физического «закона». Содержательное понятие алгоритма эквивалентно по объему любому из имеющихся в данный момент математических уточнений этого понятия, в частности вычислимости на машине Тьюринга.
Одним из последних появилось уточнение алгоритма, наиболее близкое к современным языкам программирования, — рекурсивные схемы Скотта. Это — совокупность определений вида /(5c)
Хотя неформально математики все время занимались поиском алгоритмов, данное понятие было уточнено лишь в 30-х гг. 20 в. Первыми уточнениями были абстрактные определения частично-рекурсивных и представимых функций в формальной теории чисел, появившиеся в связи с задачами доказательств теории. В 1936 Э. Пост и А. Тьюринг независимо друг от друга предложили понятия абстрактных вычислительных машин и подметили, что любой алгоритм в интуитивном смысле слова может быть реализован на данных машинах, несмотря на кажущуюся примитивность их элементарных действий. Так, памятью машины Тьюринга является потенциально бесконечная лента, в каждой клетке которой записан символ из заранее заданного конечного алфавита. Более того, достаточно рассматривать ленту, каждая клетка которой содержит один бит информации, т. е. либо пуста, либо содержит символ |. Процессор машины Тьюринга состоит из головки, которая в любой момент обозревает одну клетку, и программы, состоящей из конечного числа команд, обычно нумеруемых натуральными числами. Каждая команда представляет собой условное действие, зависящее от символа, записанного в клетке. Это действие имеет вид совокупности элементарных инструкций формы ab(L, R, S)i, в которой присутствует лишь одна из букв L, R, S. — приказ сдвинуться на следующем такте на одну клетку влево, R—враво, S— остаться на месте. Элементарная инструкция означает следующее: если машина видит а, записать в клетку Ь, передвинуться в соответствии с командой и перейти к исполнению команды /. Такая элементарность действий машины явилась результатом проведенного Тьюрингом методологического анализа элементарных действий человека по исполнению алгоритмов. Команды машины Поста предвосхитили систему команд современных вычислительных машин. В машине имеются регистры, содержащие натуральные числа, элементарные операции увеличения и уменьшения числа на 1 и условный переход, если число в регистре равно 0. Одновременно А. Черч и X. Б, Карри создали одно из самых абстрактных понятий алгоритма: gamma-определимость, выразимость с помощью терма комбинаторной логика.
И ранее созданные теоретические понятия, и самые элементарные, и самые абстрактные из вновь появившихся уточнений алгоритма оказались эквивалентны. Этот факт, подтвержденный в дальнейшем для всех вновь появлявшихся точных определений алгоритма, послужил основой утверждения, скромно называемого в математике тезисом Черча, хотя степень его подтвержденности ныне выше, чем у любого физического «закона». Содержательное понятие алгоритма эквивалентно по объему любому из имеющихся в данный момент математических уточнений этого понятия, в частности вычислимости на машине Тьюринга.
Одним из последних появилось уточнение алгоритма, наиболее близкое к современным языкам программирования, — рекурсивные схемы Скотта. Это — совокупность определений вида /(5c)
Источник: Новая философская энциклопедия