Русская Википедия:Блок-дизайн

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Блок-схема — это множество вместе с семейством подмножеств (повторение подмножеств разрешено в некоторых случаях), члены которого удовлетворяют некоторым свойствам, которые считаются полезными для конкретного приложения. Эти приложения приходят из разных областей, включая планирование эксперимента, конечную геометрию, тестирование программного обеспечения, криптографию и алгебраическую геометрию. Рассматривалось много вариантов, но наиболее интенсивно изучались сбалансированные неполные блок-схемы (Balanced Incomplete Block Designs, BIBD, 2-схемы), которые исторически были связаны со статистическими задачами при планировании экспериментаШаблон:SfnШаблон:Sfn.

Блок-схема, в которой все блоки имеют один размер, называется однородной. Схемы, обсуждаемые в этой статье, все однородны. Попарно сбалансированные схемы (Pairwise balanced designs, PBD) являются примерами блок-схем, которые не обязательно однородны.

Определение BIBD (или 2-схемы)

Если задано конечное множество X (элементов, которые называются точками) и целые числа k, r, λ ≥ 1, мы определяем 2-схему B как семейство k-элементных подмножеств множества X, называемых блоками, таких, что любой элемент x из X содержится в r блоках, и любая пара различных точек x и y в X содержится в λ блоках.

Слово «семейство» в определении выше может быть заменено словом «множество», если повторение блоков не разрешено. Схемы, в которых повторение блоков не позволяется, называются простыми.

Здесь v (число элементов X, называемых точками), b (число блоков), k, r и λ являются параметрами схемы. (Чтобы избежать вырожденных примеров, предполагается, что v > k, так что никакой блок не содержит все элементы множества. Поэтому в названии схем присутствует слово «неполные».) В таблице:

v	точки, число элементов X
b	число блоков
r	число блоков, содержащих данную точку
k	число точек в блоке
λ	число блоков, содержащих любые 2 (или, более обще, t) точек

Схема называется (v, k, λ)-схемой или (v, b, r, k, λ)-схемой. Параметры не являются независимыми — v, k и λ определяют b и r, и не все комбинации v, k и λ допустимы. Два основных равенства, содержащих эти параметры

<math> bk = vr, </math>

получается путём подсчёта пар (B, p), где B — блок, а p — точка в этом блоке

<math> \lambda(v-1) = r(k-1), </math>

получается путём подсчёта троек (p, q, B), где p и q — различные точки, и B — блок, содержащий обе точки, и делением числа троек на v.

Эти условия не достаточны, так как, например, (43,7,1)-схемы не существует

Порядок 2-схемы определяется как n = r − λ. Дополнение 2-схемы получается путём замены каждого блока его дополнением в множестве точек X. Дополнение является также 2-схемой и имеет параметры v′ = v, b′ = b, r′ = b − r, k′ = v − k, λ′ = λ + b − 2r. 2-Схема и её дополнение имеют один порядок.

Фундамендальная теорема, неравенство Фишера, названное именем статистика Рональда Фишера, утверждает, что b ≥ v в любой 2-схеме.

В терминах теории графов определение 2-схемы можно переформулировать так: блок-схема — это покрытие с кратностью <math>\lambda</math> полного графа на <math>v</math> вершинах полными графами на <math>k</math> вершинах. Блок-схемы при <math>k=0,1</math> и <math>v</math> тривиальны, поэтому обычно предполагается, что <math>2\le k\le n-1</math>.

Примеры

Единственная (6,3,2)-схема имеет 10 блоков (b = 10) и каждый элемент повторяется 5 раз (r = 5)Шаблон:Sfn. Если использовать символы 0 − 5, блоки содержат следующие тройки:

012    013    024    035    045    125    134    145    234    235.

Одна из четырёх неизоморфных (8,4,3)-схем имеет 14 блоков, в которых элементы повторяются 7 раз. Если использовать символы 0 – 7, блоками являются следующие четвёрки: Шаблон:Sfn

0123    0124    0156    0257    0345    0367    0467    1267    1346    1357    1457    2347    2356    2456.

Единственная (7,3,1)-схема имеет 7 блоков, в которых каждый элемент повторён 3 раза. Если использовать символы 0 − 6, блоками служат следующие тройки: Шаблон:Sfn

013    026    045    124    156    235    346. Если элементы понимаются как точки на плоскости Фано, то эти блоки являются прямыми.

