Математическая энциклопедия

БЛОКСХЕМА

- система подмножеств конечного множества, удовлетворяющая нек-рым условиям, связанным с частотой появления пар элементов множества в подмножествах системы. Понятие Б.-с. возникло в теории планирования эксперимента в 20-30-х гг. 20 в., однако под названием тактических конфигураций Б.-с. изучались уже в сер. 19 в. Понятие Б.-с. является вариантом понятий гиперграфа, сети, комплекса. Обычно в Б.-с. на семейства подмножеств накладывается целый ряд дополнительных ограничений. Б.-с. можно задать парой множеств (F, В),где


Элементы множества Vназ. элементами Б.-с., а элементы множестваВ -ее блоками. Элемент гг блок инцидентны, если . Число элементов, инцидентных блоку , обозначается обычно через , а число блоков, инцидентных элементу , - через . Через обозначается число


Числа наз. параметрами Б.-с. Если для всех для всех есть уравновешенная не полная Б.-с., или BIB-схема (от английского balanced incomplete block design) с параметрами Слово "уравновешенный" характеризует одинаковую частоту появлений элементов и пар элементов в блоках, а слово "неполный" служит для указания того, что, вообще говоря, не все k-элементные подмножества входят вВ.

Пусть среди чисел встречается ровно различных: и пусть на элементах множества введено симметричных отношений связанности так, что выполнены следующие условия:

а) множество всех пар элементов множества разбивается на непересекающихся подмножеств причем если то говорят, что элементы -связаны;


причем в силу симметричности Б.-с.со свойствами а) - г) наз. частично уравновешенной Б .-с. с ттипами связей, или PBIB(m)-cхемой (от английского partially balanced incomplete block design). Правило, задающее отношение связанности, наз. схемой связанности. BIB-схема является PBIB (1)-схемой. Примером PBIB (2)-схемы является Б.-с., к-рую можно представить в виде таблицы


где любые два числа из одного столбца 1-связаны, а любые два числа, не принадлежащие одному столбцу, - 2-связаны. Здесь n1=9, n2=2,


Всякой Б.-с. с элементами и bблоками соответствует матрица инцидентности где , если в противном случае, В теории Б.-с. рассматриваются вопросы существования, классификации и вопросы, связанные с построением Б.-с. с заданными параметрами. Параметры Б.-с. связаны определенными соотношениями. Для BIB-схем справедливы равенства:


Для параметров PBIB (m)-схем справедливы равенство (1) и следующие соотношения:


Матрица инцидентности BIB-схемы удовлетворяет основному матричному соотношению


гдеЕ -единичная матрица порядкаv,a J - матрица порядка , составленная сплошь из единиц. Существование (0,1)-матрицы, удовлетворяющей условию (2), является достаточным условием существования BIB-схемы с заданными параметрами. Из (2) вытекает неравенство . BIB-схема, для к-рой (и значит r=k), наз. симметричной Б.-с., или -конфигурацией. Для симметричных BIB-схем справедлива теорема: если существует симметричная BIB-схема с параметрами то: а) при четном есть квадрат, б) при vнечетном уравнение


имеет решение в целых числахх, у, z,не равных одновременно нулю. Условия этой теоремы достаточны для существования рациональной матрицыА,удовлетворяющей (2).

Специальный Круг вопросов, относящихся к существованию BIB-схем, возникает в связи с задачей: даны b блоков; каковы Условия того, чтобы эти блоки можно было дополнить др BIB-схемы? В наиболее общем виде эти условия выражаются как требования положительной определенности нек-рой квадратичной формыQ,а также возможности представить Qв виде суммы квадратов линейных форм с неотрицательными коэффициентами.

Среди BIB-схем различают как наиболее изученные следующие подклассы: системы Штейнера (BIB-схемы с ), в частности системы троек Штейнера (); адамаровы конфигурации ( ), матрица инцидентности к-рых получается изАдамара матрицы;аффинные конечные геометрии и проективные копечные геометрии (см. [1]). В классе PBIB-схем наиболее изучены PBIB (2)-схемы, среди к-рых по виду схемы связанности выделяют так наз. Б.-с. с делимостью на группы, треугольные Б.-с., Б.-с. типа латинского к-в адрата, циклические Б.-с. и т. д. (см. [3]).

Методы построения Б.-с. принято разделять на прямые и рекурсивные. Рекурсивные методы позволяют строить с помощью схем с меньшими значениями параметров схемы с большими значениями параметров. В прямых методах обычно используются свойства конечных полей "или какие-либо геометрические свойства.

