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

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

Страницы работы

12 страниц (Word-файл)

Посмотреть все страницы

Скачать файл

Содержание работы

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

Найти некоторое приближение к оптимальному решению этой задачи можно, выделив в матрице Х некоторый строчный (составленный из строк) минор X', все столбцы которого различны, а число строк минимально. Этот минор и представляет искомую матрицу У. Что же касается матрицы В, то она строится следующим образом: столбцы из В, соответствующие выделенным строкам из X, образуют квадратный минор, которому приписывается значение 1 путем заполнения единицами его главной диагонали, все остальные элементы получают значение 0.

Покажем применение описанного метода на следующем примере, при подготовке которого считалась заданной лишь матрица X. В ней отмечены символом + выделенные строки, образующие минор X', этот минор передан в качестве значения матрице Y, и соответственно сконструирована матрица В.

Самым трудным при решении данной задачи является нахождение минора X' с заданными свойствами. Эта операция рассматривается в теоретической диагностике, где она известна под названием задачи о минимальном диагностическом тесте.

Нахождение минимального диагностического теста. Данная задача возникает при рассмотрении двух множеств явлений: множества причин А = {a₁, a₂, . . ., a_n} и множества следствий В ={b₁, b₂,,…, b_m}. Эти два множества связаны отношением влечения, которое можно представить булевой матрицей X: х_i^j =1 если явление а_j (причина) влечет явление b_i (следствие), и x_i^j = 0 в противном случае. Матрица X считается известной, причем полагается, что все ее столбцы различны, т. е. нет различных причин, влекущих одинаковые наборы следствий.

Диагностирование, как известно, заключается в определении причин по тем следствиям, которые они вызывают. При этом в число причин попадают обычно явления, непосредственное наблюдение за которыми осуществить трудно или даже практически невозможно, в связи с чем их приходится «вычислять». Напротив, следствия, называемые также признаками, представляют собой непосредственно наблюдаемые явления, и именно наблюдение за ними поставляет исходную информацию для вычисления причин. Однако эта информация не дается даром, в связи с чем число наблюдаемых признаков целесообразно ограничить.

Так возникает оптимизационная задача нахождения такого минимального подмножества S признаков из множества В, наблюдение за которыми дает достаточную информацию для того, чтобы установить путем логических рассуждений, какая из причин имеет место — для простоты считается, что совместное появление нескольких причин невозможно. Такое подмножество S называется минимальным диагностическим тестом.

Легко показать, что решение этой задачи сводится к уже знакомой нам задаче нахождения в булевой матрице Х минимального строчного минора X' с попарно различными столбцами. Будем называть такой минор минимальным тестом матрицы X. Подмножество S образуется элементами из множества В, соответствующими вошедшим в минор X' строкам.

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

Для примера покажем матрицу различий D, полученную из приведенной выше матрицы X, отметив столбцы матрицы D парами образующих их столбцов из X:

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

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

Заметим, что матрица различий быстро растет с увеличением числа столбцов в матрице X, а именно по квадратичному закону, и наступает момент, когда становится практически невозможно пользоваться ею. В связи с этим представляет интерес развитие таких методов нахождения минимального теста, которые не связаны с построением матрицы D, а работают непосредственно с исходной матрицей Х. Рассмотрим один из них, приближенный.

Будем конструировать искомый тест, оперируя с переменным множеством Р, которое первоначально принимается пустым, а затем в него добавляются последовательно признаки, выбираемые определенным образом из множества В. Каждый признак (строка матрицы X) задает некоторое двублочное разбиение на множестве А, т. е. на множестве столбцов матрицы X, различая элементы, принадлежащие различным блокам разбиения. Число различаемых пар, равное произведению мощностей блоков, может быть принято за меру различающей способности признака.