Математика \ Дискретная математика

Задача о кодировании. Задача о генерировании, страница 4

Выбирая в матрице X* первую из строк с максимальным качеством, а именно строку 3, присоединим к ней дизъюнктивно строку 2, получив таким образом первый элемент теста — первую строку искомой матрицы У

y1 =01110100

и первую строку матрицы В

b1 =0110000.

Сразу же можно найти и соответствующую строку матрицы Т, удовлетворяющей исходному уравнению Y = ТÑХ. Следует лишь учитывать, что при переходе от матрицы В к матрице Т нули заменяются значением «—», а единицы остаются (в столбцах, которым соответствуют строки матрицы X*, равные одноименным строкам матрицы X) или заменяются нулями (в столбцах, соответствующие которым строки матрицы X* были получены инверсированием одноименных строк из X).

В данном случае t1 = - 01----. Соответственно переставив столбцы, покажем порождаемое полученным вектором y1 разбиение множества столбцов матрицы X* на два равномощных блока:

Далее мы будем интересоваться" лишь дроблением полученных блоков разбиения, соответственно оценивая качество второго элемента теста. Применяемый нами метод приводит теперь к выбору строки 1 и дизъюнктивному присоединению к ней строки 6 В результате получим значения вторых строк искомых матриц:

У2 = 1 1 1 0 0 0 1 0,

B2 = 1 0 0 0 0 1  0,

T2, = 0 ----1-


и новое разбиение множества столбцов:

Те же правила определяют заключительный шаг: выбор строки 1 и дизъюнктивное присоединение к ней сначала строки 2, а затем строки 5. Так получаются

У3 = 0 0 1 1 1 0 1 0,

B3 = 1 1 0 0 1 0 0,

T3 =  00——1——,

и разбиение множества столбцов становится полным. Формируя из найденных строк матрицы У и Т, представим решение в целом:

Очевидно, что это решение оптимально. Однако напомним, что в общем случае оптимальность данным методом не гарантируется.

13. Задача о генерировании

Задача о кратчайшем покрытии булевой  м а т р и ц ы парными минорами. Ранее (§ 11) нами рассматривалась задача, которую можно назвать задачей о генерировании заданного множества булевых векторов, подразумевая при этом, что задача заключается в построении своеобразного «генератора» данных векторов, представляющего собой сочетание некоторой простейшей элементарной матричной схемы и некоторого множества булевых векторов, подаваемых на вход этой схемы и инициирующих появление требуемых векторов на ее выходе. Мы решили эту задачу для случая, когда генератор ищется в классе b-схем, и показали, что в этом случае она сводится к нахождению минимального дизъюнктивного базиса для заданного множества булевых векторов, или, что то же самое,к нахождению кратчайше-то минорного покрытия матрицы У, представляющей это множество.

Перейдем к исследованию этой задачи в более общей постановке, когда решение ищется среди t-схем, описываемых уравнением У = ТÑХ, где матрица У считается заданной, а Т и Х — неизвестными. Критерием простоты искомой схемы считаем по-прежнему число столбцов l в операторной матрице (в данном случае это будет троичная матрица Т), равное числу строк входной матрицы X.

Прежде всего попытаемся выявить комбинаторную суть отличия новой постановки задачи от старой, для чего обратимся к сравнению дизъюнктивного разложения

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

иллюстрируемым примером:

Из примера видно, что выходная матрица У дизъюнктивно разлагается теперь уже не на единичные минеры, а на пары единичных миноров, причем такие, что строки одного из миноров, образующих некоторую пару, являются инверсиями строк другого минора этой же пары. Назовем такие пары парными минорами, рассматривая далее единичные миноры, как их частный случай, при котором задается лишь один элемент пары.

Нетрудно видеть, что в новой постановке задача сводится к нахождению кратчайшего покрытия заданной булевой матрицы У парными минорами.

Скачать файл