مترابطة بيانية

الموسوعة الحرة

في الرياضيات ، يُعرف الصف بأنه سلسلة منتهية (أو قائمة مرتبة) من الأعداد . وبشكل أعم، هو سلسلة من الكائنات الرياضية ، تُسمى عناصر الصف. الصف ذو الـ n عنصرًا هو صف مكون من n عنصرًا، حيث n عدد صحيح غير سالب . يوجد صف واحد فقط ذو 0 عنصرًا، يُسمى الصف الفارغ . يُطلق على الصف ذو الـ 1 عنصرًا اسم "المجموعة المفردة"، وعلى الصف ذو الـ 2 عنصرًا اسم " الزوج المرتب " . يُستخدم مصطلح "الصف اللانهائي" أحيانًا للإشارة إلى "السلاسل اللانهائية" .

تُكتب المجموعات عادةً بسرد العناصر داخل أقواس " ( ) " مفصولة بفواصل؛ على سبيل المثال، (2، 7، 4، 1، 7) يدل على مجموعة خماسية. تُستخدم أنواع أخرى من الأقواس أحيانًا، على الرغم من أنها قد تحمل معنى مختلفًا. [ أ ]

يمكن تعريف المجموعة المرتبة n رسميًا بأنها صورة دالة يكون مجالها مجموعة الأعداد الطبيعية n الأولى ( 1، 2، ...، n ). كما يمكن تعريف المجموعات المرتبة من الأزواج المرتبة عن طريق علاقة تكرارية تبدأ من زوج مرتب؛ في الواقع، يمكن تعريف المجموعة المرتبة n بالزوج المرتب المكون من أول ( n - 1) عنصرًا منها وعنصرها n ، على سبيل المثال.(((1،2)،3)،4)=(1،2،3،4){\displaystyle \left(\left(\left(1,2\right),3\right),4\right)=\left(1,2,3,4\right)}.

في علوم الحاسوب ، تتخذ المجموعات أشكالًا متعددة. تُنفذ معظم لغات البرمجة الوظيفية ذات الكتابة المجموعات مباشرةً كأنواع ضرب ، [ 1 ] وهي مرتبطة ارتباطًا وثيقًا بأنواع البيانات الجبرية ، ومطابقة الأنماط ، وتعيين التفكيك . [ 2 ] تقدم العديد من لغات البرمجة بديلًا للمجموعات، يُعرف بأنواع السجلات ، والتي تتميز بعناصر غير مرتبة يتم الوصول إليها بواسطة التسمية. [ 3 ] تجمع بعض لغات البرمجة بين أنواع ضرب المجموعات المرتبة وأنواع السجلات غير المرتبة في بنية واحدة، كما هو الحال في هياكل C وسجلات Haskell. قد تُعرّف قواعد البيانات العلائقية صفوفها (سجلاتها) رسميًا على أنها مجموعات .

تظهر المجموعات أيضًا في الجبر العلائقي ؛ عند برمجة الويب الدلالي باستخدام إطار وصف الموارد (RDF)؛ في اللغويات ؛ [ 4 ] وفي الفلسفة . [ 5 ]

أصل الكلمة

نشأ المصطلح كتعبير مجرد عن التسلسل: مفرد، زوج/مزدوج، ثلاثي، رباعي، خماسي، سداسي، سباعي، ثماني، ...، مجموعة من n ، ...، حيث تُستمد البادئات من الأسماء اللاتينية للأعداد. تُسمى المجموعة الصفرية الفريدة بالمجموعة الفارغة . تُسمى المجموعة الأحادية مفردًا ، وتُسمى المجموعة الثنائية زوجًا مرتبًا ، وتُسمى المجموعة الثلاثية ثلاثية . يمكن أن يكون العدد n أي عدد صحيح غير سالب . على سبيل المثال، يمكن تمثيل العدد المركب بمجموعة ثنائية من الأعداد الحقيقية، ويمكن تمثيل الكواترنيون بمجموعة رباعية، ويمكن تمثيل الأوكتوني بمجموعة ثمانية، ويمكن تمثيل السدينيون بمجموعة ستة عشر.

