4511
правок
Приближенные словари: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 57: | Строка 57: | ||
Теорема 3. Для любого 0 < | '''Теорема 3. Для любого Для любого <math>0 < \epsilon \le \frac{1}{4}</math> существует схема хранения подмножеств S размером не более n с элементами из совокупности размера m с использованием <math>O( \tbinom{n}{\epsilon}^2 \; log \; m)</math> бит, так что на любой запрос о принадлежности «Принадлежит ли u к S?» можно ответить с вероятностью ошибки не более e с помощью рандомизированного алгоритма, который делает единственный битовый запрос к структуре данных. Более того, если <math>u \in S</math>, то вероятность ошибки равна 0.''' | ||
Хотя эта схема и не обеспечивает оптимальное использование памяти, она все же требует ее значительно меньше, чем битовый вектор. Однако зависимость от n квадратичная, в отличие от схемы с двусторонней ошибкой, где она была линейной. В работе [ ] показано, что эта схема практически оптимальна: для любой схемы с односторонней ошибкой обязательно существует квадратичная зависимость от ^. | Хотя эта схема и не обеспечивает оптимальное использование памяти, она все же требует ее значительно меньше, чем битовый вектор. Однако зависимость от n квадратичная, в отличие от схемы с двусторонней ошибкой, где она была линейной. В работе [2] показано, что эта схема практически оптимальна: для любой схемы с односторонней ошибкой обязательно существует квадратичная зависимость от ^. | ||
Теорема 4. Предположим, что | '''Теорема 4. Предположим, что <math>\frac{n}{m^{1/3}} \le \epsilon \le \frac{1}{4}</math>. Рассмотрим статическую задачу о принадлежности для множества S размера не более n из совокупности размера m. Тогда любая схема с односторонней <math>\epsilon</math>-ошибкой, отвечающая на запросы с использованием не более одного битового зонда, должна использовать <math>\Omega \big( \frac{n^2}{\epsilon^2 \; log(n/\epsilon)} \; log \; m \big)</math> бит памяти.''' | ||
Замечание. Можно также рассмотреть однозондовые схемы с односторонней ошибкой, которые допускают ошибки только в положительных экземплярах. Это означает, что для элементов запроса, не входящих в множество S, ошибки не допускаются. | |||
''Замечание''. Можно также рассмотреть однозондовые схемы с односторонней ошибкой, которые допускают ошибки только в положительных экземплярах. Это означает, что для элементов запроса, ''не входящих'' в множество S, ошибки не допускаются. | |||