Приближенные словари: различия между версиями

Бурман и коллеги [ ] изучают сложность статической задачи о принадлежности в модели ''битового зонда''. Это вариация модели клеточного зонда, в которой каждая клетка содержит всего один бит. Иными словами, размер слова w равен 1. Таким образом, в этой модели алгоритму запроса предоставляется побитовый доступ к структуре данных. Изучение задачи о принадлежности в модели битового зонда было начато Минским и Папертом в книге «[[Перцептроны]]» [https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D1%86%D0%B5%D0%BF%D1%82%D1%80%D0%BE%D0%BD%D1%8B_(%D0%BA%D0%BD%D0%B8%D0%B3%D0%B0] [12]. Однако их интересовали верхние границы ''в среднем случае', тогда как далее рассматриваются границы для задачи о принадлежности ''в наихудшем случае''.

Заметим, что если от схемы требуется хранить множества размером не более n, то она должна использовать не менее <math>\lceil log \; \sum_{i \le n} \tbinom{m}{i} \rceil</math> бит. Если n < m1~i2<-1\, это означает, что схема должна хранить Q(n\ogm) бит (и, следовательно, использовать Q(n) ячеек). Целью работы [2] является получение схемы, которая отвечает на запросы с помощью постоянного числа битовых зондов и при этом использует таблицу размером O(n log m) бит.

=== Родственные работы ===

Статическая задача о принадлежности хорошо изучена в модели клеточного зонда, где каждая клетка способна вместить один элемент совокупности. То есть w = O (log m). В своей фундаментальной работе Фредман и др. [8] предложили схему для решения статической задачи о принадлежности в модели клеточного зонда с размером слова O(log m), которая использует постоянное количество зондов и таблицу размера O(n). Далее эта схема будет называться схемой FKS. Таким образом, с точностью до постоянных коэффициентов схема FKS использует оптимальные объем памяти и количество клеточных зондов. Фактически, Фиат и др. [ ], Бродник и Манро [ ] и Паг [13] получили схемы, которые используют объем памяти (в битах) в пределах небольшого аддитивного члена dlog X!;<n (7)1 и отвечают на запросы, считывая не более чем постоянное число клеток. Несмотря на все эти фундаментальные результаты для задачи о принадлежности в модели клеточного зонда, до выхода работы [2] было очень мало известно о сложности этой задачи в модели битового зонда.

=== Основные результаты ===