|
Подскажите по алгоритмам идентификации(свой-чужой) |
|
|
|
Dec 5 2008, 21:25
|

Местный
  
Группа: Свой
Сообщений: 208
Регистрация: 6-10-05
Из: Ukraine, Kiev
Пользователь №: 9 300

|
Цитата(rezident @ Dec 5 2008, 19:36)  Многие видимо считают, что их задача уникальная и потому секретная.  А до них ее никто не решал и не исследовал. Поэтому и задаются изначально вопросы в столь экзотических формулировках  Нет чтобы сразу описать задачу полностью и получить советы, исходя из реального опыта. никаких тайн, начал задавать вопросы, - сам понял как лучше выразить что хотел  , далее и формализировал: Цитата есть массив А, можно ли написать функцию, которая будет обладать свойством: f( a )=f( b )=f( c )!=f( d ), если числа a,b,c принадлежать массиву A, а число d нет? Цитата(xemul @ Dec 5 2008, 19:21)  Занятная постановка задачи. Вы хотите просто съэкономить память под ключи или организовать обновление наборов ключей в некоторой (распределенной) куче коробочек в соответствии с некоторой базой, учитывающей ключи? первое, и наверное Вы правы, - лучше застроить базу, - вероятность правильного ответа = 100%
|
|
|
|
|
Dec 6 2008, 23:07
|
Гуру
     
Группа: Свой
Сообщений: 3 020
Регистрация: 7-02-07
Пользователь №: 25 136

|
Как я понял, задача такая: есть набор серийных номеров iButton S[i] (для примера, 100 номеров), каждый из которых имеет размер 64 бита. То есть суммарный объём этого массива - 6400 битов. Хочется иметь некий алгоритм, который на входе имеет число K, являющееся функцией того массива, и тестируемый произвольный серийный номер T (64 бит), а на выходе этот алгоритм должен сказать со 100% определённостью, что серийный номер является или нет частью исходного массива. Немного сложно сформулировал, наверное... Есть очевидный ответ: число К - это все биты массива S[i]. То есть число К имеет объём 6400 битов. Только, как я понял, хочется, чтобы число К было значительно меньше, чем 6400 битов. Рассчитаем, сколько нужно битов, чтобы сохранить полную информацию о массиве S[i]. Массив S[i] - не что иное, как выборка 100 элементов (в нашем случае) из 2^64 элементов (полное пространство серийных номеров). Известна формула для числа выборок. Если применить эту формулу, то выяснится, что для хранения числа возможных выборок потребуется приблизительно (6400 - 48) битов. Так что экономия от любого такого алгоритма будет ничтожная. Вот если отказаться от "100% определённости", то можно начать экономить. Только это совсем другая история...
|
|
|
|
|
Dec 7 2008, 14:50
|
Знающий
   
Группа: Свой
Сообщений: 754
Регистрация: 29-06-06
Из: Volgograd
Пользователь №: 18 458

|
Цитата(S_agent @ Dec 5 2008, 16:45)  есть массив А, можно ли написать функцию, которая будет обладать свойством: f( a )=f( b )=f( c )!=f( d ) , если числа a,b,c принадлежать массиву A, а число d нет? Наконец-то задача прояснилась. Я думаю кучу вариантов придумать можно. Например, возьмите точку в 100 мерном пространстве, все что попало в некий радиус - это свои не попало - чужие. Решающее правило (Xi-xi)^2 < R^2, где X - координаты "секретного" центра x - левые координаты. i=1...100. Или возьмите числа Фибоначи Решающее правило Фибоначи - свой Не Фибоначи - чужой. В общем, это вопрос фантазии - каким условием связать числа в исходном массиве. Если исходные числа случайные - решающее правило - запомнить все числа.
|
|
|
|
|
Dec 7 2008, 19:03
|

Местный
  
Группа: Свой
Сообщений: 208
Регистрация: 6-10-05
Из: Ukraine, Kiev
Пользователь №: 9 300

|
2 AndreyVN: не всегда число может быть задано, - оно может быть внешним, и, соответственно не попадать под эти правила. идет к тому что бы запоминать весь массив. за мысль сеньк, уже хоть направление +- виндно  2 scifi: и вам сеньк, но нужна 100% достоверность, а вот если к полному массиву применить сжатие, то его хранение будет чуууть  меньше места требовать....
|
|
|
|
|
Dec 7 2008, 22:17
|
Гуру
     
Группа: Свой
Сообщений: 3 020
Регистрация: 7-02-07
Пользователь №: 25 136

|
Цитата(S_agent @ Dec 7 2008, 22:03)  2 scifi: и вам сеньк, но нужна 100% достоверность, а вот если к полному массиву применить сжатие, то его хранение будет чуууть  меньше места требовать.... Ну, анализ был упрощённый. Предполагалось, что серийные номера случайные, независимые и с равномерным распределением. На практике это далеко не так, поэтому любой приличный алгоритм сжатия должен существенно уменьшить массив. Если цель - сэкономить память, то лучше, чем сжатие, трудно что-то придумать.
|
|
|
|
|
Dec 8 2008, 10:16
|

Местный
  
Группа: Свой
Сообщений: 208
Регистрация: 6-10-05
Из: Ukraine, Kiev
Пользователь №: 9 300

|
Цитата(scifi @ Dec 8 2008, 00:17)  Ну, анализ был упрощённый. Предполагалось, что серийные номера случайные, независимые и с равномерным распределением. На практике это далеко не так, поэтому любой приличный алгоритм сжатия должен существенно уменьшить массив. Если цель - сэкономить память, то лучше, чем сжатие, трудно что-то придумать. будем ж рать
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|