Логіко-обчислювальна семантична мережа як модель подання знань

Размещено на http://www.allbest.ru/

Національна академія наук України

Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова

Автореферат

дисертації на здобуття наукового ступеня

доктора технічних наук

Спеціальність 01.05.02 - Математичне моделювання та обчислювальні методи

Логіко-обчислювальна семантична мережа як модель подання знань

Яловець Андрій Леонідович

Київ 2008

Дисертацією є рукопис.

Робота виконана в Інституті проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України

Науковий консультант: доктор технічних наук, професор Кондращенко Володимир Якович, Інститут проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України, завідувач відділу

Офіційні опоненти: доктор фізико-математичних наук, професор, член-кореспондент НАН України Перевозчикова Ольга Леонідівна, Інститут кібернетики ім. В.М.Глушкова НАН України, завідувач відділу автоматизації програмування;

доктор фізико-математичних наук, професор, заслужений діяч науки і техніки України Анісімов Анатолій Васильович, Київський національний університет імені Тараса Шевченка, декан факультету кібернетики;

доктор технічних наук, професор Тоценко Віталій Георгійович, Інститут проблем реєстрації інформації НАН України, завідувач відділу аналітичних методів інформаційних технологій.

Захист відбудеться “28” лютого 2008 р. о 14 годині на засіданні спеціалізованої вченої ради Д 26.185.01 Інституту проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України за адресою: 03164, м.Київ-164, вул. Генерала Наумова, 15.

З дисертацією можна ознайомитись у бібліотеці Інституту проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України за адресою: 03164, м.Київ-164, вул. Генерала Наумова, 15.

Автореферат розісланий “ 23 ” січня 2008 р.

Вчений секретар спеціалізованої вченої ради Д 26.185.01 Семагіна Е.П.

1. Загальна характеристика роботи

знання верифікація семантичний мережа

Актуальність теми. В останні десятиріччя сформувалась і отримала потужний розвиток нова методологія наукових досліджень - методологія математичного моделювання. Сутність даної методології полягає у переході від об'єкта, що вивчається, до його математичної моделі і дослідженні отриманої математичної моделі за допомогою сучасних обчислювальних засобів. Робота не з самим об'єктом (явищем, процесом), а з його математичною моделлю дозволяє досліджувати властивості та поведінку об'єкта в будь-яких можливих ситуаціях. В той же час обчислювальні експерименти над математичними моделями об'єктів дозволяють, спираючись на потужність сучасних обчислювальних методів, детально та глибоко вивчати досліджувані об'єкти з достатньою повнотою, недоступною сугубо теоретичним підходам. Завдяки цьому методологія математичного моделювання бурхливо розвивається, охоплюючи нові напрямки досліджень - від розробки великих технічних систем і управління ними, до аналізу складних економічних, соціальних і природних процесів, в тому числі і процесів, пов'язаних з проблематикою штучного інтелекту.

На сьогоднішній день однією з центральних і найбільш складних проблем математичного моделювання в галузі штучного інтелекту (ШІ) є проблема подання та обробки знань, де неформально під знаннями розуміється сукупність відомостей, утворюючих цілісний опис об'єктів досліджуваної предметної області (ПО) та відношень між ними. Складність даної проблеми полягає в її комплексності, пов'язаної з тим, що рішення проблем подання знань не може і не повинно розглядатися у відриві від рішення проблем обробки знань, і навпаки.

Для рішення проблем подання знань використовуються спеціалізовані математичні моделі (що називаються моделями подання знань (МПЗ)), основною вимогою, що пред'являється до яких, є адекватність їх властивостей природним властивостям знань. Для досягнення такої адекватності МПЗ повинна задовольняти, принаймні, загальним вимогам, у відповідності до яких повинна дозволяти:

· подавати як декларативні, так і процедурні знання;

· подавати як чіткі, так і нечіткі знання;

· подавати ієрархічну структуру знань;

· подавати знання в термінах природної мови;

· подавати логічні операції;

· подавати семантичні відношення досліджуваної ПО.

На сьогоднішній день існує чотири основних МПЗ: логічна модель, продукційна модель, фреймова модель і модель семантичної мережі Куілліана. Незважаючи на те, що перелічені МПЗ мають ряд переваг, завдяки яким вони знайшли використання при розробці різноманітних систем, заснованих на знаннях (СЗЗ), нажаль, жодна з них одночасно не задовольняє всім вище переліченим загальним вимогам. Як наслідок, очевидна актуальність задачі розробки нової МПЗ, яка задовольняла би множині перелічених вимог. Одним з можливих шляхів вирішення цієї задачі є використання методології математичного моделювання для виконання аналізу природних властивостей знань з метою розробки такої МПЗ. Звідси випливає необхідність проведення досліджень з використання та розвитку методології математичного моделювання для розробки нової моделі подання знань.

Для рішення проблем обробки знань використовуються обчислювальні методи, до яких, в загальному випадку, можна віднести методи логічного виводу на поданих знаннях, а також методи верифікації і тестування поданих знань. Такі обчислювальні методи, як правило, мають спеціалізований характер, оскільки вони призначені для виконання обробки знань, поданих за допомогою цілком визначеної МПЗ. Як наслідок, в процесі рішення задачі розробки МПЗ виникають додаткові (й не менш важливі) актуальні задачі розробки спеціалізованих методів обробки знань, серед яких особливе місце займає задача розробки метода логічного виводу, яка не може розглядатись без врахування властивостей класу задач, вирішуваних на знаннях, поданих за допомогою МПЗ, що розробляється. Так, у відповідності до класифікації Д.Пойа існує два достатньо загальних класи задач: задачі на знаходження і задачі на доказ. За своїми властивостями названі класи задач є діаметрально протилежними: якщо задачі на знаходження характеризуються тим, що явно задані вхідні дані і невідомий шуканий об'єкт, і необхідно знайти невідомий шуканий об'єкт, який задовольняє умовам задачі, то задачі на доказ - тим, що відомі як умови задачі, так і шуканий об'єкт, і необхідно довести, що шуканий об'єкт визначається з умов задачі. Слід підкреслити, що задачі на знаходження складають клас практично значимих задач, рішення яких вимагає використання методів і засобів ШІ. Внаслідок цього актуальним є вибір класу задач на знаходження у якості досліджуваного класу задач. Виходячи з властивостей названих класів задач, для рішення задач на знаходження доцільно використовувати прямий („від даних”) вивід, в той час як для рішення задач на доказ - зворотний („від цілі”) вивід. При цьому, на відміну від методів зворотного виводу, достатньо глибоко теоретично досліджених і широко використовуваних при побудові СЗЗ, методи прямого виводу вимагають свого розвитку як в теоретичному, так і в прикладному напрямках. Виходячи з цього, актуальною є задача розробки методу прямого виводу на знаннях, поданих за допомогою МПЗ, що розробляється.

