Posibniki.com.ua Інформатика Прикладні системи штучного інтелекту 5.3. Дедуктивний висновок на семантичних мережах


< Попередня  Змiст  Наступна >

5.3. Дедуктивний висновок на семантичних мережах


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

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

Такі види механізмів зазвичай використовуються виконуваними семантичними мережами:

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

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

Імовірність. Багато що з прямого і зворотного виведень, використовуваних із системою доведення істинності, може також бути пристосоване для імовірнісної інтерпретації, оскільки істинність може розглядатись як імовірність 1,0, а хибність як імовірність 0,0. Неперервний діапазон імовірностей від 1,0 до 0,0, однак, підвищує потребу в більш тонких інтерпретаціях і збільшує складність обчислень. Найбільш детальне вивчення імовірнісних виведень у причинних або довірчих мережах було виконано Ю. Перлом, який аналізував різні методи для застосування байєсівської статистики, щоб одержати причинну мережу за даними, що спостерігаються, і робити судження щодо них.

• перетворення графа — комбінують графи, змінюють, або розривають їх на менші графи. У типовому доказі теорем такі перетворення виконуються програмою, зовнішньою до графа. Коли вони викликані графами безпосередньо, то поводяться подібно хімічним реакціям, що комбінують молекули або ламають їх на частини.

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

Важливий клас виконуваних мереж був натхненний роботою фізіолога О. Селза (O. Selz), який запропонував схематичне сподівання (schematic anticipation) як спрямований метою метод зосередження розумового процесу на завдання заповнення порожніх слотів у шаблоні або схемі.

Графи потоків даних (dataflow graph) — найпростіші мережі з приєднаними процедурами, що містять пасивні вузли, які містять дані, та активні вузли, котрі подають функції, що беруть дані від вхідних вузлів і надсилають обчислені результати вихідним вузлам.

Мережа Петрі (Petri net) — різновид графів потоків даних, запропонована К. А. Петрі 1962 року, містить пасивні вузли, називані місцями (places), що містять дані, називані токенами (tokens), та активні вузли, називані переходами (transitions), що видаляють токени з їхніх вхідних вузлів і поміщають токени в їхні вихідні вузли. Крім того, вони мають набір правил для маркування місць крапками (токенами, символами) та для виконання (firing) або виключення переходів. Правила для виконання переходів роблять мережі Петрі формально еквівалентними версії лінійної логіки.

Кожне місце в мережі Петрі є попередньою умовою для переходів, що використовують його як вхід, і постумовою для переходів, що використовують його як вихід. Символ у певному місці стверджує, що відповідна умова (стан) є істинною. Видаляючи символ з кожного місця входу, виключення переходу скасовує твердження попередніх умов. Додаючи символ до кожного місця виходу, виключення стверджує, що кожна з постумов стала істинною.

Хоча графи потоків даних і мережі Петрі зазвичай не називаються семантичними мережами, подібні методи були втілені в процедурних семантичних мережах (procedural semantic networks). Дж. Милопоулос (J. Mylopoulos) та ін. вчені створили

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

5. Мережі, що навчаються (learning networks), будують або розширюють свої уявлення, здобуваючи знання за прикладами. Нове знання може змінювати стару мережу за допомогою додавання і видалення вузлів і дуг або зміни числових значень, називаних вагами, зіставлених вузлам і дугам.

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

Системи, що використовують мережні подання, можуть змінювати мережі у такий спосіб:

Занесення в пам’ять — найпростіша форма навчання — перетворення нової інформації у мережу і додавання її до поточної мережі без будь-яких подальших змін.

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

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

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

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

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

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

Рис. 2.1. Багатошарова нейронна мережа

Рис. 2.1. Багатошарова нейронна мережа

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

режі, що є подібними, але не ідентичні будь-якому даному прикладу.

6. Гібридні мережі (hybrid networks)

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

5.3. Дедуктивний висновок на семантичних мережах

Як уже зазначалося, у семантичній мережі вершини є понятійними об’єктами, а дуги — семантичні відносини.

Семантичні відносини класифікують на: а) структурні; б) логічні; в) процедурні.

Приклад: Між поняттями студент 5 курсу ФІСІТ і дисципліна ПСШІ є структурний зв’язок.

Між поняттями успішний і студент є логічний зв’язок: будьякий індивідуум, який належить поняттю успішний, належить і поняттю студент.

