реклама на сайте
подробности

 
 
2 страниц V  < 1 2  
Reply to this topicStart new topic
xemul
сообщение Dec 5 2008, 18:43
Сообщение #16



*****

Группа: Свой
Сообщений: 1 928
Регистрация: 11-07-06
Пользователь №: 18 731



Цитата(Tanya @ Dec 5 2008, 20:57) *
Можно хэши хранить... Еще короче.

DOW CRC8 и есть 1-байтовый хэш остатних 7 байт ROM ID. Хинт был именно на эту тему.
Go to the top of the page
 
+Quote Post
S_agent
сообщение Dec 5 2008, 21:25
Сообщение #17


Местный
***

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



Цитата(rezident @ Dec 5 2008, 19:36) *
Многие видимо считают, что их задача уникальная и потому секретная. smile.gif А до них ее никто не решал и не исследовал. Поэтому и задаются изначально вопросы в столь экзотических формулировках wink.gif Нет чтобы сразу описать задачу полностью и получить советы, исходя из реального опыта.


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


Цитата(xemul @ Dec 5 2008, 19:21) *
Занятная постановка задачи. smile.gif
Вы хотите просто съэкономить память под ключи или организовать обновление наборов ключей в некоторой (распределенной) куче коробочек в соответствии с некоторой базой, учитывающей ключи?

первое, и наверное Вы правы, - лучше застроить базу, - вероятность правильного ответа = 100% smile.gif
Go to the top of the page
 
+Quote Post
scifi
сообщение Dec 6 2008, 23:07
Сообщение #18


Гуру
******

Группа: Свой
Сообщений: 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% определённости", то можно начать экономить. Только это совсем другая история...
Go to the top of the page
 
+Quote Post
AndreyVN
сообщение Dec 7 2008, 14:50
Сообщение #19


Знающий
****

Группа: Свой
Сообщений: 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.

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

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

Если исходные числа случайные - решающее правило - запомнить все числа. smile.gif
Go to the top of the page
 
+Quote Post
S_agent
сообщение Dec 7 2008, 19:03
Сообщение #20


Местный
***

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



2 AndreyVN:

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

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

santa2.gif
Go to the top of the page
 
+Quote Post
scifi
сообщение Dec 7 2008, 22:17
Сообщение #21


Гуру
******

Группа: Свой
Сообщений: 3 020
Регистрация: 7-02-07
Пользователь №: 25 136



Цитата(S_agent @ Dec 7 2008, 22:03) *
2 scifi:
и вам сеньк, но нужна 100% достоверность,
а вот если к полному массиву применить сжатие, то его хранение будет чуууть smile.gif меньше места требовать....

Ну, анализ был упрощённый. Предполагалось, что серийные номера случайные, независимые и с равномерным распределением. На практике это далеко не так, поэтому любой приличный алгоритм сжатия должен существенно уменьшить массив. Если цель - сэкономить память, то лучше, чем сжатие, трудно что-то придумать.
Go to the top of the page
 
+Quote Post
S_agent
сообщение Dec 8 2008, 10:16
Сообщение #22


Местный
***

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



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

будем жрать smile.gif
Go to the top of the page
 
+Quote Post

2 страниц V  < 1 2
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 11th July 2025 - 13:21
Рейтинг@Mail.ru


Страница сгенерированна за 0.01426 секунд с 7
ELECTRONIX ©2004-2016