Симметричные BIBD

Случай равенства в неравенстве Фишера, то есть 2-схема с одинаковым числом точек в блоках, называется симметричной схемой. Симметричные схемы имеют наименьшее число блоков среди всех 2-схем с тем же числом точек.

В симметричной схеме выполняется r = k, как и b = v, и, хотя это неверно для произвольных 2-схем, в симметричных схемах любые два различных блока имеют общими λ точекШаблон:Sfn. Теорема Шаблон:Не переведено 5 даёт обратный вывод — если X является множеством из v элементов, а B является набором из v k-элементных подмножеств («блоков»), таких, что любые два различных блока имеют в точности λ общих точек, то (X, B) является симметричной блок-схемойШаблон:Sfn.

Параметры симметричной схемы удовлетворяют равенству

<math> \lambda (v-1) = k(k-1). </math>

Равенство накладывает сильное ограничение на v, так что число точек далеко от произвольного. Теорема Брука — Райзера — Човла даёт необходимое, но не достаточное условие существования симметричных схем в терминах их параметров.

Ниже приведены важные примеры симметричных 2-схем:

Проективные плоскости

Конечные проективные плоскости являются симметричными 2-схемами с λ = 1 и порядком n > 1. Для этих схем равенство симметричной схемы превращается в:

<math>v-1 = k(k-1).\,</math>

Поскольку k = r, мы можем записать порядок проективной плоскости как n = k − 1 и, из приведённого выше равенства, мы получаем v = (n + 1)n  +  1 = n²  +  n  +  1 точек в проективной плоскости порядка n.

Так как проективная плоскость является симметричной схемой, мы имеем b = v, что означает, что b = n²  +  n  +  1 также. Число b является числом прямых проективной плоскости. Не может быть повторяющихся прямых, поскольку λ = 1, так что проективная плоскость является простой 2-схемой, в которой число прямых и число точек всегда равны. Для проективной плоскости k является числом точек на прямой и оно равно n + 1. Аналогично, r = n + 1 является числом прямых, с которыми данная точка инцидента.

Для n = 2 мы имеем проективную плоскость порядка 2, которая называется также плоскостью Фано, с v = 4 + 2 + 1 = 7 точками и 7 прямыми. На плоскости Фано любая прямая имеет в точности n + 1 = 3 точек и каждая точка принадлежит n + 1 = 3 прямым.

Известно, что проективные плоскости существуют для всех порядков, равных простым числам и их степеням. Они образуют единственное известное бесконечное семейство симметричных блочных схемШаблон:Sfn.

Бипланарная геометрия

Бипланарная геометрия — это симметричная 2-схема с λ = 2. То есть любое множество из двух точек содержится в двух блоках («прямых»), а любые две прямые пересекаются в двух точкахШаблон:Sfn. Бипланарные геометрии аналогичны проективным плоскостям, за исключением того, что две точки не определяют прямую (а две прямые не определяют точку). В бипланарной геометрии две точки определяют две прямых (соответственно, две прямые определяют две точки). Бипланарная геометрия порядка n — это схема, блоки которой имеют k = n + 2 точек, Всего же точек v = 1 + (n + 2)(n + 1)/2 (поскольку r = k).

18 известных примеровШаблон:Sfn перечислены ниже.

• (Тривиальная схема) Бипланарная геометрия порядка 0 имеет 2 точки (и прямые размера 2; 2-(2,2,2) схема); это две точки и два блока, которые содержат обе точки. Геометрически это двуугольник.
• Бипланарная геометрия порядка 1 имеет 4 точки (и прямые размера 3; 2-(4,3,2) схема); это полная схема с v = 4 и k = 3. Геометрически точки являются вершинами, а блоки являются гранями тетраэдра.
• Бипланарная геометрия порядка 2 является дополнением плоскости Фано — она содержит 7 точек (и прямые размера 4; 2-(7,4,2)) схема, где прямые задаются как дополнения (3-точечных) прямых плоскости ФаноШаблон:Sfn.
• Бипланарная геометрия порядка 3 имеет 11 точек (и прямые размера 5; 2-(11,5,2)) схема, которая известна как бипланарная геометрия Пэли по имени Шаблон:Не переведено 5; Схема связана с графом Пэли порядка 11, который строится с помощью поля с 11 элементами, и является 2-схемой Адамара, связанной с матрицей Адамара размера 12, см. статью «Построение Пэли I».

