تصميم الكتلة

في الرياضيات التوافقية ، يُعرف تصميم الكتل بأنه بنية وقوعية تتكون من مجموعة مع عائلة من المجموعات الجزئية تُعرف بالكتل ، يتم اختيارها بحيث يحقق عدد مرات ظهور كل عنصر شروطًا معينة، مما يجعل مجموعة الكتل متناظرة (متوازنة). تُستخدم تصميمات الكتل في العديد من المجالات، بما في ذلك التصميم التجريبي ، والهندسة المحدودة ، والكيمياء الفيزيائية ، واختبار البرمجيات ، والتشفير ، والهندسة الجبرية .

بدون مزيد من التحديدات، يشير مصطلح تصميم الكتلة عادةً إلى تصميم الكتلة غير المكتمل المتوازن ( BIBD )، وتحديدًا (وأيضًا بشكل مرادف) تصميم 2، وهو النوع الأكثر دراسة تاريخيًا نظرًا لتطبيقه في تصميم التجارب . ^{[ 1 ] [ 2 ]} يُعرف تعميمه باسم تصميم t .

يُقال إن التصميم متوازن (حتى t ) إذا ظهرت جميع المجموعات الفرعية t من المجموعة الأصلية في عدد متساوٍ من الكتل (أي λ ) . عندما لا تُحدد قيمة t ، يُفترض عادةً أنها  2، مما يعني أن كل زوج من العناصر موجود في نفس عدد الكتل، ويكون التصميم متوازنًا ثنائيًا . أما عندما t  =  1، فيظهر كل عنصر في نفس عدد الكتل ( عدد التكرار ، ويُرمز له بـ r )، ويُقال إن التصميم منتظم . يُسمى تصميم الكتل الذي تكون فيه جميع الكتل متساوية الحجم (ويُرمز لها عادةً بـ k ) تصميمًا منتظمًا أو مناسبًا . جميع التصاميم التي نُوقشت في هذه المقالة منتظمة. كما دُرست تصاميم الكتل التي ليست منتظمة بالضرورة؛ وعندما t  =  2، تُعرف في الأدبيات باسم التصاميم المتوازنة ثنائيًا (PBDs). أي تصميم موحد متوازن حتى قيمة t يكون متوازنًا أيضًا في جميع القيم الأدنى لـ t (وإن كانت بقيم λ مختلفة )، فعلى سبيل المثال، يكون التصميم المتوازن ثنائيًا ( t  =  2) منتظمًا أيضًا ( t  =  1). عندما لا يتحقق شرط التوازن، قد يظل التصميم متوازنًا جزئيًا إذا أمكن تقسيم المجموعات الفرعية t إلى n فئة، لكل منها قيمة λ خاصة بها (مختلفة) . بالنسبة لـ t  =  2، تُعرف هذه التصاميم باسم PBIBD( n ) ، وتشكل فئاتها مخطط ارتباط .

عادة ما يقال (أو يفترض) أن التصاميم غير مكتملة ، مما يعني أن مجموعة الكتل ليست كل المجموعات الفرعية الممكنة من النوع k ، وبالتالي استبعاد التصميم التافه.

قد تحتوي تصميمات الكتل على كتل متكررة أو لا. وتسمى التصميمات التي لا تحتوي على كتل متكررة بالتصميمات البسيطة ، ^{[ 3 ]} وفي هذه الحالة تكون "عائلة" الكتل مجموعة وليست مجموعة متعددة .

في الإحصاء ، يمكن توسيع مفهوم تصميم الكتل ليشمل تصميمات الكتل غير الثنائية ، حيث قد تحتوي الكتل على نسخ متعددة من العنصر (انظر: التجميع (الإحصاء) ). يُطلق على التصميم الذي يظهر فيه كل عنصر نفس العدد الإجمالي من المرات اسم "متساوي التكرار"، مما يعني أنه تصميم منتظم فقط عندما يكون التصميم ثنائيًا أيضًا. تُدرج مصفوفة التكرار لتصميم غير ثنائي عدد مرات تكرار كل عنصر في كل كتلة.