Складніший логічний зв’язок простежується між поняттями успішний, оцінка, бал і дисципліна ПСШІ: індивідуум є успішним тоді і тільки тоді, коли його оцінка з будь-якої дисципліни не менша 3 балів.

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

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

Розглянемо приклади висловів і їх відповідні семантичні мережі. Хай дано вираз: «куб № 2 знаходиться завжди в тому самому місці, де куб № 1». У формі диз’юнкта цей вираз має вигляд: В(куб1) ? Вуб2).

Тут В — предикат «знаходиться в місці», а х є будь-яким індивідуумом (пов’язаний квантором спільності).

чення значень виходів. На стадії навчання система визначає, чи є отримані значення правильними, і методами, заснованими на зворотному поширенні помилки (error backpropagation), прагне відрегулювати ваги на дугах, що ведуть до результату.

Твердження «куб № 1 знаходиться в місці а» записуватимемо як TRUE(куб1,а), або в скороченій формі ?B(куб1), і вважатимемо консеквентом.

Вираз «куб № 1 не знаходиться в місці а» матиме вигляд: B(куб1) ? FALSE або в скороченому записі B(куб1) ?, і він вважається антецедентом.

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

1 ) розфарбовуватимемо антецеденти; б) пунктирною лінією (Ц

2 ) — консеквенти.

Пояснимо зазначене прикладом. Нехай маємо такий набір висловів:

1. Якщо куб № 1 знаходиться на місці а, то куб № 2 теж знаходиться в тому самому місці.

2. Якщо куб № 1 знаходиться на місці а, то куб № 3 знаходиться в місці b.

3. Куб № 1 знаходиться в місці а.

У диз’юнктивній формі:

1. B(куб1) ? В(куб2) P

1 , P

2 , P

3 пропозиційні символи.

2. B(куб1)? В(куб3,b) P

4 , P

5 , P

пропозиц. символи.

6

3. ?B(куб1) — P

7 пропозиц. символ.

Відповідну семантичну мережу подано на рис. 2.2. У мережі буквою Р

1 позначена пропозиційні вершина, відповідна першому вислову в цілому, пропозиційна вершини P

2 і P

3 позначають відповідно антецедент В(куб1) і консеквент В(куб2) те й друге в цілому. Далі розписують антецедент і консеквент. Антецедент складається з термів «куб1», «а» і предиката В — «знаходиться в місці», а консеквент — з термів «куб2», «а» і того ж предиката В. Аналогічно розписують решту висловів.

Рис. 2.2. Семантична мережа

Рис. 2.2. Семантична мережа

Припустимо, необхідно знайти в мережі твердження ? В(куб1). Спочатку знаходимо всі пропозиційні символи, пов’язані з вершинами «В», «куб1» і «а». Це — P

2 , P

5 , P

7 , оскільки P

2 і P

5 є антецедентами, то вони виключаються, а вершині P

7 відповідає третє твердження. Аналогічно знаходять будь-яке інше твердження.

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

1) дається ефективна індексація інформації за допомогою розфарбованих графів, що дозволяє обробляти мережі великої розмірності;

2) ефективно видаляється з мережі інформація, що не стосується даного питання.

Надалі для простоти зображатимемо семантичну мережу, що складається з диз’юнктивних вершин, тобто вершин, яким відповідають початкові диз’юнкти, предикативних вершин і дуг, позначених двома кольорами. Тоді після спрощень наведена вище семантична мережа матиме вигляд, зображений на рис. 2.3, де g

1 , g

2 , g

3 початкові диз’юнкти, В — предикат.

Рис. 2.3. Різновид семантичної мережі

терм

Рис. 2.3. Різновид семантичної мережі

Такі спрощені мережі називаються L-мережами, які задаються четвіркою: P — множина предикативних вершин G — множина диз’юнктних вершин F

L=

1 ,F

2 >(1) L=

1 ,F

2 >(1)

1 , F

2

відображення G в Р, що представляється множиною дуг, позначених відповідно пунктиром Ц

1 і Ц

2 . L-мережі введені нами тільки для зручності ілюстрації процедур дедуктивного висновку. Семантичні мережі, будучи формалізмом представлення знань у СШІ, володіють, отже, такими особливостями:

1) у семантичній мережі представлені такі види об’єктів, як поняття, події, ситуації, а також спеціалізовані методи висновку. При цьому слід урахувати, що збільшення номенклатури об’єктів знижує однорідність мережі та потребує збільшення кількості методів висновку;