Алгебраически это соответствует особому вложению проективной специальной линейной группы PSL(2,5) в PSL(2,11) – для детального описания см. проективная линейная группа: действие на p точекШаблон:Sfn.

• Имеется три бипланарных геометрии порядка 4 (16 точек, прямые размера 6; 2-(16,6,2)) схемы. Эти три схемы являются также схемами Менона.
• Имеется четыре бипланарных геометрии порядка 7 (37 точек, прямые размера 9; 2-(37,9,2) схемы)Шаблон:Sfn
• Имеется пять бипланарных геометрий порядка 9 (56 точек, прямые размера 11; 2-(56,11,2) схемы)Шаблон:Sfn
• Известны две бипланарные геометрии порядка 11 (79 точек, прямые размера 13; 2-(79,13,2) схемы)Шаблон:Sfn.

2-схемы Адамара

Матрица Адамара размера m — это m × m матрица H, элементы которой равны ±1, такая, что HH^⊤  = mE_m, где H^⊤ равна транспонированной матрице H, а E_m — m × m единичная матрица. Матрицу Адамара можно представить в стандартной форме (то есть привести к эквивалентной матрице Адамара), в которой первая строка и первый столбец состоят из +1. Если размер m > 2, m должен делиться на 4.

Если дана матрица Адамара размера 4a в стандратной форме, удалим первую строку и первый столбец и заменим все элементы −1 на 0. В результате получим матрицу M, состоящую из 0 и 1, которая является матрицей инцидентности симметричной 2-(4a − 1, 2a − 1, a − 1) схемы. Эта схема называется 2-схемой АдамараШаблон:Sfn. Схема содержит <math>4a-1</math> блоков, каждый из которых содержит <math>2a-1</math> точек, и <math>4a-1</math> точек, которые содержатся в <math>2a-1</math> блоках. Каждая пара точек содержится точно в <math>a-1</math> блоках.

Построение обратимо, и матрица инцидентности симметричной 2-схемы с этими параметрами может быть использовано для формирования матрицы Адамара размера 4a.

Разрешимые 2-схемы

Разрешимая 2-схема — это BIBD, блоки которого могут быть разбиты на множества (называемые параллельными классами), каждое из которых образует раздел разбиения точек из BIBD. Множество параллельных классов называется разрешением схемы.

Если 2-(v,k,λ) разрешимая схема имеет c параллельных классов, то b  ≥ v + c − 1Шаблон:Sfn.

Следовательно, симметричная схема не может иметь нетривиальное (более одного параллельного класса) разрешениеШаблон:Sfn.

Архетипичные разрешимые 2-схемы — это конечные проективные плоскости. Решение знаменитой задачи Киркмана о школьницах является разрешением 2-(15,3,1) схемыШаблон:Sfn.

Обобщения: t-схемы

Если дано любое положительное число t, t-схема B — это класс k-элементных подмножеств множества X, называемых блоками, таких, что любая точка x из X появляется точно в r блоках, а любое t-элементное подмножество T содержится ровно в λ блоках. Числа v (число элементов в X), b (число блоков), k, r, λ и t служат параметрами схемы. Схему можно назвать t-(v,k,λ)-схемой. Снова эти четыре числа определяют b и r, а сами четыре числа нельзя выбрать произвольно. Связывающие их равенства

<math> \lambda_i = \lambda \left.\binom{v-i}{t-i} \right/ \binom{k-i}{t-i} \text{ for } i=0,1,\ldots,t, </math>,

где λ_i — число блоков, которые содержат любое i-элементное множество точек.

Заметим, что <math>b = \lambda_0 = \lambda {v\choose t} / {k\choose t}</math>.

Теорема:Шаблон:Sfn Любая t-(v,k,λ)-схема является также s-(v,k,λ_s)-схемой для любого числа s при условии 1 ≤ s ≤ t. (Заметим, что «значение лямбда» меняется, как выше указано, и зависит от s.)

Следствие этой теоремы — любая t-схема с t ≥ 2 является также 2-схемой.

Схема t-(v,k,1) называется системой Штейнера.

Сам по себе термин блок-схема обычно подразумевает 2-схему.

Производные и расширяемые t-схемы

