Hoofdmenu openen

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]

VoorbeeldenBewerken

  • Een opsomming van een verzameling S geeft een indexverzameling  , waar   de verbijzonderde opsomming van S is.
  • Enige oneindig telbare verzameling kan worden geïndexeerd door  .
  • Voor  , is de indicatorfunctie op r de functie   gegeven door
 

De verzameling van alle   functies is een overaftelbare verzameling geïndexeerd door  .

ReferentiesBewerken

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