Как обращаться к «эквивалентным» алгоритмам

Следующее определение можно найти в файле Информация для тега algorithm.

An algorithm is a set of ordered instructions based on a formal language with the following conditions:

Finite. The number of instructions must be finite.

Executable. All instructions must be executable in some language-dependent way, in a finite amount of time.

Учитывая особенно

set of ordered instructions based on a formal language

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

Ваш пример Грамма-Шмидта против модифицированного Грама-Шмидта интересен. Глядя на структуру каждого алгоритма, как определено здесь, это действительно разные алгоритмы, даже в описании высокого уровня. Шаги идут в разном порядке.

Необходимо провести важное различие между набором инструкций и выходным набором. Здесь вы можете найти описание трех алгоритмов кратчайшего пути. Набор возможных результатов на основе ввода одинаков, но это три совершенно разных алгоритма. И у них также есть три совершенно разных описания высокого уровня. Тому, кого это не волнует, хотя эти "делают то же самое" (мне почти больно это писать) и являются эквивалент.

Еще одним важным отличием является сходство шагов между алгоритмами. Давайте возьмем ваш пример и напишем его в более формальной нотации:

procedure 1 (list, n):
    let sum = 0
    for i = 1 : n
        sum = sum + list[i]
    end for
    sum //using implicit return

procedure 2 (list, n):
    let sum = 0
    for i = n : 1
        sum = sum + list[i]
    end for
    sum //using implicit return

Эти два фрагмента кода имеют одинаковый набор результатов, но инструкции выглядят по-разному. Тем не менее, это не так на высоком уровне. Это зависит от того, как вы формализуете процедуры. Циклы — это одна из тех вещей, которые, если мы сведем их к индексам, изменят нашу процедуру. Однако в этом конкретном случае (как уже отмечалось в комментариях) мы можем заменить цикл на более формализованный цикл for each.

procedure 3 (list):
    let sum = 0
    for each element in list
        sum = sum + element
    end for
    sum

procedure 3 теперь делает то же самое, что и procedure 1 и procedure 2, их результат тот же, но инструкции снова кажутся разными. Таким образом, процедуры представляют собой алгоритмы эквивалент, но отличаются на уровне реализации. Они не совпадают, так как порядок выполнения инструкций по суммированию различен для procedure 1 и procedure 2 и полностью игнорируется в procedure 3 (это зависит от вашей реализации for each!).

Вот тут-то и появляются концепции описание высокого уровня. Они одинаковы для всех трех алгоритмов, как вы уже указали. Следующее взято из Статья в Википедии, на который вы ссылаетесь.

1 High-level description

"...prose to describe an algorithm, ignoring the implementation details. At this level, we do not need to mention how the machine manages its tape or head."

2 Implementation description

"...prose used to define the way the Turing machine uses its head and the way that it stores data on its tape. At this level, we do not give details of states or transition function."

3 Formal description

Most detailed, "lowest level", gives the Turing machine's "state table".

Имея это в виду, ваш вопрос действительно зависит от контекста, в котором он задан. Все три процедуры для высокий уровень одинаковы:

1. Let sum = 0
2. For every element in list add the element to sum
3. Return sum

Нам все равно, как мы пройдемся по списку или как подведем итоги, нам важно только то, что мы делаем.

На уровень реализации мы уже видим расхождение. Процедуры перемещаются по «ленте» по-разному, но сохраняют информацию одинаковым образом. В то время как procedure 1 перемещается по ленте «вправо» из начальной позиции, procedure 2 перемещается «влево» по ленте с «конца» (осторожно с этим, потому что в TM такого нет, его нужно определить с другим состоянием , который мы не используем на этом уровне). procedure 3, ну, это недостаточно хорошо определено, чтобы сделать это различие.

На низкий уровень нам нужно быть очень точными. Я не собираюсь опускаться до уровня таблицы состояний ТМ, поэтому, пожалуйста, примите это довольно неформальное описание процедуры.

procedure 1:

1. Move right until you hit an unmarked integer or the "end" 
//In an actual TM this would not work, just for simplification I am using ints
    1.e. If you hit the end terminate //(i = n)
2. Record value //(sum += list[i]) (of course this is a lot longer in an actual TM)
3. Go back until you find the first marked number
4. Go to 1.

procedure 2 будет обратным по инструкции 1. и 3., поэтому они не совпадают.

Но эквивалентны ли эти процедуры на этих разных уровнях? Согласно Мерриам Вебстер, я бы сказал, что они есть на всех уровнях. Их «значение» или, лучше сказать, их «выход» одинаковы для одних и тех же входных данных**. Проблема с общением заключается в том, что эти алгоритмы, как вы уже указали в своем вопросе, возвращают одно и то же, что делает их эквивалент, но не такой же.

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

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

Последним важным отличием является дальнейшая формализация алгоритма путем назначения его набору из-за его сложности (как прекрасно указано в комментариях @jdehesa). Если вы просто используете большой омикрон, ну... ваши наборы будут огромными и сделают больше алгоритмов «эквивалентными». Это связано с тем, что и сортировка слиянием, и пузырьковая сортировка являются членами множества O(n^2) для их временной сложности (очень неточно, но n^2 является верхней границей для обоих). Очевидно, пузырьковой сортировки нет в O(n*log[2](n)), но в описании это не указано. Если мы используем большой тета, то пузырьковая сортировка и сортировка слиянием больше не находятся в одном и том же наборе, контекст имеет значение. Описание алгоритма — это больше, чем просто его шаги, и это еще один способ, которым вы можете помнить, чтобы различать алгоритмы.

Подводя итог: это зависит от контекст, особенно от того, с кем вы разговариваете. Если вы сравниваете алгоритмы, убедитесь, что вы указали уровень, на котором вы это делаете. Для любителя будет достаточно сказать «добавьте список», поскольку в ваших документах используется описание высокого уровня, при объяснении вашего кода поясняйте свою реализацию вышеприведенного высокого уровня, и когда вам действительно нужно формализовать свою идею, прежде чем помещать ее в код использует формальное описание. Последнее также позволит вам доказать, что ваша программа выполняется правильно. Конечно, в настоящее время вам больше не нужно записывать все состояния базовой TM. Когда вы описываете свои алгоритмы, делайте это в соответствующей сеттингу форме. И если у вас есть две разные реализации одного и того же алгоритма высокого уровня, просто укажите различия на уровне реализации (направление обхода, реализация суммирования, формат возвращаемых значений и т. д.).

Я думаю, вы могли бы назвать это неоднозначным алгоритмом. Хотя этот термин может быть недостаточно определен в литературе, рассмотрим ваш пример добавления списка элементов.

Это можно определить как
1. Инициализировать сумму до нуля
2. Добавляйте элементы в список, чтобы суммировать их один за другим.
3. вернуть сумму

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

Один хороший пример, с которым я столкнулся: слайд лекции Корнелла. Этот грязный пример с бутербродом — золотой.

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

Возможно, вы имеете в виду алгоритмы, которые, по крайней мере на первый взгляд, выполняют одну и ту же основную задачу, но имеют разные уровни численной стабильности («надежность»). Два примера этого могут быть:

• вычисление среднего и дисперсии (где так называемый «алгоритм Велфорда» численно более стабилен, чем наивный подход), и
• решение квадратного уравнения (с множеством формул с разной "надежностью" на выбор).

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