Таким чином, очевидна актуальність задачі використання і розвитку методології математичного моделювання для створення нової моделі подання знань і розробки методів обробки знань, поданих за допомогою даної моделі подання знань.

Зв'язок роботи з науковими програмами, планами, темами. Дослідження по дисертаційній роботі виконувались у відповідності з планами науково-дослідних робіт Інституту проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України в рамках наступних науково-дослідних тем: „Адаптивні методи та засоби оптимізації і моделювання складних систем мережової топології” (шифр - Циклод-3), РК №0199U000258 (1999-2001р.р.), виконавець; „Методи та засоби моделювання, логічного виведення та оптимізації для організаційно-технічних систем з складною сітьовою структурою внутрішньосистемних відношень та масоенергетичних потоків” (шифр - Циклод-4), РК №0102U000902 (2002-2004р.р.), виконавець; „Розробка методів та комп'ютерних засобів підтримки прийняття рішень в задачах ситуаційного та технологічного управління в енергетиці” (шифр - Управління), РК №0102U005589 (2002-2006р.р.), відповідальний виконавець розділу.

Мета і завдання дослідження. Мета роботи полягає в розробці теоретичних основ моделювання процесів подання та обробки знань, в тому числі моделі подання знань та методів їх обробки, та створенні на їх базі програмно-інструментального середовища подання та обробки знань.

Для досягнення поставленої мети необхідно вирішити наступні задачі:

· Розробити модель подання знань. Для цього:

– виконати аналіз природних властивостей декларативних і процедурних знань з метою виявлення структурних, логічних, семантичних і обчислювальних властивостей, які повинна мати модель подання знань, що розробляється;

– побудувати математичну модель, яка би мала множину виявлених властивостей.

· Розробити методи обробки знань, а саме:

– метод прямого логічного виводу;

– метод побудови початкового стану процесу прямого логічного виводу;

– методи статичної верифікації поданих знань;

– методи генерації множини тестових випадків на поданих знаннях.

· На основі розроблених моделі подання знань і методів обробки знань створити програмно-інструментальне середовище подання і обробки знань.

Об'єкт дослідження - подання і обробка знань.

Предмет дослідження - модель подання знань і методи обробки знань.

