Равенство функций нескольких аргументов

[bin]

migmit в сообщении #245499 писал(а):

Цитата:

мне нужно описать алгоритм, где сравниваются две системы

Поясните для начала, что вы понимаете под "системой".

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

-- Вт сен 22, 2009 17:18:58 --

venco в сообщении #245504 писал(а):

z:=1/x+y;
z:=x+1/y;

А у меня вообще слово function не использовано. Значит ли это, что функции нет?
Нет, это значит, что часть реализации второй функции, а именно - перестановку аргументов, вы переложили на вызывающий код.

Предложенный Вами код не эквивалентен моему! (Одни конструкции языка Вы заменили другими.)И реальный компилятор выдаст другой исполняемый файл. Хотя результат работы программ будет один и тот же. Программы с одной и той же выдачей не обязательно одинаковы! Можно сравнить с техникой раскрытия цикла, код:

{пример 1}
for i:=1 to 3 do
a := a+i;

заменяется на код:

{пример 2}
a := a+1;
a := a+2;
a := a+3;

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

В примере 1 есть цикл, в примере 2 - линейная последовательность операторов. Точно так же в моем коде 1 функция и 2 вызова, в Вашем коде линейная последовательность двух операторов. Из моего кода видно, что функция (в смысле языка программирования) единственная. Из Вашего кода этого не видно.

[arseniiv]

Алгоритм ≠ Программный код, bin, вы помните?

[migmit]

Ну, вообще-то, почти равно. Цимес не в этом; цимес в том, что понятие "функция в терминах некоторого языка программирования" и понятие "функция" - сильно разные вещи.

[bin]

arseniiv в сообщении #245509 писал(а):

Алгоритм ≠ Программный код, bin, вы помните?

Смотря в каком смысле. Если говорить о деталях реализации: специфических особенностях платформы, ограничениях компилятора и т.д. - то исполняемый код содержит массу избыточных для обобщенного описания деталей. Но мы не говорили и не будем говорить о деталях реализации. Мы говорим о некоей идеализированной паскаль-машине. С тем же успехом мы можем обратиться к машине Тьюринга, которая традиционно используется для теоретической оценки вычислительной сложности алгоритмов. В таком контексте наш код = алгоритму. По Н.Вирту: алгоритмы+структуры данных=программы, структуры данных мы опускаем, получаем алгоритмы=программы

-- Вт сен 22, 2009 17:52:39 --

migmit в сообщении #245510 писал(а):

Ну, вообще-то, почти равно. Цимес не в этом; цимес в том, что понятие "функция в терминах некоторого языка программирования" и понятие "функция" - сильно разные вещи.

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

[arseniiv]

Какого алгоритма? Ну вы покажите его сначала!

[bin]

arseniiv в сообщении #245527 писал(а):

Какого алгоритма? Ну вы покажите его сначала!

Зачем? Куча лишних деталей для решения данной подзадачи. Кому нужно читать несколько десятков страниц текста с формулами, вникать в предметную область и т.д. Совершенно излишне! Существует подзадача, которую можно обсудить изолированно от основных задач - это общая практика.

[man]

bin в сообщении #245465 писал(а):

... как назвать отношение эквивалентности функций для указанных случаев (т.е. когда при перестановке переменных получаются тождественные выражения)?...

Цитата:

bin в сообщении #245484 писал(а):

Если я описываю алгоритм, то я описываю обе неравные функции одной и той же функцией, как на псевдокоде, так и на языке программирования при реализации этого алгоритма. ...
function F(arg1, arg2 : real) : real;
begin
F:=1/arg1+arg2
end;
Получается, что неравные функции алгоритмически могут быть заданы одним и тем же алгоритмом и реализованы одним и тем же исполняемым кодом !

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

[arseniiv]

bin в сообщении #245534 писал(а):

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

А ещё существует такая вещь как оптимизация...

[bin]

man в сообщении #245584 писал(а):

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

Спасибо! Вот и я хотел бы определиться Ранее мы тут договорились описывать алгоритмы стандартным Паскалем. При описании алгоритма оказалось, что неравные, но "коджибулярные" ("транспараметричные") функции описываются одной и той же паскалевской функцией. Т.о. была отмечена разница математической и программистской трактовок понятия "функция". Из-за этой разницы у меня проблема с доказательством корректности алгоритма. Может, стоит вместо понятия функция применять понятие "оператор" (в математическом смысле) ?

Попробую уточнить проблему, двигаясь "методом последовательных уточнений": если, например:

$y=k_1x_1+k_2x_2+k_3x_3$

