Multimultzo

Artikulu hau matematikaren kontzeptu bati buruzkoa da, konputazioaren zientzian erabilitako egiturei buruz zerbait jakiteko ikus Multimultzo (datu mota abstraktu) artikulua.

Matematikan multimultzo bat multzo baten generalizazioa da, multimultzotan haien elementuak behin baino gehiago agertu ahal direla. Adibidez, a eta b elementuak eta ez beste ezein elementurik dituen multzo bakar bat dago, baina baldintza hori betetzen duten multimultzo asko daude:a-ren kopia bi eta b-ren kopia bat dituen multimultzoa, a-ren hiru kopia eta b-ren beste hiru kopia dituen multimultzoa eta abar. "Multimultzo" izena Nicolaas Govert de Bruijn-ek sortu zuen 1970ean. Matematikan eta beste eremu batzuetan multimultzoak "multimultzo" izena baino mende batzuk lehenago erabili dira. Knuth-ek (1998) multimultzoen lehenengo ikerketa multimultzoen permutazioak deskribatu zituen Bhascara Acharya matematikari indiarrak egindakoa dela esaten du, 1150 urtearen inguruan.

Sinopsia

Elementu baten agerpenen kopurua multimultzo batean elementu horren multimultzo horrekiko anizkoiztasuna da. Multimultzo baten elementu guztien kopurua, errepikatutako elementuena barne, multimultzoaren kardinalitatea da. Adibidez, {a, a, b, b, b, c} multimultzoan a, b, eta c elementuen anizkoiztasunak, hurrenez hurren, 2, 3, eta 1 dira, eta multimultzoaren kardinalitatea 6. Batzuetan multzoak eta multimultzoak bereizteko kako zuzenak erabilten dira: {2,2,3} multimultzoa adierazteko [2,2,3] erabiliz. Multimultzoetan, multzoetan bezala baina n-koteetan ez bezala, elementuen hurrenkerak ez du garrantzirik: {a, a, b} eta {a, b, a} multimultzoak multimultzo bera dira.

Definizio formala

Multzo-teorian, multimultzo bat formalki $\left(A,m\right)$ bikoteaz definitu ahal da, $A$ multzo bat eta $m\colon A\to \mathbb {N} _{\geq 1}$ funtzioa $A$-tik zenbaki arrunt positiboen $\mathbb {N} _{\geq 1}=\left\{1,2,3,\dots \right\}$ multzorako funtzio bat direla. $A$ multzoari elementuen azpiko multzoa esaten zaio. $A$ multzoaren $a$ elementuaren anizkoiztasuna (hau da, bere agerpenen kopurua) $m\!\left(a\right)$ zenbakia da. $A$ multzoko elementuak $U$ multzo unibertsalaren elementuak izan behar badira, definizioa $U$-tik zenbaki arrunten $\mathbb {N} =\left\{0,1,2,3,\dots \right\}$ multzorako $m_{U}\colon U\to \mathbb {N}$ anizkoiztasun funtzio bakar batera sinplifikatu ahal da, azken hau $m$ funtzioa $U$-ra hedatuz lortzen dela, 0 balioko anizkoiztasuna emanik $A$-ren elementuak ez diren $U$-ren elemntuei. Anizkoiztasun-funtzio orokorrago hau beherago $1_{A}$ deitutako anizkoiztasun funtzioa da. Beste edozein funtzio bezala, $m$ futzioa bere grafoaren bidez definitu ahal da: $\left\{\left(a,m\left(a\right)\right):a\in A\right\}$ bikote ordenatuen multzoaz. Definizio honekin $\left\{a,a,b\right\}$ idazten den multimultzoa $\left(\left\{a,b\right\},\left\{\left(a,2\right),\left(b,1\right)\right\}\right)$ legez definitzen da eta $\left\{a,b\right\}$ multimultzoa $\left(\left\{a,b\right\},\left\{\left(a,1\right),\left(b,1\right)\right\}\right)$ bezala.