Методи дослідження. Для досягнення поставленої мети в роботі були використані: методи математичного моделювання, методи логічної семантики, методи формальної логіки, методи штучного інтелекту, методи теорії алгоритмів (всі перелічені методи використані для розробки моделі подання знань), методи математичної логіки (для розробки моделі подання знань і метода побудови мінімальної позитивної моделі), методи теорії моделей (для розробки метода побудови мінімальної позитивної моделі), методи теорії логічного виводу (для розробки метода виводу), методи теорії доказів (для розробки метода виводу і методів виявлення нерозв'язних неводів), методи теорії множин (для розробки моделі подання знань, метода виводу, методів статичної верифікації, метода підрахунку кількості тестових випадків, метода генерації множини тестових випадків), методи теорії графів (для розробки моделі подання знань, метода виводу, метода побудови мінімальної позитивної моделі, методів статичної верифікації, метода генерації множини тестових випадків).

Наукова новизна одержаних результатів. Розроблено теоретичні основи моделювання процесів подання та обробки знань і одержано нове комплексне рішення проблеми подання і обробки знань, що включає в себе розробку нових моделі подання знань та сукупності методів обробки знань, які дозволяють забезпечити не тільки виконання виводу на знаннях, а й рішення задач статичної верифікації і емпіричного тестування поданих знань. В рамках одержаного комплексного рішення:

1. Розроблено нову модель подання знань, що названа логіко-обчислювальною семантичною мережею (ЛОС-мережею), в якій реалізовано структурні, логічні, семантичні та обчислювальні властивості, що виявлені в результаті аналізу природних властивостей декларативних і процедурних знань, завдяки чому ЛОС-мережа отримала нову сукупність функціональних можливостей, одночасно не притаманних іншим відомим МПЗ.

2. Розроблено метод прямого логічного виводу, що є єдиним методом виводу як на чітких, так і на нечітких процедурно-декларативних знаннях, поданих у ЛОС-мережі, який засновується не на переборі вершин, потенційно придатних для виконання виводу, а на процедурі аналізу поточного стану процесу пошуку виводу і формуванні множин вершин ЛОС-мережі, з кожної з яких безпосередньо вивідна деяка раніше не виведена вершина, що у сукупності вигідно відрізняє розроблений метод виводу від інших відомих методів виводу на знаннях.

3. Вперше розроблено метод побудови початкового стану процесу прямого логічного виводу, що дозволяє виключити можливість завдання суперечних, неповних або надлишкових вхідних даних при описі ситуації для рішення проблемних задач на ЛОС-мережі.

4. Розроблено методи статичної верифікації знань, поданих у ЛОС-мережі. На відміну від відомих методів статичної верифікації баз знань, які дозволяють виявляти аномалії (можливі помилки в базі знань), розроблені методи дозволяють виявляти фактичні помилки в поданих знаннях.

5. Розроблено метод генерації множини тестових випадків для ЛОС-мережі. На відміну від відомих методів генерації множини тестових випадків, що допускають помилки в процесі генерації тестової множини, розроблений метод дозволяє правильно формувати множину тестових випадків, що необхідно для виконання емпіричного тестування знань, поданих у ЛОС-мережі.

Практичне значення одержаних результатів. Розроблені в дисертаційній роботі модель подання знань і методи обробки знань реалізовано у програмно-інструментальному середовищі подання і обробки знань (шифр - СЛМ-технологія), що підтримує процеси подання і обробки як чітких, так і нечітких процедурно-декларативних знань, і призначена для рішення задач, що зводяться до задач на знаходження. На відміну від відомих систем і середовищ подання та обробки знань, СЛМ-технологія автоматично виконує статичну верифікацію (в тому числі і перевірку несуперечності) поданих знань і забезпечує автоматичне генерування множини тестових випадків, що необхідно для виконання емпіричного тестування поданих знань. СЛМ-технологія є завершеним програмним продуктом, повністю готовим для широкого практичного застосування.

СЛМ-технологія використовується для вирішення прикладних задач: в Управлінні планування та моніторингу Головного управління МНС в Запорізькій області (де використовується для рішення задач реагування на розлив небезпечних речовин) та в НДЦ „ТЕЗІС” НТУУ „КПІ” (де використовується для розробки системи підтримки прийняття рішень). Крім того, результати дисертаційних досліджень (в тому числі і СЛМ-технологія) впроваджено в навчальний процес: в Національному університеті харчових технологій і в Національному університеті „Києво-Могилянська академія”.

Особистий внесок здобувача. В роботах, написаних у співавторстві, автору належать: в [5] - всі результати, за винятком реалізації систем МЕТОД і ПРИЗМА, авторство на які належить д.т.н., професору Кондращенко В.Я.; в [18] - методика, що покладена в основу оцінки часової складності алгоритму виводу; виконання оцінки часової складності алгоритму.

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідались і обговорювались на Міжнародній конференції з управління “Автоматика-2000” (м.Львів, 2000р.), Міжнародній конференції “Искусственный интеллект-2000” (м.Кацивелі, 2000р.), Міжнародному семінарі “Фундаментальные и прикладные проблемы мониторинга и прогноза стихийных бедствий” (Стихия-2001) (м.Севастополь, 2001р.), Російсько-українському науковому семінарі “Интеллектуальный анализ информации” (ИАИ-2002) (м.Київ, 2002р.), Міжнародному семінарі “Фундаментальные и прикладные проблемы мониторинга и прогноза стихийных бедствий” (Стихия-2002) (м.Севастополь, 2002р.), Міжнародній науково-практичній конференції “Искусственный интеллект-2002” (м.Кацивелі, 2002р.), Російсько-українському науковому семінарі “Интеллектуальный анализ информации” (ИАИ-2003) (м.Киев, 2003р.), Міжнародній конференції “Информационные технологии в управлении энергетическими системами” (ИТУЭС-2005) (м.Киев, 2005р.), конференції “Моделирование-2006” (м.Київ, 2006р.), Десятой национальной конференции по искусственному интеллекту с международным участием КИИ-2006 (м.Обнінськ, Росія, 2006р.), а також на щорічних науково-технічних конференціях Інституту проблем моделювання в енергетиці ім. Г.Є.Пухова НАН України в 2000-2004р.р.

Публікації. Результати дисертації опубліковані в 41 роботі, в тому числі: в 36 статтях в професійних наукових журналах і збірниках наукових праць, що входять до переліку, затвердженому ВАК України, та в 5 публікаціях в матеріалах конференцій. До автореферату дисертації включено 30 основних публікацій, виданих в фахових наукових журналах і збірниках наукових праць, що входять до переліку, затвердженому ВАК України.

Структура та обсяг дисертації. Дисертація складається із вступу, 9 розділів, висновків, списку використаних джерел та 18 додатків, які видані окремою книгою. Загальний обсяг роботи складає 366 сторінок. Дисертація містить 102 рисунки та 24 таблиці, що займають 33 сторінки. Список використаних джерел включає 290 найменувань на 25 сторінках. Обсяг додатків складає 198 сторінок.

2. Основний зміст роботи

У вступі обґрунтовано актуальність напрямку досліджень, відзначено зв'язок дисертаційної роботи з науковими програмами, планами, темами, сформульовано мету і завдання досліджень, визначено методи досліджень, викладено наукову новизну і практичне значення одержаних результатів, наведено відомості про апробацію результатів роботи та про публікації.

У розділі 1 виконано аналітичний огляд сучасного стану досліджень з питань подання та обробки знань і проаналізовано основні проблеми математичного моделювання подання та обробки знань. Обґрунтовано актуальність розробки нових моделі подання знань та методів обробки знань (в тому числі методу логічного виводу на знаннях і методів статичної верифікації та емпіричного тестування поданих знань). Обґрунтовано актуальність створення моделюючого середовища подання та обробки знань, яке повинно спиратися на модель подання знань та методи обробки знань, що розробляються в дисертаційній роботі. Визначено місце дисертаційних досліджень серед основних напрямів досліджень, присвячених проблемам подання та обробки знань.

Обґрунтовано актуальність вибору класу задач на знаходження (за класифікацією Д.Пойа) у якості класу задач, досліджуваного у дисертаційній роботі. Відзначено, що до задач на знаходження зводяться такі відомі категорії задач, як діагностика, інтерпретація, класифікація, моніторинг, ремонт, оцінка, прогноз. Показано, що для рішення задач на знаходження доцільно використовувати прямий („від даних”) метод логічного виводу.

Встановлено, що моделлю подання знань, яку доцільно розглядати як базову МПЗ, що потребує розвитку логічних та обчислювальних властивостей, є модель семантичної мережі Куілліана. Виконано аналітичний огляд одинадцяти відомих моделей подання знань, що є розвитком моделі семантичної мережі Куілліана, на основі якого виявлено множину вимог до моделі подання знань, що необхідно розробити. До таких вимог належать: можливість подання знань в термінах природної мови; можливість подання процедурно-декларативних знань; можливість подання як чітких, так і нечітких знань; можливість подання логічних операцій; можливість подання кванторів; можливість подання екстенсіоналу та інтенсіоналу; можливість розпізнавання суперечностей в поданих знаннях; однорідність моделі; забезпечення цілісності подання знань; наочність опису знань; можливість об'єднання структур знань. Показано, що жодна відома МПЗ одночасно не задовольняє всім наведеним вимогам.

Проаналізовано проблеми, що притаманні відомим методам прямого виводу на знаннях. Обґрунтовано актуальність задачі розробки метода побудови початкового стану процесу прямого виводу. Проаналізовано основні підходи з організації процесу прямого виводу на знаннях, поданих за допомогою відомих МПЗ (в тому числі і мережних МПЗ), на основі чого сформульовано множину вимог до методу прямого виводу, який необхідно розробити. Виходячи з цих вимог, метод виводу повинен: засновуватись на аналізі поточного стану процесу пошуку виводу і на кожному кроці виводу оптимізувати вибір таких екземплярів знань, з яких гарантовано вивідні раніше не виведені екземпляри знань; засновуватись на ефективній процедурі виводу; бути уніфікованим і універсальним, тобто єдиним методом виводу як на чітких, так і на нечітких процедурно-декларативних знаннях.

Розглянуто проблему валідації і верифікації (V&V) СЗЗ. Показано, що на сьогоднішній день відомі методи V&V СЗЗ призначені для рішення задач статичної верифікації та емпіричного тестування продукційних СЗЗ.

Виконано аналітичний огляд відомих методів та програмних засобів статичної верифікації продукційних СЗЗ, по результатах якого сформульовано множину вимог до методів статичної верифікації, що необхідно розробити. Виходячи з цих вимог, методи статичної верифікації повинні: дозволяти виявляти фактичні (а не можливі) помилки в поданих декларативних і процедурних знаннях; не передбачати завдання користувачем будь-яких додаткових метазнань (семантичних обмежень); не засновуватись на використанні механізму логічного виводу. Показано, що відомі методи статичної верифікації одночасно не задовольняють всім наведеним вимогам.

Виконано аналітичний огляд відомих методів та програмних засобів емпіричного тестування продукційних СЗЗ. Виконано порівняльний аналіз відомих систем емпіричного тестування, на основі якого сформульовано множину вимог до методів формування множини тестових випадків, які необхідно розробити. Виходячи з цих вимог, методи формування множини тестових випадків повинні: забезпечувати правильне формування множини тестових випадків в БЗ, що містить процедурно-декларативні знання, подані за допомогою МПЗ, що необхідно розробити; ґрунтуватися на методах генерації множини шляхів виводу, що існують в БЗ. Показано, що відомі методи формування множини тестових випадків одночасно не задовольняють всім наведеним вимогам.

Викладено вимоги до створюваного моделюючого програмно-інструментального середовища (інструментального засобу (ІЗ)) подання та обробки знань, що включають вимоги до ІЗ як зі сторони використовуваних моделі подання знань і методів обробки знань, що розробляються в дисертації, так і зі сторони побудови ергономічного середовища подання та обробки знань.

На основі виконаного огляду сформульовано задачі досліджень.

У розділі 2 з метою побудови моделі подання знань, яка б мала множину властивостей, притаманних знанням як таким, виконано аналіз природних властивостей декларативних і процедурних знань, в процесі якого вирішувались три задачі:

1). Виявлення основних властивостей структури декларативних знань, як структури, що відображає семантичні відношення, що існують між об'єктами довільної ПО, та структури процедурних знань, як структури, що відображає відношення, що існують, з одного боку, між задачами довільної ПО, з іншого боку, між параметрами, що визначаються в результаті рішення таких задач. Мета рішення цієї задачі полягає в виявленні вимог, які необхідно пред'явити до структурних властивостей МПЗ, що розробляється.

