partitioneringsfunksjoner

Partitioneringsfunksjoner er funksjoner som tilordner hvert element i et domene til en av et begrenset antall blokker slik at blokkene danner en partisjon av domenet. Med andre ord er hver del disjunkt og unionen av delene dekker domenet. En slik tilordning kan representeres ved en funksjon f: D -> K der K er en endelig mengde av etiketter som betegner blokkene.

I matematikk skiller man mellom partisjon av en mengde og partisjoner av et heltall. En partisjon av en mengde er en samling disjunkte delmengder som dekker mengden; antall slike partisjoner kalles Bell-tall. En partisjon av heltallet n er en måte å skrive n som summen av positive heltall, hvor rekkefølgen ikke teller; antall slike partisjoner kalles p(n).

Eksempelvis kan en tilordning f fra mengden {a,b,c} til etikettene {1,2} gi partisjonen { {a,b}, {c} }. For heltallet n = 4 er de fem partisjonene: 4, 3+1, 2+2, 2+1+1 og 1+1+1+1.

Anvendelser av partitioneringsfunksjoner spenner fra ren matematikk til databehandling. I database- og distribuert systemdesign brukes partisjoneringsfunksjoner til å fordele data mellom noder (for eksempel hash-, range- eller konsistentsky-partisjonering) for å balansere last og lagre effektivt. Innen maskinlæring og mønstergjenkjenning brukes partitionering for klynging og segmentering av data. I kombinatorikk brukes partisjonering både til å telle strukturer og til å klassifisere ulike måter å bygge dem på.

Se også: partisjon (matematikk), partisjonering i databaseteknologi, partisjonering i grafteori.