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

Бурман и коллеги [ ] изучают сложность статической задачи о принадлежности в модели ''битового зонда''. Это вариация модели клеточного зонда, в которой каждая клетка содержит всего один бит. Иными словами, размер слова 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, то она должна использовать не менее dlog P i < n (7) "I бит. Если n < m1~i2<-1\, это означает, что схема должна хранить Q(n\ogm) бит (и, следовательно, использовать Q(n) ячеек). Целью работы [2] является получение схемы, которая отвечает на запросы с помощью постоянного числа битовых зондов и при этом использует таблицу размером O(n log m) бит.