$y'=k'_1x'_1+k'_2x'_2+k'_3x'_3$

$k_1=k'_3, k_2=k'_2, k_3=k'_1 $

То я хочу доказать, что функции у,у' одна и та же "функция"/"оператор" (или еще что-нибудь), и при любых $x_1=x'_3, x_2=x'_2, x_3=x'_1 $ равенство у=у' будет истинным. И в общем случае, если

$y=k_1x_1+k_2x_2+...+k_nx_n$
$y'=k'_1x'_1+k'_2x'_2+...+k'_nx'_n$

И если для всех коэффициентов имеются соответствующие пары $k_i=k'_j$ (как это лучше сказать?), то для любых значений соответствующих пар $x_i=x'_j $ равенство у=у' будет истинным. Как лучше записать доказательство такой очевидной вещи? (у=у')

[Андрей АK]

Мне кажется, тут участвуют не две функции, а две пары функций.
Вернее две пары: функция плюс оператор.

Оператор перестановки (х<->y)
В первом случае у нас функция E*f(x,y) , где E - тождественный оператор.
Во втором случае P(х<->y)*f(x,y) , где P(х<->y) - оператор перестановки переменных.

Другая трактовка - обе функции - суть одна и та-же функция ... но только после обезличивания её параметров.

Т.е. если мы говорим о функции f(x,y) которая жестко привязана к пространству (x,y) то это одна функция.
А если у нас есть более абстрактная функция f(arg1,arg2) то это функция более высокого "уровня".

Т.е. отличие как у функций: f(x) и f(0) - в первую можно подставить любое значение x, а в f(0) - это значение уже подставлено.

Следовательно f(arg1,arg2) это функция ,до того как в неё подставили конкретные координаты (x,y).

А кто сказал, что подстановка x:=0 - это нормально, а (arg1,arg2) := (x,y) - не нормально?
Мы имеем право использовать в качестве подстановки как константы, так и переменные.
Ну может быть ,разве что, надо f(arg1,arg2) называть оператором, а не функцией...

PS
Ах да.
Это ещё напоминает различие между свободными и связанными переменными, в логике.
Тогда можно сказать, что эти две функции "равны в связанных состояниях своих переменных".
Или "равны при связанных переменных".
Или "связанно равны"
А если использовать термин - "обезличенные переменные"
то будет "Равны при обезличенных переменных"
Или "обезличенно равны"

[Circiter]

2bin

Цитата:

И в общем случае, если

$y=k_1x_1+k_2x_2+...+k_nx_n$
$y'=k'_1x'_1+k'_2x'_2+...+k'_nx'_n$

И если для всех коэффициентов имеются соответствующие пары $k_i=k'_j$ (как это лучше сказать?), то для любых значений соответствующих пар $x_i=x'_j $ равенство у=у' будет истинным. Как лучше записать доказательство такой очевидной вещи? (у=у')

Например, от противного. Пусть $y\neq y'$, тогда $k_1x_1+k_2x_2+...+k_nx_n\neq k'_1x'_1+k'_2x'_2+...+k'_nx'_n$, т.е. $k_1x_1+k_2x_2+...+k_nx_n-(k'_1x'_1+k'_2x'_2+...+k'_nx'_n)\neq 0$, после приведения подобных слагаемых получаем $0\neq 0$, противоречие. Значит, $y=y'$, ч.т.д.

P.S.: Мне кажется, или коджибулярность/транспараметричность суть синонимы слова симметричность?

[bin]

Большое спасибо за обсуждение!
Очень помогло для решения важной проблемы: http://arxiv.org/abs/1004.1808v1
Обсуждение этой статьи открою в новой теме.

[arseniiv]

Только если вы использовали формулу, подправьте её. Я тогда забыл, как обозначается множество подстановок. Замените квантор с переменной $t$ на $\exists t \in S_n$. И ничего особенного в ней нет, это же просто формализация определения.

[bin]

arseniiv в сообщении #310569 писал(а):

Только если вы использовали формулу, подправьте её. Я тогда забыл, как обозначается множество подстановок. Замените квантор с переменной $t$ на $\exists t \in S_n$. И ничего особенного в ней нет, это же просто формализация определения.

Ok! Cпасибо. Дать корректное и удобно формализированное определение очень важно, особенно в случае попытки решения открытой проблемы (мой случай ). Ничего особенного в таком определении и не требуется, но без него не обойтись. Поэтому я бы очень хотел поблагодарить Вас в окончательном варианте своей статьи. Напишите, пожалуйста, мне email: mt2 собака comtv точка ru!
-- Михаил.