Алгоритм - это детерминированный автомат для достижения цели, которая, начиная с заданного начального состояния, закончится в конечном состоянии. Качество реализации зависит от ее скорости, размера и потребления ресурсов.

Резюме

Что такое алгоритм?

Общепринятого определения слова «алгоритм» не существует.
Простое определение: Набор инструкций для решения задачи.

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

Очень простым примером алгоритма является умножение двух чисел: на ранних компьютерах с ограниченными процессорами это достигалось подпрограммой, которая в ряде циклов, основанных на первом числе, складывала второе число. Алгоритм переводит метод в компьютерные команды.

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

«Неформальный

аргумент Тьюринга в пользу своего тезиса оправдывает более сильный тезис: любой алгоритм может быть смоделирован машиной Тьюринга».

и Savage:

«Алгоритм - это вычислительный процесс, определяемый машиной Тьюринга».

Обычно, когда алгоритм участвует в обработке информации, данные считываются из входного источника, или устройства, записываются на выход, или устройства. периферийные и/или сохраненные для последующей обработки. Запись данных рассматривается как внутренняя часть объекта, выполняющего алгоритм. На практике состояние хранится в структуре данных.

Для всех этих вычислительных процессов алгоритм должен быть строго определён: должно быть определено, как он ведёт себя во всех возможных обстоятельствах. При этом все условные шаги должны систематически рассматриваться в каждом конкретном случае; критерии для каждого должны быть четкими и вычислимыми.

Поскольку алгоритм - это точный список точных шагов, порядок вычислений всегда будет иметь решающее значение для работы алгоритма. Инструкции должны быть явно определены и описаны сверху вниз, идея, формально выраженная как поток управления. До этого момента обсуждение определения алгоритма предполагало императивное программирование. Это самая распространённая концепция; он пытается описать задачу дискретными, «механическими» средствами. Понятие присвоения значения переменной специфично для этой концепции. Это приводит к представлению о «памяти» как о обрывке листа бумаги.

Функциональное программирование или логическое программирование предлагают различные концепции того, что такое алгоритм.

Определения алгоритма слова

Бласс и Гуревич

Бласс и Гуревич описывают свою работу как вдохновлённую машинами Тьюринга, машины Колмогорова-Успенского (KU-машины), машина модификации хранилища Шёнхаге (SMM), а указательные машины, определённые Кнутом, Ганди и Марковым, также рассматриваются как влиятельные предшественники.

Гуревич предлагает четкое определение того, что такое алгоритм (кратко изложено здесь):

Неформальный аргумент Тьюринга в пользу своего тезиса оправдывает более сильный тезис: любой алгоритм может быть смоделирован машиной Тьюринга. На практике это может показаться нелепым. Можем ли мы обобщить машинность так, чтобы любой алгоритм, независимо от степени его абстракции, моделировался общей машиной? Но предположим, что такая обобщенная машина Тьюринга существует. Какими были бы ее государства? Структура первого порядка... Во всех случаях будет достаточно небольшого конкретного набора инструкций. Обработка была бы эволюцией государства. Он может быть недетерминированным, может взаимодействовать со своей средой, быть параллельным и многоагентным, иметь динамическую семантику. Две точки опоры их работы: тезисы Тьюринга и представление Тарского о структуре первого порядка.

Приведенное выше предложение «обработка как эволюция состояния» заметно отличается от определения алгоритма Кнута и Стоуна как машинной программы Тьюринга. Скорее, это соответствует тому, что Тьюринг назвал полной конфигурацией, которая включает в себя как текущую инструкцию (состояние), так и состояние ленты. Kleene (1952) показывает пример ленты с 6 символами на ней, все остальные квадраты белые, и как «Gödelize» комбинированный статус таблицы-ленты.

Булос и Джеффри

Их определение таково:

"Явные инструкции для определения n-го члена множества, для n произвольно конечного. Такие инструкции даются достаточно явно, в форме, которую может использовать компьютер» .calculate или человеком, который способен транспонировать очень базовые операции в символы».

Кнут

Кнут (1968, 1973) дал список из пяти свойств, которые широко признаны в качестве предпосылок алгоритма:

1. Конечность: «Алгоритм всегда должен заканчиваться после конечного числа шагов».
2. Точное определение: "Каждый шаг алгоритма должен быть точно определён; действия, подлежащие переносу, должны быть строго и однозначно определены для каждого случая
.
3. Входы: "... величины, заданные ему до начала работы алгоритма. Эти входные данные берутся из указанного набора объектов".
4. Выходные данные: «... количества, имеющие определенное отношение к входным данным».
5. Пропускная способность: «... все операции, которые должен выполнять алгоритм, должны быть достаточно базовыми, чтобы их можно было в принципе выполнить за конечное время человеком с помощью бумаги и карандаша».