على الرغم من أن هذه الاستخدامات تُعامل اللاحقة "-tuple "، إلا أن اللاحقة الأصلية كانت "-ple" كما في "triple" (ثلاثي) أو "decuple" (عشري). يعود أصل هذه اللاحقة إلى اللاتينية في العصور الوسطى " plus " (بمعنى "أكثر")، وهي مرتبطة بالكلمة اليونانية "-πλοῦς"، التي حلت محل اللاحقة الكلاسيكية والقديمة المتأخرة "-plex" (بمعنى "مطوي")، كما في "duplex". [ 6 ] [ ب ]

ملكيات

القاعدة العامة لتحديد هوية مجموعتين من n عنصرًا هي

(أ1،أ2،...،أن)=(ب1،ب2،...،بن){\displaystyle (a_{1},a_{2},\ldots ,a_{n})=(b_{1},b_{2},\ldots ,b_{n})}إذا وفقط إذاأ1=ب1، أ2=ب2، ...، أن=بن{\displaystyle a_{1}=b_{1},{\text{ }}a_{2}=b_{2},{\text{ }}\ldots ,{\text{ }}a_{n}=b_{n}}.

وبالتالي، فإن للزوج المرتب خصائص تميزه عن المجموعة :

  1. قد تحتوي المجموعة على عدة نسخ من نفس العنصر، لذا فإن المجموعة(1،2،2،3)≠(1،2،3){\displaystyle (1,2,2,3)\neq (1,2,3)}لكن اضبط{1،2،2،3}={1،2،3}{\displaystyle \{1,2,2,3\}=\{1,2,3\}}.
  2. يتم ترتيب عناصر المجموعة: مجموعة(1،2،3)≠(3،2،1){\displaystyle (1,2,3)\neq (3,2,1)}لكن تم تحديده{1،2،3}={3،2،1}{\displaystyle \{1,2,3\}=\{3,2,1\}}.
  3. تحتوي المجموعة المرتبة على عدد محدود من العناصر، بينما قد تحتوي المجموعة أو المجموعة المتعددة على عدد لا نهائي من العناصر.

التعريفات

هناك العديد من تعريفات المجموعات التي تمنحها الخصائص الموضحة في القسم السابق.

الصفوف كدوال

ال0{\displaystyle 0}يمكن تعريف الدالة -tuple على أنها دالة فارغة .ن≥1،{\displaystyle n\geq 1,}الن{\displaystyle n}-مترابطة بيانية(أ1،...،أن){\displaystyle \left(a_{1},\ldots ,a_{n}\right)}يمكن تحديدها بالدالة الشاملة

F : {1،...،ن} → {أ1،...،أن}{\displaystyle F~:~\left\{1,\ldots ,n\right\}~\to ~\left\{a_{1},\ldots ,a_{n}\right\}}

مع النطاق

اِختِصاص⁡F={1،...،ن}={أنا∈شمال:1≤أنا≤ن}{\displaystyle \operatorname {domain} F=\left\{1,\ldots ,n\right\}=\left\{i\in \mathbb {N} :1\leq i\leq n\right\}}

ومع النطاق المشترك

نطاق مشترك⁡F={أ1،...،أن}،{\displaystyle \operatorname {codomain} F=\left\{a_{1},\ldots ,a_{n}\right\},}

ذلك محدد فيأنا∈اِختِصاص⁡F={1،...،ن}{\displaystyle i\in \operatorname {domain} F=\left\{1,\ldots ,n\right\}}بواسطة

F(أنا):=أأنا.{\displaystyle F(i):=a_{i}.}

إنه،F{\displaystyle F}هي الدالة المعرفة بواسطة

1↦أ1⋮ن↦أن{\displaystyle {\begin{alignedat}{3}1\;&\mapsto &&\;a_{1}\\\;&\;\;\vdots &&\;\\n\;&\mapsto &&\;a_{n}\\\end{alignedat}}}

وفي هذه الحالة تكون المساواة

(أ1،أ2،...،أن)=(F(1)،F(2)،...،F(ن)){\displaystyle \left(a_{1},a_{2},\dots ,a_{n}\right)=\left(F(1),F(2),\dots ,F(n)\right)}

ينطبق بالضرورة.

المجموعات المرتبة هي مجموعات من الأزواج المرتبة

تُعرَّف الدوال عادةً برسومها البيانية ، وهي عبارة عن مجموعة معينة من الأزواج المرتبة. في الواقع، يستخدم العديد من المؤلفين الرسوم البيانية كتعريف للدالة. باستخدام هذا التعريف للدالة، فإن الدالة المذكورة أعلاهF{\displaystyle F}يمكن تعريفها على النحو التالي:

