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