يُعرف أبسط أنواع التصميم "المتوازن" ( t = 1) بالتكوين التكتيكي أو التصميم الأحادي . ويُعرف هيكل التداخل المقابل في الهندسة ببساطة بالتكوين ، انظر التكوين (الهندسة) . يتميز هذا التصميم بالانتظام والانتظام: تحتوي كل كتلة على k عنصرًا، ويحتوي كل عنصر على r كتلة. يرتبط عدد عناصر المجموعة v وعدد الكتل b بالعلاقة التالية:${\displaystyle bk=vr}$، وهو العدد الإجمالي لتكرارات العنصر.

كل مصفوفة ثنائية ذات مجموع ثابت للصفوف والأعمدة هي مصفوفة وقوع لتصميم كتلي منتظم موحد. كما أن لكل تكوين رسمًا بيانيًا ثنائي الأجزاء منتظمًا يُعرف باسم رسم بياني الوقوع أو رسم بياني ليفي .

بفرض وجود مجموعة منتهية X (تتكون عناصرها من نقاط ) وأعداد صحيحة k و r و λ ≥ 1، نُعرّف التصميم الثنائي (أو BIBD ، اختصارًا لتصميم الكتل غير الكاملة المتوازنة) B بأنه عائلة من المجموعات الجزئية المكونة من k عنصرًا من X ، تُسمى كتلًا ، بحيث يكون أي عنصر x في X موجودًا في r كتلة، وأي زوج من النقاط المختلفة x و y في X موجودًا في λ كتلة. هنا، يُعد شرط احتواء أي عنصر x في X في r كتلة شرطًا زائدًا، كما هو موضح أدناه.

هنا ، v (عدد عناصر X ، وتُسمى النقاط)، وb (عدد الكتل)، و k ، وr ، وλ هي معلمات التصميم. (ولتجنب الأمثلة الشاذة، يُفترض أيضًا أن v > k ، بحيث لا تحتوي أي كتلة على جميع عناصر المجموعة. وهذا هو معنى كلمة "غير مكتمل" في اسم هذه التصاميم). في جدول:

v	النقاط، عدد عناصر X
ب	عدد الكتل
ر	عدد الكتل التي تحتوي على نقطة معينة
ك	عدد النقاط في المربع
λ	عدد الكتل التي تحتوي على أي نقطتين (أو بشكل أعم t ) مختلفتين

يُطلق على هذا التصميم اسم تصميم ( v , k , λ ) أو تصميم ( v , b , r , k , λ ). ليست جميع المعاملات مستقلة؛ إذ تحدد v و k و λ قيمتي b و r ، وليست كل التوليفات الممكنة لـ v و k و λ ممكنة. المعادلتان الأساسيتان اللتان تربطان هذه المعاملات هما:

${\displaystyle bk=vr,}$

يتم الحصول عليها عن طريق حساب عدد الأزواج ( B ، p ) حيث B عبارة عن كتلة و p عبارة عن نقطة في تلك الكتلة، و

${\displaystyle \lambda (v-1)=r(k-1),}$

تم الحصول على هذه النتيجة من خلال حساب الثلاثيات ( x , y , B ) عند قيمة ثابتة لـ x، حيث x و y نقطتان مختلفتان و B كتلة تحتوي عليهما. تثبت هذه المعادلة، لكل قيمة لـ x، أن r ثابت (مستقل عن x ) حتى دون افتراض ذلك صراحةً، مما يثبت أن شرط احتواء أي x في X ضمن r كتلة هو شرط زائد، ويمكن حساب r من المعاملات الأخرى.

يجب أن تكون قيمتا b و r الناتجتان أعدادًا صحيحة، مما يفرض شروطًا على v و k و λ . هذه الشروط غير كافية، فعلى سبيل المثال، لا يوجد تصميم (43,7,1). ^{[ 4 ]}

يُعرَّف ترتيب التصميم الثنائي بأنه n = r − λ . ويُحصل على متمم التصميم الثنائي باستبدال كل كتلة بمتممها في مجموعة النقاط X. وهو أيضًا تصميم ثنائي، وله المعاملات التالية: v′ = v، b′ = b، r ′ = b − r ، k ′ = v − k ، λ ′ = λ + b − 2r . للتصميم الثنائي ومتممه نفس الترتيب .          