2). Дослідження властивостей імен вершин, що входять до складу структури декларативних (процедурних) знань. Мета рішення цієї задачі полягає в виявленні вимог, які необхідно пред'явити до імен, що вибираються для іменування вершин структури знань, поданих за допомогою МПЗ, що розробляється.

3). Дослідження логічної структури імен, зіставлених вершинам, що входять до складу структури декларативних (процедурних) знань. Мета рішення цієї задачі полягає в виявленні сукупності логічних операцій, які необхідно зіставити вершинам МПЗ, що розробляється, для досягнення адекватного подання логічної структури знань.

З метою рішення сформульованих задач для декларативних знань, виконано аналіз їх властивостей, заснований на теоретичних положеннях логічної семантики.

В результаті вирішення задачі (1) встановлено, що структура декларативних знань, що описують довільну ПО, подається у вигляді простого однонаправленого кінцевого зв'язного ациклічного графа мережної ієрархічної структури.

В результаті вирішення задачі (2) встановлено, що будь-яке ім'я, що включається у якості імені вершини в структуру декларативних знань, повинно бути однозначно інтерпретованим і повинно однозначно визначати об'єкт, що їм позначається, виражаючи узагальнений смисл, що міститься в інших іменах, які можуть бути застосовані для позначення об'єкту.

В процесі рішення задачі (3) досліджено особливості подання логічної структури імен (у якості яких можуть виступати слова (словосполучення) або речення), зіставлених вершинам, що входять до структури декларативних знань. Введено і досліджено поняття інтенсіоналу та екстенсіоналу імен.

Обґрунтовано, що для подання логічної структури імені, що є словом (словосполученням), необхідно і достатньо трьох логічних операцій: повної диз'юнкції (), кон'юнкції (&) та заперечення (), де операція вводиться як частка (або приставка) „не” до імені. Логічна операція повної диз'юнкції є n-арною (де n 2), і має наступну формулу еквівалентних перетворень:

тільки одна з підформул Ai (i = 1,n), що до неї входять.

На основі узагальнення результатів рішення задач (1) (3) показано, що структура декларативних знань про довільну ПО може бути подана у вигляді простого ациклічного кінцевого зв'язного однонаправленого графа ієрархічної мережної структури, в якому кожна вершина має ім'я, яке позначає цілком визначений об'єкт ПО; кожній нетермінальній вершині ставиться у відповідність цілком визначена логічна операція, що належить до системи операцій ,&); вершині може бути зіставлена операція заперечення, яка вводиться як частка (або приставка) „не” до імені вершини.

З метою рішення трьох вище сформульованих задач для процедурних знань, виконано аналіз властивостей цих знань, що ґрунтувався на узагальненні відомого підходу, заснованого на редукції задач на взаємно незалежні підзадачі з побудовою І/АБО-графу, де редукція задач виконувалась до рівня вхідних параметрів, необхідних для рішення задач (підзадач).

В результаті вирішення задачі (1) встановлено, що структура процедурних знань про довільну ПО може бути подана у вигляді простого однонаправленого кінцевого зв'язного графа мережної ієрархічної структури.

В процесі рішення задачі (2) властивості імен вершин, що входять до складу структури процедурних знань, досліджено з двох сторін: зі сторони іменування вершин за допомогою імен параметрів, що визначаються в результаті рішення задач, зіставлених вершинам, та зі сторони іменування вершин за допомогою імен методів, використовуваних для рішення задач, зіставлених вершинам.

В результаті вирішення задачі (3) доведено, що для подання логічної структури процедурних знань необхідно і достатньо двох логічних операцій: ,&).

