Здравствуйте,

есть желание найти/придумать алгоритм построения контрольной суммы, позволяющий обнаружить незначитильные изменения исходника по некоторому определённому изменению контрольной суммы.
например 32 байта).
Затем в исходном наборе несколько чисел (скажем 10), незначительно увеличиваются/уменьшаются (скажем на 1 или 2).

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

Возможно, такой алгоритм уже есть? Или есть доказательство, что такого алгоритма построить нельзя?

Здравствуйте, Аноним, Вы писали:

А>Или есть доказательство, что такого алгоритма построить нельзя?
В столь неформальной постановке ни о каком доказательстве не может быть и речи.

Вообще же стоит посмотреть в сторону алгоритмов хеширования CRC, MD5, SHA1 итп.

Здравствуйте, Mab, Вы писали:

Mab>Вообще же стоит посмотреть в сторону алгоритмов хеширования CRC, MD5, SHA1 итп.

Насколько мне известно, MD5 никаких выводов, по сравнению двух контрольных сумм, кроме проверки на идентичность сделать не сможет...

А>например 32 байта).
А>Затем в исходном наборе несколько чисел (скажем 10), незначительно увеличиваются/уменьшаются (скажем на 1 или 2).

Сорри, часть примера испарилась.

Пример:

Есть последовательность 200 чисел, и есть каким-то образом (каким?) полученная по ним сигнатура, длинной, например 32 байта.
Затем в исходном наборе несколько чисел (скажем 10), незначительно увеличиваются/уменьшаются (скажем на 1 или 2).
Хочется, сравнив новую сигнатуру со старой, уметь выносить вердикт с достаточно большой степенью вероятности — "похожи" ли исходники — и насколько.

Здравствуйте, Аноним, Вы писали:

А>Насколько мне известно, MD5 никаких выводов, по сравнению двух контрольных сумм, кроме проверки на идентичность сделать не сможет...
В смысле -- кроме проверки на идентичность? Думаете не существует двух различных наборов данных с одинаковым MD5 digest?

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

Здравствуйте, Аноним, Вы писали:

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

Здравствуйте, Mab, Вы писали:

Mab>В смысле -- кроме проверки на идентичность? Думаете не существует двух различных наборов данных с одинаковым MD5 digest?

конечно, существует

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

А чего не хватает в условиях для того, чтобы признать её формализованной?

Здравствуйте, Mab, Вы писали:

Mab>Возможно есть смысл поспрашивать у народа, занимающегося теорией кодирования. Может быть какой-то стандартный код с обнаружением ошибок подойдет...

Так а теория кодирования — это разве не алгоритмистика ?
А что за эвристические методы вы имели в виду?
А понять что имелось в виду, возможно, поможет пример, который я выше привёл?

Важна небольшая длина сигнатуры (например 32 байта).

Здравствуйте, Аноним, Вы писали:

А>Так а теория кодирования — это разве не алгоритмистика ?
Нет. Это раздел на стыке дискретной математики, алегебры и комбинаторики. Я им не занимаюсь

А>А что за эвристические методы вы имели в виду?
Общеизвестные хеши. Примеры я приводил. Формализованных гарантий, впрочем, никаких не будет.

Здравствуйте, Аноним, Вы писали:
А>А чего не хватает в условиях для того, чтобы признать её формализованной?
Вот это

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

по-прежнему не формализовано. По какому распределению берется вероятность?

Впрочем, не важно. Даже если Вы скажете, например, что распределение здесь равномерное, я помочь все равно не смогу Всего лишь хочу подтолкнуть к мысли, что полного математического описания задачи пока еще нет.

Здравствуйте, Mab, Вы писали:

Mab>Нет. Это раздел на стыке дискретной математики, алегебры и комбинаторики. Я им не занимаюсь

жаль, значит, вопрос — действительно не к вам