تنص نظرية أساسية، وهي متباينة فيشر ، التي سميت على اسم الإحصائي رونالد فيشر ، على أن b  ≥ v في أي تصميم ثنائي. 

من النتائج التوافقية المفاجئة وغير البديهية (لكنها عامة جدًا) لهذه التصاميم، أنه إذا رُمز للنقاط بأي مجموعة مختارة عشوائيًا من الأرقام المتساوية أو غير المتساوية التباعد، فلا يوجد اختيار لمجموعة كهذه تجعل جميع مجاميع الكتل (أي مجموع جميع النقاط في كتلة معينة) ثابتة. ^{[ 5 ] [ 6 ]} مع ذلك، قد يكون هذا ممكنًا في تصاميم أخرى، مثل تصاميم الكتل غير الكاملة المتوازنة جزئيًا. وقد نوقشت العديد من هذه الحالات في ^{[ 7 ]} . لكن يمكن ملاحظة ذلك بسهولة أيضًا في المربعات السحرية أو المستطيلات السحرية، التي يمكن اعتبارها تصاميم كتل غير كاملة متوازنة جزئيًا.

تُسمى حالة التساوي في متباينة فيشر، أي التصميم الثنائي الذي يحتوي على عدد متساوٍ من النقاط والمربعات، بالتصميم المتناظر . ^{[ 9 ]} تتميز التصاميم المتناظرة بأقل عدد من المربعات بين جميع التصاميم الثنائية التي تحتوي على نفس عدد النقاط.

في التصميم المتناظر، يتحقق الشرط r = k وكذلك b = v ، وبينما لا يصح هذا الشرط عمومًا في التصاميم الثنائية العشوائية، فإنه في التصميم المتناظر، تلتقي كل كتلتين مختلفتين في λ نقطة. ^{[ 10 ]} تنص نظرية رايزر على عكس ذلك. إذا كانت X مجموعة مكونة من v عنصرًا، و B مجموعة مكونة من v عنصرًا من مجموعات فرعية مكونة من k عنصرًا (الكتل)، بحيث تشترك أي كتلتين مختلفتين في λ نقطة بالضبط، فإن ( X, B ) هو تصميم كتل متناظر. ^{[ 11 ]}

تُحقق معايير التصميم المتناظر

${\displaystyle \lambda (v-1)=k(k-1).}$

يفرض هذا قيودًا صارمة على v ، لذا فإن عدد النقاط ليس عشوائيًا على الإطلاق. تُقدّم نظرية بروك-رايزر-تشاولا شروطًا ضرورية، ولكنها غير كافية، لوجود تصميم متناظر بدلالة هذه المعايير.

فيما يلي أمثلة مهمة على التصاميم المتناظرة من الدرجة الثانية:

التصميم القابل للحل من الرتبة 2 هو تصميم ثنائي الأبعاد يمكن تقسيم كتله إلى مجموعات (تسمى الفئات المتوازية )، تشكل كل منها تجزئة لمجموعة نقاط التصميم الثنائي الأبعاد. وتُسمى مجموعة الفئات المتوازية حلاً للتصميم.

إذا كان التصميم القابل للحل 2-( v , k ,λ) يحتوي على c فئات متوازية، فإن b  ≥ v + c − 1. ^{[ 20 ]}     

وبالتالي، لا يمكن أن يكون للتصميم المتناظر حل غير تافه (أكثر من فئة متوازية واحدة). ^{[ 21 ]}

تُعدّ المستويات الأفينية المحدودة من النماذج النموذجية للتصاميم القابلة للحل من الرتبة 2. ويُعتبر حل مسألة التلميذات الخمس عشرة الشهيرة حلاً لتصميم 2-(15، 3، 1). ^{[ 22 ]}

بفرض أي عدد صحيح موجب t ، فإن التصميم t - B هو فئة من المجموعات الجزئية المكونة من k عنصرًا من X ، تُسمى الكتل ، بحيث يظهر كل عنصر x في X في r كتلة بالضبط، وتظهر كل مجموعة جزئية T مكونة من t عنصرًا في λ كتلة بالضبط. الأعداد v (عدد عناصر X )، وb (عدد الكتل)، و k ، و r ، وλ، و t هي معلمات التصميم. يُطلق على هذا التصميم اسم تصميم t- ( v , k , λ). مرة أخرى، تحدد هذه الأعداد الأربعة b و r ، ولا يمكن اختيارها بشكل عشوائي. المعادلات هي

