Методичка для 3 лабы по ОТКДС (Лабораторная работа 3 ОТКДС)

Посмотреть архив целиком

10



Работа № 3. ИССЛЕДОВАНИЕ ЛОГИЧЕСКИХ АЛГОРИТМОВ РАСПОЗНАВАНИЯ

Цель работы: ознакомление с методами решения логических задач распознавания (образов) на основе использования теории функции алгебры логики (ФАЛ) и реализации этих методов на ЭВМ.

Общие сведения

Качественное описание задачи распознавания.

Распознавание - процесс преобразования входной информации, в качестве которой рассматриваются некоторые параметры (признаки распознаваемых образов), в выходную, представляющую собой заключение о том, к какому классу относится распознаваемый образ. Задачу распознавания можно представить в следующей трактовке.

Пусть имеется некоторая совокупность объектов или явлений. В соответствии с выбранными принципами классификации она подразделена на ряд классов. Например, при распознавании диспетчерской службой аэропорта прибывающих самолетов различаются классы: пассажирские, транспортные, спортивные и т.д. Разработан словарь признаков и с его помощью описываются классы объектов, т.е. на основе априорных данных (предыдущего опыта) устанавливается связь между классами и признаками (априорная информация). Например, признаки для самолетов: максимальная скорость, предельная высота полета, число и тип двигателей, размах крыльев и т.п.

Появляется объект, подлежащий распознаванию, вместе со сведениями о присущих ему признаках (апостериорная информация).

Необходимо определить к какому классу может быть отнесен данный объект.

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

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

Пример [3]. В результате продолжительных наблюдений за воздушным противником установлено что на выполнение боевого задания направляется следующий состав авиационных средств:

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

- либо появляются тяжелые бомбардировщики и истребители сопровождения и нет истребителей-перехватчиков, причем легкие бомбардировщики и штурмовики появляются одновременно.

На основании этих данных образующих априорную информацию требуется определить, например:

а) какие выводы можно сделать относительно появления бомбардировщиков если известно что ожидается налет, в котором будут участвовать истребители сопровождения и не будет штурмовиков;

б) что можно сказать о возможности появления истребителей и штурмовиков если известно что в налете вообще не будут участвовать бомбардировщики либо будут только легкие бомбардировщики и не будет тяжелых.

На материале этой задачи далее будет рассмотрен общий подход к формализации логических задач распознавания и методы их решения.

Основу для постановки логической задачи распознавания составляют два конечных множества Х и элементами которых являются двоичные (булевы) логические переменные хj , j :

Х = {х1 х2 ... хn }, = {1 2 ... m}.

Одно из них, например Х, является множеством классов другое – - множеством признаков. Их значения будут:


Для нашего примера Х = { х1 х2 х3 }‚ = {1 2}‚ где булевы переменные означают (равны 1):

х1 - наличие истребителей сопровождения;

х2 - наличие истребителей перехватчиков;

х3 – наличие штурмовиков;

1 - наличие тяжелых бомбардировщиков;

2 - наличие легких бомбардировщиков.

Как видно в данном случае разница между классами и признаками определяется структурой исходных данных и является весьма условной.

Для конкретной предметной области между логическими переменными хi(i= 1 2... n) и j=(j = 1 2... m) устанавливаются зависимости выражающиеся в форме логических условий вида:

хi = Fi (1 2 ... m);

j = Фj1 х2 ... хn) ,

или

хi Fi (1 2 ... m) = 1;

Фj1 х2 ... хn) j = 1,

или

F1 х2 ... хn) Ф (1 2 ... m) = 1,

или

F1 х2... хn 1 2... m) = Ф1 х2... хn , 1 2... m).


Подобные зависимости выражают формально априорную информацию для задач распознавания которая в общем случае в результате преобразований может быть представлена единым соотношением вида

1 х2... хn 1 2... m) = 1 (3.1)


Приведение к форме (3.1) возможно на основе известных преобразований, например:

зависимость F1 х2... хn 1 2... m) = Ф1 х2... хn‚ 1 2... m)

эквивалентна выражению F( ) Ф( ) = 1 = [ F( ) Ф( ) ] [ F( ) Ф( )],

а зависимость F( х1 х2... хn 1 2... m ) Ф( х1 х2... хn‚ 1 2... m ) = 1


эквивалентна F( ) Ф( ) = 1.


В нашем конкретном примере априорная информация может быть представлена в форме


1 х2 х3 1 2) = х1· х2 · х3 · 1 х1·х 2·13·2 х 3·2) = 1, (3.2)