Multimultzo-kontzeptua multzo-kontzeptuaren jeneralizazioa da. Multzo arrunt bat elementu guztiek 1 anizkoiztasuna (eta ez beste zenbaki arrunt handiago bat) duten multimultzo bat da.

Multimultzoen definizioa hedatu ahal da elementuen anizkoitasunak zenbaki arrunt finituez gain infinituak izaten ere onartuz, baina era horretan multimultzoen propietate guztiak ez dira mantentzen eta artikulu honetan goiko definizioa erabiliko da, anizkoiztasun finituena.

Ereduak

Eredu arrunt eta errazenetariko bat n zenbaki baten zatitzaile lehenen multimultzoarena da. Hemen elementuen azpiko multzoa n-ren zatitzaile lehenen multzoa da. Esate baterako, 120 zenbakiak {2, 2, 2, 3, 5} multimultzoa ematen duen $120=2^{3}3^{1}5^{1}\,$ lehenen bidezko faktorizazio du.

Beste eredu bat ekuazio aljebraiko baten ebazpenen multimultzoa da. Adibidez, ekuazio koadratiko batek ebazpen bi ditu baina batzuetan bi ebazpenak zenbaki berbera dira; beraz ekuazioaren ebazpenen multimultzoa { 3, 5 } edo { 4, 4 } modukoa izan daiteke. Bigarren kasuan ebazpena 2 anizkoiztasunekoa da.

Orokortzeak

Multimultzoen orokortze batzuk aurkeztu, ikertu eta problema batzuen irtenbideak aurkitzeko erabili dira 1980tik hona.

Yager-ek (1986) zorro lausoak deitu zituen multimultzo lausoak sortu zituen (fuzzy multisets ingelesez).

Grzymala-Busse-k (1987an) multierlazioak erabiliz, hurbilketazko multimultzoak aurkeztu zituen (rough multisets ingelesez).

Blizard-ek (1989an) anizkoiztasun errealeko multimultzoak asmatu zituen, haien elementuen anizkoiztasuna edozein zenbaki erreal ez-negatibokoa izan daitekeela. Geroago (1990) anizkoiztasun negatiboko multimultzoak ere aurkeztu zituen.

Loeb-ek (1992an) multzo hibridoak eta multimultzoen orokortze bat aurkeztu zituen, multimultzo horietan elementuen anizkoiztasuna edozein zenbaki osoa izan ahal dela.

Miyamoto-k (2001ean) are gehiago orokortu zituen multimultzoak, elementuen anizkoiztasuna balio errealeko edozein funtzio mailakatua izan daitekeen multimultzoak aurkeztuz.

Alkhazaleh, Salleh eta Hassan-ek (2011n) multimultzo bigunak aurkeztu zituzten eta Alkhazaleh eta Salleh-ek (2012an) multimultzo bigun lausoak (fuzzy soft multisets ingelesez).

Burgin-ek (1990; 1992; 2004; 2011) multimultzoak eta multzoen beste orokortze guztiak batu zituen izendatutako multzo kontzeptuaren bidez (named set ingelesez).

Erreferentziak