${\displaystyle \lambda _{i}=\lambda \left.{\binom {v-i}{t-i}}\right/{\binom {k-i}{t-i}}{\text{ for }}i=0,1,\ldots ,t,}$

حيث λ _i هو عدد الكتل التي تحتوي على أي مجموعة من النقاط المكونة من i عنصر و λ _t = λ.

لاحظ أن${\displaystyle b=\lambda _{0}=\lambda {v \choose t}/{k \choose t}}$و${\displaystyle r=\lambda _{1}=\lambda {v-1 \choose t-1}/{k-1 \choose t-1}}$.

النظرية : ^{[ 23 ]} أي تصميم t- ( v , k , λ) هو أيضًا تصميم s- ( v , k , λs ₎ لأي قيمة s حيث 1  ≤ s ≤ t . (لاحظ أن "قيمة لامدا" تتغير كما سبق وتعتمد على s ).   

ومن نتائج هذه النظرية أن كل تصميم t مع t ≥ 2 هو أيضًا تصميم 2.

يُطلق على تصميم t - ( v , k ,1) اسم نظام شتاينر .

يشير مصطلح تصميم الكتلة في حد ذاته عادةً إلى تصميم ثنائي.

يتألف مخطط الارتباط من n فئة من مجموعة X بحجم v بالإضافة إلى تقسيم S للمجموعة X × X إلى n + 1 علاقة ثنائية ، R0 _، R1 _، ...، Rn _. يُقال إن زوجًا من العناصر في العلاقة Ri _مرتبط من الرتبة i . كل عنصر من X له n _من الشركاء من الرتبة i . علاوة على ذلك: 

• ${\displaystyle R_{0}=\{(x,x):x\in X\}}$وتسمى علاقة الهوية .
• تعريف${\displaystyle R^{*}:=\{(x,y)\mid (y,x)\in R\}}$إذا كان R في S ، فإن R* في S
• لو${\displaystyle (x,y)\in R_{k}}$عدد${\displaystyle z\in X}$بحيث${\displaystyle (x,z)\in R_{i}}$و${\displaystyle (z,y)\in R_{j}}$ثابت${\displaystyle p_{ij}^{k}}$يعتمد ذلك على i و j و k ولكن ليس على الاختيار المحدد لـ x و y .

يكون مخطط الارتباط تبادليًا إذا${\displaystyle p_{ij}^{k}=p_{ji}^{k}}$لجميع قيم i و j و k . يفترض معظم المؤلفين هذه الخاصية.

تصميم الكتلة غير المكتمل المتوازن جزئيًا مع n فئة مرتبطة (PBIBD( n )) هو تصميم كتلة يعتمد على مجموعة v X مع b كتلة كل منها بحجم k ومع ظهور كل عنصر في r كتلة، بحيث يكون هناك مخطط ارتباط مع n فئة معرف على X حيث إذا كان العنصران x و y مرتبطين i ، 1 ≤ i ≤ n ، فإنهما يكونان معًا في λ _i كتلة بالضبط.

تحدد PBIBD( n ) مخطط ارتباط، لكن العكس غير صحيح. ^{[ 29 ]}

مثال

ليكن A (3) مخطط الارتباط التالي بثلاث فئات ارتباط على المجموعة X = {1,2,3,4,5,6}. المدخل ( i , j ) هو s إذا كان العنصران i و j في علاقة R _s .

	1	2	3	4	5	6
1	0	1	1	2	3	3
2	1	0	1	3	2	3
3	1	1	0	3	3	2
4	2	3	3	0	1	1
5	3	2	3	1	0	1
6	3	3	2	1	1	0

تتكون كتل PBIBD(3) المستندة إلى A (3) مما يلي:

124	134	235	456
125	136	236	456

معاملات نموذج PBIBD(3) هي: v  =  6، b  =  8، k  =  3، r  = 4 ،  وλ₁ ₌  λ₂  = 2 _، و λ₃ ₌ 1. كذلك، بالنسبة لخطة الارتباط _، لدينا n₀ = _n₂ = 1 و n₁ = _n₃ = _2. ^{[ 30 ]} مصفوفة الحدوث M هي            

${\displaystyle {\begin{pmatrix}1&1&1&1&0&0&0&0\\1&1&0&0&1&1&0&0\\0&0&1&1&1&1&0&0\\1&0&1&0&0&0&1&1\\0&1&0&0&1&0&1&1\\0&0&0&1&0&1&1&1\end{pmatrix}}}$

ومصفوفة التوافق MM ^T هي

${\displaystyle {\begin{pmatrix}4&2&2&2&1&1\\2&4&2&1&2&1\\2&2&4&1&1&2\\2&1&1&4&2&2\\1&2&1&2&4&2\\1&1&2&2&2&4\\\end{pmatrix}}}$

ومنها يمكننا استعادة قيمتي λ و r .

نشأ موضوع تصميم القطاعات في الإطار الإحصائي لتصميم التجارب . وقد كانت هذه التصاميم مفيدة بشكل خاص في تطبيقات تقنية تحليل التباين (ANOVA) . ولا يزال هذا مجالًا مهمًا لاستخدام تصميم القطاعات.

في حين أن أصول الموضوع تستند إلى التطبيقات البيولوجية (كما هو الحال مع بعض المصطلحات الموجودة)، فإن التصاميم تستخدم في العديد من التطبيقات التي يتم فيها إجراء مقارنات منهجية، كما هو الحال في اختبار البرمجيات .

توفر مصفوفة وقوع تصميمات الكتل مصدراً طبيعياً لرموز الكتل المثيرة للاهتمام والتي تُستخدم كرموز تصحيح الأخطاء . كما تُستخدم صفوف مصفوفات وقوعها كرموز في شكل من أشكال تعديل موضع النبضة . ^{[ 36 ]}

• هندسة السقوط
• نظام شتاينر
• تصميم العامل الجزئي

• أشباخر، مايكل (1971). "حول مجموعات التوازي لتصميمات الكتل المتناظرة" . مجلة نظرية التوافيق . السلسلة أ. 11 (3): 272-281 . doi : 10.1016/0097-3165(71)90054-9 .
• أسماس، إي إف؛ كي، جيه دي (1992)، التصاميم ورموزها ، كامبريدج: مطبعة جامعة كامبريدج، رقم ISBN 0-521-41361-3
• بيث، توماس؛ يونغنيكل، ديتر ؛ لينز، هانفريد (1986)، نظرية التصميم ، مطبعة جامعة كامبريدجالطبعة الثانية (1999) ISBN 978-0-521-44432-3.
• بوز، آر سي (1949)، "ملاحظة حول متباينة فيشر لتصميمات الكتل غير الكاملة المتوازنة"، حوليات الإحصاء الرياضي ، 20 (4): 619-620 ، doi : 10.1214/aoms/1177729958
• بوز، ر.  س .؛ شيماموتو، ت. (1952)، "تصنيف وتحليل تصميمات القطاعات غير الكاملة المتوازنة جزئيًا مع فئتين مرتبطتين"، مجلة الجمعية الإحصائية الأمريكية ، 47 (258): 151-184 ، doi : 10.1080/01621459.1952.10501161
• كاميرون، بي جيه؛ فان لينت، جيه إتش (1991)، التصاميم، والرسوم البيانية، والرموز، وروابطها ، مطبعة جامعة كامبريدج، رقم ISBN 0-521-42385-6
• كولبورن، تشارلز جيه؛ دينيتز، جيفري إتش (2007)، دليل التصاميم التوافقية (  الطبعة الثانية)، بوكا راتون: تشابمان آند هول/ سي آر سي، رقم ISBN 978-1-58488-506-1
• فيشر، ر. أ. (1940)، "دراسة للحلول المختلفة الممكنة لمشكلة في كتل غير مكتملة"، حوليات علم تحسين النسل ، 10 : 52-75 ، doi : 10.1111/j.1469-1809.1940.tb02237.x ، hdl : 2440/15239
• هول، مارشال الابن (1986)، نظرية التوافيق (  الطبعة الثانية)، نيويورك: وايلي-إنترساينس، رقم ISBN 0-471-09138-3
• هيوز، د. ر.؛ بايبر، إ. س. (1985)، نظرية التصميم ، كامبريدج: مطبعة جامعة كامبريدج، رقم ISBN 0-521-25754-9
• كاسكي، بيتري؛ أوسترجارد، باتريك (2008). "يوجد خمسة طائرات ثنائية السطح بالضبط حيث k = 11". مجلة التصاميم التوافقية . 16 (2): 117-127 . doi : 10.1002/jcd.20145 . MR 2384014. S2CID 120721016 .  
• لاندر، إي إس (1983)، التصاميم المتناظرة: منهج جبري ، مطبعة جامعة كامبريدج، رقم ISBN 978-0-521-28693-0
• ليندنر، سي سي؛ رودجر، سي إيه (1997)، نظرية التصميم ، بوكا راتون: مطبعة سي آر سي، رقم ISBN 0-8493-3986-3
• راغافاراو، داماراجو (1988). الإنشاءات والمسائل التوافقية في تصميم التجارب . دوفر. ISBN 978-0-486-65685-4.
• راغافاراو، داماراجو ؛ بادجيت، إل في (11 أكتوبر 2005). تصميمات الكتل: التحليل، والتوافقية، والتطبيقات . وورلد ساينتيفيك. ISBN 978-981-4480-23-9.
• رايزر، هربرت جون (1963)، "8. التصاميم التوافقية" ، الرياضيات التوافقية ، سلسلة كاروس للدراسات الرياضية، المجلد  14، الجمعية الرياضية الأمريكية، الصفحات 96-130 ، ISBN  978-1-61444-014-7{{citation}}عدم توافق رقم ISBN / التاريخ ( مساعدة )
• سالواش، تشيستر جيه؛ ميزاروبا، جوزيف أ. (1978). "الطائرات ثنائية السطح الأربعة ذات k = 9" . مجلة نظرية التوافيق . السلسلة أ. 24 (2): 141-145 . doi : 10.1016/0097-3165(78)90002-X .
• خاتري، رافيندرا (2019). "ملاحظة حول عدم وجود تصميمات الكتل غير الكاملة المتوازنة ذات مجموع الكتل الثابت". الاتصالات في الإحصاء - النظرية والأساليب . 48 (20): 5165-5168 . doi : 10.1080/03610926.2018.1508715 . S2CID 125795689 . 
• خاتري، رافيندرا (2022). "حول بناء تصاميم مجموع الكتل الثابتة المتساوية التكرار". الاتصالات في الإحصاء - النظرية والأساليب . 51 (2): 4434-4450 . doi : 10.1080/03610926.2020.1814816 . S2CID 225335042 . 
• شريكاندي، إس إس ؛ بهات-ناياك، فاسانتي ن. (1970)، "حلول غير متماثلة لبعض تصميمات الكتل غير الكاملة المتوازنة I"، مجلة نظرية التوافيق ، 9 (2): 174-191 ، doi : 10.1016/S0021-9800(70)80024-2
• ستينسون، دوغلاس ر. (2003)، التصاميم التوافقية: الإنشاءات والتحليل ، سبرينغر، ISBN 0-387-95487-2
• ستريت، آن بينفولد وستريت ، ديبورا جيه. (1987). توافيق التصميم التجريبي . مطبعة جامعة أكسفورد [كلارندون]. ISBN 0-19-853256-3.
• فان لينت، جيه إتش؛ ويلسون، آر إم (1992). دورة في التوافقية . مطبعة جامعة كامبريدج. ISBN 978-0-521-41057-1.

• DesignTheory.Org : قواعد بيانات لتصميمات الكتل التوافقية والإحصائية والتجريبية. برامج وموارد أخرى تستضيفها كلية العلوم الرياضية في جامعة كوين ماري، جامعة لندن.
• مصادر نظرية التصميم : صفحة بيتر كاميرون لموارد نظرية التصميم على الإنترنت.
• وايسستين، إريك دبليو. “تصاميم الكتل” . عالم الرياضيات .