устанавливающей истинность перечисленных выше условий регламентирующих состав боевых средств при налете противника.

Задача распознавания возникает когда в дополнение к априорной информации (3.1) появляется полученная на основе дополнительных наблюдений (экспериментов) апостериорная информация устанавливающая истинность некоторой заданной булевой функции G(1 2 ... m) логических переменных 1 2 ... m и требуется определить какие выводы можно сделать относительно логических переменных х1 х2... хn и выражающей их состояние и взаимосвязь функции F1 х2 ... хn).

Формально это сводится к нахождению булевой функции F1 х2 ... хn) такой, чтобы выполнялось условие


G (1 2 ... m) F1 х2 ... хn) = 1 (3.3)


при ограничениях (3.1). Эта задача называется прямой задачей распознавания.

Если же апостериорная информация задана в виде булевой функции R1 х2 ... хn) переменных х1 х2 ... хn и нужно определить какие следствия это породит в отношении переменных 1 2 ... m т.е. найти функцию Q (1 2 ... m) удовлетворяющую уравнению


R1 х2 ... хn) Q (1 2 ... m) =1 (3.4)


при ограничениях (3.1) то такая задача называется сопряженной задачей распознавания.

Принципиальная разница между прямой и сопряженной задачами распознавания состоит в том что в первом случае апостериорная информация, образующая посылку, задается на множестве признаков а искомое следствие определяется на множестве классов Х тогда как во втором случае наоборот. Однако в обоих случаях требуется на основании заданной посылки определить следствие”‚ удовлетворяющее априорной информации (3.1).

Применительно к рассматриваемому примеру апостериорная информация в п. а) формально задается в виде

R1 х2 х3) = x1 · х 3

и ставится сопряженная задача распознавания:

(x1 · х 3) Q (1 2) = 1, Q (1 2) = ?.

В п. б) апостериорная информация задается в виде


G (1 2) = (1 2) 1 · 2 = 1 · 2 1 · 2 = 1


и ставится прямая задача распознавания:


1 F 1 х2 х3) = 1, F 1 х2 х3) = ?


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

Так если задана Q (x1, х2, хn) и требуется найти R (1 2,, m) такую, что

R (1 2, …, m) Q (x1, х2 хn) = 1, R (1 2, …, m) =? , (3.5)


то это обратная прямой задача распознавания.

Если же задана H (1 2, …, m) и требуется найти L( х1 х2 …, хn), такую, что

L ( х1 х2 …, хn) H (1 2, …, m) = 1, L ( х1 х2 …, хn) = ?, (3.6)


то это обратная сопряженной задача распознавания.


Например:

в) Какая ситуация с участием в налете тяжелых и легких бомбардировщиков влечет за собой наличие истребителей сопровождения и отсутствие штурмовиков (обратная прямой задача распознавания) ?

R (1 2) x1 х 3 = 1, R (1 2) = ?


г) Какая ситуация с участием в налете истребителей и штурмовиков влечет за собой наличие легких бомбардировщиков и отсутствие тяжелых (обратная сопряженной задача распознавания) ?

L ( х1 х2 х3) 1 · 2 = 1, L ( х1 х2 х3) = ?


Метод решения логических задач распознавания

Принципиальная возможность решения поставленных логических задач распознавания связана с существованием логической зависимости между классами и признаками которая содержится в априорной информации (3.1).

Представление этой зависимости в более явной форме в виде соотношения между наборами (х1 х2... хn) и (1 2... m) удовлетворяющего (3.1) лежит в основе метода и связана с построением так называемого сокращенного базиса .

Пусть определена функция 1 х2... хn 1 2... m), выражающая априорную информацию в соотношении (3.1).

Сокращенный базис есть множество (n+m) разрядных наборов при которых удовлетворяется условие (3.1), то есть множество наборов (х1 х2... хn 1 2... m) на которых функция ( ) равна единице (множество T1 функции ). Сокращенный базис для заданной функции может быть представлен в виде например специальной таблицы (см. таблицу 3.1).


Таблица 3.1

х1

0

1

  

0

1

х2

1

0


0

1






хn

0

1


1

0

1

1

0


1

0

2

0

0


0

1






m

1

1

  

0

1


Каждый элемент сокращенного базиса - (n+m) - разрядный двоичный набор (столбец в таблице 3.1) может быть разбит на две части: n - разрядный соответствующий аргументам х1 х2... хn (верхняя часть таблицы) и m-разрядный соответствующий аргументам 1 2 ... m (нижняя часть таблицы). Таким образом устанавливается соответствие между наборами (х1 х2... хn) и наборами (1 2 ... m) при которых априорная информация является “истинной”, (выполняется (3.1)).