На основі узагальнення результатів рішення задач (1) (3) показано, що структура процедурних знань про довільну ПО може бути подана у вигляді простого кінцевого зв'язного однонаправленого графа ієрархічної мережної структури, в якому кожна вершина має ім'я, яке позначає цілком визначений об'єкт ПО; кожній нетермінальній вершині ставиться у відповідність цілком визначена логічна операція, що належить до системи операцій ,&); кожній нетермінальній вершині ставиться у відповідність ім'я метода, вихідним параметром якого є ім'я даної вершини.

В результаті узагальнення вище виявлених властивостей декларативних і процедурних знань сформульовано основні властивості моделі подання знань, що необхідно розробити. Виходячи з наявних властивостей моделі подання знань, введено і обґрунтовано її назву - логіко-обчислювальна семантична мережа.

У розділі 3 наведено визначення логіко-обчислювальної семантичної мережі (ЛОС-мережі), виконано формалізацію властивостей вершин ЛОС-мережі, надано приклади подання знань в ЛОС-мережі та виконано порівняння функціональних можливостей ЛОС-мережі і трьох інших відомих різновидів семантичних мереж.

Визначення 3.1. Під логіко-обчислювальною семантичною мережею LCSN=(V,E,Д) розуміється простий ациклічний однонаправлений кінцевий зв'язний граф, який має наступні властивості.

Існує дві суттєві відмінності властивостей дуг ЛОС-мережі від властивостей дуг в більшості інших відомих різновидах семантичних мереж.

По-перше, дуги в ЛОС-мережі є непоміченими (тобто їм не ставиться у відповідність сутність відображуваного відношення - типу “is-a”, “part-of” і т.п.). Змістовна інтерпретація відношень, що моделюються за допомогою дуг, в кожному конкретному випадку стає зрозумілою з контексту, що відображається в структурі ЛОС-мережі.

По-друге, на відміну від більшості різновидів відомих семантичних мереж (що представляють собою орієнтовані графи, в яких орієнтація дуг може бути довільною), ЛОС-мережа є однонаправленим графом.

Множина імен термінальних вершин (вершин типа 0) ЛОС-мережі відповідає універсуму вхідних параметрів, за допомогою яких виконуваний опис різноманітних ситуацій в досліджуваній ПО. Інші вершини (вершини типа 1 5) можуть виступати тільки у якості нетермінальних вершин ЛОС-мережі.

Вершини типа 1 називаються логічними І-вершинами, а вершини типа 2 - логічними АБО-вершинами. За допомогою вершин типа 1 (типа 2) подається інтенсіонал (екстенсіонал) імені релевантної логічної І-вершини (АБО-вершини), який включає до свого складу множину імен вершин, суміжних даній І-вершині (АБО-вершині) по дугах, що в неї заходять. Показано, що для адекватного подання декларативних знань в ЛОС-мережі необхідно і достатньо трьох типів вершин: типа 0, типа 1 та типа 2.

Для подання процедурних знань введено вершини типа 3, 4 і 5. Вершина типа 3 називається обчислювальною І-вершиною. Сутність цієї вершини подібна сутності вершини типа 1 з тією різницею, що вершині типа 3 зіставлений обчислювальний метод. Вершина типа 4 називається умовною І-вершиною, а вершина типа 5 - ітераційною І-вершиною.

Для опису властивостей введених типів вершин коротко розглянемо особливості реалізації в них вище перелічених засобів опису програм.

Оператор присвоювання є властивим для всіх типів вершин і виконується в результаті завдання вершини у якості вхідного параметру (для вершини типа 0) або виведення вершини (для інших типів вершин).

Механізм виклику процедур є властивим для вершин типа 3 і типа 4.

Інші засоби опису програм (тобто умовний оператор і оператор переходу, а також оператор циклу) реалізуються у рамках наступних сполучень алгоритмів: послідовна композиція, паралельна композиція, розгалуження та повторне використання. Коротко розглянемо особливості програмування перелічених типів сполучень алгоритмів в структурі ЛОС-мережі.

Під повторним використанням алгоритму розуміється повторення використання алгоритму до поточних даних до тих пір, поки виконується деяка умова Ф (де під Ф розуміється деякий розпізнаючий алгоритм). Програмування повторного використання алгоритму в ЛОС-мережі полягає в побудові композиції вершин, яка включає одну вершину типа 4, одну або декілька вершин типа 3 і одну вершину типа 5. Вершина типа 5 є ітераційною І-вершиною.

Виходячи з вищевикладеного, показано, що для адекватного подання процедурних знань в ЛОС-мережі необхідно і достатньо п'яти типів вершин: типа 0, типа 2, типа 3, типа 4 і типа 5.

Наведено приклади подання декларативних та процедурних знань в ЛОС-мережі (приклад подання процедурно-декларативних знань в ЛОС-мережі). Виконано порівняння функціональних можливостей ЛОС-мережі та пропозиціональної семантичної мережі (S.C.Shapiro), процедурної семантичної мережі (H.Levesque, J.Mylopoulos) і блочної семантичної мережі (G.G.Hendrix) на конкретних прикладах подання знань. Продемонстровано, що ЛОС-мережа за своїми функціональними можливостями перевершує перелічені мережні моделі.

Показано, що ЛОС-мережа задовольняє всім пред'явленим до неї вимогам.

У розділі 4 побудовано обчислення, що формалізує логічні властивості ЛОС-мережі, виконано формалізацію структури ЛОС-мережі, формалізовано поняття логічного виводу та викладено метод прямого виводу на ЛОС-мережі.

У відповідності до визначення 3.1, ЛОС-мережа представляє собою орграф з вищевикладеними властивостями, до структури якого входить множина V вершин, де

V=Vt * Vnt; Vt -

кінцева множина термінальних вершин ЛОС-мережі, Vnt - кінцева множина нетермінальних вершин ЛОС-мережі,

Множина Vt включає вершини, імена яких є елементарними іменами досліджуваної ПО, які не мають власної логічної структури в рамках досліджуваної ПО і безпосередньо позначають відповідні об'єкти досліджуваної ПО. Ідентифікатори термінальних вершин, імена яких не містять заперечення (частки (або приставки) „не”), будемо називати атомами. Атом або заперечення атома будемо називати літералом. Як наслідок, ідентифікатор будь-якої термінальної вершини є літералом.

