Здравствуйте, Кодёнок, Вы писали:
Кё>Пузырек и qsort не эквивалентны Это два разных алгоритма, которые выполняют разное количество разных операций. Например, они будут работать разное время, а это может быть критично (например, кто-то использует сортировку для задержки).
Почему? Они выполняют одну и ту же работу. Если в программе поменять сортировку пузырьком на быструю, это скажется только на производительности, но не на функциональности. Так что они очень даже эквивалентны. Другое дело, что эти алгоритмы не идентичны.
Quintanar wrote:
>>> C>Ну и уж если вам так хочется, то можно взять какую-нибудь другую >>> C>проблему из теории чисел, например, гипотезу Гольдбаха: >>> C>http://en.wikipedia.org/wiki/Goldbach%27s_conjecture >>> Опять же, нет никаких оснований полагать, что решатель не сможет >>> доказать эту гипотезу. > C>А вдруг не сможет? > А вдруг дедушка — это бабушка. Приведите доказательство, что не сможет.
В достаточно сложной теории существуют утверждения, такие, что не может
быть доказана за конечное число шагов их верность или ложность.
То есть если наш решатель работает в рамках арифметики Пеано, в которой
можно сформулировать теорему Ферма, то он вряд ли найдет ее
доказательство — это требует привлечения дополнительных аксиоматик.
Здравствуйте, Privalov, Вы писали:
P>Почему? Они выполняют одну и ту же работу. Если в программе поменять сортировку пузырьком на быструю, это скажется только на производительности, но не на функциональности. Так что они очень даже эквивалентны. Другое дело, что эти алгоритмы не идентичны.
Предположим, сортировку используют для ЗАДЕРЖКИ, вместо пустого цикла. В этом случае они вдруг становятся неэквивалентны. Улавливаешь? эквивалентность/неэквивалентность алгоритмов зависит не только от них самих.
Другой пример. Эвивалентны ли алгоритмы BitBlt и AlphaBlend? Вообще — нет. Но если они используются для вывода полностью непрозрачной картинки с неважно какой скоростью — да.
Взаимозаменяемы ли миникувалда и топор? Если забивать гвозди — да, если рубить деревья — нет. И так далее.
Здравствуйте, Кодёнок, Вы писали:
Кё>Предположим, сортировку используют для ЗАДЕРЖКИ, вместо пустого цикла. В этом случае они вдруг становятся неэквивалентны. Улавливаешь? эквивалентность/неэквивалентность алгоритмов зависит не только от них самих.
Кё>Другой пример. Эвивалентны ли алгоритмы BitBlt и AlphaBlend? Вообще — нет. Но если они используются для вывода полностью непрозрачной картинки с неважно какой скоростью — да.
Кё>Взаимозаменяемы ли миникувалда и топор? Если забивать гвозди — да, если рубить деревья — нет. И так далее.
Ты манипулируешь понятием алгоритма, как-будто у него нет определения (эквивалентность зависит от цели применения и т.д.). На самом деле в теории алгоритмов есть строгое понятие алгоритма в терминах машины Тьюринга (http://en.wikipedia.org/wiki/Church-Turing_thesis). И в такой постановке задача эквивалентности алгоритмов алгоритмически неразрешима.
Здравствуйте, Glоbus, Вы писали:
G>Здравствуйте, chukichuki, Вы писали:
C>>Представим ситуацию. Существует два алгоритма, описывающих по сути одну и ту же операцию. Например, cортировку некоторого массива. Первый алгоритм выполняет сортировку методом "пузырька", второй — быстрой сортировкой (qsort). Алгоритмы записаны на некотором (любом) императивном языке программирования и оформленны в виде подпрограмм, которым на вход поступает массив из n элементов, а на выходе получается массив из n отсоритированных в соотвествии с заданным критерием элементов. Стоит фантастическая задача: разработать алгоритм (программу) при помощи которой можно было бы показать, что два указанных алгоритма эквиваленты с точки зрения выполняемой операции. Анализ алгоритмов должен производится без их выполнения т.е. в статическом режиме. Как вы думаете, решение такой задачи возможно ?
G>Правильно ли я понял — машина должна сам разрулить, что делают алгоритмы и сказать, что да, они делают одно и тоже (если это так)?
Ну в идеале (недостижимом за конечное время — да !
Здравствуйте, Cyberax, Вы писали:
C>В достаточно сложной теории существуют утверждения, такие, что не может C>быть доказана за конечное число шагов их верность или ложность.
C>То есть если наш решатель работает в рамках арифметики Пеано, в которой C>можно сформулировать теорему Ферма, то он вряд ли найдет ее C>доказательство — это требует привлечения дополнительных аксиоматик.
А можно ссылочку на источник подобных утверждений?
Получается, что теорема Ферма в арифметике Пеано недоказуема?
Здравствуйте, Кодёнок, Вы писали:
Кё>Предположим, сортировку используют для ЗАДЕРЖКИ, вместо пустого цикла. В этом случае они вдруг становятся неэквивалентны. Улавливаешь? эквивалентность/неэквивалентность алгоритмов зависит не только от них самих.
Почему? Разве эквивалентность алгоритмов зависит от того, где и как их используют? Если, как ты предлагаешь, использовать сортировку для задержки, она от этого в генератор случайных чисел не превратится.
Кё>Другой пример. Эвивалентны ли алгоритмы BitBlt и AlphaBlend? Вообще — нет. Но если они используются для вывода полностью непрозрачной картинки с неважно какой скоростью — да.
В обоих приведенных тобой примерах речь идет не об алгоритмах как таковых, а об их использовании.
Кё>Взаимозаменяемы ли миникувалда и топор? Если забивать гвозди — да, если рубить деревья — нет. И так далее.
И здесь речь идет о применении инструментов. Кстати, в этом случае ответ зависит еще и от параметров самих инструментов (размеры, масса и т. д.)
Здравствуйте, Кодёнок, Вы писали:
P>>Почему? Они выполняют одну и ту же работу. Если в программе поменять сортировку пузырьком на быструю, это скажется только на производительности, но не на функциональности. Так что они очень даже эквивалентны. Другое дело, что эти алгоритмы не идентичны.
Кё>Предположим, сортировку используют для ЗАДЕРЖКИ, вместо пустого цикла. В этом случае они вдруг становятся неэквивалентны. Улавливаешь? эквивалентность/неэквивалентность алгоритмов зависит не только от них самих.
Кё>Другой пример. Эвивалентны ли алгоритмы BitBlt и AlphaBlend? Вообще — нет. Но если они используются для вывода полностью непрозрачной картинки с неважно какой скоростью — да.
Кё>Взаимозаменяемы ли миникувалда и топор? Если забивать гвозди — да, если рубить деревья — нет. И так далее.
Что означает, что решение такого важного вопроса нужно начать с определения понятия "эквивалентность".
Здравствуйте, Gleb Alexeev, Вы писали:
GA>Ты манипулируешь понятием алгоритма, как-будто у него нет определения (эквивалентность зависит от цели применения и т.д.). На самом деле в теории алгоритмов есть строгое понятие алгоритма в терминах машины Тьюринга (http://en.wikipedia.org/wiki/Church-Turing_thesis). И в такой постановке задача эквивалентности алгоритмов алгоритмически неразрешима.
А я и не говорю о теоретической возможности построить для машины Тьюринга алгоритм определения эквивалентности алгоритмов (тоже наверное для машины Тьюринга которой не существует). Я о возможной реализации.
У нас же всегда работает реальная программа на реальной ЭВМ, в некотором окружении. Окружение, в том числе операционная система, может влиять на выполнение программы. Два разных алгоритма очевидно будут вызывать множество разных эффектов. Какие-то эффекты будут вызываться обоими алгоритмами, какие-то только одним из них. Какие из эффектов будут важны — зависит от _нашей_ цели! Можно ли два немного отличающихся эффекта счесть одним и тем же — опять же зависит от нас.
WFrag wrote:
> C>В достаточно сложной теории существуют утверждения, такие, что не может > C>быть доказана за конечное число шагов их верность или ложность. > > C>То есть если наш решатель работает в рамках арифметики Пеано, в которой > C>можно сформулировать теорему Ферма, то он вряд ли найдет ее > C>доказательство — это требует привлечения дополнительных аксиоматик. > А можно ссылочку на источник подобных утверждений?
Первое утверждение — теорема Геделя о неполноте, смотрится в учебнике
мат. логики.
> Получается, что теорема Ферма в арифметике Пеано недоказуема?
Да, _исключительно_ в рамках арифметики Пеано она, скорее всего, не
доказуема — известное доказательство требует привлечения кучи других
аксиоматик.
Здравствуйте, Privalov, Вы писали:
P>Можно ли считать 2 алгоритма эквивалентными, если, получая на входе одинаковые данные, они возвращают одинаковые результаты?
Почему нет? Однако можно определить "эквивалентность" и так:
Две программы Тьюринга (не "алгоритмы", дабы избежать тонкости связанной с определением понятия "алгоритм") считаются эквивалентными, если для любого входного кортежа обе программы завершаются за одинаковое время (или обе зацикливаются) и выдают одинаковый результат.
В таком случае задача "неэквивалентности" — разрешима. Можно написать программу (для МТ), которая получая на вход код двух программ и остановится если они неэквивалентны и зациклится — если эквивалентны.
Однако обратная задача ("эквивалентности") же — неразрешима, хотя с ходу доказательство я, наверное, и не придумаю. Видимо, надо как-то свести задачу к известной задаче разрешимости (например, к задача об остановке).
Privalov wrote:
> WF>Что означает, что решение такого важного вопроса нужно начать с > определения понятия "эквивалентность". > Можно ли считать 2 алгоритма эквивалентными, если, получая на входе > одинаковые данные, они возвращают одинаковые результаты?
Да. Хотя они еще могут и ничего не возвращать (т.е. зациклиться).
Здравствуйте, Privalov, Вы писали:
WF>>Что означает, что решение такого важного вопроса нужно начать с определения понятия "эквивалентность".
P>Можно ли считать 2 алгоритма эквивалентными, если, получая на входе одинаковые данные, они возвращают одинаковые результаты?
А что такое результаты? Тепловыделение и потеря времени — тоже результаты. Для разных алгоритмов разные. Даже для одного алгоритма, выполненного два раза, могут быть разными. Можно ли раз и навсегда выработать правило, какие полученные эффекты включать в "результаты", а какие — нет?
Здравствуйте, WFrag, Вы писали:
Кё>>Взаимозаменяемы ли миникувалда и топор? Если забивать гвозди — да, если рубить деревья — нет. И так далее.
WF>Что означает, что решение такого важного вопроса нужно начать с определения понятия "эквивалентность".
Не нужно, достаточно интуитивного понимания. Дело в другом. См. ответ Глебу. Каждое реальное выполнение программы (на реальной ЭВМ) вызывает бесконечное множество эффектов, от очень заметных до совсем незаметных (выделение тепла, потеря тобой 1 минуты жизни на ожидание и т.д.). Человек может каким угодно образом решить, были два набора эффектов для него одним и тем же результатом, или разными результатами. Два разных человека решат по разному.
Здравствуйте, Кодёнок, Вы писали:
Кё>>>Взаимозаменяемы ли миникувалда и топор? Если забивать гвозди — да, если рубить деревья — нет. И так далее.
WF>>Что означает, что решение такого важного вопроса нужно начать с определения понятия "эквивалентность".
Кё>Не нужно, достаточно интуитивного понимания. Дело в другом. См. ответ Глебу. Каждое реальное выполнение программы (на реальной ЭВМ) вызывает бесконечное множество эффектов, от очень заметных до совсем незаметных (выделение тепла, потеря тобой 1 минуты жизни на ожидание и т.д.). Человек может каким угодно образом решить, были два набора эффектов для него одним и тем же результатом, или разными результатами. Два разных человека решат по разному.
Собственно, ты сам себе и противоречишь. Второе предложение собственно и обосновывает, почему нужно строго определять. У каждого — свое интуитивное понимание, не формализовав его говорить о задаче — бессмысленно. Потому что разные поределения будут давать разные задачи. Например, меня бы устроила эквивалентность данная мной в соседней ветке (по результату + времени), с условием, что МТ заменить на что-нибудь более близкое к реалиям (хоть бы даже и на JVM ).
Здравствуйте, WFrag, Вы писали:
WF>Две программы Тьюринга (не "алгоритмы", дабы избежать тонкости связанной с определением понятия "алгоритм") считаются эквивалентными, если для любого входного кортежа обе программы завершаются за одинаковое время (или обе зацикливаются) и выдают одинаковый результат.
Я думаю одинаковое время выполнения для эквивалентности не столь критично. Его можно опустить.
WF>В таком случае задача "неэквивалентности" — разрешима. Можно написать программу (для МТ), которая получая на вход код двух программ и остановится если они неэквивалентны и зациклится — если эквивалентны.
WF>Однако обратная задача ("эквивалентности") же — неразрешима, хотя с ходу доказательство я, наверное, и не придумаю. Видимо, надо как-то свести задачу к известной задаче разрешимости (например, к задача об остановке).
Я совсем ничего не понял. Разве не (не эквиваленты) != эквиваленты ? В чем разница между задачами "неэквивалентости" и "эквивалентности" ?
Здравствуйте, WFrag, Вы писали:
WF>Однако обратная задача ("эквивалентности") же — неразрешима, хотя с ходу доказательство я, наверное, и не придумаю. Видимо, надо как-то свести задачу к известной задаче разрешимости (например, к задача об остановке).
О! Придумал доказательство!
Пусть у нас есть МТ, которая на вход получает две программы МТ (способ кодирования их несущественнен) и выдает 0 если они неэквивалентны, 1 — если да (назовем ее Э). Посмотрим, как можно свести задачу к задаче остановки (которая, как известно, неразрешима).
Пусть дана программа П и входные данные Д. Построим программу ПД, которая вычисляет П(Д) (т.е это просто композиция двух программ — одна забивает ленту входными данными Д, вторая — просто вычисляет П). Очевидно, что ПД не зависит от входных данных. Т.е она либо останавливается и выдает в точности П(Д), либо зацикливается.
Вычислим Э(ПД, Б), где Б — бесконечный цикл. Если они неэквивалентны, то сущ. входные данные на которых ПД останавливается (так как Б не останавливается при любых входных данных), а значит ПД останавливается везде (так как не зависит от входных данных), а значит П(Д) — останавливается. Если же Э(ПД, Б) выдает 1, то ПД — не останавливается, а значит не останавливается и П(Д)!
Мы решили задачу об остановке -> противоречие. Такого алгорится Э не существует.
Здравствуйте, WFrag, Вы писали:
WF>Две программы Тьюринга (не "алгоритмы", дабы избежать тонкости связанной с определением понятия "алгоритм") считаются эквивалентными, если для любого входного кортежа обе программы завершаются за одинаковое время (или обе зацикливаются) и выдают одинаковый результат.
А зачем добавлять в определение время выполнения? Опять же, в случае сортировки можно подобрать данные так, что и быстрый метод, и пузырек управятся с ними за одинаковое время. При этом оба метода завершаются и выдают одинаковый результат. Ясно, что в общем случае это не так, однако алгоритмы, imho, остаются эквивалентными для внешнего наблюдателя. Кому из программистов не доводилось менять тот же пузырек в пробной версии на быструю сортировку в рабочей? Производительность меняется, функциональность — нет. Т. е. внешний наблюдатель увидит уменьшение (или увеличение) времени выполнения программы, однако не заметит никаких различий в результатах.
Это два разных алгоритма, которые выполняют разное количество разных операций. Например, они будут работать разное время, а это может быть критично (например, кто-то использует сортировку для задержки). 
— да !