Такое соответствие между наборами можно формализовать с помощью булевой матрицы Е размера 2n×2m элементы которой eij = 1 если i-ый набор (х1 х2... хn) совместно с j-м набором ( 1 2 ... m) образуют элемент базиса и eij = 0 в противном случае. Назовем такую матрицу перестановочной.

Продемонстрируем построение сокращенного базиса для априорной информации представленной в соответствии с выражением (3.2). Составим для его правой части


1 х2 х3 1 2) = х1· х2 · х3 · 1 х1·х 2·13·2 х 3·2)

таблицу истинности (табл. 3.2) и по ней найдем сокращенный базис (табл. 3.3).



Таблица 3.2


Таблица 3.3


T

3

3

4

5

х1

0

0

1

1

х2

1

1

0

0

х3

1

1

0

1

1

0

0

1

1

2

0

1

0

1

j

0

1

2

3


Как видно сокращенный базис состоит из четырех 5-ти разрядных наборов (12 13 18 и 23) и регламентирует следующую связь между наборами ( х1 х2 х3 ) с номерами i и наборами (1 2) с номерами j:


i = 3  j = 0, i = 3  j = 1, i = 4  j = 2, i = 5  j = 3.


Соответствующая перестановочная матрица имеет вид (рис. 3.1).


=


Рис. 3.1


После того как определены искомые связи между наборами (х1х2... хn) и (1 2 ... m) прямая и сопряженная задачи распознавания решаются путем удовлетворения соотношениям (3.3) или (3.4) наборами с номерами i и j находящимися в такой связи. Практически это осуществляется путем “вычисления” изображающего числа искомой ФАЛ на основе логического умножения справа изображающего числа ФАЛ задающей апостериорную информацию, на перестановочную матрицу отображающую априорную информацию.

Для прямой задачи распознавания (3.3) это имеет вид:


#F1 х2... хn) = #G (1 2 ... k) Eт (3.7)

(1× 2m) (1× 2m) ( 2m×2n)


Для сопряженной задачи распознавания (3.4):


#Q (1 2 ... m) = #R1 х2... хn) E (3.8)

(1× 2m) (1× 2n) ( 2n×2m)


Обоснованием данного способа “вычисления” искомых ФАЛ может служить известное свойство проявляющееся при умножении справа изображающего числа ФАЛ отличной от константы «ноль» например R1 х2... хn) на прямоугольную булеву матрицу например Е и заключающееся в том что единица в i-ой строке и j-м столбце матрицы Е (то есть еij= 1) обеспечивает перемещение единицы находящейся на i-ом месте в #R1 х2... хn) на j-ое место результата - изображающего числа #Q (1 2 ... m).

Это значитчто при еij= 1 единица на i-ом месте #R1 х2... хn) обеспечивает единицу на j-ом месте # Q (1 2 ... m) (см. рис 3.2) что соответствует истинности импликации. Если учесть все единицы в #R1 х2... хn) то #R1 х2... хn) #Q (1 2 ... k) = 1 что соответствует решению задачи (3.4).




Рис. 3.2


Аналогично при умножении #G (1 2... m) на ЕТ получаем #F1 х2... хn) причем #G (1 2... m) #F1 х2... хn) = 1.

Применяя описанный метод к решению конкретных задач распознавания а) и б) для рассматриваемого примера, находим:


а) #R (х1 х2 х3) = #1 · х3) = (00001010),


#Q (1 2) = (00001010) = (0010),


следовательно Q(1 2) = 1·2, что обозначает: в налете будут участвовать тяжелые бомбардировщики и не будет легких;

б) #G (1 2) = # (1) = (1100),

#F1 х2 х3) = (1101) = (00010000) ,


следовательно F (х1 х2 х3) = x1 · х2 · х3 , что означает: в налете будут участвовать истребители-перехватчики и штурмовики и не будет истребителей сопровождения.

Решение обратных задач распознавания может быть осуществлено путем сведения их к прямым путем элементарных преобразований.

Пусть для заданной функции Q (х1 х2... хn) требуется найти такую функцию R(1 2... m) что R (1 2, …, n) Q (x1, х2 хn) = 1, R (1 2, …, n) =?

Так как R Q = R Q = Q R = Q R = 1 то рассматриваемая обратная задача может быть заменена прямой


Q (x1, х2 хn) R (1 2 . . . k) = 1, R (1 2, …, k) =?,

содержащей инверсии заданной и искомой функции.

На этом построение методики решения задач распознавания (3.3) (3.4) (3.5) (3.6) завершено.

