Разработка алгоритма рационального покрытия булевых матриц
Разработка алгоритма рационального покрытия булевых матриц - раздел Педагогика, Введение в техническую диагностику Предмет и задачи дисциплины, ее значение и роль в обеспечении надежности технических объектов В Терминах Матрицы Различимости Задача Выбора Минимального Множества Элемента...
В терминах матрицы различимости задача выбора минимального множества элементарных проверок формулируется как задача нахождения кратчайшего строкового покрытия этой матрицы. Строковым покрытием матрицы , , , называется подмножество ее строк, таких, что столбец матрицы содержит единицу хотя бы в одной из строк подмножества . Покрытие называется тупиковым, а соответствующее ему множество проверок – тупиковым тестом [14], если никакое его собственное покрытие не является покрытием. Наименьшее из тупиковых покрытий является кратчайшим (минимальным).
Определение тупиковых покрытий возможно на основе алгоритма С.В.Яблонского [44], согласно которому на основании матрицы различимости , , , составляется выражение
, (8.13)
где – множество строк матрицы A, содержащих на пересечении с n–м столбцом единицы.
Полученная согласно (8.13) конъюнкция дизъюнкций, преобразуется в равносильную ей форму – дизъюнкцию конъюнкций
, (8.14)
где – множество тупиковых покрытий матрицы A.
Упрощение (8.14) на основе законов алгебры логики позволяет определить все множество тупиковых покрытий и выбрать из него кратчайшее. Их может быть несколько. Каждое из них определяет минимальное число элементарных проверок для отыскания любой неисправности объекта.
Для принятия окончательного решения о наиболее эффективном покрытии (в смысле минимальности длины и достоверности распознавания) определим суммарный весовой коэффициент :
,
где – множество индексов проверок .
Коэффициенты берутся из матрицы нечеткой эквивалентности. Таким образом, величина имеет смысл степени, с которой проверка различает неисправности и по вероятностно-лингвистическим синдромам и соответственно, индексы которых связаны соотношением (8.11). Поэтому изложенная процедура зависит от достоверности распознавания.
Несмотря на то, что алгоритм Яблонского позволяет получить строго минимальное покрытие матрицы различимости, использование его для сложных объектов связано с большими вычислительными трудностями. Это объясняется тем, что размерность матрицы различимости (число столбцов N) возрастает пропорционально квадрату роста числа столбцов вероятностно-лингвистической диагностической таблицы: .
Поэтому актуальной является задача разработки процедуры покрытия матрицы различимости, отличающейся простотой реализации и дающей приемлемые по точности решения.
Для решения поставленной задачи обратимся к семантике матрицы различимости. Очевидно, что единица, стоящая в матрице различимости в q–й строке и n–м столбце, означает, что проверка различает неисправности и . Поэтому, чем меньше в столбце n единиц, тем меньше проверок может быть использовано для распознавания неисправностей и . А это означает, что в тупиковый тест так или иначе должна войти хотя бы одна проверка, различающая неисправности и . И если при нахождении покрытия булевой матрицы будут выбраны проверки отличные от проверок, имеющих единицы в столбце n с их наименьшим по сравнению с другими столбцами количеством, то обязательно возникнет необходимость включить в тест еще и одну из отмеченных проверок. В противном случае получаемая совокупность проверок не будет обладать распознающими способностями исходного множества проверок .
1. Проверить, является ли матрица нулевой. Если является, то перейти к п. 10, в противном случае – к п. 2.
2. Заменить матрицу соответствующей ей упрощенной матрицей и перейти к п. 3.
3. Проверить, равное ли количество единиц в столбцах матрицы. Если нет, то перейти к п. 4, если да – к п.6.
4. Найти в матрице столбец (столбцы) с наименьшим количеством единиц. Для каждой строки, в которой в выделенном столбце (выделенных столбцах) стоят единицы, подсчитать число единиц. Инвертировать матрицу по строке, для которой это число единиц максимально. Если таких строк несколько, то выбрать ту, для которой показатель достоверности , определяемый по формуле
,
где берется из матрицы нечеткой эквивалентности, максимален. Перейти к п. 5.
5. Проверить, является ли матрица нулевой. Если да, то перейти к п. 9, если нет – к п. 2.
6. Найти в матрице строку с наибольшим числом единиц. Если таких строк несколько, то для выбрать ту, для которой показатель достоверности максимален. Перейти к п. 7.
7. Инвертировать матрицу по выбранной строке. Перейти к п.8.
8. Проверить, является ли матрица нулевой. Если да, то перейти к п. 9, если нет – к п. 2.
9. Выписать номера тех строк, по которым в ходе выполнения процедуры производились инверсии (номера строк исходной матрицы A, а не упрощенных). Перейти к п. 10.
10. Закончить процедуру.
Ниже приводятся понятия, использованные при описании процедуры.
Определение 8.2. Под нулевой матрицей понимается матрица, все элементы которой равны нулю.
, ; – нулевая матрица,
если , , .
Определение 8.3. Под инверсной строкой строки матрицы A понимается строка , элементы которой получаются в соответствии со следующим правилом:
Определение 8.4. Под инверсией матрицы , , , по строке понимается матрица , , , элементы которой получаются умножением элементов инверсной строки , , на элементы матрицы A согласно правилу:
, ; .
Определение 8.5. Под упрощенной матрицей понимается матрица, полученная из исходной путем исключения всех нулевых строк и столбцов.
Предмет и задачи дисциплины ее значение и роль в обеспечении надежности технических объектов... Одной из основных задач эксплуатации технических объектов и систем является... Прошедший приемо сдаточные испытания на заводе изготовителе и принятый в эксплуатацию технический объект изначально...
Историческая справка о развитии дисциплины
Усиление интереса к технической диагностике в последние годы объясняется созданием и применением в народном хозяйстве все более сложных изделий, устройств и систем (объектов) при непрерывном увелич
Основные термины и определения
До настоящего момента уже достаточно интенсивно использовались многие понятия технической диагностики, смысл которых в большей степени можно было понять интуитивно, основываясь на опыте и логике. П
Математические модели дискретных устройств
В предыдущем разделе пособия были рассмотрены отдельные, наиболее важные свойства и параметры функциональных элементов ЭЭСА, имеющих радиоэлектронную природу, была дана классификация этих функциона
Понятие правильной логической сети
Логическая сеть определяется множеством {hi} логических элементов из базиса Н, множеством {хa} входных полюсов и множеством {zg} выходных полюс
Исследование правильности логической сети
Заметим, что требование правильности логической сети не исключает наличия в ней петель обратной связи или циклов в соответствующем ей графе. Логическая сеть, построенная из логических элементов без
Физические основы логического контроля дискретных устройств
Прежде чем рассматривать неисправности КУ, следует вспомнить их классификацию, исходя из состава элементной базы, на которой они построены.
КУ подразделяются на:
· релейно-контакт
Разрыв реагирующих органов РКС
Разрыв реагирующих органов в РКС проявляется в том, что реле не срабатывает тогда, когда оно должно сработать (на обмотку реле подано напряжение – управляющий сигнал). В этом случае размыкающие кон
Разрыв реагирующих органов БКС
Разрыв реагирующего органа в БКС проявляется в том, что на одноименном входе входной сигнал имеет только нулевое значение независимо от его действительного значения. В этом случае размыкающие испол
Короткое замыкание путей воздействия
Пусть состояние исполнительных органов r, s, …, k, …, m по прежнему таково, что они обеспечивают прохождение входного сигнала A по пути воздействия ar
Разрыв путей воздействия
Пусть состояние исполнительных органов r, s, …, k, …, m по прежнему таково, что они обеспечивают прохождение входного сигнала A по пути воздействия ar
Логические неисправности типа const1
Логической неисправностью типа const1 на входе A логического элемента называется такая неисправность, которая проявляет себя на его выходе так, как будто на вход A приложен пос
Понятие о функции неисправностей
Формализация методов построения алгоритмов диагностирования технического состояния предполагает наличие формального описания объекта диагностирования и его поведения в исправном и неисправных состо
Понятие неисправности физических объектов
Определение 5.1. Под неисправностью si физических объектов, предназначенных для переработки дискретной информации, будем понимать последствия некоторого событ
Понятие о правильных и неправильных неисправностях
Вне зависимости от того, какой моделью пользуются при описании исправного устройства А, множество всех неисправностей, которые в нем могут возникнуть, делят на два класса: правильн
Работа исправного устройства
Рассмотрим работу исправного логического элемента И-НЕ. Данный логический элемент работает в отрицательной логике, т.е. логическому 0 соответствует незначительное отрицательное напряжение (для опре
Работа неисправного устройства
При неисправности s1 (обрыв цепи коллектора транзистора VT1) iк = 0, поэтому uвых = - Eпит
Неисправности связей элементов комбинационных устройств
Среди наиболее часто встречающихся физических неисправностей связей (соединений) элементов устройства можно выделить следующие неисправности:
1) обрыв соединения;
2) замыкание сое
Понятие о логических неисправностях
При построении неявных математических моделей объектов диагностирования требуется задание математических моделей их неисправностей. Это равносильно выбору из всех возможных неисправностей объекта н
Математические модели непрерывных устройств логического типа
При диагностировании технического состояния непрерывных объектов широкое распространение получили допусковые (как наиболее простые и легко поддающиеся автоматизации) способы, характеризующиеся тем,
Процедура построения функциональной модели
Пусть непрерывный объект диагноза состоит из N связанных между собой компонент (блоков, узлов, агрегатов, составных частей и т.п.). Состав компонент, связи между ними и внешние связи
Определение общего числа неисправностей
По условию задачи необходимо построить таблицу функций неисправностей на множестве одиночных неисправностей. С учетом того, что каждый из контактов релейно-контактного устройства может находиться в
Построение таблицы функций неисправностей
Заполнение таблицы функций неисправностей производится на основе анализа работы устройства с учетом вносимых неисправностей или на основании анализа логического выражения, описывающего работу РКС в
Определение общего числа неисправностей
На основании выражения, описывающего исправное состояние устройства в сигналах, и приведенной на рис. 48 схемы может быть построено логическое выражение, описывающее исправное функционирование беск
Построение таблицы функций неисправностей
Заполнение таблицы функций неисправностей (табл. 9) производится аналогично описанному в п. 7.1 для релейно-контактного устройства либо на основе анализа работы устройства с учетом вносимых неиспра
Характеристика диагностической экспертной информации
При управлении качеством функционирования ЭЭСА важным моментом является анализ доступных для наблюдения признаков и принятия решения о месте расположения в системе отказавшего функционального элеме
Принцип нечеткого описания
Принцип нечеткого описания продиктован особенностями восприятия, организации и использования специалистами по поиску и устранению неисправностей в ОУ доступной диагностической информации. Эти особе
Анализ диагностической экспертной информации и вывод решений
Основой метода диагностирования является процедура поиска неисправностей. Причем в технической диагностике под процедурой поиска неисправностей понимается формализованный способ построения алгоритм
Процедура обучения
Представленный экспертами объем диагностической информации, формализованной в виде модели (8.1), позволяет решать диагностические задачи с достоверностью, оцениваемой согласно формуле:
Оценка сходимости процедуры обучения
В предыдущем пункте предложена процедура обучения, которая после очередного шага диагностирования изменяет уровень достоверности используемых при поиске неисправностей лингвистических переменной
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
, 
, 
, называется подмножество 
ее строк, таких, что столбец матрицы содержит единицу хотя бы в одной из строк подмножества 
. Покрытие называется тупиковым, а соответствующее ему множество проверок – тупиковым тестом [14], если никакое его собственное покрытие не является покрытием. Наименьшее из тупиковых покрытий является кратчайшим (минимальным).
возможно на основе алгоритма С.В.Яблонского [44], согласно которому на основании матрицы различимости 
, (8.13)
– множество строк матрицы A, содержащих на пересечении с n–м столбцом единицы.
, (8.14)
– множество тупиковых покрытий матрицы A.
:
,
– множество индексов проверок 
.
берутся из матрицы нечеткой эквивалентности. Таким образом, величина 
имеет смысл степени, с которой проверка 
различает неисправности 
и 
по вероятностно-лингвистическим синдромам 
и 
соответственно, индексы которых связаны соотношением (8.11). Поэтому изложенная процедура зависит от достоверности распознавания.
.
.
, определяемый по формуле
,
, 
; 
– нулевая матрица,
, 
, 
.
матрицы A понимается строка 
, элементы которой получаются в соответствии со следующим правилом:
, 
понимается матрица 
, 
, 
, 
Новости и инфо для студентов