РОЗДІЛ II.
Оцінка складності та ефективності оптимізації деревоподібної системи розпізнавання.
2.1. Представлення дерев розпізнавання за допомогою функцій алгебри висловлювань.
Як було сказано в попередньому розділі роботи, сконструйовану СР у вигляді дерева розпізнавання можна записати або в ДНФ, або в КНФ формі. Так дерево розпізнавання, яке являє собою певне правило класифікації, можна представити за допомогою відповідної логічної функції . Отже важливою проблемою при побудові СР такого типу буде проблема синтезу логічної функції, яка еквівалентна даному дереву розпізнавання [34,38].
Зі збільшенням числа аргументів функції швидко зростає складність одного з етапів синтезу функції - етапу мінімізації. Виходом з даного положення може бути не знаходження її мінімальної форми, а представлення у вигляді , де функції будуть залежати від меншого числа змінних (), з наступною мінімізацією виразів для функції та .
Якщо множина аргументів , від яких залежить функції і множина не мають спільних елементів, то функціональна декомпозиція називається роздільною або неперетинною. Якщо ж це не так, тобто існує хоча б один аргумент , який входить більш ніж в одну множину , то функціональна декомпозиція називається нероздільною або перетинною.
Якщо функцію можна представити у вигляді , то функціональна декомпозиція називається простою. Прикладом функціональної декомпозиції може служити представлення функції у вигляді розкладу по -му аргументу:
,
він може бути представлений у вигляді: , де відповідно
, ,
Отже виходячи з вищесказаного, маємо, що даний випадок є простою роздільною функціональною декомпозицією, яка відрізняється від тривіальної декомпозиції такого типу - розкладу функції по її аргументу.
Графічна інтерпретація функціональної декомпозиції, в загальному випадку, дуже ефективна для мінімізації логічних деревоподібних структур. Так, наприклад, розклад певної функції по першому аргументу можна зобразити наступною графічною конструкцією (рис. 2.1).
Рис. 2.1. Схема розкладу функції по першому аргументу
Вихідна функція побудована на основі . Отже ту ж саму побудову можна застосувати і до функцій і , вважаючи їх вихідними функціями деякої комбінаційної схеми. Тоді кожну з цих функції можна записати у вигляді:
, .
А це в свою чергу можна зобразити у вигляді графів (рис. 2.2а, рис. 2.2б)
Рис. 2.2а. Розклад Рис. 2.2б. Розклад
Якщо в рис. 2.1 включити рис. 2.2а та рис. 2.2б, то отримуємо рис. 2.3, вихідною функцією якого буде .
Рис. 2.3. Вихідна функція
Продовживши розмірковувати таким чином відносно функцій , отримаємо графічну структуру дерева для функції , вхідними функціями якої будуть , де - значення функції на нульовому наборі аргументів, а - на одиничному (рис. 2.4).
Отже, зважаючи на все вищесказане, зрозуміло, що довільне дерево розпізнавання буде еквівалентним логічному дереву відповідної функції , і воно буде повністю характеризувати властивості даної функції. Логічне дерево являє собою графічну інтерпретацію комбінаційного автомата, вихід якого дорівнює [39,40].
Ярусом будемо вважати частину дерева, (кола та стрілки) причому в колах знаходиться змінна лише одного індексу. Наприклад, для першого ярусу (рис. 2.4) - це коло зі змінною та дві стрілки, які входять в це коло. Загальна кількість ярусів рівна кількості змінних заданої функції. Відлік ярусів проводиться зверху вниз від 1-го до -го.
Рис. 2.4. Схема логічного дерева
Крім того, представлення функцій у вигляді логічних дерев дає можливість провести їх мінімізацію, яка полягає в наступному [10]. Нехай є довільна функція та ряд функцій більш простого виду ніж . Наприклад - . Необхідно знайти таке представлення , щоб виконувалась рівність , де , фіксовано, а деякий оператор над . Оператор може бути представлений в довільній формі. Так, оператор може мати аналітичну або графічну форму. Метод дерева (графічна форма) не завжди дає мінімальну форму. Це залежить від розташування змінних по ярусам.
Для прикладу застосуємо метод дерева для мінімізації функції , яка задана в табличній формі (табл. 2.1).
Таблиця 2.1
Таблична форма
10111110000011110011001101010101 Спочатку візьмемо порядок розташування змінних по ярусам таким чином: 1-й ярус -; 2-й ярус - ; 3-й ярус - . Структура дерева при цьому буде наступною - рис. 2.5.
Рис. 2.5. Початкова структура логічного дерева функції
Знайдемо , враховуючи, що
;
;
;
;
.
Таке представлення початкової функції не буде її мінімальною формою. Змінимо порядок розташування змінних по ярусам дерева. Нехай 1-й ярус -; 2-й ярус - ; 3-й ярус - . В такому випадку дерево буде мати наступний вигляд - рис.2.6.
Рис. 2.6. Змінена структура логічного дерева функції
;
;
;
;
.
Саме таке представлення початкової функції і буде її мінімальною формою. Але кількість всіх дерев для функції рівна кількості перестановок , тобто при великому незручно, а іноді і неможливо перебирати всі можливі дерева. Виникає проблема знаходження саме тих логічних дерев заданої функції, які відповідають мінімальним формам або формам, близьким до них, а це потребує, в свою чергу, вивчення оцінок ефективності процесу перестановки аргументів.
Важливими перевагами методу дерева для мінімізації функції є те, що з деревом досить просто працювати при великій кількості аргументів . Крім того, дуже просто автоматизувати процес мінімізації за рахунок написання простої машинної програми. Вибір "найкращого" дерева також можна передати машині [41,42,43,44].
2.2. Оцінка ефективності перестановки ярусів в логічних деревах розпізнавання.
Як вже було сказано вище, кількість усіх бінарних дерев, які фактично е