-Поиск по дневнику

Поиск сообщений в zhurnalist

 -Подписка по e-mail

 

 -Статистика

Статистика LiveInternet.ru: показано количество хитов и посетителей
Создан: 26.11.2010
Записей:
Комментариев:
Написано: 18

Правило желательных соседств

Дневник

Вторник, 04 Января 2011 г. 20:22 + в цитатник
Здесь отражена ситуация, которая учитывается при подсчете значения wij. Пара вектор-строк (xs1, xs2, … , xsn, zp1, zp2, … , zpk) и (zi1, zi2, … , zik) матриц U и V представляет переход автомата из состояния qp в состояние qi при входном символе as, выражаемый формулой (as, qp)  qi. Точно так же пара строк (xt1, xt2, … , xtn, zp1, zp2, … , zpk), (zj1, zj2, … , zjk) представляет переход, выражаемый формулой (at, qp)  qj. Отсюда видно, что чем больше одноименных компонент векторов (zi1, zi2, … , zik) и (zj1, zj2, … , zjk), являющихся кодами состояний qi и qj, совпадают и равны единице, тем больше, возможно, будет условий для простого склеивания элементарных конъюнкций в получаемой системе ДНФ.

Ситуация, учитываемая при подсчете значения wij, представляется следующими матрицами:

U  , V  .

Здесь пары строк (xu1, xu2, … , xun, zi1, zi2, … , zik), (zv1, zv2, … , zvk) и (xu1, xu2, … , xun, zj1, zj2, … , zjk), (zv1, zv2, … , zvk) представляют переходы в одно и то же состояние qv при одном и том же значении au переменной а, т. е. (au, qi)  (au, qj)  qv. Ясно, что желательно иметь соседними коды тех состояний qi и qj, для которых переменная а принимает много значений аи, удовлетворяющих (au, qi)  (au, qj). Тогда возможно простое склеивание элементарных конъюнкций, представленных показанными строками матрицы U.
Одна из реализаций метода «желательных соседств» представляется как процесс построение k-мерного гиперкуба, напоминающий сборку некоторой простой механической конструкции. При этом вершины гиперкуба, являющиеся первоначально вершинами некоторого пустого графа (без ребер), заранее поставлены в соответствие состояниям автомата и на парах этих вершин заданы величины wij.

Метки:  

 Страницы: [1]