Mab>Я всего лишь предложил (ввиду отсутствия формализованной постановки задачи) ограничиться эвристическими подходами.
А>>А что за эвристические методы вы имели в виду?
Mab>Общеизвестные хеши. Примеры я приводил. Формализованных гарантий, впрочем, никаких не будет.

такой эвристический метод, как md5, здесь, к сожалению, беспомощен.

А>>А чего не хватает в условиях для того, чтобы признать её формализованной?
Mab>Вот это...
Mab>Всего лишь хочу подтолкнуть к мысли, что полного математического описания задачи пока еще нет.

согласен :

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

Если так нужна формализованность — возьмём этот идеальный критерий похожести.

Hello Mab, you wrote:

>> Или есть доказательство, что такого алгоритма построить нельзя?
> В столь неформальной постановке ни о каком доказательстве не может быть и речи.

Мне думается, что имелась ввиду "метрика", а не контрольная сумма.

--
Всего хорошего, Слава
ICQ: 197577902

Здравствуйте, Аноним, Вы писали:

А>

А>Хочется, сравнив новую сигнатуру со старой, уметь выносить вердикт — насколько похожи исходники. Степень похожести идеальном образом выразило бы стремление к нулю суммы прибавленных к первой последовательности чисел взятых по модулю.

Стремиться к нулю может только функция Соответственно встает вопрос о том, что считать переменной в рассматриваемом случае.

Здравствуйте, Slava Antonov, Вы писали:

SA>Мне думается, что имелась ввиду "метрика", а не контрольная сумма.

Имелся в виду набор 32 байт — он же является результатом получения "контрольной суммы md5". Наверное его можно и метрикой назввать, и сигнатурой...

Здравствуйте, Mab, Вы писали:

А>>

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

Mab>Стремиться к нулю может только функция Соответственно встает вопрос о том, что считать переменной в рассматриваемом случае.

переменной, очевидно следует считать пары различающихся последовательностей

Здравствуйте, Аноним, Вы писали:

А>переменной, очевидно следует считать пары различающихся последовательностей
И какая же топология вводится на множестве значений переменной...?

Hello Аноним, you wrote:

> Имелся в виду набор 32 байт — он же является результатом получения "контрольной суммы md5". Наверное его можно и метрикой назввать, и сигнатурой...

У метрики есть строгое определение. Под которое md5 имхо явно не подходит.

--
Всего хорошего, Слава
ICQ: 197577902

Hello Аноним, you wrote:

> Имелся в виду набор 32 байт — он же является результатом получения "контрольной суммы md5". Наверное его можно и метрикой назввать, и сигнатурой...

У метрики есть строгое определение. Под которое md5 имхо явно не подходит.

--
Всего хорошего, Слава
ICQ: 197577902

Здравствуйте, Slava Antonov, Вы писали:

SA>У метрики есть строгое определение. Под которое md5 имхо явно не подходит.

Конечно!

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

вы которое имели в виду?..
и в каком контексте?

Здравствуйте, Mab, Вы писали:

Mab>И какая же топология вводится на множестве значений переменной...?

Это зависит от того, что вы под этим понимаете — приведите точное определение со ссылкой на источник.

Хотя, я не вижу в этом особого смысла.
Из примеров вполне понятно, что имелось в виду. И если вы ничем полезным мне помочь не можете (в чём сами и признались) — может займётесь чем-то действительно полезным?..

Здравствуйте, Аноним, Вы писали:

А>Это зависит от того, что вы под этим понимаете — приведите точное определение со ссылкой на источник.
http://en.wikipedia.org/wiki/Topological_space

А>Из примеров вполне понятно, что имелось в виду. И если вы ничем полезным мне помочь не можете (в чём сами и признались) — может займётесь чем-то действительно полезным?..
-1

Честно говоря. я несколько разочарован, т. к. всегда считал, что на профильных форумах РАСД — завсегдатаи первым делом пытаются помочь, а флудом занимаются в специально отведённых для этого форумах...
Или вы просто мимо проходили больше не нашли где опрожниться?