Кнут предлагает в качестве примера алгоритм Евклида для определения наибольшего общего делителя двух целых чисел.

Кнут признает, что, хотя его описание того, что такое алгоритм, может быть интуитивно ясным, ему не хватает формальной строгости, при этом точно не ясно, что означает «точно определенный», или «строго и однозначно определенный», или «достаточно базовый», и так далее. Усилия в этом направлении он прилагает в своём первом томе, где подробно определяет то, что называет "машинным языком", для своего "мифического MIX... первый полиненасыщенный компьютер» .в мире». Многие алгоритмы книги написаны на языке MIX. Он также использует древовидные диаграммы, блок-схемы и диаграммы состояний.

Марков

А. А. Марков (1954) даёт такое определение алгоритма:

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

"Следующие три характеристики специфичны для алгоритмов и определяют их роль в математике:

а) точность рецепта, не оставляя места для произвола, и его универсальная понятность, таким образом, определенный аспект алгоритма;

б) возможность старта с исходных данных, которые могут меняться в заданных пределах: общность алгоритма;

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

Он признает, что его определение «не претендует на математическую точность». Его монография 1954 года была попыткой более точно определить алгоритм; полученное определение - свой формальный алгоритм - он видел как «эквивалентное понятию рекурсивной функции». Это определение включало четыре основных компонента: 1. Разделите элементарные шаги, каждый из которых выполняется в соответствии с одним из правил подстановки, приведенных в начале.

2. Шаги местного характера.

3. Схема алгоритма: правила подстановки формул.

4. Способ выявления подстановки для заключения.

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

Минский

Минский (1967) утверждает, что алгоритм является «эффективной процедурой» и является для него синонимом.
Этот термин используется другими авторами, в том числе Кнутом. То, что Минский называет «эффективной процедурой», определяется следующим образом:

«Набор правил, который говорит нам, от момента к моменту, точно, как себя вести».

Однако он признает, что это открыто для критики:

«Толкование правил оставлено в распоряжении любого лица или агента».

Это приводит его к улучшению, чтобы указать "наряду с инструкциями правил детали механизма, который их интерпретирует. Чтобы избежать утомительного процесса необходимости делать это постоянно для каждой новой процедуры, он рассчитывает определить достаточно однородное семейство механизмов, следующих правилам. Он формулирует это следующим образом:

"(1) язык, в котором выражены своды правил поведения, и

(2) единая машина, которая может интерпретировать инструкции на языке и таким образом транспонировать этапы указанного процесса".

Однако в итоге он все же сокрушается, что субъективная сторона остается. Разные люди могут не согласиться с тем, можно ли считать ту или иную процедуру эффективной.

Но Минский не сдается. Он немедленно выпускает «Анализ вычислительного процесса Тьюринга». В ней он описывает то, что называет тезисом Тьюринга:

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

Проанализировав «Аргумент Тьюринга», он наблюдает эквивалентность многих интуитивных формулировок Тьюринга, Чёрча, Клини, Поста и Смулляна, что приводит к предположению, что действительно существует объективное или абсолютное понятие.

Камень

Стоун (1972) и Кнут были профессорами Стэнфордского университета в то же время, и мы не удивлены, обнаружив сходство в их определениях:

"Таким образом, мы определяем алгоритм

int multiply(int x, int y) 
   int sum = 0 
   while y > 0 
      sum + x 
   let y - 1 
return sum 

int a = 5 
int b = 7 

print a,"x", b, "=", multiply(a, b)

Références

• Мартин Дэвис. The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions. New York: Raven Press, 1965.
  Davis fournit un commentaire avant chaque article.
• Юрий Гуревич. Последовательные абстрактные конечные автоматы захватывают последовательные алгоритмы, ACM Transactions on Computational Logic, Vol 1, No 1 (July 2000), pages 77-111.
  Inclut une bibliographie de 33 sources.
• А. А. Марков. Теория алгоритмов. Импринт Москва, АН СССР, 1954. Titre original: Teoriya algerifmov.
• Марвин Минский. Вычисление: Finite and Infinite Machines, First, Prentice-Hall, Englewood Cliffs, NJ. 1967.
• Гарольд С. Стоун. Введение в компьютерную организацию и структуры данных, 1972, McGraw-Hill, New York.
  n particulier le premier chapitre intitulé: Алгоритмы, машины Тьюринга и программы.

Алгоритмы

Определение алгоритма слова - Классификация - История алгоритмов - Список алгоритмов - Сито Эратосфена - Число Фибоначчи