Indexverzameling

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

In de wiskunde kunnen de elementen van een verzameling A worden geïndexeerd of gelabeled met behulp van een verzameling J, die om die reden een indexverzameling wordt genoemd. Het indexeren bestaat uit een surjectieve functie van J op A en de geïndexeerde collectie wordt typisch een geïndexeerde familie genoemd, wat vaak wordt genoteerd als (Aj)jJ.

In de complexiteitstheorie en cryptografie is een indexverzameling een verzameling, waarvoor een algoritme I bestaat, dat deze verzameling efficiënt kan doorlopen en bevragen; dat wil zeggen dat op basis van een korte input (lengte n) de indexverzameling I een veel langer (veelvoud van lengte n) element uit de verzameling kan selecteren en teruggeven.[1]

Voorbeelden[bewerken]

  • Een opsomming van een verzameling S geeft een indexverzameling J \sub \mathbb{N}, waar f:J \rarr \mathbb{N} de verbijzonderde opsomming van S is.
  • Enige oneindig telbare verzameling kan worden geïndexeerd door \mathbb{N}.
  • Voor r \in \mathbb{R}, is de indicatorfunctie op r de functie \mathbf{1}_r\colon \mathbb{R} \rarr \mathbb{R} gegeven door
\mathbf{1}_r (x) := \begin{cases} 0, & \mbox{if } x \ne r \\ 1, & \mbox{if } x = r. \end{cases}

De verzameling van alle \mathbf{1}_r functies is een overaftelbare verzameling geïndexeerd door \mathbb{R}.

Referenties[bewerken]

  1. Goldreich, Oded, Foundations of Cryptography: Volume 1, Basic Tools, Cambridge University Press, 2001 ISBN 0-521-79172-3.

Zie ook[bewerken]