алгоритм

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

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

Каждый А. определяет вычислимую функцию (функцию, вычислимую данным А.): аргумент функции принимает значения из совокупности возможных исходных данных, а значениями являются соответствующие результаты работы А. Одна вычислимая функция может определяться разными А.

Начиная с 30-х гг. 20 в. математики выработали многочисленные формальные аналоги понятия А. и вычислимой функции: машина Поста; машина Тьюринга; нормальный алгорифм Маркова; частично рекурсивная функция; А.-определимая функция и др. В дальнейшем были предложены и другие формализации; в частности, программы, написанные на любом языке программирования из применяемых на практике, задают А. Все предложенные до сих пор формализации понятия А. оказались эквивалентными: классы определяемых ими функций совпадают. Это подтверждает так называемый тезис Черча: класс вычислимых функций, задаваемых (неформальными) А., совпадает с вычислимыми функциями, задаваемыми А., описанными в одной (любой) из указанных формализации. Поскольку А., заданный в фиксированной формализации, является точно описанным математическим объектом, тезис Черча позволил создать математическую теорию алгоритмов.

А.В. Чагров

Лит.: Катленд Н. Вычислимость: Введение в теорию рек у р с и в н ы х функций. М., 1983; Мальцев А.И. Алгоритмы и рекурсивные функции. М., 1986; Марков А.А., Нагорный Н.М. Теория алгорифмов. М., 1996; Роджерс X. Теория рекурсивных функций и эффективная вычислимость. М., 1972.

Источник: Энциклопедия эпистемологии и философии науки на Gufo.me


Значения в других словарях

  1. АЛГОРИТМ — АЛГОРИТМ, разложенный поэтапно набор команд или процедур, которым необходимо следовать для получения определенного результата из исходного набора вводных данных. Научно-технический словарь
  2. алгоритм — АЛГОРИТМ (от algorithmi, algorismus, первонач. — лат. транслитерация араб. имени ср.-азиатского математика аль-Хорезми), способ (программа) решения вычислит. Сельскохозяйственный словарь
  3. Алгоритм — Способ (программа) решения вычислительных и других задач, точно предписывающий, как и в какой последовательности получить результат, однозначно определяемый исходными данными; одно из основных понятий математики и кибернетики. Название: от фр. Судьба эпонимов. Словарь-справочник
  4. АЛГОРИТМ — АЛГОРИТМ (лат. algoritmi, algoritmus; первоначально — транслитерация имени среднеазиатского ученого 9 в. — Мухамеда бен Мусы аль-Хорезми) — одно из основных понятий логики и математики. Термин... Новейший философский словарь
  5. алгоритм — сущ., м., употр. сравн. часто (нет) чего? алгоритма, чему? алгоритму, (вижу) что? алгоритм, чем? алгоритмом, о чём? об алгоритме; мн. что? алгоритмы, (нет) чего? алгоритмов, чему? алгоритмам, (вижу) что? алгоритмы, чем? алгоритмами, о чём?... Толковый словарь Дмитриева
  6. алгоритм — Заимств. в Советскую эпоху из англ. яз., в котором algorithm восходит к ср.-лат. algorithmus < algorizmus (по имени узбек. математика Аль-Хорезми). Этимологический словарь Шанского
  7. алгоритм — АЛГОРИТМ -а; м. 1. Матем. Последовательность проведения вычислительных операций для определения искомого результата, искомой величины. А. извлечения корня из числа. // Последовательность действий для выполнения какой-л. задачи. Толковый словарь Кузнецова
  8. АЛГОРИТМ — АЛГОРИТМ, алгорифм (от лат. algorithmi, algorismus, по имени арабского ученого 9 в. ал-Хорезми) – точное предписание, задающее потенциально осуществимый (см. Новая философская энциклопедия
  9. алгоритм — Способ (программа) решения вычислительных и других задач, точно предписывающий, как и в какой последовательности получить результат, однозначно определяемый исходными данными. Техника. Современная энциклопедия
  10. АЛГОРИТМ — (от имени среднеазиатского математика VIII-IX вв. аль-Хорезми) — в математике: точное предписание для выполнения «вычислительного» (комбинаторного) процесса. Обычно подразумевается, что... Большой психологический словарь
  11. алгоритм — алгоритм I м. см. алгорифм 1. Определенная последовательность операций или вычислений (в математике). 2. Программа для электронной вычислительной машины, позволяющая от исходных данных прийти к искомому результату (в информатике). II м. Обобщённая схема какой-либо или чьей-либо деятельности. Толковый словарь Ефремовой
  12. АЛГОРИТМ — АЛГОРИТМ (алгорифм) (от algorithmi — algorismus, первоначально — лат. транслитерация имени математика аль-Хорезми) — способ (программа) решения вычислительных и др. Большой энциклопедический словарь
  13. алгоритм — АЛГОРИТМ, а, м. (спец.). Совокупность действий, правил для решения данной задачи. А. извлечения корня. | прил. алгоритмический, ая, ое. Толковый словарь Ожегова
  14. алгоритм — -а, м. мат. Система вычислений по строго определенным правилам, которая после последовательного их выполнения приводит к решению поставленной задачи. Алгоритм извлечения корня из числа. Построение системы алгоритмов. Малый академический словарь
  15. алгоритм — Английское – algorithm. Латинское – algorizmus. Слово «алгоритм» получило распространение в русском языке в конце 20-х гг. XX в. По всей видимости, данное слово заимствовано из английского языка и восходит к латинскому algorizmus... Этимологический словарь Семёнова
  16. алгоритм — Алгори́тм/. Морфемно-орфографический словарь
  17. алгоритм — Совокупность последовательных логических действий, реализуемых машиной и аналогичных некоторым операциям естественного логического мышления. Толковый переводоведческий словарь / Л.Л. Нелюбин. — 3-е изд., перераб. — М.: Флинта: Наука, 2003 Толковый переводоведческий словарь
  18. Алгоритм — (от algorithmi, algorismus, первоначально — латинская транслитерация имени среднеазиатского ученого АЛЬ-ХОРЕЗМИ) способ решения вычислительных и других задач, точно предписывающий, как и в какой последовательности получить результат... Педагогический терминологический словарь
  19. алгоритм — орф. алгоритм, -а Орфографический словарь Лопатина
  20. Алгоритм — Алгорифм, одно из основных понятий (категорий) математики, не обладающих формальным определением в терминах более простых понятий, а абстрагируемых непосредственно из опыта. Большая советская энциклопедия
  21. Алгоритм — I Алгоритм набор правил, позволяющий решить любую конкретную задачу из определенного класса. С помощью А. задают последовательность действий, которые надо совершить для получения искомого решения, например А. диагностики заболевания по симптомам (см. Медицинская энциклопедия
  22. АЛГОРИТМ — (от латинской формы имени среднеазиатского математика аль-Хорезми) правило действий, последовательность проведения вычислительных операций, способ нахождения искомого результата. Экономический словарь терминов
  23. алгоритм — (algorismus) Решение задачи при помощи системы вычислений, ориентированной на разбиение операций на более простые, и последовательное их выполнение. Для алгоритма характерны дискретность, детерминированность шагов, направленность, массовость. Словарь лингвистических терминов Жеребило
  24. алгоритм — АЛГОРИТМ а, м. algorithme m. 1230 algorisme. Лексис.1. В математике — общепонятное предписание, определяющее детерминированный вычислительный процесс, ведущий от исходных данных к искомому результату. БАС-2. Словарь галлицизмов русского языка