Multiset

Multiset je modifikace konceptu sady , která umožňuje zahrnutí stejného prvku do kolekce několikrát. Počet prvků v multimnožině, při zohlednění opakujících se prvků, se nazývá její velikost nebo síla .

Myšlenka multimnožiny byla implicitně používána již od starověku ( Knuth uvádí příklad Bhaskary II z 12. století, který studoval permutace multimnožin), ale zavedení konceptu a fixace termínu jsou připisovány de Bruijnovi (70. léta 20. století) [1] . Používá se především v aplikacích ( informatika , umělá inteligence , teorie rozhodování ), při aplikaci na teorii Petriho sítí se multimnožina nazývá množina [2] . Různé aplikace používají různý zápis.

Formálně je multimnožina na množině definována jako uspořádaná dvojice , kde je funkce , která každému prvku množiny přiřadí nějaké přirozené číslo , nazývané násobnost tohoto prvku. $A$ $(Dopoledne)$ $m \colon A \to \mathbb{N}$ $A$

Jedním z nejjednodušších příkladů je vícenásobná množina prvočinitelů celého čísla. Takže například rozklad čísla 120 na prvočinitele má tvar: , takže jeho multimnožina prvočíselných dělitelů je . $120=2^{3}3^{1}5^{1}$ $\{2, 2, 2, 3, 5\}$

Dalším příkladem je multimnožina kořenů algebraické rovnice . Například rovnice má kořeny . $x^3 - 5x^2 + 8x - 4 = 0$ $\{1, 2, 2\}$

Počet různých multimnožin mohutností sestávajících z prvků vybraných ze sady mohutností lze vypočítat z následujícího vzorce jako binomický koeficient : $k$ $n$

{n+k-1 \vyberte k}

Poznámky

↑ Donald Knuth . Umění počítačového programování, díl 2. Výsledné algoritmy = Umění počítačového programování, díl 2. Seminumerické algoritmy. - 3. vyd. - M. : Williams, 2007. - S. 832. - ISBN 0-201-89684-2 .
↑ James Peterson. Přehled teorie stavebnic // Teorie Petriho sítí a modelování systémů. - M .: Mir , 1984. - S. 231-235. — 264 s. - 8400 výtisků.

Literatura

A. B. Petrovský. Prostory množin a multimnožin . - M. : Editorial URSS, 2003. - S. 248. - ISBN 5-7262-0633-9 .