2) багатовимірність семантичних мереж дозволяє представити в них численні семантичні відносини, що зв’язують окремі поняття, поняття і події в пропозиціях, а також пропозиції в текстах. Крім того, у семантичній мережі може бути відображена семантична ієрархія спеціалізованих методів висновку, що визначає їх взаємозалежність;

3) формалізація, як структурне подання семантичних знань, дозволяє накласти на ці знання деяку суперсемантику, що відображає відносну «силу» семантичних відносин, що, у свою чергу, сприяє підвищенню ефективності висновку в семантичних мережах;

4) на кожній стадії розв’язування задачі можна виділити повні знання системи (повна семантична мережа) і поточне знання — збуджену ділянку семантичної мережі, в якій проводяться деякі операції (процес «розуміння», висновку і т. д.).

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

Алгоритм семантичної уніфікації диз’юнктів працює при пошуку резольвенти двох диз’юнктів.

Опис алгоритму:

1) якщо в мережі є вершина, вільна від мультидуг, то переходимо на наступний крок, інакше на крок 8;

2) виділяємо предикативну вершину Р, яка вільна від мультидуг;

3) обчислюємо A = {F

1 (P)}

множина вершин з дугами кольору Ц

1 , що входять у вершину Р;

4) обчислюємо В = {F

2 (P)} множина вершин з дугами кольору Ц

2 , що входять у вершину Р;

5) F = A ? B;

6) резольвуємо диз’юнкти з множина F за предикатом Р. Якщо одержали результат, то зупинка;

7) у семантичну мережу додаються всі диз’юнкти, що згенерували в кроці 6, і з семантичної мережі видаляються всі диз’юнкти з множини F, потім перехід на крок 1;

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

Даний алгоритм заснований на перетворенні семантичних мереж. Тепер розглянемо алгоритм, у якому в процесі висновку семантична мережа не змінюється.

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

Якщо у вершину входять дуги тільки одного кольору (так звані «чисті» диз’юнкти), то вони не впливають на процес виведення порожньої мережі й видаляються з розгляду. Процес продовжується доти, допоки не буде виведена порожня мережа. Наведемо детальнішу інтерпретацію методу.

Позначимо через CLIST — робочий список, а ALIST — список альтернатив.

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

1. CLIST = 0; ALIST = 0.

2. A = {F

1 (g) ? F

2 (g)}.

3. Множина А модифікується так, щоб кожен елемент мав вигляд (1).

4. CLIST = A.