Помимо планирования экспериментов, Б.-с. применяются также в теории игр, теории графов и при построении кодов, исправляющих ошибки.

Лит.:[1] Райзер Г. Дж., Комбинаторная математика, пер. с англ., М., 1966; [2] Холл М., Комбинаторика, пер. с англ., М., 1970; 13] Широкова С. А., "Успехи матем. наук", 1968, т. 23, Л? 5, с. 51-98.В. Е. Тараканов.


Синонимы:
схема


  1. блоксхема—блоксхемаfludiagramm...Большой немецко-русский и русско-немецкий словарь
  2. блоксхема—мен. жн. роду...Большой украинско-русский словарь
  3. блоксхема—условное изображение алгоритма решения задачи документооборота последовательности выполнения рабочих операций или процедур с помощью стрелок соединительных линий и геомет...Большой экономический словарь
  4. блоксхема—и ж.i Схема що складаться з окремих елементв блокв.Блоксхема програми графчне зображення перебгу виконання програми за допомогою типово символки....Великий тлумачний словник (ВТС) сучасної української мови
  5. блоксхема—блоксхема block scheme flow chart block diagram Blockschema схема машини приладу апарата пристрою в якй основн вузли блоки що утворюють зображено прямокутниками та нш...Гірничий енциклопедичний словник
  6. блоксхема—статическое или динамическое отображение какихлибо объектов с помощью символов стрелок графов соединительных линий и геометрических фигур текстов....Глобальная экономика. Энциклопедия
  7. блоксхема—Начальная форма Блоксхема единственное число женский род именительный падеж неодушевленное...Морфологический разбор существительных
  8. блоксхема—Блок здесь относится к последовательности событий. Блоксхема графическое или пиктографическое представление такой последовательности. Первоначально использовавшийся в пр...Оксфордский толковый словарь по психологии
  9. блоксхема—Блок здесь относится к последовательности событий. Блоксхема графическое или пиктографическое представление такой последовательности. Первоначально использовавшийся в пр...Оксфордский толковый словарь по психологии
  10. блоксхема—блоксхема блоксхема ы...Орфографический словарь
  11. блоксхема—блоксхема менник жночого роду...Орфографічний словник української мови
  12. блоксхема—diagramme de blocs diagramme de circulation blocdiagramme diagramme densemble diagramme fonctionnel ordinogramme tableau synoptique...Политехнический русско-французский словарь
  13. блоксхема—блоксхема блоксхемы блоксхемы блоксхем блоксхеме блоксхемам блоксхему блоксхемы блоксхемой блоксхемою блоксхемами блоксхеме блоксхемах...Полная акцентуированная парадигма по Зализняку
  14. блоксхема—Орфографическая запись слова блоксхема Ударение в слове блоксхема Деление слова на слоги перенос слова блоксхем Фонетическая транскрипция слова блоксхема [блаксхэм] Хара...Полный фонетический разбор слов
  15. блоксхема—Графический систематизатор показывающий какие действия должны быть осуществлены если выполняются или не выполняются какиелибо предварительные условия....Психология критического мышления
  16. блоксхема—блоксхема ыСинонимы схема...Русский орфографический словарь
  17. блоксхема—ж....Русско-английский автомобильный словарь
  18. блоксхема—flow chart block schematic diagram flow diagram schematic diagram flowchart flowdiagram...Русско-английский машиностроительный словарь
  19. блоксхема—flow chart...Русско-английский морской словарь
  20. блоксхема—flow chart block diagram complete circuit diagram flow diagram skeleton diagram flowchart block scheme flow scheme блоксхема м.uflow chart block [skeleton] diagramсостав...Русско-английский политехнический словарь
  21. блоксхема—flowchart схема...Русско-английский словарь по машиностроению
  22. блоксхема—ж.block diagram flow diagram skeleton diagram flowchart...Русско-английский словарь по физике
  23. блоксхема—программы или алгоритма flow chart block diagram flow diagram flowchart flow sheet sheet...Русско-английский словарь по электронике
  24. блоксхема—block scheme...Русско-английский строительный словарь
  25. блоксхема—ampLTcomput.ampGT block diagram block representation flow chart flowchart skeleton diagram блоксхема программыСинонимы схема...Русско-английский технический словарь
  26. блоксхема—flowchart flow chart logic diagram...Русско-английский толковый словарь терминов по информатике
  27. блоксхема—flow block...Русско-английский экономический словарь
  28. блоксхема—блоксхема...Русско-белорусский математический словарь
  29. блоксхема—блоксхе Синонимы схема...Русско-ивритский словарь
  30. блоксхема—esquema sinptico diagrama sinptico diagrama de bloques составлять блоксхему...Русско-испанский автотранспортный словарь
  31. блоксхема—bloqueesquema прогр. esquema en bloque...Русско-испанский экономический словарь
  32. блоксхема—ж. diagramma m sinottico schema m a blocchi organigramma m...Русско-итальянский политехнический словарь
  33. блоксхема—diagramma a blocchi...Русско-итальянский экономический словарь
  34. блоксхема—жиынслба блок слба...Русско-казахский терминологический словарь «Машиностроение»
  35. блоксхема—blokshma...Русско-латышский словарь
  36. блоксхема—ж.Blockschaltbild nu Blockschaltplan mu bersichtschaltplan mu Strukturdiagramm n схема...Русско-немецкий автомобильный словарь
  37. блоксхема—bersichtsschaltplan...Русско-немецкий автосервисный словарь
  38. блоксхема—Ablaufplan Baugliedplan Bausteinschaltbild Blockplan Blockdiagramm напр. программыem Fludiagramm Prinzipanordnung Prinzipskizze алгоритмаem Strukturdiagramm bersichtsscha...Русско-немецкий политехнический словарь
  39. блоксхема—Baugliedplan Fliediagramm...Русско-немецкий словарь по химии и химической технологии
  40. блоксхема—Baugliedplan Fliediagramm...Русско-немецкий химический словарь
  41. блоксхема—blocdiagramme...Русско-французский словарь по химии
  42. блоксхема—blokov schma blokov zapojen blokov diagram...Русско-чешский словарь
  43. блоксхема—блоксхема блоксхемы схема...Слитно или раздельно? Орфографический словарь-справочник
  44. блоксхема—flowchart Диаграмма представляющая собой последовательность логических шагов необходимых для решения проблемы. Полезный инструмент для программиста который использует его...Словарь бизнес терминов
  45. блоксхема—блоксхема сущ. колво синонимов схема Словарь синонимов ASIS.В.Н. Тришин. . Синонимы схема...Словарь синонимов II
  46. блоксхема—Графическое представление потока информации изображение процесса при котором для обозначения операций данных формируемых отчетов оборудования и т.п. используются условные...Словарь терминов по управленческому учету
  47. блоксхема—блоксхема ж. блок схема схема машини приладу апарата пристрою в якй основн вузли блоки що утворюють зображено прямокутниками та ншими фгурами а звязок мж ними показано ...Словник іншомовних слів
  48. блоксхема—блоксхема вд блок схема схема машини приладу апарата пристрою в якй основн вузли блоки що утворюють зображено прямокутниками та ншими фгурами а звязок мж ними показано...Словник іншомовних слів Мельничука
  49. блоксхема—БЛОКСХЕМА и ж. спец. Фзичне представлення задач для аналзу або розвязування за допомогою спецальних символв геометричних образв як позначають так елементи як операц потк...Словник української мови у 20 томах
  50. блоксхема—Блоксхема flowchart flow diagram графическое представление задачи для проведения анализа или решения с помощью специальных символов обозначающих такие элементы как опера...Терминологический словарь автоматизации строительства и производственных процессов
  51. блоксхема—так принято называть схему отражающую основные узлы какоголибо технического устройства или процесса с указанием связей между ними.Синонимы схема...Толковый переводоведческий словарь
  52. блоксхема—и ж. Схема що складаться з окремих елементв блокв. Блоксхема програми графчне зображення перебгу виконання програми за допомогою типово символки....Толковый словарь украинского языка
  53. блоксхема—Ударение в слове блоксхемаУдарение падает на букву еБезударные гласные в слове блоксхема...Ударение и правописание
  54. блоксхема—БЛОКСХЕМА bar chart flow diagram....Украинско-английский бизнес словарь
  55. блоксхема—тех.flow chart flow sheet block diagram...Українсько-англійський словник
  56. блоксхема—Блоксхема Блоксхема в программировании графическое представление программы или алгоритма с использованием стандартных графических элементов прямоугольников ромбиков тра...Финансовый словарь
  57. блоксхема—блоксхема блоксхемы блоксхемы блоксхем блоксхеме блоксхемам блоксхему блоксхемы блоксхемой блоксхемою блоксхемами блоксхеме блоксхемах Источник Полная акцентуированная па...Формы слова