Следующее определение можно найти в Info для тега algorithm .
Алгоритм представляет собой набор упорядоченных инструкций, основанных на формальном языке, со следующимиусловия:
Конечно.Количество инструкций должно быть конечным.
Исполняемый файл.Все инструкции должны быть выполнены в зависимости от языка, за ограниченное время.
Особенно учитывая
набор упорядоченных инструкций на основе формального языка
Это говорит нам о том, что порядок инструкций имеет значение.Хотя результат двух различных алгоритмов может быть одинаковым, это не означает, что алгоритмы одинаковы.
Ваш пример Грам-Шмидта против МодифицированногоГрам-Шмидт интересный.Глядя на структуру каждого алгоритма, как определено здесь , это действительно разные алгоритмы, даже в описании высокого уровня.Шаги в разных порядках.
Одно важное различие, которое вам нужно сделать, - это набор инструкций и выходной набор. Здесь вы можете найти описание трех алгоритмов кратчайшего пути.Набор возможных результатов на основе входных данных одинаков, но они представляют собой три совершенно разных алгоритма.И у них также есть три совершенно разных описания высокого уровня.Для того, кому это безразлично, хотя они «делают то же самое» (почти больно мне это писать) и эквивалент .
Другим важным отличием является сходство шагов между алгоритмами.Давайте возьмем ваш пример и напишем его в несколько более формальной записи:
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 Описание высокого уровня
"... проза для описания алгоритма, игнорируядетали реализации. На этом уровне нам не нужно упоминать, как машина управляет своей лентой или головкой. "
2 Описание реализации
" ... проза, используемая для определения способа тьюрингаМашина использует свою голову и то, как она хранит данные на своей ленте. На этом уровне мы не предоставляем подробных сведений о состояниях или функции перехода. "
3 Формальное описание
Наиболее подробно"самый низкий уровень ", дает" таблицу состояний "машины Тьюринга.
Учитывая это, ваш вопрос действительно зависит от контекста, в котором он задан. Все три процедуры на высоком уровне одинаковы:
1. Let sum = 0
2. For every element in list add the element to sum
3. Return sum
Нам все равно, как мы проходим список или как мы суммируем, только то, что мы делаем.
На уровне реализации мы уже видим расхождение.Процедуры по-разному перемещаются по «ленте», но сохраняют информацию таким же образом.В то время как procedure 1 перемещает «вправо» на ленте из начальной позиции, procedure 2 перемещает «влево» на ленте от «конца» (осторожно с этим, потому что в ТМ такого нет, его нужно определитьс другим состоянием, которое мы не используем на этом уровне).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., поэтому они не одинаковы.
Но эквивалентны ли эти процедуры на этих разных уровнях?Согласно Merriam Webster , я бы сказал, что они на всех уровнях.Их «ценность» или, что лучше, их «результат» одинаковы для одного и того же входа **.Проблема с сообщением состоит в том, что эти алгоритмы, как вы уже заявили в своем вопросе, возвращают то же самое, делая их эквивалент , но не то же самое .
Вы имеете в виду ** Погрешность с плавающей запятой подразумевает уровень реализации, на котором два алгоритма уже различны.В качестве математической модели нам не нужно беспокоиться о неточности с плавающей запятой, потому что в математике такого нет (математики живут в "идеальном" мире).
Эти алгоритмы разныеописания уровня реализации того же описания высокого уровня.Таким образом, я бы сослался на различных реализаций одного и того же алгоритма высокого уровня, поскольку идея одна и та же.
Последним важным отличием является дальнейшая формализация алгоритма путем назначения его набору по его сложности (как прекрасно отмечено в комментариях @jdehesa).Если вы просто используете большой omicron, ну ... ваши наборы будут огромными и сделают больше алгоритмов "эквивалентными".Это связано с тем, что как сортировка слиянием, так и пузырьковая сортировка являются членами набора O(n^2) по своей временной сложности (очень неточно, но n^2 является верхней границей для обоих).Очевидно, что пузырьковая сортировка не в O(n*log[2](n)), но это описание не указывает это.Если мы используем большую тэту, то сортировка пузырей и слияний больше не совпадает, контекст имеет значение.Описание алгоритма - это больше, чем просто его шаги, и это еще один способ различать алгоритмы.
Подводя итог: это зависит от контекста , особенно от того, кто выразговаривают сЕсли вы сравниваете алгоритмы, обязательно укажите уровень, на котором вы это делаете.Для любительского высказывания «добавить список» будет достаточно, поскольку ваши документы используют описание высокого уровня, когда при объяснении вашего кода объясняйте реализацию вышеупомянутого высокого уровня, и когда вам действительно нужно формализовать свою идею перед ее внесением вкод использовать формальное описание.Последние также позволят вам доказать, что ваша программа выполняется правильно .Конечно, в настоящее время вам больше не нужно писать все состояния базовой TM.Когда вы описываете свои алгоритмы, делайте это в соответствующей форме для настройки.И если у вас есть две разные реализации одного и того же алгоритма высокого уровня, просто укажите различия на уровне реализации (направление обхода, реализация суммирования, формат возвращаемых значений и т. Д.).