Множина Vnt включає вершини, імена яких є складними іменами, тобто такими, що мають власну логічну структуру в рамках досліджуваної ПО. Будь-яке складне ім'я може бути сформовано з елементарних імен шляхом зв'язування їх логічними операціями, що належать базису ,&,). Як наслідок, кожній нетермінальній вершині ЛОС-мережі може бути поставлена у відповідність деяка формула, побудована з атомів, зв'язаних між собою логічними операціями, що належать базису. В зв'язку з тим, що ідентифікатори вершин мають складну структуру, для позначення формул будемо використовувати прописні готичні букви: A, B, C, … (можливо, з індексами).

Побудовано C-обчислення, що формалізує логічні властивості ЛОС-мережі. Задано алфавіт (множину символів) C-обчислення, визначено правила утворення формул C-обчислення та введено правила висновку для C-обчислення.

Знаки, що використані для побудови C-обчислення, поділяються на дві групи: (1) символи; (2) формули - кінцеві послідовності символів.

1. Символи

1.1. Логічні символи: повна диз'юнкція ; кон'юнкція &; заперечення .

1.2. Ідентифікатори: множина букв A, B, C, … (можливо, з індексами).

1.3. Допоміжні символи: ліва скобка ( , права скобка ) .

2. Формули

Формулою C-обчислення будемо називати вираз, що задовольняє наступному індуктивному визначенню:

Атом є формулою.

Якщо A - формула, то (A) - формула.

Якщо A1, …, An - формули, то (A1 & … & An), - формули, де n - натуральне число.

Інших правил утворення формул немає.

Будь-якій вершині ЛОС-мережі можна поставити у відповідність цілком визначену формулу C-обчислення, і навпаки. Покажемо це на прикладі довільної ЛОС-мережі, зображеної, в якій вершинам B3 і D зіставлена операція повної диз'юнкції (про що свідчать „дужки”, які зв'язують дуги, що заходять в ці вершини), а вершинам B1, B2, C - логічна операція кон'юнкції. Наприклад, вершина B3 подає в структурі ЛОС-мережі формулу. В свою чергу, вірно і зворотне, тобто наведена формула подана в структурі ЛОС-мережі за допомогою вершини B3. В цілому формула, яка відповідає всій ЛОС-мережі, заміщується формулою D

Як слідує з (2), скобки в формулах відображають порядок входження підформул у формули.

Поняття підформули формули C-обчислення визначається індуктивно:

A є підформула формули A;

Якщо (B1&…&Bn), є підформула формули A, то (B1,…,Bn) є підформулами формули A;

Інших правил утворення підформул немає.

На основі вищевикладених положень виконано формалізацію структури ЛОС-мережі. Оскільки будь-якій вершині ЛОС-мережі може бути поставлена у відповідність деяка цілком визначена заміщуюча формула, що позначається ідентифікатором такої вершини, і враховуючи, що ЛОС-мережа являє собою зв'язний орграф, показано, що структура ЛОС-мережі може бути адекватно описана за допомогою множини відображень виду: Ai>{B1,…,Bm}, де Ai - ідентифікатор довільної вершини ЛОС-мережі (iI; I=card(V)); B1,…,Bm - ідентифікатори вершин, суміжних вершині Ai по дугах, що з неї виходять.

Для виконання формалізації поняття логічного виводу для C-обчислення введемо ряд допоміжних понять і визначень.

Визначимо поняття нелогічної аксіоми стосовно до C-обчислення. Для цього визначимо поняття інтерпретації для формул C-обчислення: під інтерпретацією розуміється таке приписування значень істинності літералам, при якому кожний з них приймає логічне значення „істина” (І) або „хиба” (Х), але не те і інше одночасно. Тоді будь-який літерал, що прийняв в даній інтерпретації логічне значення І, будемо називати нелогічною аксіомою (далі - аксіомою).

Введемо поняття фрагмента ЛОС-мережі. Для цього виконаємо розріз ЛОС-мережі з формуванням m орієнтованих кореневих дерев, у яких всі дуги орієнтовані до кореня і довжина шляхів будь-якої дуги дорівнює 1, де

m=card(Vnt)

Кожне таке ордерево будемо називати фрагментом. Корінь фрагмента будемо називати кореневою вершиною фрагмента. Вершини фрагмента, суміжні його кореневій вершині, будемо називати висячими вершинами фрагмента.

Будемо називати фрагмент, кореневій вершині якого зіставлена логічна операція &, кон'юнктивним фрагментом, а фрагмент, кореневій вершині якого зіставлена логічна операція , диз'юнктивним фрагментом.

Будемо говорити, що корінь будь-якого фрагмента відповідає породжуваній формулі, а будь-яка висяча вершина фрагмента - породжуючій формулі.

Поняття безпосередньо вивідної формули (в рамках C-обчислення) визначається індуктивно:

Породжувана формула мінімального кон'юнктивного фрагмента є безпосередньо вивідною, якщо кожна її породжуюча формула є аксіомою.

Породжувана формула мінімального диз'юнктивного фрагмента є безпосередньо вивідною, якщо одна і тільки одна її породжуюча формула є аксіомою.

Породжувана формула не мінімального кон'юнктивного фрагмента є безпосередньо вивідною, якщо кожна її породжуюча формула є або аксіомою, або безпосередньо вивідною формулою нижче розташованого фрагмента.

Породжувана формула не мінімального диз'юнктивного фрагмента є безпосередньо вивідною, якщо одна і тільки одна її породжуюча формула є або аксіомою, або безпосередньо вивідною формулою нижче розташованого фрагмента.

Будь-яка формула є безпосередньо вивідною тільки в силу п.п.1-4.

Відношення, що існують між породжуючими формулами і безпосередньо вивідною формулою, формалізуються за допомогою правил висновку. Розрізняються правила висновку для кон'юнктивного і диз'юнктивного фрагмента. Показано, що правила висновку формалізують відношення вивідності формули B з формул A1,…,Ak (символічно: A1,…,Ak |- B), де значення k залежить від виду правила висновку. Таким чином, отримання безпосередньо вивідної формули пов'язано з застосуванням одного з правил висновку до деякої множини породжуючих формул.

На основі визначених понять формалізовано поняття логічного виводу для ЛОС-мережі. Будемо говорити, що безпосередньо вивідна вершина idvi є розв'язною, якщо метод, зіставлений цій вершині, успішно виконано (де під idvi розуміється ідентифікатор вершини vi Vnt).