F := {(1،أ1)،...،(ن،أن)}.{\displaystyle F~:=~\left\{\left(1,a_{1}\right),\ldots ,\left(n,a_{n}\right)\right\}.}

المجموعات المرتبة كأزواج مرتبة متداخلة

هناك طريقة أخرى لنمذجة المجموعات المرتبة في نظرية المجموعات وهي اعتبارها أزواجًا مرتبة متداخلة . يفترض هذا النهج أن مفهوم الزوج المرتب قد تم تعريفه مسبقًا.

  1. يتم تمثيل المجموعة الصفرية (أي المجموعة الفارغة) بواسطة المجموعة الفارغة∅{\displaystyle \emptyset }.
  2. يمكن تعريف المجموعة المرتبة n ، حيث n > 0 ، على أنها زوج مرتب من العنصر الأول ومجموعة مرتبة ( n − 1) (والتي تحتوي على العناصر المتبقية عندما n > 1) :
    (أ1،أ2،أ3،...،أن)=(أ1،(أ2،أ3،...،أن)){\displaystyle (a_{1},a_{2},a_{3},\ldots ,a_{n})=(a_{1},(a_{2},a_{3},\ldots ,a_{n}))}

يمكن تطبيق هذا التعريف بشكل متكرر على المجموعة ( n − 1) :

(أ1،أ2،أ3،...،أن)=(أ1،(أ2،(أ3،(...،(أن،∅)...)))){\displaystyle (a_{1},a_{2},a_{3},\ldots ,a_{n})=(a_{1},(a_{2},(a_{3},(\ldots ,(a_{n},\emptyset )\ldots ))))}

وهكذا، على سبيل المثال:

(1،2،3)=(1،(2،(3،∅)))(1،2،3،4)=(1،(2،(3،(4،∅)))){\displaystyle {\begin{aligned}(1,2,3)&=(1,(2,(3,\emptyset )))\\(1,2,3,4)&=(1,(2,(3,(4,\emptyset ))))\\\end{aligned}}}

يبدأ أحد أشكال هذا التعريف "بتقشير" العناصر من الطرف الآخر:

  1. المجموعة الصفرية هي المجموعة الفارغة∅{\displaystyle \emptyset }.
  2. لـ n > 0 :
    (أ1،أ2،أ3،...،أن)=((أ1،أ2،أ3،...،أن-1)،أن){\displaystyle (a_{1},a_{2},a_{3},\ldots ,a_{n})=((a_{1},a_{2},a_{3},\ldots ,a_{n-1}),a_{n})}

يمكن تطبيق هذا التعريف بشكل متكرر:

(أ1،أ2،أ3،...،أن)=((...(((∅،أ1)،أ2)،أ3)،...)،أن){\displaystyle (a_{1},a_{2},a_{3},\ldots ,a_{n})=((\ldots (((\emptyset ,a_{1}),a_{2}),a_{3}),\ldots ),a_{n})}

وهكذا، على سبيل المثال:

(1،2،3)=(((∅،1)،2)،3)(1،2،3،4)=((((∅،1)،2)،3)،4){\displaystyle {\begin{aligned}(1,2,3)&=(((\emptyset ,1),2),3)\\(1,2,3,4)&=((((\emptyset ,1),2),3),4)\\\end{aligned}}}

المجموعات المتداخلة