1. Aigner, M. (1979). Combinatorial Theory, Springer Verlag, New York/Berlin.
2. Alkhazaleh, S. and Salleh, A.R. (2012). Fuzzy Soft Multiset Theory, Abstract and Applied Analysis, article ID 350600, 20 p.
3. Alkhazaleh, S., Salleh, A.R. and Hassan, N. (2011). Soft Multisets Theory, Applied Mathematical Sciences, 5(72):3561–3573.
4. Anderson, I. (1987). Combinatorics of Finite Sets, Clarendon Press, Oxford.
5. Angelelli, I. (1965). Leibniz's misunderstanding of Nizolius' notion of 'multitudo', Notre Dame Journal of Formal Logic, 6:319–322.
6. Blizard, Wayne D. (1989). "Multiset theory," Notre Dame Journal of Formal Logic, 30(1), Winter:36–66. doi:10.1305/ndjfl/1093634995 http://projecteuclid.org/euclid.ndjfl/1093634995 MR990203 0668.03027
7. Blizard, WD. (1989). Real-valued Multisets and Fuzzy Sets, Fuzzy Sets and Systems, 33:77–97.
8. Blizard, W. (1990). Negative Membership, Notre Dame Journal of Formal Logic, 31(1):346–368.
9. Blizard, WD. (1991). The Development of Multiset Theory, Modern Logic, 1(4):319–352.
10. Bogart, Kenneth P. (2000). Introductory combinatorics, 3rd. ed. San Diego CA: Harcourt.
11. Burgin M. (1990). Theory of Named Sets as a Foundational Basis for Mathematics, In: Structures in Mathematical Theories, San Sebastian, pp. 417–420 (http://www.blogg.org/blog-30140-date-2005-10-26.html)
12. Burgin, M. (1992). On the concept of a multiset in cybernetics, Cybernetics and System Analysis, 3:165–167.
13. Burgin, M. (2004). Unified Foundations of Mathematics, Preprint Mathematics LO/0403186, 39 p. (electronic edition: http://arXiv.org)
14. Burgin, M. (2011), Theory of Named Sets, Mathematics Research Developments, Nova Science Pub Inc, ISBN 978-1-61122-788-8, books.google.com
15. Dedekind R. (1888). Was sind und was sollen die Zahlen?, Vieweg, Braunschweig.
16. Gessel, Ira M., and Stanley, Richard P. (1995). "Algebraic enumeration" in Graham, R. L., Grötschel, M., & Lovász, L., eds., Handbook of combinatorics, 2:1021–1061. Elsevier, ISBN 0-444-82351-4, 0-444-88002-X, 0-262-07171-1, 0-262-07169-X.
17. Grzymala-Busse, J. (1987). Learning from examples based on rough multisets, in Proceedings of the 2nd International Symposium on Methodologies for Intelligent Systems, Charlotte, NC, USA, pp. 325–332.
18. Grumbach, S. and Milo, T. (1996). Towards tractable algebras for bags, Journal of Computer and System Sciences, 52(3):570–588.
19. Hickman, J. L. (1980). A note on the concept of multiset, Bulletin of the Australian Mathematical Society, 22:211–17.
20. Kircher, A. (1650). Musurgia Universalis, Corbelletti, Rome.
21. Knuth, Donald E. (1998). The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Addison Wesley. p. 694. ISBN 0-201-89684-2.
22. Knuth, D. (1998). The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, Mass.
23. Libkin, L. and Wong, L. (1994). Some properties of query languages for bags, in Proceedings of the Workshop on Database Programming Languages, Springer Verlag, pp. 97–114.
24. Libkin, L. and Wong, L. (1995). On representation and querying incomplete information in databases with bags, Information Processing Letters, 56(4):209–214.
25. Loeb, D. (1992). Sets with a negative numbers of elements, Advances in Mathematics, 91:64–74.
26. Miyamoto S. (2001). Fuzzy Multisets and their Generalizations, in ‘'Multiset Processing’', LNCS 2235:225–235.
27. Prestet, J. (1675). Elemens des Mathematiques, André Pralard, Paris.
28. Singh D. (1994) A Note on the Development of Multiset Theory, Modern Logic, 4:405–406.
29. Singh D, Ibrahim AM, Yohanna T, and Singh JN. (2007) An overview of the applications of multisets, Novi Sad Journ. Math., 37(2):73–92.
30. Stanley, Richard P. (1997, 1999). Enumerative Combinatorics, Vols. 1 and 2., Cambridge University Press. ISBN 0-521-55309-1, 0-521-56069-1.
31. Syropoulos, Apostolos. (2001). "Mathematics of Multisets" in C. S. Calude et al., eds., Multiset processing: Mathematical, computer science, and molecular computing points of view, LNCS 2235. Springer-Verlag: 347–358.
32. Yager, R. R. (1986). On the Theory of Bags, International Journal of General Systems, 13:23–37.
33. Wallis (1685). A treatise of algebra, John Playford, London.

Kanpo estekak

• Datuak: Q864377