Multiset

A multihalmaz a halmaz fogalmának olyan módosítása, amely lehetővé teszi, hogy ugyanazt az elemet többször is beépítsék egy gyűjteménybe. A multihalmaz elemeinek számát, az ismétlődő elemeket figyelembe véve, méretének vagy teljesítményének nevezzük .

A multihalmaz gondolatát implicit módon az ókor óta használják ( Knuth II. Bhaskara példáját idézi a 12. századból, aki a multihalmazok permutációit tanulmányozta), de a fogalom bevezetése és a kifejezés rögzítése de Bruijn nevéhez fűződik . (1970-es évek) [1] . Főleg alkalmazásokban ( informatika , mesterséges intelligencia , döntéselmélet ) használják, a Petri-háló elméletére alkalmazva a multihalmazt halmaznak nevezzük [2] . A különböző alkalmazások eltérő jelölést használnak.

Formálisan egy halmaz multihalmazát rendezett párként definiáljuk , ahol egy függvény , amely a halmaz minden eleméhez hozzárendel egy természetes számot , amelyet ezen elem többszörösének nevezünk. $A$ $(A,m)$ $m \kettőspont A \ - \mathbb{N}$ $A$

Az egyik legegyszerűbb példa egy egész szám prímtényezőinek multihalmaza. Így például a 120-as szám prímtényezőkre bontásának alakja: , tehát prímosztóinak sokhalmaza : . $120=2^{3}3^{1}5^{1}$ $\{2, 2, 2, 3, 5\}$

Egy másik példa egy algebrai egyenlet gyökeinek multihalmaza . Például az egyenletnek gyökei vannak . $x^3 - 5x^2 + 8x - 4 = 0$ $\{1, 2, 2\}$

A számossághalmazból kiválasztott elemekből álló különböző kardinalitási multihalmazok száma a következő képletből számítható ki binomiális együtthatóként : $k$ $n$

{n+k-1 \válasszon k}

Jegyzetek

↑ Donald Knuth . The Art of Computer Programming, Volume 2. Az eredményül kapott algoritmusok = The Art of Computer Programming, vol.2. Félnumerikus algoritmusok. - 3. kiadás - M. : Williams, 2007. - S. 832. - ISBN 0-201-89684-2 .
↑ James Peterson. A kit elmélet áttekintése // Petri-háló elmélet és rendszerek modellezése. - M .: Mir , 1984. - S. 231-235. — 264 p. - 8400 példány.

Irodalom

A. B. Petrovszkij. Halmazok és multihalmazok terei . - M. : Szerkesztői URSS, 2003. - S. 248. - ISBN 5-7262-0633-9 .