Набор индексов
В математике индексный набор — это набор, члены которого обозначают (или индексируют) элементы другого набора. [1] [2] Например, если элементы набора A могут быть проиндексированы или помечены с помощью элементов набора J , то J является набором индексов. Индексирование состоит из сюръективной функции из J на A индексированный набор обычно называется индексированным семейством , часто записываемым как { A j } j ∈ J. , а
Примеры
[ редактировать ]- Перечисление S набора дает набор индексов , где : J → S — частная нумерация S. f
- Любое счетное бесконечное множество может быть (инъективно) проиндексировано множеством натуральных чисел . .
- Для , индикаторной функцией на r является функция данный
Набор всех подобных индикаторных функций, , представляет собой несчетное множество , индексируемое .
Другое использование
[ редактировать ]В теории сложности вычислений и криптографии набор индексов — это набор, для которого существует алгоритм I , который может эффективно выбирать набор; например, на входе 1 н , я могу эффективно выбрать поли(n)-битный длинный элемент из набора. [3]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Вайсштейн, Эрик. «Индексный набор» . Вольфрам Математический мир . Вольфрам Исследования . Проверено 30 декабря 2013 г.
- ^ Манкрес, Джеймс Р. (2000). Топология . Том. 2. Река Аппер-Седл: Прентис-холл.
- ^ Гольдрейх, Одед (2001). Основы криптографии: Том 1, Основные инструменты . Издательство Кембриджского университета. ISBN 0-521-79172-3 .