Подскажите по алгоритмам идентификации(свой-чужой) Опции

[S_agent]

есть массив чисел A[], применив к любому из его элементов f(Ai) и, возможно число K(определенное по массиву?) необходимо получить ответ - есть ли это число в массиве(в месте принятия решения из массива доступен только текущий элемент).
Какие есть пути решения?
Сеньк.

[AndreyVN]

есть массив чисел A[], применив к любому из его элементов f(Ai) и, возможно число K(определенное по массиву?) необходимо получить ответ - есть ли это число в массиве(в месте принятия решения из массива доступен только текущий элемент).
Какие есть пути решения?
Сеньк.

Раз восемь перечитал Ваш пост... Что есть число K????

[S_agent]

Раз восемь перечитал Ваш пост... Что есть число K????

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

Убрав всевышенаписаное. Необходимо произвести идентификацию, - было ли проверяемое число в исходном массиве или нет. Весь массив в момент проверки недоступен, только проверяемый элемент.

[bav]

если правильно понял, то:
дано: y = f(A), тогда
A = F(y), где F - обратная функция.
просто решаем обратную задачу.

[S_agent]

если правильно понял, то:
дано: y = f(A), тогда
A = F(y), где F - обратная функция.
просто решаем обратную задачу.

попробую обьяснить по-другому
есть массив чисел A,
нужен алгоритм проверки, на входе которого есть число, и нужно определить, пренадлежит ли это число массиву А.
при проверке к массиву доступа нет

[bav]

тогда получается проверка того, не знаю чего.
зачем писали "f(Ai)"?

[S_agent]

тогда получается проверка того, не знаю чего.
зачем писали "f(Ai)"?

гдето так ....
вместо f(Ai) наверное правильно будет написать f(F(A), N),
где
N - проверяемое число,
F(A) - вспомогательное число, общее для всех проверок полученое от массива (нужно ли оно, незнаю )
и f() собственно проверочная функция
звыняйте, ежели совсем запутал

[bav]

есть ли доступ через к-л функцию ко всем элементам массива?
к примеру (уже писал):
y = f(A[]), тогда находите обратную функцию.
добавлю, что бывают неопределенности при таком подходе, но с какой-то вероятностью можно предположить, что такой элемент есть или его нет.
вообще, попробуйте нормально сформулировать задачу. может, даже практическое применение, чтобы я мог точнее уловить вашу мысль.

[S_agent]

есть ли доступ через к-л функцию ко всем элементам массива?

нет.

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

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




попробую еще понятнее обьяснить.
есть массив А, можно ли написать функцию, которая будет обладать свойством: f( a )=f( b )=f( c )!=f( d )
, если числа a,b,c принадлежать массиву A, а число d нет?

[bav]

думаю, что нет.

[S_agent]

думаю, что нет.

и на том спасибо

[rezident]

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

[xemul]

Занятная постановка задачи.
Вы хотите просто съэкономить память под ключи или организовать обновление наборов ключей в некоторой (распределенной) куче коробочек в соответствии с некоторой базой, учитывающей ключи?
Если первое, то просто хранить ключи будет дешевле. Хинт (применительно к iButton): для ускорения поиска ключа начинайте сравнение с контрольной суммы. А можно еще и базу упорядочить...
Если второе, то в дополнение к п.1 организуйте обновление хоть через промежуточную носимую коробочку (которая, н-р, через то же гнездо считывателя по волшебному слову сливает новый набор в целевую коробочку), хоть через GPRS с ftp.

[rezident]

Занятная постановка задачи.

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

[Tanya]

Занятная постановка задачи.
Вы хотите просто съэкономить память под ключи или организовать обновление наборов ключей в некоторой (распределенной) куче коробочек в соответствии с некоторой базой, учитывающей ключи?
Если первое, то просто хранить ключи будет дешевле. Хинт (применительно к iButton): для ускорения поиска ключа начинайте сравнение с контрольной суммы. А можно еще и базу упорядочить...

