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