Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

10

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Х = {х₁‚ х₂‚ ...‚ х_n },  = {₁‚ ₂‚ ...‚ _m}.

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

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

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

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

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

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

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

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

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

х_i = F_i (₁‚ ₂‚ ...‚ _m);

_j = Ф_j (х₁‚ х₂‚ ...‚ х_{n) ,}

или

х_i  F_i (₁‚ ₂‚ ...‚ _m) = 1;

Ф_j (х₁‚ х₂‚ ...‚ х_n)  _j = 1,

или

F (х₁‚ х₂‚ ...‚ х_n)  Ф (₁‚ ₂‚ ...‚ _m) = 1,

или

F(х₁‚ х₂‚...‚ х_n ‚ ₁‚ ₂‚...‚ _m) = Ф (х₁‚ х₂‚...‚ х_n , ₁‚ ₂‚...‚ _m).

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

 (х₁‚ х₂‚...‚ х_n‚ ₁‚ ₂‚...‚ _m) = 1 (3.1)

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

зависимость F(х₁‚ х₂‚...‚ х_n‚ ₁‚ ₂‚...‚ _m) = Ф (х₁‚ х₂‚...‚ х_n‚ ₁‚ ₂‚...‚ _m)

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

а зависимость F( х₁‚ х₂‚...‚ х_n‚ ₁‚ ₂‚...‚ _m )  Ф( х₁‚ х₂‚...‚ х_n‚ ₁‚ ₂‚...‚ _m ) = 1

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

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

 (х₁‚ х₂‚ х₃‚ ₁‚ ₂) = х₁· х₂ · х₃ · ₁  х₁·х ₂·₁ (х₃·₂  х ₃·₂) = 1, (3.2)

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

Задача распознавания возникает‚ когда в дополнение к априорной информации (3.1) появляется полученная на основе дополнительных наблюдений (экспериментов) апостериорная информация‚ устанавливающая “истинность” некоторой заданной булевой функции G(₁‚ ₂‚ ...‚ _m) логических переменных ₁‚ ₂‚ ...‚ _m и требуется определить‚ какие выводы можно сделать относительно логических переменных х₁‚ х₂‚...‚ х_n и выражающей их состояние и взаимосвязь функции F(х₁‚ х₂‚ ...‚ х_n).

Формально это сводится к нахождению булевой функции F(х₁‚ х₂‚ ...‚ х_n)‚ такой, чтобы выполнялось условие

G (₁‚ ₂‚ ...‚ _m)  F (х₁‚ х₂‚ ...‚ х_n) = 1 (3.3)

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

Если же апостериорная информация задана в виде булевой функции R (х₁‚ х₂‚ ...‚ х_n) переменных х₁‚ х₂‚ ...‚ х_n и нужно определить‚ какие следствия это породит в отношении переменных ₁‚ ₂‚ ...‚ _m ‚ т.е. найти функцию Q (₁‚ ₂‚ ...‚ _m)‚ удовлетворяющую уравнению

R (х₁‚ х₂‚ ...‚ х_n)  Q (₁‚ ₂‚ ...‚ _m) =1 (3.4)

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

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

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

R (х₁‚ х₂‚ х₃) = x_{1 ·} х ₃

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

( x_{1 ·} х ₃)  Q (₁‚ ₂) = 1, Q (₁‚ ₂) = ?.

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

G (₁‚ ₂) = (₁  ₂)  _{1 ·} ₂ = _{1 ·} ₂  _{1 ·} ₂ = ₁

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

₁  F (х₁‚ х₂‚ х₃) = 1, F (х₁‚ х₂‚ х₃) = ?

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

Так если задана Q (x_1, х₂‚ …, х_n) и требуется найти R (₁‚ ₂, …, _m) такую, что

R (₁‚ ₂, …, _m)  Q (x_1, х₂‚ … х_n) = 1, R (₁‚ ₂, …, _m) =? , (3.5)

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

Если же задана H (₁‚ ₂, …, _m) и требуется найти L( х₁‚ х₂‚ …, х_n), такую, что

L ( х₁‚ х₂‚ …, х_n)  H (₁‚ ₂, …, _m) = 1, L ( х₁‚ х₂‚ …, х_n) = ?, (3.6)

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

Например:

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

R (₁‚ ₂)  x₁ х ₃ = 1, R (₁‚ ₂) = ?

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

L ( х₁‚ х₂‚ х₃)  _{1 ·} ₂ = 1, L ( х₁‚ х₂‚ х₃) = ?

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов книги