В заключение рассмотрим важный частный случай.

Пусть сокращенный базис состоит из 2m (n + m) - разрядных наборов причем в нем представлены все m - разрядные наборы 1 2... m (такая ситуация имела место в нашем примере и отражена в таблице 3.3). Соответствующая перестановочная матрица Е имеет по одной единице в каждом столбце. Можно заметить что в этом случае логические переменные х1 х2... хn могут быть представлены как некоторые функции логических переменных 1 2... m, образующие решение булевского уравнения (3.1) в виде

хi = fi (1 2... m) i = 12,..., n. (3.9)


Например таблица 3.3 задает три ФАЛ:

х 1 = 1 , х 2 = 1 , х 3 = 1 2 .


В данной ситуации решение сопряженной задачи распознавания (3.4) может быть получено аналитически путем подстановки в заданную функцию R(х1 х2... хn ) функций хi = fi (1 2... m). В результате получится искомая функция Q (1 2... m).


Для рассматриваемого примера R (х1 х2 х3) = х1 · х 3


Q (1 2) = R (f1 (1 2) f2 (1 2) f3 (1 2)) = 1· (1 2) = 1· 1· 2 = = 1 · 2 ,

что совпадает с полученными ранее.

При наличии нескольких единиц в каждом столбце сокращенного базиса решение исходного уравнения вида (3.9) будет не единственное. При отсутствии единицы хотя бы в одном столбце решения уравнения (3.1) в виде хi = fi (1 2... m) i = 12,...,n не существует.

Следует заметить, что рассмотренный выше вариант представления сокращенного базиса в виде перестановочной матрицы соответствует заданию конечного автомата без памяти с двоичными входами 1 2... m и выходами х1 х2... хn , обеспечивающего решение исходного уравнения (3.1).

Наличие сокращенного базиса позволяет искать решения исходного уравнения (3.1) также в виде

j = φj1 х2... хn) j = 12,...,m. (3.10)


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

В данной лабораторной работе необходимо осуществить анализ полученного сокращенного базиса на существование и единственность решения (3.9). При наличие нескольких привести все решения.

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


Задание.

Для конкретного варианта исходных данных требуется :

1. Осуществить необходимую формализацию и приведение данных к форме логических задач распознавания.

2. Используя полученный сокращенный базис выполнить анализ существования и единственности решения исходного уравнения в виде (3.9). Найти все существующие решения.

3. Найти решения поставленных задач распознавания вручную и записать полные качественные ответы на поставленные вопросы.

4. Используя стандартную программу ЭВМ получить машинное решение задач распознавания.

5. Проанализировать результаты ручного и машинного счета сравнить их сделать выводы.

6. Сформулировать самостоятельно на материале исходных данных две обратные задачи распознавания осуществить их решение записать качественные ответы.


Исходные данные.

При функционировании технической системы состоящей из 3–х взаимосвязанных подсистем (блоков) в условиях нормальной (повышенной) температуры и нормальной (повышенной) влажности выявлено наличие совместно 4 связей (№№ задаются для каждой бригады) из нижеследующего списка.


1. Пpи ноpмальной температуре и влажности все блоки pаботоспособны.

2. При повышенной температуре и повышенной влажности все блоки неpаботоспособны.

3. Пpи ноpмальной температуре и повышенной влажности теpяет pаботоспособность 2-й блок.

4. Пpи повышенной температуре и ноpмальной влажности теpяет pаботоспособность 1-й блок.

5. Пpи ноpмальной температуре pаботоспособны 1-й и 3-й блоки.

6. Пpи повышенной температуре отказывает 1-й блок, а 2-й и 3-й либо оба pаботоспособны, либо оба неpаботоспособны.

7. Пpи ноpмальной влажности pаботоспособны 2-й и 3-й блоки.

8. Пpи повышенной влажности отказывает 2-й блок, а 1-й и 3-й либо оба pаботоспособны, либо оба не pаботоспособны.

9. Пpи ноpмальной температуре и повышенной влажности теpяет pаботоспособность только 2-й блок.

10. Пpи повышенной температуре и ноpмальной влажности pаботоспособен только 2-й блок.

11. Пpи ноpмальной температуре pаботоспособны блоки 1 и 2-й.

12. Пpи повышенной температуре отказывают 1 и 3-й блоки.

13. Пpи ноpмальной влажности pаботоспособен блок 2, а блоки 1 и 3 или оба pаботоспособны или оба не pаботоспособны.

14. Пpи повышенной влажности отказывает 3-й блок, а блоки 1 и 2-й или оба pаботоспособны или оба неpаботоспособны.