باستخدام تمثيل كوراتوفسكي للزوج المرتب ، يمكن إعادة صياغة التعريف الثاني أعلاه من حيث نظرية المجموعات البحتة :

  1. يتم تمثيل المجموعة الصفرية (أي المجموعة الفارغة) بواسطة المجموعة الفارغة∅{\displaystyle \emptyset }؛
  2. يتركx{\displaystyle x}ليكن n -tuple(أ1،أ2،...،أن){\displaystyle (a_{1},a_{2},\ldots ,a_{n})}ودعx→ب≡(أ1،أ2،...،أن،ب){\displaystyle x\rightarrow b\equiv (a_{1},a_{2},\ldots ,a_{n},b)}. ثم،x→ب≡{{x}،{x،ب}}{\displaystyle x\rightarrow b\equiv \{\{x\},\{x,b\}\}}(السهم الأيمن،→{\displaystyle \rightarrow }(يمكن قراءتها على أنها "ملحق بـ.")

في هذه الصيغة:

()=∅(1)=()→1={{()}،{()،1}}={{∅}،{∅،1}}(1،2)=(1)→2={{(1)}،{(1)،2}}={{{{∅}،{∅،1}}}،{{{∅}،{∅،1}}،2}}(1،2،3)=(1،2)→3={{(1،2)}،{(1،2)،3}}={{{{{{∅}،{∅،1}}}،{{{∅}،{∅،1}}،2}}}،{{{{{∅}،{∅،1}}}،{{{∅}،{∅،1}}،2}}،3}}{\displaystyle {\begin{array}{lclcl}()&&&=&\emptyset \\&&&&\\(1)&=&()\rightarrow 1&=&\{\{()\},\{(),1\}\}\\&&&=&\{\{\emptyset \},\{\emptyset ,1\}\}\\&&&&\\(1,2)&=&(1)\rightarrow 2&=&\{\{(1)\},\{(1),2\}\}\\&&&=&\{\{\{\{\emptyset \},\{\emptyset ,1\}\}\},\\&&&&\{\{\{\emptyset \},\{\emptyset ,1\}\},2\}\}\\&&&&\\(1,2,3)&=&(1,2)\rightarrow 3&=&\{\{(1,2)\},\{(1,2),3\}\}\\&&&=&\{\{\{\{\{\{\emptyset \},\{\emptyset ,1\}\}\},\\&&&&\{\{\{\emptyset \},\{\emptyset ,1\}\},2\}\}\},\\&&&&\{\{\{\{\{\emptyset \},\{\emptyset ,1\}\}\},\\&&&&\{\{\{\emptyset \},\{\emptyset ,1\}\},2\}\},3\}\}\\\end{array}}}

مجموعات من n عنصر من m عنصر

في الرياضيات المتقطعة ، وخاصةً في التوافقية ونظرية الاحتمالات المحدودة ، تظهر المجموعات المرتبة من الرتبة n في سياق مسائل العد المختلفة، وتُعامل بشكل غير رسمي كقوائم مرتبة طولها n . [ 7 ] تُسمى المجموعات المرتبة من الرتبة n التي تنتمي عناصرها إلى مجموعة من m عنصرًا أيضًا بالترتيبات المتكررة ، أو تباديل مجموعة متعددة ، وفي بعض المراجع غير الإنجليزية، بالتغيرات المتكررة . عدد المجموعات المرتبة من الرتبة n لمجموعة من m هو m^ n . وهذا ناتج عن قاعدة الضرب التوافقية . [ 8 ] إذا كانت S مجموعة منتهية ذات عدد عناصر m ، فإن هذا العدد هو عدد عناصر القوة الديكارتية من الرتبة n ، S × S × ⋯ × S. المجموعات المرتبة هي عناصر من مجموعة الضرب هذه.

نظرية الأنواع

في نظرية الأنواع ، الشائعة الاستخدام في لغات البرمجة ، يمتلك الزوج المرتب نوع ضرب ؛ وهذا لا يحدد طوله فحسب، بل يحدد أيضًا الأنواع الأساسية لكل مكون. رسميًا:

(x1،x2،...،xن):تي1×تي2×...×تين{\displaystyle (x_{1},x_{2},\ldots ,x_{n}):{\mathsf {T}}_{1}\times {\mathsf {T}}_{2}\times \ldots \times {\mathsf {T}}_{n}}

والإسقاطات هي مُنشئات المصطلحات :

π1(x):تي1، π2(x):تي2، ...، πن(x):تين{\displaystyle \pi _{1}(x):{\mathsf {T}}_{1},~\pi _{2}(x):{\mathsf {T}}_{2},~\ldots ,~\pi _{n}(x):{\mathsf {T}}_{n}}

يحتوي الصف ذو العناصر المصنفة المستخدم في النموذج العلائقي على نوع سجل . ويمكن تعريف كلا النوعين على أنهما امتدادان بسيطان لحساب لامدا ذي النوع البسيط . [ 9 ]

يرتبط مفهوم المجموعة المرتبة في نظرية الأنواع ومفهومها في نظرية المجموعات على النحو التالي: إذا نظرنا إلى النموذج الطبيعي لنظرية الأنواع، واستخدمنا أقواس سكوت للإشارة إلى التفسير الدلالي ، فإن النموذج يتكون من بعض المجموعات.S1،S2،...،Sن{\displaystyle S_{1},S_{2},\ldots ,S_{n}}(ملاحظة: استخدام الخط المائل هنا يميز المجموعات عن الأنواع) بحيث:

[[تي1]]=S1، [[تي2]]=S2، ...، [[تين]]=Sن{\displaystyle [\![{\mathsf {T}}_{1}]\!]=S_{1},~[\![{\mathsf {T}}_{2}]\!]=S_{2},~\ldots ,~[\![{\mathsf {T}}_{n}]\!]=S_{n}}

وتفسير المصطلحات الأساسية هو:

[[x1]]∈[[تي1]]، [[x2]]∈[[تي2]]، ...، [[xن]]∈[[تين]]{\displaystyle [\![x_{1}]\!]\in [\![{\mathsf {T}}_{1}]\!],~[\![x_{2}]\!]\in [\![{\mathsf {T}}_{2}]\!],~\ldots ,~[\![x_{n}]\!]\in [\![{\mathsf {T}}_{n}]\!]}.

إن المجموعة n من نظرية النوع لها تفسير طبيعي على أنها مجموعة n من نظرية المجموعات: [ 10 ]

[[(x1،x2،...،xن)]]=([[x1]]،[[x2]]،...،[[xن]]){\displaystyle [\![(x_{1},x_{2},\ldots ,x_{n})]\!]=(\,[\![x_{1}]\!],[\![x_{2}]\!],\ldots ,[\![x_{n}]\!]\,)}

يُفسر نوع الوحدة دلاليًا على أنه مجموعة من 0.

للاطلاع على قائمة بأنواع المجموعات في لغات البرمجة، انظر نوع المنتج#أنواع المنتجات في لغات البرمجة .

انظر أيضاً

ملحوظات

  1. تُستخدم الأقواس المربعة للمصفوفات ، بما في ذلك متجهات الصفوف . أما الأقواس المعقوفة فتُستخدم للمجموعات . ولكل لغة برمجة اصطلاحها الخاص في استخدام الأقواس المختلفة.
  2. ↑ قارن أصل كلمة ploidy ، من الكلمة اليونانية التي تعني -fold.

مراجع

  1. ↑ "نوع البيانات الجبرية - هاسكل ويكي" . wiki.haskell.org .
  2. ↑ "تفكيك عملية التخصيص" . وثائق MDN على الويب . 18 أبريل 2023.
  3. ↑ "هل يضمن جافا سكريبت ترتيب خصائص الكائن؟" . ستاك أوفرفلو .
  4. ↑ ماثيوز، دكتوراه في الفلسفة، محرر. (يناير 2007). "مجموعة من N" . قاموس أكسفورد الموجز للغويات . مطبعة جامعة أكسفورد. ISBN 9780199202720تم الاطلاع عليه بتاريخ 1 مايو 2015 .
  5. ↑ بلاكبيرن، سيمون (1994). "مجموعة مرتبة من n عنصر". قاموس أكسفورد للفلسفة . دليل أكسفورد المرجعي السريع ( الطبعة الثالثة). أكسفورد: مطبعة جامعة أكسفورد (نُشر عام 2016). ص 342. ISBN   9780198735304تم الاسترجاع في 30-06-2017 . الصف المرتب n[:] تعميم لمفهوم [...] الزوج المرتب إلى متواليات من n عنصر.
  6. ↑ قاموس أكسفورد الإنجليزي ، sv "ثلاثي"، "رباعي"، "خماسي"، "ثنائي"
  7. ↑ دانجيلو وويست 2000 ، ص 9 
  8. ↑ دانجيلو وويست 2000 ، ص 101 
  9. ↑ بيرس، بنجامين (2002). أنواع ولغات البرمجة . مطبعة معهد ماساتشوستس للتكنولوجيا. الصفحات 126-132 . ISBN  0-262-16209-1.
  10. ↑ ستيف أوودي، من المجموعات إلى الأنواع إلى الفئات إلى المجموعات ، 2009، نسخة أولية

مصادر

  • شعار ويكشنريتعريف كلمة tuple في قاموس ويكشنري