Пусть D = (X, B) является t-(v,k,λ) схемой и пусть p — точка множества X. Производная схема D_p имеет множество точек X − {p}, а в качестве множества блоков все блоки D, которые содержат p и в которых точка p удалена. Эта схема является (t − 1)-(v − 1, k − 1, λ) схемой. Заметим, что порождённые схемы для различных точек могут не быть изоморфными. Схема E называется расширением схемы D, если E имеет точку p, такую, что E_p изоморфна D. Мы называем D расширяемым, если схема имеет расширение.

Теорема:Шаблон:Sfn Если t-(v,k,λ) схема имеет расширение, то k + 1 делит b(v + 1).

Расширяемые проективные плоскости (симметричные 2-(n² + n + 1, n + 1, 1) схемы) — это только те, порядки которых равны 2 и 4Шаблон:Sfn.

Любая 2-схема Адамара расширяема (до 3-схемы Адамара)Шаблон:Sfn.

Теорема:Шаблон:Sfn Если D, симметричная 2-(v,k,λ) схема, расширяема, выполняется одно из:

1. D является 2-схемой Адамара,
2. v  =  (λ + 2)(λ² + 4λ + 2), k = λ² + 3λ + 1,
3. v = 495, k = 39, λ = 3.

Заметим, что проективная плоскость порядка два является 2-схемой Адамара. Проективная плоскость порядка четыре имеет параметры, которые подпадают под случай 2. Другие известные симметричные 2-схемы с параметрами из случая 2 — бипланарные геометрии порядка 9, но ни одна из них не расширяема. Симметричные 2-схемы с параметрами случая 3 неизвестныШаблон:Sfn.

Круговая плоскость

Схема с параметрами расширения Шаблон:Не переведено 5, то есть 3-(n² + 1, n + 1, 1) схема, называется конечной круговой плоскостью или плоскостью Мёбиуса порядка n.

Можно дать геометрическое описание некоторых круговых плоскостей, более того, всех известных круговых плоскостей. Шаблон:Не переведено 5 в PG(3,q) является множеством из q² + 1 точек, никакие три из которых не коллинеарны. Можно показать, что любая плоскость (которая является гиперплоскостью в размерности 3) в PG(3,q) пересекает овоид O либо в одной, либо в q + 1 точках. Пересечения овоида O размера q + 1 плоскостью — это блоки круговой плоскости порядка q. Любая круговая плоскость, получающаяся таким образом, называется яйцевидной. Все известные круговые плоскости яйцевидны.

Примером овоида служит Шаблон:Не переведено 5, множество нулей квадратичной формы

x₁x₂ + f(x₃, x₄),

где f — неприводимая квадратичная форма от двух переменных над GF(q). [f(x,y)=x² + xy + y², например].

Если q равно нечётной степени 2, известен другой тип овоида — Шаблон:Не переведено 5.

Теорема. Пусть q — положительное целое число, не меньшее 2. (a) Если q нечётно, любой овоид проективно эквивалентен эллиптической квадрике в проективной геометрии PG(3,q), так что q является степенью простого числа и существует единственная яйцеподобная круговая плоскость порядка q (неизвестно при этом, существуют ли не яйцеподобные плоскости.) (b) если q чётно, то q является степенью 2 и любая круговая плоскость порядка q яйцеподобна (возможно, существуют некоторые неизвестные овоиды).

Частично сбалансированные схемы (PBIBD)

n-Класс схемы отношения состоит из множества X размера v вместе с разбиением S множества X × X на n + 1 бинарных отношений R₀, R₁, ..., R_n. Говорят, что пара элементов находятся в отношении R_i (элементы i-сочетаются). Каждый элемент из X имеет n_i i-ых сочетаний. Кроме того:

• <math>R_{0} = \{(x,x):x\in X\}</math> и называется отношением тождества.
• Если определить <math> R^* := \{(x,y)|(y,x)\in R\}</math>, то из принадлежности R разбиению S, следует принадлежность R* разбиению S
• Если <math>(x,y)\in R_{k}</math>, число элементов <math>z\in X</math>, таких что <math>(x,z)\in R_{i}</math> и <math>(z,y)\in R_{j}</math>, постоянно (равно <math>p^k_{ij}</math>) и это число зависит от i, j, k, но не от выбора x и y.

Схема сочетаний коммутативна, если <math>p_{ij}^k = p_{ji}^k</math> для всех i, j и k. Большинство авторов предполагают это свойство.