Поняття виводу для ЛОС-мережі можна визначити наступним чином: вивід з множини О0 аксіом є послідовність вершин, така, що кожна вершина, яка входить в цю послідовність, є або однією з аксіом множини О0, або розв'язною вершиною, безпосередньо вивідною по одному з правил висновку з вершин, що передують їй в даній послідовності. Будемо говорити, що вершина idvi вивідна з множини О0 аксіом, якщо і тільки якщо існує вивід з аксіом множини О0 і idvi є останньою вершиною в послідовності вершин, що формують даний вивід. Такий вивід будемо називати виводом вершини idvi.

Викладено метод і алгоритм прямого логічного виводу на ЛОС-мережі. Показано, що розроблений метод виводу дозволяє формалізувати процес застосування правил висновку. Завдяки цьому розроблений метод виводу забезпечує формування множин породжуючих вершин, застосування точно визначеного правила висновку до кожної з яких дозволяє гарантовано отримувати деяку безпосередньо вивідну вершину.

Алгоритм виводу включає 4 кроки.

Крок 1. Вибирається вершина idi O1 (де i I; I = card(O1)), яка запам'ятовується як id, і виконується формування доповнення до множини вершин, суміжних вершині id:

= Vnt \ ID,

де ID вибирається з відображення {id>ID}S. Вершина id додається до U: U = {id} і виконується перехід до кроку 2.

Крок 2. Виконується формування множини U

Крок 3. Виконується формування множини множин R за рахунок перетворення множини U. По завершенню виконання кроку 3 виконується очистка множини U: U={} і здійснюється перехід до кроку 4.

Крок 4. Виконується формування вивідних вершин. Для цього послідовно вибираються RnR. Для (idm)Rn (де m M; M = card(Rn)) знаходяться множини IDm (в {idm>IDm}S), над якими виконується операція перетину. У випадку, якщо множина, що отримана в результаті операції перетину, містить більше одного елемента, виконується ОСТАНОВ роботи алгоритму з діагностикою логічної помилки структури ЛОС-мережі. В супротивному випадку така множина буде містити один елемент idn, що є вершиною, породжуваною з множини породжуючих вершин idmRn. По idn в множині Q визначається логічний тип вершини idn:

1) Якщо тип вершини - І-вершина, то для (idm)Rn перевірити, що idmO1. У випадку неуспішного завершення перевірки додати Rn (така множина називається нерозв'язною) до R і виконати перехід до кроку 4.

2) Якщо тип вершини - АБО-вершина, то перевірити, що !(idm)Rn такий, що idmO1. У випадку неуспішного завершення - ОСТАНОВ роботи алгоритму з діагностикою виведення логічної суперечності.

У випадку успішного завершення перевірки (при цьому idn виступає в якості безпосередньо вивідної вершини) визначити ім'я метода, зіставленого вершині idn, і виконати метод. У випадку неуспішного завершення виконання метода - ОСТАНОВ роботи алгоритму з діагностикою помилки виконання метода, зіставленого вершині idn. В супротивному випадку (при цьому idn виступає у якості розв'язної вершини), idn додається до множини O1 (що відповідає виводу вершини idn), множина Rn, що обробляється (така множина називається розв'язною) видаляється з множини множин R і виконується перехід до кроку 4.

По завершенню виконання кроку 4 здійснюється перехід до кроку 1.

Завершення виконання алгоритму виводу відбувається при досягненні ситуації, коли на кроці 4 алгоритму з множин RnR не виведена жодна вершина (тобто у складі R містяться тільки нерозв'язні множини Rn), що означає, що до складу множини O1 не може бути доданий жодний елемент.

Обґрунтовано правильність алгоритму виводу та показано, що розроблений метод виводу задовольняє всім пред'явленим до нього вимогам. Наведено оцінку часової складності алгоритму виводу щодо рішення задач на знаходження і показано, що алгоритм, реалізований на основі розробленого метода прямого виводу, не поступається алгоритму, реалізованому на основі метода резолюцій.

У розділі 5 розглянуто питання інтерпретації формул C-обчислення, визначено та досліджено поняття мінімальної позитивної моделі формули C-обчислення і показано, що побудова мінімальної позитивної моделі формули C-обчислення, що описує довільну ЛОС-мережу, відповідає формуванню деякого початкового стану процесу прямого виводу на такій ЛОС-мережі, та викладено метод побудови мінімальної позитивної моделі.

Наведемо необхідні визначення.

Визначення 5.1. Під позитивною моделлю (П-моделлю) формули C-обчислення розуміється власна підмножина моделі, що включає до свого складу тільки літерали, які прийняли в даній інтерпретації логічне значення І.

Визначення 5.2. Під мінімальною позитивною моделлю (МП-моделлю) формули C-обчислення розуміється П-модель M1, для якої не існує жодної іншої П-моделі M2 такої, що M2 M1.

Для МП-моделей формул C-обчислення доведено наступну теорему:

Теорема 5.1. МП-модель формули C-обчислення містить мінімальну кількість літералів, необхідних і достатніх для її виконуваності.

Досліджено умови існування МП-моделей, на основі чого сформульовано:

Наслідок 5.1. Формула C-обчислення має всі можливі МП-моделі тоді і тільки тоді, коли будь-яка її підформула має МП-моделі, серед яких немає двох таких, які б були підмножиною однієї і тієї ж П-моделі, і кожна з цих МП-моделей або в точності співпадає з деякою П-моделлю, або є підмножиною деякої П-моделі, а будь-який літерал формули належить хоча б одній МП-моделі.

На основі викладених положень сформульовано узагальнену теорему про повноту для множини формул (формули) C-обчислення:

Теорема 5.2. Множина формул C-обчислення несуперечлива тоді і тільки тоді, коли вона виконувана. Еквівалентне формулювання: Формула C-обчислення несуперечлива тоді і тільки тоді, коли виконувана будь-яка її підформула.

Викладено метод побудови МП-моделі. Побудова МП-моделі виконується шляхом побудови розв'язного графа (див. розділ 4), множина висячих вершин якого представляє собою літерали, що формують таку МП-модель. Метод побудови МП-моделі, умовно названий нами методом підйому та спуску, засновується на формуванні МП-моделі за рахунок послідовного вибору термінальних вершин ЛОС-мережі, що включаються до складу МП-моделі, з виконанням підйому по структурі ЛОС-мережі зі знаходженням кореневих вершин ЛОС-мережі, які досяжні з вибраної термінальної вершини, і наступного спуску по структурі ЛОС-мережі з формуванням множини термінальних вершин, що містить елементи вибору, які потенційно можуть бути включені до складу МП-моделі. На основі метода підйому та спуску розроблено алгоритм побудови МП-моделі. Виконано оцінку часової складності алгоритму побудови МП-моделі, у відповідності до якої даний алгоритм правильно виконує побудову МП-моделі за час, що не перевищує O(mn + nr), де m - загальна кількість вершин ЛОС-мережі, n - кількість термінальних вершин ЛОС-мережі, r - коефіцієнт, значення якого залежить від висоти і ширини ЛОС-мережі, що розглядається.

У розділі 6 досліджено проблему виконання статичної верифікації знань, поданих у ЛОС-мережі, та викладено методи статичної верифікації таких знань.

Запропоновано класифікацію помилок, що діагностуються на етапах виконання статичної верифікації та емпіричного тестування знань, поданих у ЛОС-мережі, в якій відображено, на яких саме етапах відповідні помилки виявляються.

Викладено методи перевірки правильності побудови ЛОС-мережі. Дані методи засновуються на аналізі структури ЛОС-мережі з метою перевірки:

1) чи є досліджувана ЛОС-мережа простим однонаправленим ациклічним зв'язним графом (тобто чи відповідає структура ЛОС-мережі визначенню 3.1);

2) чи включає досліджувана ЛОС-мережа багатозначні та синонімічні імена.

