4511
правок
Приближенные словари: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
'''Задача и модель''' | '''Задача и модель''' | ||
Задача о статической структуре данных состоит из набора данных D, набора запросов Q, набора ответов A и функции <math>f: D \times Q \to A</math>. Целью является хранение данных в сжатом виде таким образом, чтобы на любой запрос можно было ответить с помощью всего нескольких обращений к структуре данных. ''Статическая задача о принадлежности'' представляет собой хорошо изученный раздел в проектировании структур данных [1, 4, 7, 8, 12, 13, 16]. | Задача о статической структуре данных состоит из набора данных D, набора запросов Q, набора ответов A и функции <math>f: D \times Q \to A</math>. Целью является хранение данных в сжатом виде таким образом, чтобы на любой запрос можно было ответить с помощью всего нескольких обращений к структуре данных, или зондирований. ''Статическая задача о принадлежности'' представляет собой хорошо изученный раздел в проектировании структур данных [1, 4, 7, 8, 12, 13, 16]. | ||
| Строка 14: | Строка 14: | ||
'''Определение 2 (модель клеточного зонда)'''. Схема клеточного зонда (s, w, t) для решения задачи о статической структуре данных <math>f: D \times Q \to A</math> состоит из двух компонентов: схемы хранения и схемы выполнения запросов. Схема хранения хранит данные <math>d \in D</math> в виде таблицы T[d] из s клеток, каждая из которых содержит слово размером w бит. Схема хранения является детерминированной. Если задан запрос <math>q \in Q</math>, схема выполнения запроса вычисляет f(d, q), выполняя не более t зондирований T[d], причем каждое зондирование читает по одной клетке за раз, а сами операции зондирования могут быть адаптивными. В детерминированной схеме клеточного зонда схема выполнения запросов является детерминированной. В рандомизированной схеме клеточного зонда схема выполнения запросов рандомизирована и может ошибаться с небольшой вероятностью. | '''Определение 2 (модель клеточного зонда)'''. Схема клеточного зонда (s, w, t) для решения задачи о статической структуре данных <math>f: D \times Q \to A</math> состоит из двух компонентов: схемы хранения и схемы выполнения запросов. Схема хранения хранит данные <math>d \in D</math> в виде таблицы <math>T[d]</math> из <math>s</math> клеток, каждая из которых содержит слово размером <math>w</math> бит. Схема хранения является детерминированной. Если задан запрос <math>q \in Q</math>, схема выполнения запроса вычисляет <math>f(d, q)</math>, выполняя не более <math>t</math> зондирований <math>T[d]</math>, причем каждое зондирование читает по одной клетке за раз, а сами операции зондирования могут быть адаптивными. В детерминированной схеме клеточного зонда схема выполнения запросов является детерминированной. В рандомизированной схеме клеточного зонда схема выполнения запросов рандомизирована и может ошибаться с небольшой вероятностью. | ||
Бурман и коллеги [2] изучают сложность статической задачи о принадлежности в модели ''битового зонда''. Это вариация модели клеточного зонда, в которой каждая клетка содержит всего один бит. Иными словами, размер слова 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]. Однако их интересовали верхние границы ''в среднем случае', тогда как далее рассматриваются границы для задачи о принадлежности ''в наихудшем случае''. | Бурман и коллеги [2] изучают сложность статической задачи о принадлежности в модели ''битового зонда''. Это вариация модели клеточного зонда, в которой каждая клетка содержит всего один бит. Иными словами, размер слова 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]. Однако их интересовали верхние границы ''в среднем случае'', тогда как далее рассматриваются границы для задачи о принадлежности ''в наихудшем случае''. | ||