Частично сбалансированная неполная блочная схема с n классами сочетаний (PBIBD(n)) — это блок-схема, основанная на множестве X с v элементами, имеющая b блоков по k элементов в каждом, в которой каждый элемент появляется в r блоках и для которой существует схема сочетаний с n классами, определёнными на X, при этом, если элементы x и y i-сочетаются для 1 ≤ i ≤ n, то они содержатся вместе точно в λ_i блоках.

PBIBD(n) определяет схему сочетаний, но обратное неверноШаблон:Sfn.

Пример

Пусть 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.Шаблон:Sfn

Свойства

Параметры PBIBD(m) удовлетворяют равенствам:Шаблон:Sfn

1. <math> vr=bk </math>
2. <math> \sum_{i =1}^m n_i = v-1 </math>
3. <math> \sum_{i = 1}^m n_i \lambda_i = r(k-1) </math>
4. <math> \sum_{u = 0}^m p_{ju}^h = n_j </math>
5. <math> n_i p_{jh}^i = n_j p_{ih}^j </math>

PBIBD(1) — это BIBD, PBIBD(2), в которой λ₁  =  λ₂, также является BIBDШаблон:Sfn.

PBIBD с двумя классами сочетаний

Схемы PBIBD(2) изучались больше всего ввиду их простоты и полезности Шаблон:Sfn. Они распадаются на шесть типов , если базироваться на проведённой Бозе и Шимамото классификации известных тогда схем PBIBD(2): Шаблон:SfnШаблон:Sfn

1. разбиваемые на группы
2. треугольные
3. типа «Латинский квадрат»
4. циклические
5. частичная геометрия
6. остальные

Приложения

Математический субъект блок-схем возник как статистическая основа планирования эксперимента. Схемы были особенно полезны в приложениях техники дисперсионного анализа (ANOVA). Эта область остаётся существенной частью использования блочных схем.

Хотя источником были биологические приложения, схемы используются во многих других областях, где осуществляются систематические сравнения, таких как тестирование программного обеспечения.

Матрица инцидентности блок-схемы даёт естественный источник интересных блочных кодов, которые используются как коды, исправляющие ошибки. Строки матрицы инцидентности используются также как символы в фазово-импульсной модуляцииШаблон:Sfn.

Статистические приложения

Предположим, что исследователи рака кожи хотят проверить три различных солнцезащитных крема. Они наносят два различных крема на верхние стороны рук испытуемых. После облучения ультрафиолетом они записывают степень раздражения кожи в терминах солнечного ожога. Число способов лечения — 3 (число кремов), размер блока равен 2 (число рук у человека).

Соответствующая схема BIBD может быть получена как R-функция design.bib пакета R-package agricolae и определяется следующей таблицей:

Опыт	Блок	Лечение
101	1	3
102	1	2
201	2	1
202	2	3
301	3	2
302	3	1

Исследователь выбирает параметры Шаблон:Math, Шаблон:Math и Шаблон:Math для блок-схемы, которые подставляются в R-функцию. Оставшиеся параметры Шаблон:Mvar и Шаблон:Mvar определяются автоматически.

Используя базовые отношения, мы вычисляем, что нам нужно Шаблон:Math блоков, то есть 3 испытуемых, чтобы получить сбалансированную неполную блок-схему. Обозначив блоки Шаблон:Math и Шаблон:Mvar, чтобы не путаться, мы получаем блок-схему,

Шаблон:Math},   Шаблон:Math} и Шаблон:Math}.

Соответствующая матрица инцидентности приведена в таблице:

Лечение	Блок A	Блок B	Блок C
1	0	1	1
2	1	0	1
3	1	1	0

Каждое лечение содержится в 2 блоках, так что Шаблон:Math.

Только один блок (Шаблон:Mvar) содержит лечения 1 и 2 одновременно, и то же самое верно для пар лечений (1,3) и (2,3). Поэтому Шаблон:Math.

Невозможно использовать полную схему (все лечения в каждом блоке) в этом примере, поскольку имеется 3 крема и только по 2 руки у каждого испытуемого.

См. также

• Геометрия инцидентности
• Система Штейнера

Литература

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга

Ссылки

• DesignTheory.Org: Databases of combinatorial, statistical, and experimental block designs. Software and other resources hosted by the School of Mathematical Sciences at Queen Mary College, University of London.
• Design Theory Resources: Peter Cameron's page of web based design theory resources.
• Шаблон:Mathworld