Послідовність виконання методів перевірки правильності побудови ЛОС-мережі відображено.

Досліджено проблему виникнення логічних суперечностей в ЛОС-мережі. Встановлено, що виникнення логічних суперечностей в ЛОС-мережі може бути викликано двома причинами:

1). Приналежністю імен вершин, що входять у вивід, множині семантичних обмежень ПО (множині пар імен ПО, що взаємно виключають одне інше, які повинні бути попередньо задані експертом ПО).

2). Неповнотою або надлишковістю поданих знань, що призводить до формування в структурі ЛОС-мережі спеціальних видів структурних утворень, названих нами нерозв'язними неводами.

Визначення поняття „невід” засновується на відомому в теорії графів понятті напівконтура. Введемо поняття мінімального напівконтура, під яким будемо розуміти всякий напівконтур, який не включає в себе жодного іншого напівконтура.

Визначення 6.1. Під неводом розуміється структурне утворення в ЛОС-мережі, що являє собою або окремий мінімальний напівконтур, або декілька мінімальних напівконтурів, що мають загальну кінцеву вершину, але різні початкові вершини, такі, що кожна з них належить тільки одному з цих напівконтурів.

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

Існує два класи неводів: нерозв'язні неводи та розв'язні неводи. По структурі названі класи неводів розрізняються тим, що нерозв'язні неводи містять критичні траєкторії I або II роду.

Визначення 6.2. Під критичною траєкторією I роду розуміється траєкторія невода, що містить внутрішню АБО-вершину, одна з породжуючих вершин якої одночасно є початковою вершиною невода.

Визначення 6.3. Під критичною траєкторією II роду розуміється траєкторія невода, що містить внутрішню І-вершину, множина породжуючих вершин якої співпадає з множиною початкових вершин невода.

Виконано класифікацію нерозв'язних неводів, у відповідності до якої нерозв'язні неводи поділяються на неводи I роду, неводи ІІ роду та неводи ІІІ роду.

Визначено необхідні і достатні умови, що формалізують ситуації, при яких виникають нерозв'язні неводи в структурі ЛОС-мережі. Так, необхідною умовою їх існування є наявність у структурі ЛОС-мережі хоча б однієї АБО-вершини.

Достатньою умовою існування нерозв'язних неводів є:

ь для неводів I роду:

· якщо АБО-вершина має породжуючу вершину vi, яка є породжуючою вершиною деякої іншої вершини, і вершина vi є початковою вершиною мінімального напівконтура з кінцевою вершиною vj, то vi буде початковою вершиною, а vj - кінцевою вершиною невода;

ь для неводів II роду:

· якщо І-вершина vi є породжуючою вершиною АБО-вершини vj і vi має множину V1 породжуючих вершин, що є підмножиною множини породжуючих вершин І-вершини vk, і всі vnV1 (n = 1,N; N = deg+(vi)) виступають в якості початкових вершин мінімальних напівконтурів, які мають загальну кінцеву вершину vm, а вершини vi, vj і vk належать кожному такому напівконтуру, то V1 буде являтися множиною початкових вершин, а vm - кінцевою вершиною невода;

ь для неводів III роду:

· якщо вершина має множину V1 породжуючих вершин і кожна viV2 (де V2V1; card(V2) > 1) є породжуючою вершиною деякої АБО-вершини, і всі viV2 виступають в якості початкових вершин мінімальних напівконтурів, що мають загальну кінцеву вершину vk, то V2 буде являтися множиною початкових вершин, а vk - кінцевою вершиною невода.

На основі визначених умов виявлено множину теоретично можливих видів нерозв'язних неводів. Для цього виконано наступну послідовність операцій:

1) виявлено множину теоретично можливих видів траєкторій неводів;

2) з множини одержаних видів траєкторій сформовано всі теоретично можливі нерозв'язні неводи;

3) виконано співвіднесення виявлених випадків формування нерозв'язних неводів з відповідними родами неводів.

В результаті виконання указаної послідовності операцій визначено, що існує: 17 теоретично можливих варіантів формування неводів I роду, 7 теоретично можливих варіантів формування неводів IІ роду та 10 теоретично можливих варіантів формування неводів IІІ роду.

Викладено методи виявлення нерозв'язних неводів в структурі ЛОС-мережі, які засновуються на аналізі окремих компонент ЛОС-мережі, що задовольняють необхідній і достатній умовам існування неводів I, II і III родів. Якщо аналізований компонент ЛОС-мережі задовольняє вищезгаданим умовам, виконується знаходження і аналіз траєкторій неводів. Якщо сполучення знайдених траєкторій відповідає одному з теоретично можливих варіантів формування неводу, то виконується діагностика відповідного нерозв'язного невода.

...