15. Пpи повышенной температуре и влажности pаботоспособен только 2-й блок.

16. Пpи ноpмальной температуре и повышенной влажности неpаботоспособен только 1-й блок.

17. Пpи повышенной температуре и ноpмальной влажности pаботоспособен только 1-й блок.

18. Пpи ноpмальной температуре pаботоспособны 2 и 3-й блоки.

19. Пpи повышенной температуре не pаботоспособны только 3-й блок и какой-либо блок из оставшихся (1-й или 2-й).

20. Пpи ноpмальной влажности pаботоспособен 1-й блок, а остальные либо оба pаботоспособны, либо оба не pаботоспособны.

21. Пpи повышенной влажности 1-й блок не pаботоспособен, а 2-й pаботоспособен.

22. При повышенных температуре и влажности работоспособен только 3-ий блок

23. При нормальной температуре и повышенной влажности неработоспособен только 3-ий блок

24. При повышенной температуре и нормальной влажности неработоспособен только 2-ий блок

25. При нормальной температуре работоспособны 1-ый и 2-ой блоки

26. При повышенной температуре 2-ой блок не работоспособен, а 3-ий работоспособен

27. При нормальной влажности работоспособны 1-ый и 3-ий блоки

28. При повышенной влажности или работоспособен только 3-ий блок или неработоспособен только 3-ий блок.


Требуется определить:

1) Если известно что функционирование системы протекает при нормальной температуре какие блоки потеряют (не потеряют) работоспособность?

2) Если потерял работоспособность блок 1 или блоки 2 и 3 (совместно) какое сочетаний температуры и влажности имеет место?


Методические указания

I. Формализация задачи осуществляется по схеме, описанной в разделе «Общие сведения», и предусматривает следующее:

  • определение множества "классов", множества "признаков" и введение соответствующих групп логических переменных;

  • запись на языке ФАЛ априорной информации, устанавливающей связь между "классами" и "признаками";

  • запись на языке ФАЛ апостериорной информации, характеризующей результат дополнительного наблюдения;

  • записи на языке ФАЛ конкретных задач распознавания и определение их вида.

2. Анализ существования и единственности решения полученного уравнения выполнить используя перестановочную матрицу Найти все существующие решения.

3. Решение задач распознавания производится на основе составления сокращенного базиса, формирования перестановочной матрицы и вычисления изображающих чисел по формулам (3.7) или (3.8).

4. Если решение сопряженной задачи распознавания (3.4) допускает аналитическое решение, то получить его путем подстановки в заданную функцию R(х1 х2... хn ) функций хi = fi (1 2... m). Если аналитических решений несколько, то найти все решения.

5. Машинное решение задач распознавания предусматривает:

  • ознакомление с описанием и работой стандартной программы;

  • описание на языке программы априорной и апостериорной информации, задание вида задачи распознавания;

  • машинный счет с выводом результатов счета на печать.

6. Все этапы решения должны быть подробно отражены в отчете.

7. Анализ результатов включает в себя сопоставление результатов расчетов и затрат на получение ручного и машинного решений с учетом возможного увеличения числа классов, признаков, ограничений и т.п.

Контрольные вопросы

1. Какие задачи называются логическими задачами распознавания?

2. В каких формах задается априорная информация для задач распознавания?

3. В чем отличие прямой задачи распознавания от сопряженной?

4. В чем отличие обратных задач от прямой и сопряженной?

5. Что такое сокращенный базис?

6. Что такое унитарная перестановочная матрица и каковы ее свойства?

7. Как на основе сокращенного базиса строится перестановочная матрица?

8. Как устанавливается возможность аналитического решения логических задач распознавания?



Варианты заданий:


№№

Условия

№№

Условия

№№

Условия

№№

Условия

1

1, 2, 3, 4

7

1, 2, 9, 10

13

1, 15, 16, 17

19

1, 22, 23, 24

2

1, 2, 5, 6

8

1, 2, 11, 12

14

1,15,16,17

20

1,22,25,26

3

1, 2, 7, 8

9

1, 2, 13, 14

15

1,15,20,21

21

1,22,27,28

4

2, 5, 6, 7

10

2,11, 12, 13

16

15,18,19,20

22

22,25,26,27

5

2, 5, 6, 7

11

1, 11, 13, 14

17

1,18,20,21

23

1,25,27,28

6

2, 5, 6, 7

12

11, 12,13, 14

18

18,19,20,21

24

25,26,27,28




Случайные файлы

Файл
11087.rtf
92132.rtf
13337.rtf
__pb_10-115-96.doc
17640-1.rtf