5. Береться перший елемент з CLIST, що має вигляд (P,g,I), де Р — предикативний символ, g — ім’я диз’юнкта, а I = 1, якщо дуга (g,P

1 і I = 2, якщо дуга (g, P) Ц

2 . З CLIST виключається перший елемент.

6. Якщо I = 1, то G = {F

2 –1 (P)}?g; Якщо I = 2, то G = {F

1 –1 (P)} ?g, де F

1 1 і F

2 1 відображення, зворотні F

1 і F

2 .

7. Для всіх g’ ? G повторюються кроки 8

15 доти, допоки не буде вичерпаний список G.

8. B = {F

1 (g’) ? F

2 (g’)}.

9. Модифікується В відповідно до (1).

10. Береться перший елемент (P’,g’,I’) зі списку В і він виключається з цього списку, причому імена Р і Р’ збігаються, а I’ = 1, якщо I = 2 і I’ = 2, якщо I = 1. Якщо таких елементів немає для ?g’ ? G, то — перехід на крок 17.

11. Знаходимо ? для Р і Р’.

12. B = B ? CLIST.

13. B = B?.

14. Якщо В = ?, то процедура завершилася успішно, інакше перехід на крок 15.

15. Першим елементом ALIST стає підсписок В.

16. Вибирається перший елемент з ALIST і він видаляється з СLIST, перехід на крок 5.

17. Якщо ALIST = ?, то процедура завершилася невдало, інакше в СLIST заноситься перший елемент ALIST, і цей елемент видаляється з ALIST.

18. Перехід до кроку 5.

Приклад: ()() ??yxMyxQg,,:

1 . ()()() vuQwvHvuMg,,,:

2 ??. ()()() zxHyzMyxFg,,,:

3 ?? . () abMg,:

4 ?. () acFg,:

5 ?. () cdMg,:

6 ?. g

4 QMHF g

5 g

3 g

6 g

1 g

2

2. A = {F

1 (g) F

2 (g)}.

3. Множина А модифікується так, щоб кожен елемент мав вигляд (1).

4. CLIST = A.

5. Береться перший елемент з CLIST, що має вигляд (P,g,I), де Р — предикативний символ, g — ім’я диз’юнкта, а I = 1, якщо дуга (g,P

1 і I = 2, якщо дуга (g, P) Ц

2 . З CLIST виключається перший елемент.

6. Якщо I = 1, то G = {F

2 –1 (P)}?g; Якщо I = 2, то G = {F

1 –1 (P)} ?g, де F

1 1 і F

2 1 відображення, зворотні F

1 і F

2 .

7. Для всіх g’ ? G повторюються кроки 8

15 доти, допоки не буде вичерпаний список G.

8. B = {F

1 (g’) ? F

2 (g’)}.

9. Модифікується В відповідно до (1).

10. Береться перший елемент (P’,g’,I’) зі списку В і він виключається з цього списку, причому імена Р і Р’ збігаються, а I’ = 1, якщо I = 2 і I’ = 2, якщо I = 1. Якщо таких елементів немає для ?g’ ? G, то — перехід на крок 17.

11. Знаходимо ? для Р і Р’.

12. B = B ? CLIST.

13. B = B?.

14. Якщо В = ?, то процедура завершилася успішно, інакше перехід на крок 15.

15. Першим елементом ALIST стає підсписок В.

16. Вибирається перший елемент з ALIST і він видаляється з СLIST, перехід на крок 5.

17. Якщо ALIST = ?, то процедура завершилася невдало, інакше в СLIST заноситься перший елемент ALIST, і цей елемент видаляється з ALIST.

18. Перехід до кроку 5.

Приклад: ()() ??yxMyxQg,,:

1 . ()()() vuQwvHvuMg,,,:

2 ??. ()()() zxHyzMyxFg,,,:

3 ?? . () abMg,:

4 ?. () acFg,:

5 ?. () cdMg,:

6 ?. g

4 QMHF g

5 g

3 g

6 g

1 g

2

4. CLIST = A.

5. Береться перший елемент з CLIST, що має вигляд (P,g,I), де Р — предикативний символ, g — ім’я диз’юнкта, а I = 1, якщо дуга (g,P

1 і I = 2, якщо дуга (g, P) Ц

2 . З CLIST виключається перший елемент.

6. Якщо I = 1, то G = {F

2 –1 (P)}?g; Якщо I = 2, то G = {F

1 –1 (P)} ?g, де F

1 1 і F

2 1 відображення, зворотні F

1 і F

2 .

7. Для всіх g’ ? G повторюються кроки 8

15 доти, допоки не буде вичерпаний список G.

8. B = {F

1 (g’) ? F

2 (g’)}.

9. Модифікується В відповідно до (1).

10. Береться перший елемент (P’,g’,I’) зі списку В і він виключається з цього списку, причому імена Р і Р’ збігаються, а I’ = 1, якщо I = 2 і I’ = 2, якщо I = 1. Якщо таких елементів немає для ?g’ ? G, то — перехід на крок 17.

11. Знаходимо ? для Р і Р’.

12. B = B ? CLIST.

13. B = B?.

14. Якщо В = ?, то процедура завершилася успішно, інакше перехід на крок 15.

15. Першим елементом ALIST стає підсписок В.

16. Вибирається перший елемент з ALIST і він видаляється з СLIST, перехід на крок 5.

17. Якщо ALIST = ?, то процедура завершилася невдало, інакше в СLIST заноситься перший елемент ALIST, і цей елемент видаляється з ALIST.

18. Перехід до кроку 5.

Приклад: ()() ??yxMyxQg,,:

1 . ()()() vuQwvHvuMg,,,:

2 ??. ()()() zxHyzMyxFg,,,:

3 ?? . () abMg,:

4 ?. () acFg,:

5 ?. () cdMg,:

6 ?. g

4 QMHF g

5 g

3 g

6 g

1 g

2Р — предикативний символ, g — ім’я диз’юнкта, а I = 1, якщо дуга (g,P

1 і I = 2, якщо дуга (g, P) Ц

2 . З CLIST виключається перший елемент.

6. Якщо I = 1, то G = {F

2 –1 (P)}?g; Якщо I = 2, то G = {F

1 –1 (P)} ?g, де F

1 1 і F

2 1 відображення, зворотні F

1 і F

2 .

7. Для всіх g’ ? G повторюються кроки 8

15 доти, допоки не буде вичерпаний список G.

8. B = {F

1 (g’) ? F

2 (g’)}.

9. Модифікується В відповідно до (1).

10. Береться перший елемент (P’,g’,I’) зі списку В і він виключається з цього списку, причому імена Р і Р’ збігаються, а I’ = 1, якщо I = 2 і I’ = 2, якщо I = 1. Якщо таких елементів немає для ?g’ ? G, то — перехід на крок 17.

11. Знаходимо ? для Р і Р’.

12. B = B ? CLIST.

13. B = B?.

14. Якщо В = ?, то процедура завершилася успішно, інакше перехід на крок 15.

15. Першим елементом ALIST стає підсписок В.

16. Вибирається перший елемент з ALIST і він видаляється з СLIST, перехід на крок 5.

17. Якщо ALIST = ?, то процедура завершилася невдало, інакше в СLIST заноситься перший елемент ALIST, і цей елемент видаляється з ALIST.

18. Перехід до кроку 5.

Приклад: ()() ??yxMyxQg,,:

1 . ()()() vuQwvHvuMg,,,:

2 ??. ()()() zxHyzMyxFg,,,:

3 ?? . () abMg,:

4 ?. () acFg,:

5 ?. () cdMg,:

6 ?. g

4 QMHF g

5 g

3 g

6 g

1 g

2га (g,P

1 і I = 2, якщо дуга (g, P) Ц

2 . З CLIST виключається перший елемент.

6. Якщо I = 1, то G = {F

2 –1 (P)}?g; Якщо I = 2, то G = {F

1 –1 (P)} ?g, де F

1 1 і F

2 1 відображення, зворотні F

1 і F

2 .

7. Для всіх g’ ? G повторюються кроки 8

15 доти, допоки не буде вичерпаний список G.

8. B = {F

1 (g’) ? F

2 (g’)}.

9. Модифікується В відповідно до (1).

10. Береться перший елемент (P’,g’,I’) зі списку В і він виключається з цього списку, причому імена Р і Р’ збігаються, а I’ = 1, якщо I = 2 і I’ = 2, якщо I = 1. Якщо таких елементів немає для ?g’ ? G, то — перехід на крок 17.

11. Знаходимо ? для Р і Р’.

12. B = B ? CLIST.

13. B = B?.

14. Якщо В = ?, то процедура завершилася успішно, інакше перехід на крок 15.

15. Першим елементом ALIST стає підсписок В.

16. Вибирається перший елемент з ALIST і він видаляється з СLIST, перехід на крок 5.

17. Якщо ALIST = ?, то процедура завершилася невдало, інакше в СLIST заноситься перший елемент ALIST, і цей елемент видаляється з ALIST.

18. Перехід до кроку 5.

Приклад: ()() ??yxMyxQg,,:

1 . ()()() vuQwvHvuMg,,,:

2 ??. ()()() zxHyzMyxFg,,,:

3 ?? . () abMg,:

4 ?. () acFg,:

5 ?. () cdMg,:

6 ?. g

4 QMHF g

5 g

3 g

6 g

1 g

2

6. Якщо I = 1, то G = {F

2 –1 (P)}?g; Якщо I = 2, то G = {F

1 –1 (P)} ?g, де F

1 1 і F

2 1 відображення, зворотні F

1 і F

2 .

7. Для всіх g’ ? G повторюються кроки 8


< Попередня  Змiст  Наступна >
Iншi роздiли:
Тема 6. ЗАСОБИ ДЛЯ ПОДАННЯ Й ОБРОБКИ МОДЕЛЕЙ ЗНАНЬ У ПСШІ
6.5. Фреймові моделі та їх реалізація
ТАБЛИЧНЕ ПОДАННЯ ФРЕЙМУ
Частина 4. ЗАСОБИ ДЛЯ ПОДАННЯ Й ОБРОБКИ МОДЕЛЕЙ ЗНАНЬ У ПСШІ
Тема 7. ПРОЦЕС ПРИЙНЯТТЯ РІШЕННЯ
Дисциплiни

Медичний довідник новиниКулінарний довідникАнглійська моваБанківська справаБухгалтерський облікЕкономікаМікроекономікаМакроекономікаЕтика та естетикаІнформатикаІсторіяМаркетингМенеджментПолітологіяПравоСтатистикаФілософіяФінанси

Бібліотека підручників та статтей Posibniki (2022)