Можно хэши хранить... Еще короче.

[xemul]

Можно хэши хранить... Еще короче.

DOW CRC8 и есть 1-байтовый хэш остатних 7 байт ROM ID. Хинт был именно на эту тему.

[S_agent]

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

никаких тайн, начал задавать вопросы, - сам понял как лучше выразить что хотел , далее и формализировал:

есть массив А, можно ли написать функцию, которая будет обладать свойством: f( a )=f( b )=f( c )!=f( d ), если числа a,b,c принадлежать массиву A, а число d нет?

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

первое, и наверное Вы правы, - лучше застроить базу, - вероятность правильного ответа = 100%

[scifi]

Как я понял, задача такая: есть набор серийных номеров iButton S[i] (для примера, 100 номеров), каждый из которых имеет размер 64 бита. То есть суммарный объём этого массива - 6400 битов. Хочется иметь некий алгоритм, который на входе имеет число K, являющееся функцией того массива, и тестируемый произвольный серийный номер T (64 бит), а на выходе этот алгоритм должен сказать со 100% определённостью, что серийный номер является или нет частью исходного массива. Немного сложно сформулировал, наверное...
Есть очевидный ответ: число К - это все биты массива S[i]. То есть число К имеет объём 6400 битов.
Только, как я понял, хочется, чтобы число К было значительно меньше, чем 6400 битов. Рассчитаем, сколько нужно битов, чтобы сохранить полную информацию о массиве S[i]. Массив S[i] - не что иное, как выборка 100 элементов (в нашем случае) из 2^64 элементов (полное пространство серийных номеров). Известна формула для числа выборок. Если применить эту формулу, то выяснится, что для хранения числа возможных выборок потребуется приблизительно (6400 - 48) битов. Так что экономия от любого такого алгоритма будет ничтожная.
Вот если отказаться от "100% определённости", то можно начать экономить. Только это совсем другая история...

[AndreyVN]

есть массив А, можно ли написать функцию, которая будет обладать свойством: f( a )=f( b )=f( c )!=f( d )
, если числа a,b,c принадлежать массиву A, а число d нет?

Наконец-то задача прояснилась.
Я думаю кучу вариантов придумать можно.

Например, возьмите точку в 100 мерном пространстве, все что попало в некий радиус - это свои не попало - чужие. Решающее правило (Xi-xi)^2 < R^2, где X - координаты "секретного" центра x - левые координаты. i=1...100.

Или возьмите числа Фибоначи Решающее правило Фибоначи - свой Не Фибоначи - чужой.

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

Если исходные числа случайные - решающее правило - запомнить все числа.

[S_agent]

2 AndreyVN:

не всегда число может быть задано, - оно может быть внешним, и, соответственно не попадать под эти правила. идет к тому что бы запоминать весь массив.
за мысль сеньк, уже хоть направление +- виндно

2 scifi:
и вам сеньк, но нужна 100% достоверность,
а вот если к полному массиву применить сжатие, то его хранение будет чуууть меньше места требовать....

[scifi]

2 scifi:
и вам сеньк, но нужна 100% достоверность,
а вот если к полному массиву применить сжатие, то его хранение будет чуууть меньше места требовать....

Ну, анализ был упрощённый. Предполагалось, что серийные номера случайные, независимые и с равномерным распределением. На практике это далеко не так, поэтому любой приличный алгоритм сжатия должен существенно уменьшить массив. Если цель - сэкономить память, то лучше, чем сжатие, трудно что-то придумать.

[S_agent]

Ну, анализ был упрощённый. Предполагалось, что серийные номера случайные, независимые и с равномерным распределением. На практике это далеко не так, поэтому любой приличный алгоритм сжатия должен существенно уменьшить массив. Если цель - сэкономить память, то лучше, чем сжатие, трудно что-то придумать.

будем жрать