розділ 2).
Алгоритмічні особливості розрахунку предикатів
Як було показано вище, формула, яка визначає логічне значення факту (предикат),
подається у вигляді ДНФ. Подібна формула складається з логічних операцій Op =
(&,Ъ, Ш) та фактів, логічні значення яких зберігаються у робочій пам’яті. При
чому можливим є використання спеціальних символів типу «?», які означають, що
необхідно визначити значення факту за допомогою інтерфейсу користувача, а також
гібридний спосіб визначення значення факту через використання запису
«?/предикат», який означає, що спочатку виконується спроба визначити значення
факту аналітично, а у разі неуспіху – з інтерфейсу користувача. Таким чином, у
процесі обчислення предиката, за алгоритмом визначається перший символ рядка
предиката. Якщо він «?», то обчислення переривається і повертається невідомий
факт. Інакше ведеться обчислення значення предиката. Підчас обчислення
аналізується можливість оптимізації типу: фл & 0 = 0 та фл Ъ 1 = 1, де фл –
логічне значення факту. Якщо ж в предикаті зустрічається невідомий факт
(логічне значення 1/2), рекурсивно викликається алгоритм обчислення для даного
невідомого факту у якості аргументу. Цикл обчислення продовжується до тих пір,
поки рядок з предикатом не буде порожній. Коли цикл завершується нормально (всі
логічні значення фактів біли відомі або обчислені), встановлюється логічне
значення факту. Відповідну блок-схему алгоритму ілюструє рис.3.4.
Рис. 3.4. Блок-схема алгоритму обчислення предиката факту.
Ідея, покладена в основу алгоритму, може бути розвинута за рахунок подальшого
аналізу структури предиката. Оскільки предикат є диз’юнкцією рівноправних
кон’юнкцій [82], то оптимізуючий обчислювач має змогу виконувати перегляд
кожної з них перед рекурсивним обчисленням в разі отримання факту з логічним
значенням 1/2, тобто:
фл==
фл=1, якщо ,
фл=0, якщо ,
де фл – логічна складова факту, який розраховується,
Ki – кон’юнкція значень фактів.
На кожному кроці обчислення предикату маємо сформовані кон’юнкції:
K=K0 K1 K1/2,
K0={?фл|фл=0}, K1/2={?фл|фл=1/2}, K1={?фл|фл=1}.
В такому випадку результат:
(3.1)
Отже, виявивши у предикаті , можемо скоротити час обчислення логічних значень
фактів та уникнути ставлення додаткових запитань користувачеві. В інших
випадках, коли неможливо задовольнити умови (3.1), виконується рекурсивне
обчислення невідомих значень фактів, які входять у кон’юнкції.
Алгоритмічні особливості обчислення числової формули
Однією з задач ПЗ є врахування разом із якісними, логічними залежностями
аналітичних, кількісних. Сучасні методики та моделі оцінки, аналізу рівня ЗІ,
як правило, передбачають розрахунок імовірнісних чинників, орієнтуються на
обчислення ефективності застосування тих чи інших засобів та заходів підтримки
ЗІ у АС, а також розраховують негативний вплив вразливостей та загроз ЗІ, який
виражено кількісно. Тому, модель і на її основі ПЗ щодо підтримки прийняття
рішень у галузі ЗІ у АС мають передбачати можливість виконання аналітичних
перетворень над фактами. У другому розділі було показано, що автоматна модель
передбачає наявність механізму розрахунку числової функції. Поняття факту як
інформаційної структури ПЗ включає як логічну так і числову складову, яка може
бути розрахована за допомогою формули, зв’язаною з фактом. Така формула може
включати стандартний набір алгебраїчних функцій та операцій (рис.2.2), а також
специфічні з огляду на галузь залежності, зокрема, агрегатні суму та добуток, а
також формулу імовірності незалежних подій. Агрегатна форма спрощує побудову
формули користувачем і, з іншого боку, дозволяє підвищити ступінь
універсальності алгоритму обчислення числової формули. Зазначимо, що формули не
є чисто арифметичними виразами, а виконують певні арифметико-логічні
перетворення.
Для обчислення величин, необхідних для виконання перетворень логічних складових
значень фактів, окрім стандартного набору арифметичних операцій (таких як
додавання, віднімання, зміни знаку операнда, множення, ділення, піднесення до
ступеню тощо), необхідним є набір стандартних функцій (таких як sin, cos, tg,
arcsin, arccos, arctg, ехр, ln, log, sqrt), а також певний набір спеціальних
функцій. Оскільки ПЗ оперує також імовірнісними характеристиками, доцільним є
включення спеціальних функцій для обчислення імовірностей. Прикладом такої
функції може бути функція обчислення імовірності незалежних подій:
де Х – множина аргументів (імовірності відповідних незалежних подій).
Аргументами цієї функції є перелік фактів або метафактів - груп фактів,
об’єднаних за деякою ознакою. Таке групування спрощує уведення функціональних
залежностей, а також дозволяє виконувати уточнення результату функції у процесі
одержання нових відомостей про конкретну АС. Наприклад, замість повного
переліку всіх фактів якогось розділу БЗ можливим є використання лише одного
метафакту “всі факти розділу”. Перелік можливих позначень метафактів наведено в
табл. 3.2.
Зазначимо, що аргументами агрегатних функцій можуть бути факти, метафакти,
функції, агрегатні функції та складені з них вирази.
Блок-схему алгоритму обчислення числової функції наведено у додатку А.
Таблиця 3.2
Перелік можливих метафактів
Позначення
Множина відповідних фактів БЗ
CGxxxx0
Всі екстенсійні факти певного типу з логічним значенням 0
CGxxxx1
Всі екстенсійні факти певного типу з логічним значенням 1
CGxxxx2
Всі екстенсійні факти певного типу з логічним значенням 0 або 1
CI0
Екстенсійні факти з логічним значенням 0
CI1
Екстенсійні факти з логічним значенням 1
CI2
Екстенсійні факти з логічним значенням 0 або 1
PM0
Факти розділу підвищення рівня ЗІ з логічним значенням 0
PM1
Факти розділу підвищення рівня ЗІ з логічним значенням
- Київ+380960830922