Системи штучного інтелекту 1 Міністерство освіти і науки України Харківський національний університет імені В. Н. Каразіна В. Є. Стрілець С. І. Шматков СИСТЕМИ ШТУЧНОГО ІНТЕЛЕКТУ Практикум Електронне видання Харків – 2022 2 В. Є. Стрілець, С. І. Шматков УДК 004.89+004.4’2 С 83 Рецензенти: Г. М. Жолткевич – доктор технічних наук, професор, декан факультету математики і інформатики Харківського національного університету імені В. Н. Каразіна; І. В. Гребеннік – доктор технічних наук, професор, завідувач кафедри системо- техніки Харківського національного університету радіоелектроніки. Затверджено до розміщення в мережі Інтернет рішенням Науково-методичної ради Харківського національного університету імені В. Н. Каразіна (протокол № 6 від 16 лютого 2022 року) С 83 Стрілець В. Є. Системи штучного інтелекту : практикум [Електронне видання] / В. Є. Стрілець, С. І. Шматков. – Харків : ХНУ імені В. Н. Каразіна, 2022. – (PDF 68 с.) У практикумі викладаються основи програмування на мові Пролог, яка використовується для розв’язання задач штучного інтелекту й обробки складних символьних структур. Описані методи і засоби логічного програмування мовою SWI-Prolog, наведені приклади пролог-програм. Посібник містить методичні вказівки до виконання практичних робіт з дисципліни «Системи штучного інтелекту», яка викладається у рамках підготовки бакалаврів за спеціальностями 123 «Комп’ютерна інженерія» та 151 «Автоматизація та комп’ютерно-інтегровані технології». УДК 004.89+004.4’2 © Харківський національний університет імені В. Н. Каразіна, 2022 © Стрілець В. Є., Шматков С. І., 2022 © Дончик І. М., макет обкладинки, 2022 Електронне навчальне видання комбінованого використання Можна використовувати в локальному та мережному режимі Стрілець Вікторія Євгенівна Шматков Сергій Ігорович СИСТЕМИ ШТУЧНОГО ІНТЕЛЕКТУ Практикум Електронне видання Коректор Л. Є. Стешенко Комп’ютерне верстання В. В. Савінкова Макет обкладинки І. М. Дончик Підписано до видання 16.05.2023. Гарнітура Times New Roman Обсяг 2,26 Мб. Зам. 31/22. Харківський національний університет імені В. Н. Каразіна, 61022, м. Харків, майдан Свободи, 4. Свідоцтво суб’єкта видавничої справи ДК № 3367 від 13.01.2009 Видавництво ХНУ імені В. Н. Каразіна Системи штучного інтелекту 3 Зміст Вступ ............................................................................................................................. 4 Практична робота № 1. Числення висловлювань .................................................... 6 Практична робота № 2. Предикати, факти і правила в SWI-Prolog .................... 10 Практична робота № 3. Рекурсія в SWI-Prolog ..................................................... 20 Практична робота № 4. Списки у SWI-Prolog ....................................................... 26 Практична робота № 5. Робота з базами даних у SWI-Prolog ............................. 30 Практична робота № 6. Пошук у просторі станів ................................................. 36 Практична робота № 7. Віконні додатки у SWI-Prolog ........................................ 47 Додатки ...................................................................................................................... 53 Додаток А. Початок роботи у SWI-Prolog. Найпростіша програма ..... 53 Додаток Б. Приклади Prolog-програм ..................................................... 58 Додаток В. Вбудовані предикати і оператори SWI-Prolog .................... 64 Список літератури ..................................................................................................... 67 4 В. Є. Стрілець, С. І. Шматков Вступ Штучний інтелект (англ. Artificial intelligence) – наука та технологія ство- рення інтелектуальних машин, в особливості інтелектуальних комп’ютерних програм. Штучний інтелект пов’язаний з завданням використання комп’ютерів для розуміння людського інтелекту, але не обов’язково обмежується біологічно правдоподібними методами (Джон Маккарті, 1956 р., конференція у Дартмут- ському університеті). В подальшому було зроблено чимало спроб дати формальне визначення інтелекту взагалі та інтелекту штучного зокрема. Найбільш відомим є визначення предмета теорії штучного інтелекту, що було дане видатним дослідником у галузі штучного інтелекту М. Мінські і яке у більш або менш видозміненому вигляді потрапило до словників та енцикло- педій: «штучний інтелект є дисципліна, що вивчає можливість створення програм для вирішення задач, які при вирішенні їх людиною потребують певних інтелектуальних зусиль». Це визначення зустріло критику, яка полягала в тому, що під нього можна підвести що завгодно, наприклад, виконання простих арифметичних операцій. Відтак до цього визначення додається поправка: «сюди не входять задачі, для яких відома процедура їх вирішення». Єдиної відповіді на питання, чим займається штучний інтелект, не існує. Майже кожен автор дає своє визначення. Зазвичай ці визначення зводяться до таких:  штучний інтелект вивчає методи розв’язання задач, які потребують людського розуміння. Тут мова іде про те, щоб навчити штучний інтелект розв’язувати тести інтелекту. Це передбачає розвиток способів розв’язання задач за аналогією, методів дедукції та індукції, накопичення базових знань і вміння їх використовувати;  штучний інтелект вивчає методи розв’язання задач, для яких не існує способів розв’язання або вони не коректні (через обмеження в часі, пам’яті тощо). Завдяки такому визначенню інтелектуальні алгоритми часто використо- вуються для розв’язання NP-повних задач, наприклад, задачі комівояжера;  штучний інтелект займається моделюванням людської вищої нервової діяльності;  штучний інтелект – це системи, які можуть оперувати знаннями, а най- головніше – навчатися. В першу чергу мова йде про те, щоби визнати клас експертних систем (назва походить від того, що вони спроможні замінити «на посту» людей-експертів) інтелектуальними системами. Останнє визначення з’явилося у 1990-х рр. і засноване на так званому агентно-орієнтованому підході. Цей підхід акцентує увагу на тих методах і алгоритмах, які допоможуть інтелектуальному агенту виживати в оточуючому середовищі під час виконання свого завдання. Тому тут значно краще застосовуються алгоритми пошуку і прийняття рішення. Системи штучного інтелекту 5 Для створення систем штучного інтелекту були розроблені мови програ- мування, найбільш відомими є Lisp і Prolog. Prolog – мова логічного програмування загального призначення, яка має корені в логіці першого порядку, математичній логіці, та, на відміну від бага- тьох інших мов програмування, є декларативною: логіка програми виражається в термінах відношень, представлених як факти та правила. Обчислення ініціюються запуском запиту над цими відношеннями. Першу систему Prolog було розроблено в 1972 р. Аланом Кольмерое та Філіпом Русселем. Prolog була однією з перших логічних мов програмування, й залишається найпопулярнішою серед таких мов і на сьогодні, маючи декілька безкоштовних та комерційних реалізацій. Її застосовували як для доведення теорем, екс- пертних систем, так і для її початкової області призначення, обробки природної мови. Сучасні середовища Prolog підтримують як створення графічних інтерфейсів користувача, так і адміністративні або мережеві застосування. Prolog добре підходить для розв’язання специфічних задач, що виграють від логічних запитів на базі правил, таких як пошук базами даних, системи голосового керування та заповнення шаблонів. У межах дисципліни «Системи штучного інтелекту» студенти мають отримати навички розв’язання задач штучного інтелекту з використанням мови Prolog. Теми і структура практичних робіт розроблені таким чином, щоб допо- могти студентам оволодіти навичками програмування на Prolog, починаючи з основ. За результатами вивчення дисципліни студенти повинні вміти констру- ювати алгоритми розв’язання задач на основі числення предикатів; використо- вувати системи, що основані на правилах, для побудови і модифікації баз знань; розв’язувати задачі неінформованого та евристичного пошуку, в тому числі з використанням мови логічного програмування Prolog. 6 В. Є. Стрілець, С. І. Шматков Практична робота № 1 Числення висловлювань Мета роботи: пригадати елементи теорії логіки висловлювань; навчитися подавати висловлювання у вигляді формул алгебри висловлювань та будувати для них таблиці істинності. Теоретичні відомості Вихідним поняттям теорії логіки є висловлювання. Будь-яке розповідне речення, яке може бути істинним або брехливим, називають висловлюванням. Логічним значенням висловлювань є «істина» (true) або «брехня» (false). Приклади розповідних речень, які є висловлюваннями: «Трійка є простим числом» (має значення «істина»), «3.14 – раціональне число» (має значення «брехня»), «Х. Колумб відкрив Америку» (істинне), «Київ – столиця Молдови» (брехня). Такі висловлювання є простими або елементарними. При формальному розв’язанні задач замість поняття «прості висловлювання» використовують поняття «пропозиційні змінні» (від лат. propositio – пропозиція), які позначають великими літерами латинського алфавіту A, B, C, D і т. д. Істинність або брехливість висловлювань позначають символами T (істина, true) і F (брехня, false). Наприклад:  якщо А= «Трійка є простим числом», то А = T;  якщо B= «3.14 – раціональне число», то B = F;  якщо C= «Пінгвіни живуть в Арктиці», то C = F;  якщо D= «Відень – столиця Австрії», то D = T. Висловлювання, які отримують із речень за допомогою граматичних зв’язок «не», «і», «або», «якщо …, то …», «… тоді і лише тоді, коли …» та ін., називають складними або складеними. Для позначення граматичних зв’язок використовують логічні (або пропозиційні) зв’язки: ∧ – «і», ∨ – «або», – «не», ≡ – еквівалентність, → – «якщо …, то …» (наслідок). Наприклад:  складне висловлювання «Трійка є простим і цілим числом» можна подати як об’єднання простих висловлювань А1= «Трійка є простим числом» і А2= «Трійка є цілим числом», тоді А ∧ А Т;  складне висловлювання «Якщо число 11 є простим, то воно ціле» можна подати як наслідок простих висловлювань В1= «Число 11 є простим» і В2= «Число 11 є цілим», тобто В → В Т. Правила побудови складних висловлювань як послідовності пропозиційних змінних, логічних зв’язок і допоміжних символів визначають можливість формального розв’язання різних задач. Системи штучного інтелекту 7 Правила виконання логічних операцій над складними висловлюваннями на основі визначених логічних зв’язок і пропозиційних змінних формують алгебру висловлювань. Правила виводу нових висловлювань, заснованих на відомих відношеннях між заданими пропозиційними змінними, формують числення висловлювань. Висловлювання, з яких роблять вивід нових висловлювань, називають посилан- ням, а отримуване висловлювання – висновком. Символами числення висловлювань, тобто алфавітом, є логічні константи true і false, які позначають T і F, пропозиційні змінні А, В, С, …, які позначають літерами латинського алфавіту, логічні зв’язки ∧ – кон’юнкція, ∨ – диз’юнкція, – заперечення, ≡ – еквівалентність, → – імплікація і круглі дужки. Будь-яке складне висловлювання, яке можна отримати з елементарних висловлювань із застосуванням логічних зв’язок, називають формулою чис- лення висловлювань. Будь-яку пропозиційну змінну можна вважати формулою нульового порядку. Якщо F1 і F2 – формули, то , , ∧ , ∨ , ≡ , → також є формулами. Ніяких інших формул у численні висловлювань немає. Значення формули повністю визначається значеннями пропозиційних змінних, які до неї входять. Всі значення формули у залежності від значень елементарних висловлювань, що до неї входять, можуть бути повність описану за допомогою таблиці істинності. У табл. 1 наведені значення логічних зв’язків, які використовуються у численні висловлювань. Таблиця 1 Значення основних логічних операцій X Y ∧ ∨ → ≡ F F T F F T T F T T F T T F T F F F T F F T T F T T T T Приклади застосування логічних операцій:  є висловлювання A=«Комп’ютер містить мікропроцесор», В=«Комп’ютер містить оперативну пам’ять», С=«Комп’ютер містить контролери» і D=«Комп’ютер містить порти вводу-виводу». Тоді складене висловлювання «Комп’ютер містить мікропроцесор, оперативну пам’ять, контролери і порти вводу-виводу» можна записати формулою F=A ∧B ∧C ∧D;  є висловлювання А=«По провіднику тече електричний струм» і В=«Навколо провідника є магнітне поле». Тоді формула F=A→B відображує висловлювання «Якщо по провіднику протікає електричний струм, то навколо провідника виникає магнітне поле»;  є висловлювання А= «Бути парним числом» і В= «Число ділиться на два», тоді формула F=(A≡B) відображає висловлювання «Для того, щоб число було парним, необхідно і достатньо, щоб воно ділилося на два». 8 В. Є. Стрілець, С. І. Шматков Для визначення істинності складного висловлювання необхідно проаналі- зувати значення істинності кожного висловлювання, яке входить до його складу, і сформувати послідовно значення істинності кожної підформули, яка входить у формулу складного висловлювання. Логічні значення формули алгебри логіки повністю визначається логічними значеннями пропозиційних змінних, які входять до неї. Усі можливі логічні значення формули у залежності від значень елементарних висловлювань, які до неї входять, можуть бути повністю описані у таблиці істинності. Розглянемо як приклад складне висловлювання «Якщо обчислювальна задача немає точного розв’язку, то використовують чисельні методи або роз- робляють нові підходи, а якщо використовують чисельні методи, то отримують наближений розв’язок, і , нарешті, якщо є наближений розв’язок, при цьому задача немає точного, то розробка нових підходів не потрібна». У цьому висловлюванні є чотири елементарні висловлювання, які можна замінити пропозиційними змінними: А=«Обчислювальна задача немає точного розв’язку», В=«Використовують чисельні методи», С=«Розробляють нові підло- ди» і D=«Отриманий наближений розв’язок»; і записати формулу висловлювання: F =(A→(B∨C))&(B→D)&((D∧A)→¬C). Істинність формули F для різних значень істинності пропозиційних змін- них A, B, C, D можна визначити склавши для неї таблицю істинності (табл. 2). Таблиця 2 Таблиця істинності для складного висловлювання A B C D C D&A BC 17 BD 65 8&9 11&10 1 2 3 4 5 6 7 8 9 10 11 12 F F F F T F F T T T T T F F F T T F F T T T T T F F T F F F T T T T T T F F T T F F T T T T T T F T F F T F T T F T F F F T F T T F T T T T T T F T T F F F T T F T F F F T T T F F T T T T T T T F F F T F F F T T F F T F F T T T F F T T F F T F T F F F T T T T T T T F T T F T T T T F T F T T F F T F T T F T F F T T F T T T T T T T T T T T T F F F T T F T F F T T T T F T T T T F T F Системи штучного інтелекту 9 Завдання для практичної роботи 1. Для логічного виразу (формули) побудувати таблицю істинності (за варіантами). 2. Записати складнопідрядне речення, виділити в ньому елементарні вислов- лювання (пропозиційні змінні), записати формулу, яка відповідає реченню, та для формули побудувати таблицю істинності. Кількість елементарних висловлювань у реченні має бути не менше трьох. Варіанти для завдання 1 1. ∨ ∧ ∧ ∧ ∨ ∨ ∨ ∨ ∨ ∧ . 2. ∨ ∧ ∨ ∧ ∨ ∧ ∧ ∨ . 3. ∨ ∧ ∧ ∨ ∧ ∨ ∧ ∧ ∨ . 4. ∨ ∧ ∨ ∧ ∨ ∧ ∨ ∧ ∨ . 5. ∧ ∨ ∨ ∧ ∨ ∧ ∨ ∧ ∨ ∨ ∧ . 6. ∨ ∧ ∨ ∨ ∧ ∨ ∧ ∨ ∧ ∨ . 7. ∧ ∨ ∧ ∨ ∧ ∨ ∧ ∨ ∧ . 8. ∨ ∨ ∧ ∧ ∧ ∧ ∧ ∧ ∨ ∧ ∨ . 9. ∨ ∧ ∨ ∧ ∨ ∧ ∨ ∨ ∨ ∧ ∨ . 10. ∨ ∧ ∧ ∨ ∧ ∨ ∧ ∨ ∧ ∧ ∨ . 11. ∧ ∨ ∧ ∨ ∧ ∧ ∧ ∨ ∧ ∧ ∨ . 12. ∧ ∨ ∧ ∧ ∨ ∧ ∨ ∧ ∨ ∧ . 13. ∨ ∧ ∧ ∧ ∨ ∧ ∧ ∧ ∨ ∨ ∨ . 14. ∧ ∨ ∧ ∨ ∨ ∧ ∨ ∧ ∨ ∧ ∨ . 15. ∧ ∨ ∨ ∨ ∧ ∨ ∨ ∨ ∧ ∨ ∧ . 16. ∨ ∧ ∨ ∧ ∨ ∧ ∨ ∨ ∧ ∨ . 17. ∨ ∧ ∨ ∨ ∨ ∧ ∨ ∧ ∨ ∧ ∨ . 18. ∧ ∨ ∨ ∧ ∨ ∧ ∨ ∧ ∨ ∨ ∧ . 19. ∧ ∨ ∧ ∨ ∧ ∨ ∨ ∨ ∧ ∨ . 20. ∨ ∧ ∧ ∨ ∧ ∨ ∧ ∨ . Контрольні питання 1. Визначення висловлювання. Елементарні висловлювання. 2. Визначення алгебри висловлювань. 3. Визначення числення висловлювань. 4. Алфавіт числення висловлювань. 5. Визначення формули числення висловлювання. 6. Правила побудови формул. 7. Таблиці істинності. 10 В. Є. Стрілець, С. І. Шматков Практична робота № 2 Предикати, факти і правила в SWI-Prolog Мета роботи: отримати навички у використанні середовища програмування SWI-Prolog для розв’язання задач в області штучного інтелекту та математики. Теоретичні відомості Програма мовою SWI-Prolog є набором фактів і (за потреби) правил. Якщо програма містить лише факти, то її називають базою даних. Якщо вона містить ще й правила, то часто використовують термін база знань. Програма зазвичай описує деяку дійсність. Об’єкти (елементи) дійсності, що описується, подаються за допомогою термів. Терм – це об’єкт. Існує чотири види термів: атоми, числа, змінні і складені терми. Атоми і числа називають простішими термами. Атом – це окремий об’єкт, який вважається елементарним. У SWI-Prolog атом подається послідовністю літер нижнього і верхнього регістру, цифр і символу підкреслення «_», починаючи зі строкової букви. Змінними є строки символів, цифр і символу підкреслення, які починаються з великої літери або символу підкреслення. Символ підкреслення «_» є особливим випадком – анонімною змінною (змінною без імені). Анонімна змінна вико- ристовується тоді, коли значення змінної не використовується у програмі. Арифметичні вирази. Є у SWI-Prolog набір вбудованих атомів (функцій) для обчислення арифметичних виразів, деякі з них подані у таблиці 3. Таблиця 3 Арифметичні функції у SWI-Prolog X + Y сума X і Y X - Y різниця між X і Y X * Y добуток X і Y X / Y ділення X на Y X mod Y остача від ділення X на Y X // Y ділення націло X на Y X ** Y піднесення X у степінь Y -X зміна знака X abs(X) абсолютна величина числа X max(X,Y) більше з чисел X і Y min(X,Y) менше з чисел X і Y sqrt(X) квадратний корінь з X random(Int) випадкове ціле число в діапазоні від 0 до Int sin(X) синус X cos(X) косинус X tan(X) тангенс X Системи штучного інтелекту 11 Продовження табл. 3 log(X) натуральний логарифм (ln) числа X log10(X) десятковий логарифм (lg) числа X float(X) дійсне число, яке відповідає цілому числу X pi 3.14159 (наближене значення числа π) е 2.71828 (наближене значення числа е) Складені терми (функції) складаються з імені функції (нечислового атому) і списку аргументів (атомів, чисел, змінних або інших складених термів), який береться у круглі дужки і розділяється комами. Групи складених термів вико- ристовують для складання фраз. Не можна ставити символ пробілу між іменем функції (функтором) і дужками. У інших позиціях, однак, пробіли можуть бути корисними для написання більш читабельних програм. Список символів може бути поданий у вигляді строк, які беруться у лапки. Факт – це твердження про те, що дотримується деяке конкретне співвідношення. Він безумовно є істинним. Наприклад: «Сьогодні сонячно», «Т. Г. Шевченко – український письменник». Кома між фактами означає опера- цію логічного «і» (кон’юнкцію), факт можна записати у вигляді предиката, аргументи якого є символьними або числовими константами. У загальному випадку предикат – це логічна функція від одного або деяких аргументів, тобто функція, яка діє у множині з двох логічних значень: істина і брехня. Предикат записується у вигляді складеного терму: ім’я_предиката (аргументи). Аргументи перелічуються через кому і є деякими об’єктами або власти- востями об’єктів, а ім’я предиката означає зв’язок або співвідношення між аргументами. Предикат однозначно визначається парою: ім’я і кількість аргу- ментів. Два предикати з однаковим ім’ям, але різною кількістю аргументів, вважаються різними. Кількість параметрів предиката називається його арністю. Під час опису предиката арність указують після його імені, розділяючи їх символом слешу «/». Порядок аргументів предиката пов’язаний із сенсом факту, і тому його змінювати неможна. Під час запису фактів (предикатів) необхідно пам’ятати: ім’я факту почи- нається зі строкової літери; запис кожного факту закінчується крапкою. База даних – це сукупність фактів. У процесі роботи у базу даних можна додавати нові факти, видаляти або змінювати існуючі. Наприклад, опишемо факт того, що дехто є батьками когось: parent(Mary, Alex). % Mary є одним з батьків Alex parent(George, Alex). woman(Mary). % Mary – жінка. man(George). % George – чоловік. man(Alex). 12 В. Є. Стрілець, С. І. Шматков Тепер можна сформулювати питання: ?- parents(Mary, Alex). Yes ?- parents(George, Vita). No. ?- woman(Alex). No. Запит – це послідовність предикатів, які розділені комами і завершуються крапкою. За допомогою запитів можна «запитувати» у бази даних про те, які твердження є істинними. Предикат запиту називається ціллю. Використання змінних у запитах дозволяє ставити більш складні питання. Наприклад, питання «Хто є батьками Alex?»: ?- parent(X, Alex). X = Mary. X= George. Крім фактів, програми мовою SWI-Prolog можуть мати правила, які дозволяють отримувати додаткові знання про той світ, який описує програма. Правило задає новий предикат через визначені раніше. Правило складається з голови (предиката) і тіла (послідовності предикатів, які розділені комами). Голова і тіло розділяються знаком «:-» і, як і для кожного факту, правило повинно закінчуватись крапкою. Знак «:-» є схематичним записом стрілки «←» і показує, що з правої частини виходить ліва. Цей знак можна прочитати як «якщо». Інтуїтивний сенс правила полягає у тому, що мета, яка є головою, буде істинною, якщо можна показати, що всі вирази (підцілі) у тілі правила є істинними. Приклад 1. Скласти предикат, який буде визначати максимальне з двох чисел. Розв’язок У предикаті буде три аргументи: перші два – вхідні числа, третій – вихідний, у який буде записуватись максимум серед двох перших аргументів. Запишемо, що у випадку, якщо перше число більше другого, максималь- ним є перше число, у випадку, коли перше число менше, максимумом буде друге число. Також треба не забути про ситуацію, коли числа дорівнюють одне одному, в цьому випадку максимумом буде будь-яке з них. Розв’язок можна записати так: max(X,Y,X):-X>Y. /*якщо перше число більше другого, то перше число – максимум*/ max(X,Y,Y):-X(-2), X=< 2, Y is cos(X**4)+5); (X>2, Y is 10*sin(X)). Створюємо функцію виклику, введення вхідного значення Х та отримання результату Y. У SWI-Prolog, як і будь-якій іншій мові програмування, є заре- зервовані функції до читання інформації, яка вводиться з клавіатури, та для виводу: read() та write() відповідно. Їх будемо використовувати для введення значення змінної та виводу результату розрахунку значення математичної функції. funcY:-write(‘Enter X’),nl, read(X), fY(X,Y), write(‘Y(X)=‘),write(Y). 14 В. Є. Стрілець, С. І. Шматков Виклик функції ?- funcY. Enter X |: 3. Y(X)=1.4112000805986722 true. ?- funcY. Enter X |: -1.5. Y(X)=5.3430020941392815 true . Завдання для практичної роботи 1. Розробити Пролог-програму встановлення зв’язку між даними (задача № 1). 2. Розробити Пролог-програму реалізації розгалуженого обчислювального процесу (задача № 2). 3. Скласти звіт з роботи, в який додати лістинг програми та копію вікна з результатом виклику створеного предиката. Варіанти задач Варіант 1 1) Встановити взаємозв’язок між ім’ям людини і його професією за допомогою предиката special (name, profession). Програма повинна мати зовнішню мету. У розділ тверджень ввести не менше 10 фактів. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. , 0 sin , 0 1, 0 Варіант 2 1) Встановити взаємозв’язок між назвою міста, його населенням та площею за допомогою предиката city (name, people, square). Програма повинна мати зовнішню мету. У розділ тверджень ввести не менше 10 фактів. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. , 1 cos , 1 Варіант 3 1) Обчислити суму двох дійсних чисел. Програма повинна мати внут- рішню мету, що включає введення з клавіатури доданків і виведення. Системи штучного інтелекту 15 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. 1 2 , 1 cos 0,5 , 1 Варіант 4 1) Обчислити добуток двох дійсних чисел. Програма повинна мати внутрішню мету, що включає введення з клавіатури множників і виведення. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. 3 , 1 ln , 1 Варіант 5 1) Встановити взаємозв’язок між назвою тварини, її середнім зростом та вагою за допомогою предиката animal (name, height, weight). Програма повинна мати зовнішню мету. У розділ тверджень ввести не менше 10 фактів. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. | |, 0 exp 0.5 , 0 Варіант 6 1) Встановити взаємозв’язок між назвою фільму, роком його випуску та жанром за допомогою предиката film (title, year, type). Програма повинна мати зовнішню мету. У розділ тверджень ввести не менше 10 фактів. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. 1, 0 3 1, 0 Варіант 7 1) Встановити взаємозв’язок між назвою картини, роком її створення та автором за допомогою предиката picture (title, year, author). Програма повинна мати зовнішню мету. У розділ тверджень ввести не менше 10 фактів. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. 3 2, 1 3 3, 1 Варіант 8 1) Встановити взаємозв’язки родинних відносин з допомогою предиката family (parent, child). Програма повинна мати внутрішню мету, що дозволяє 16 В. Є. Стрілець, С. І. Шматков вводити з клавіатури ім’я дитини і виводити імена батьків. У розділ тверджень ввести не менше п’яти фактів. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. 2 √1 , 1 1 2 1, 1 Варіант 9 1) Встановити взаємозв’язки родинних відносин за допомогою предикатів family (people, people) про наявність безпосереднього родинного зв’язку, man (people) про людину-чоловіка, women (people) про людину-жінку. Програма повинна містити визначення предиката батьківства father (people, people) через вказані вище предикати і внутрішню мету. У розділ тверджень ввести не менше шести фактів по предикатах man і woman. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. 5, 0 5, 0 Варіант 10 1) Ввести координати початку і кінця відрізка в тримірному просторі, обчислити і вивести довжину відрізка. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. exp , 0 1 , 0 Варіант 11 1) Встановити взаємозв’язок між маркою машини, її максимальною швидкістю та вартістю за допомогою предиката car (type, speed, cost). Програма повинна містити внутрішню мету, що дозволяє вивести назви всіх машин з максимальною швидкістю більше 200 км/год., а також мету, яка дозволяє визначити всі машини, дорожчі за вказану ціну. У розділ тверджень ввести не менше десяти фактів. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатур. 1, 0 |sin 1 |, 1 3 Варіант 12 1) Встановити взаємозв’язки між ім’ям дитини і його віком за допомогою предиката child (name, age). Програма повинна містити предикат визначення старшинства за віком order (name, name) і зовнішню мету. У розділ тверджень ввести не менше десяти фактів. Системи штучного інтелекту 17 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. , 0 |sin |, 0 Варіант 13 1) Встановити взаємозв’язки родинних відносин з допомогою предиката family (people, people), що визначає наявність безпосереднього родинного зв’язку. Програма повинна містити визначення предиката прабатьківська grandfamily (people,people) з використанням предиката family і зовнішню мету. У розділ тверджень ввести не менше десяти фактів. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. sin , 0 1, 0 Варіант 14 1) Встановити взаємозв’язки родинних відносин з допомогою предиката parent (people, people), що визначає наявність безпосереднього родинного зв’язку. Програма повинна містити визначення предиката дядько uncle (people, people) з використанням предиката parent і зовнішню мету. У розділ тверджень ввести не менше десяти фактів. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. 2 4 3 , 0 , 0 Варіант 15 1) Встановити взаємозв’язки між ім’ям людини і його номером телефону за допомогою предиката phone_number (name, number). Програма повинна мати внутрішню мету, що включає введення з клавіатури імені, його висновок і виведення телефону. У розділ тверджень ввести не менше шести фактів. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. cos 1 , 0 sin 1 , 0 Варіант 16 1) Встановити взаємозв’язок між назвою музичного твору, жанром та автором за допомогою предиката music (title, type, author). Програма повинна мати зовнішню мету. У розділ тверджень ввести не менше 10 фактів. 18 В. Є. Стрілець, С. І. Шматков 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. 2| | 5, 0 1 , 0 1 Варіант 17 1) Встановити, чи є число, що аналізується, додатнім, нульовим або від’ємним, за допомогою предиката classify (number, sign). Програма повинна мати зовнішню мету. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. cos , 2 cos , 2 2 sin , 2 Варіант 18 1) Встановити взаємозв’язки родинних відносин за допомогою предиката parent (people, people), що визначає наявність безпосереднього родинного зв’язку. Програма повинна містити визначення предиката рідний брат або сестра і зовнішню мету. У розділ тверджень ввести не менше десяти фактів. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. 5, 0 5, 0 Варіант 19 1) Встановити взаємозв’язки родинних відносин за допомогою предиката parent (people, people), що визначає наявність безпосереднього родинного зв’язку. Програма повинна містити визначення предиката двоюрідний брат або сестра cousin (people, people) через предикат parent і зовнішню мету. У розділ тверджень ввести не менше десяти фактів. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. exp , 0 1 , 0 Варіант 20 1) Встановити взаємозв’язок між назвою витвору мистецтва, роком її створення та автором за допомогою предиката art (title, year, author). Програма повинна мати зовнішню мету. У розділ тверджень ввести не менше 10 фактів. 2) Скласти Пролог-програму обчислення функції y=f(x) для значень аргументу x, що вводиться з клавіатури. Системи штучного інтелекту 19 sin , 4 2 cos , 4 2 4 , 2 Контрольні питання 1. Поняття терму. 2. Поняття атому, змінної, складного терму. 3. Факти і предикати. 4. Запити у SWI-Prolog. 5. Правила та їх структура і синтаксис. 6. База даних і база знань у SWI-Prolog. 7. Вбудовані функції читання та виводу. 20 В. Є. Стрілець, С. І. Шматков Практична робота № 3 Рекурсія в SWI-Prolog Мета роботи: отримати навички у використанні рекурсивних викликів предикатів для розв’язання задач мовою програмування SWI-Prolog. Теоретичні відомості У SWI-Prolog циклічні обчислення виконуються за допомогою рекурсії. Рекурсія – це метод, який часто використовується для досягнення ефекту, аналогічного тому, що реалізується при використанні ітеративних керуючих конструкцій у процедурних мовах. Метод рекурсії має базис і крок. Базис рекурсії – це речення, яке визначає деяку початкову ситуацію або ситуацію у момент завершення. Як правило, у цьому реченні записується деякий найпростіший випадок, за якого відповідь отримується відразу без використання рекурсії. Крок рекурсії – це правило, у якому міститься як підціль виклик предиката, який визначається. Для того щоб запобігти зациклюванню, предикат, який визначається, повинен мати виклик не від тих параметрів, які вказані у заго- ловку правила. Параметри повинні змінюватися на кожному кроці так, щоб в результаті або був виконаний базис рекурсії, або умова виходу з рекурсії, яка розміщується у самому правилі. У загальному вигляді правило, яке реалізує крок рекурсії, виглядає так: <ім’я предикату, який визначається>:- [<підцілі>], [<умова виходу з рекурсії>], [<підцілі>], <ім’я предикату, який визначається>, [<підцілі>]. Один зі способів переходу до рекурсивних правил полягає в узагальнені нерекурсивних правил. Наприклад: parent(‘Anna’,’Tom’). parent(‘Mark’,’Tom’). parent(‘Paul’,’Monika’). %предикат для визначення предків ancestor(Ancestor, Descendant):- parent(Ancestor, Descendant). ancestor(Ancestor, Descendant):- parent(Ancestor,X), ancestor(X,Descendant). Запит матиме вигляд: ?- ancestor(X,’Tom’). X=‘Anna’. X=‘Mark’. Рекурсивний опис правила містить у собі посилання на заголовок цього правила. Системи штучного інтелекту 21 Обчислювальна рекурсія. Розглянемо варіант розв’язання задачі визначення факторіалу числа n. factorial(0,1):-!. /*умова виходу з рекурсії*/ factorial(N,F):- N1 is N-1, factorial(N1,F1), F is N*F1. У розв’язку спочатку вказана умова виходу з рекурсії. Далі записується рекурсивне правило factorial, аргументами якого є число N, для якого обчислюється факторіал, та F – результат обчислення. У тілі правила записується обчислювальне рекурсивне визначення факторіалу. У наведеному визначенні факторіалу використовується механізм відсікання (cut) «!». Відсікання є вбудованим предикатом і застосовується у випадках, коли потрібно змінити процес пошуку рішень. Виділяють три випадки використання відсікання: 1) якщо за деяких умов будь-яка ціль ніколи не повинна бути успішною. Комбінація cut-fail виключить виконання інших правил, які відповідають даній цілі. Наприклад, предикат not(P) можна визначити за допомогою відсікання: not(P):-P,!,fail. not(_):-true. 2) для запобігання нескінченних циклів. У наведеному прикладі для визна- чення факторіалу за допомогою відсікання забезпечується вихід з рекурсії. При виконанні першого правила за предикатом відсікання відбувається «заморо- жування» всіх альтернативних тверджень для factorial, які стоять нижче першого правила, тобто припиняється виконання рекурсивного правила; 3) при програмуванні взаємовиключних тверджень. Наприклад, sign(X,-1):-X<0,!. sign(X,0):-X=0,!. sign(X,1):-X>0. Вивід з останнього правила станеться лише тоді, коли X>0, у всіх інших випадках це правило не буде навіть розглядатися як альтернатива у точці повернення. Крім відсікання, для організації циклічних правил використовується предикат відмови fail. Предикат fail застосовується для отримання гаранто- ваного неуспіху при доведенні деякої цілі. Наприклад, правило A:-B,fail. буде виконуватися стільки разів, скільки є альтернатив для B у ньому. Розглянемо приклад використання предикату відмови. Створимо предикат, який буде виводити всі імена студентів. student(‘Math’,’Mary’). %першим аргументом є назва факультету, другим – ім’я студента student(‘Math’,’Loise’). student(‘Math’,’Fred’). student(‘Socio’,’Hanna’). student(‘Socio’,’Eddie’). student(‘Computer’,’Annete’). 22 В. Є. Стрілець, С. І. Шматков student(‘Computer’,’Karl’). stud_names:-student(_,Name), %виводить імена студентів з усіх факультетів write(Name),nl, fail. stud_facult(X):-student(X,Name), %виводить імена студентів з одного факультету write(Name),nl, fail. Приклад виклику предикатів ?- stud_names. Mary Loise Fred Hanna Eddie Annete Karl ?- stud_facult(‘Math’). Mary Loise Fred Розглянемо декілька прикладів використання обчислювальної рекурсії. Приклад 1. Предикат, що визначає n-не число Фібоначчі. Як перші два числа взяти 1. fibonachi(1,1). %перше число ряду – 1 fibonachi(2,1). %друге число ряду – 1 fibonachi(N,F):-N>2, %визначення чисел, починаючи з третього N1 is N-1, fibonachi(N1,F1), N2 is N-2, fibonachi(N2,F2), F is F1+F2. Виклик предиката ?- fibonachi(6,X). X = 8 . Приклад 2. Визначення суми непарних чисел з перших n чисел Фібоначчі. odd(X):-P is (X mod 2), P==1. %визначення непарного числа sumfibodd(N,X):-sumfibodd(N,0,X). %на початку сума дорівнює 0 sumfibodd(N,Sm,X):-N>0, N1 is N-1, fibonachi(N,F), (odd(F)-> Sm1 is Sm+F; Sm1 is Sm), sumfibodd(N1,Sm1,X). sumfibodd(0,Sm1,Sm1). %якщо кількість чисел 0, то сума не змінюється Виклик предиката ?- sumfibbodd(7,X). X = 23 Системи штучного інтелекту 23 Приклад 3. Обчислення функції Аккермана, визначеної на множині пар невід’ємних чисел , 1, якщо 0; , 1,1 , якщо 0, 0; 1, , 1 , якщо 0, 0. akkerman(0,0,1). akkerman(0,1,2). akkerman(X,Y,Z):- (X==0,Z is Y+1); (X>0, Y==0, X1 is X-1, akkerman(X1,1,Z)); (X>0,Y>0,X1 is X-1, Y1 is Y-1, akkerman(X,Y1,R1), akkerman(X1,R1,Z)). Виклик предиката ?- akkerman(3,2,X). X = 29 Приклад 4. Обчислити суму 10 членів функціонального ряду ∑ ! для заданого значення x=0.5. factorial(1,1). %визначення факторіалу factorial(N,F):- N>1, N1 is N-1, factorial(N1,F1), F is N*F1. sum(_,0,Y):-Y is 0. %початкове значення суми sum(X,N,Y):- N1 is N-1, factorial(N,F), sum(X,N1,Y1), Y is Y1+(X^(2*N-1)/F). Виклик предиката ?- sum(0.5,10,S). S = 0.5680508333754707 Завдання для практичної роботи 1. Розробити програму мовою SWI-Prolog для обчислення суми членів функціонального ряду для заданої кількості його членів n (з використанням рекурсій). Значення аргументу х взяти з вказаного діапазону. 2. Скласти звіт з роботи, в який додати лістинг програми та копію вікна з результатом виклику створених предикатів. 24 В. Є. Стрілець, С. І. Шматков Варіанти завдань № Функціональний ряд Діапазон зміни аргументу Кількість членів ряду n 1 2 3 4 1 3 ! [0.1;1] 10 2 cos [π/5;9π/5] 16 3 1 2 1 [0.1;1] 10 4 1 sin [π/5;4π/5] 18 5 ! [1;2] 15 6 cos /4 [0.1;1] 13 7 1 2 ! [0.1;1] 10 8 /4 [0.1;0.8] 14 9 4 1 [0.1;0.8] 17 10 cos ! [0.1;1] 20 11 2 1 ! [0.1;1] 10 12 cos /3 [0.1;0.8] 18 13 1 2 1 1 1 [0.2;1] 11 Системи штучного інтелекту 25 1 2 3 4 14 1 cos [π/5;π] 20 15 1 4 1 [0.1;1] 15 16 sin 2 1 2 1 [π/10;9π/10] 14 17 2 ! [0.1;1] 12 18 cos 2 4 1 [0.1;0.8] 13 19 2 ! [0.1;1] 20 20 1 ! 2 [0.1;1] 17 Контрольні питання 1. Поняття рекурсії. 2. Базис та крок рекурсії. 3. Відсікання у SWI-Prolog. 4. Відмова у SWI-Prolog. 5. Особливості обчислювальної рекурсії. 26 В. Є. Стрілець, С. І. Шматков Практична робота № 4 Списки у SWI-Prolog Мета роботи: ознайомитись з поняттям списку у SWI-Prolog та навчитись використовувати списки для розв’язання задач мовою SWI-Prolog. Теоретичні відомості Список – це упорядкована послідовність елементів. Елементами списку можуть бути будь-які терми SWI-Prolog. Зручною формою запису списків є списочне позначення. У цьому позначенні кожний елемент списку відокрем- люється від іншого комою, а весь набір елементів береться у квадратні дужки, наприклад [a,b,c,d]. Фактично список – це структура з функтором ‘·’/2 (точка з арністю 2). За цим визначенням список складається з першого елемента і хвоста, який є списком з решти елементів. Пустий список – це список, який не містить жодного елемента, він позначається []. Приклади списків наведені у табл. 4. Таблиця 4 Приклади списків та їх записів № Елементи списку Запис із дужками Запис з функтором ‘·’ 1 a [a] ‘·’(a,[]) 2 a b c [a,b,c] ‘·’(a, ‘·’(b, ‘·’(c,[]))) 3 [a] [[a]] ‘·’(‘·’(a,[]),[]) 4 [] [[]] ‘·’([],[]) 5 [a] [b, c] [[a],[b,c]] ‘·’(‘·’(a,[]), ‘·’(b, ‘·’(c,[]))) Список уніфікується з іншим списком, якщо попарно уніфікуються їх елементи. Список можна ділити на «голову» і «хвіст» за допомогою операції відділення голови, яка позначається вертикальною рискою (|), тобто [Голова| Хвіст]. Голова – фіксована кількість елементів. Хвіст – список із решти елементів списку. Найчастіше використовується голова, яка складається з одного елемента. Приклади списків наведені у табл. 5. Таблиця 5 Приклади співставлення списку зі списком [Голова| Хвіст] № Список Голова Хвіст 1 [a] A [] 2 [a,b,c] A [b,c] 3 [[a]] [a] [] 4 [] не співставляється не співставляється 5 [a|[c,d]] A [c,d] Системи штучного інтелекту 27 Список [1,2|[3,4]] дорівнює списку [1,2,3,4]. При співставленні зі списком [X,Y|Z] отримаємо X=1, Y = 2 і Z = [3,4]. У SWI-Prolog є особливий вид списків – символьні списки. Символьний список – це фактично послідовність цілих чисел, які відповідають ASCII-коду символів. Символьні списки беруться у подвійні лапки. Приклад списків, які можна співставити: “abc”, [97,98,99], ‘·’(97, ‘·’(98, ‘·’(99,[]))). Розглянемо декілька прикладів роботи зі списками. Приклад 1. Поділити список на голову і хвіст. write_list([]). write_list([H|T]):- /* виділити голову і хвіст, */ write(H), nl, /* вивід голови */ write_list(T)./*рекурсивний виклик для решти елементів списку*/ Приклад 2. Об’єднання і розділення списків. append([],List,List). append([X|L1],List2,[X|L3]):-append(L1,List2,L3). Виклик предиката ?- append([s,d,f],[b,n,m],X). X = [s, d, f, b, n, m]. Зауваження. Предикат append /3 є вбудованим у SWI-Prolog. Приклад 3. Використовуючи поняття списку, напишіть програми для наступних задач: а) визначення довжини списку (довжина пустого списку дорівнює 0; довжина непустого списку дорівнює довжині його хвоста плюс 1). list_lenght([],0). list_lenght([_|T],N):- list_lenght(T,N1), N is N1+1. ?- list_lenght([s,b,g,5,r,4],X). X = 6. б) визначити, чи належить елемент списку (елемент належить списку, якщо він – його голова; елемент належить списку, якщо він належить хвосту списку). inlist(R,[R|_]). inlist(R,[_|T]):- inlist(R,T). ?- inlist(s,[4,6,7,h,n,b]). false. ?- inlist(n,[4,6,7,h,n,b]). True в) пошук суми елементів числового списку. sum_list([],0). sum_list([H|T],S):- sum_list(T,S1), S is S1+H. ?- sum_list([3,6,7,2,9],S). S = 27. 28 В. Є. Стрілець, С. І. Шматков г) пошук максимального і мінімального елементів списку. max_list([X],X). max_list([H|T],H):-max_list(T,M),H>M. max_list([_|T],M):-max_list(T,M). min_list([X],X). min_list([H|T],H):-min_list(T,M),H/<арність>. Розглянемо наприклад базу даних щодо членів студентського клубу, яка містить інформацію про: прізвище, вік чи сплачений внесок. :- dynamic member/3. member(‘Vakulenko’, 33, pay). member(‘Ivanenko’, 15, pay). member(‘Vovchenko’, 27, pay). member(‘Petrenko’, 20, no_pay). member(‘Khomenko’, 25, no_pay). Для додавання фактів до бази даних використовують вбудовані предикати assert (у кінець) і asserta (у початок). Наприклад: assert(member(Surname,Age,Pay_data)). Для видалення фактів з бази даних є вбудовані предикати retract (видалити лише один запис) і retractall (видалити усі записи для заданого значення аргументу). Наприклад: %видалення всіх записів із вказаним прізвищем retractall(member(Surname,_,_)). Для того щоб змінити запис у базі даних, необхідно його спочатку видалити, а потім замість нього додати інший з новою інформацією. Розглянемо роботу з базою даних про членів клубу. Передбачимо такі можливості: перегляд інформації, додавання нового запису, видалення запису і зміна запису. Для початку необхідно видалити будь-яку інформацію про розглядувану базу даних, якщо вона зберігається у пам’яті, і завантажити базу даних із файлу, де вона зберігається: start:- retractall(member/3), reconsult(‘club_members.pl’), Системи штучного інтелекту 31 dynamic(member/3), menu. В останньому рядку йде виклик запиту menu, у якому описані дії для роботи з базою даних. Запит reconsult() завантажує на виконання файл, ім’я якого вказане у дужках. У предикаті dynamic() вказується ім’я бази даних. Далі записується запит menu: menu:-repeat, nl,nl,write("Menu"),nl, write("1. Information about club members"),nl, write("2. Change information about club members"),nl, write("3. Add club member record"),nl, write("4. Delete club member record"),nl, write("0. Output"),nl,nl, write("Enter the menu item number: "), read(X), process(X), db_save. Тут користувачу надається перелік дій з базою даних, і програма чекає поки буде введений номер дії (read(X)), потім відповідно до введеного номера викликається дія (process(X)) і в кінці при завершенні роботи всі зміни у базі даних зберігаються (db_save). Якщо користувач вводить «0» виконання програми завершується, якщо вводить номер від 1 до 4, то здійснюється перехід до подальших дій. process(0):-!. process(X):-item(X),fail. Якщо введено «1», то користувачу надається поточна інформація з бази даних. item(1):-nl,write("Club members"),nl, write("Surname\t\t"),write("Age\t"),write("Summ\t"), nl,give_info(_),!. Запит give_info() з бази даних зчитує інформацію та виводить користувачу. give_info(member(Surname,Age,Pay_data)):- member(Surname,Age,Pay_data), write(Surname),write("\t"),write(Age),write("\t"), write(Summ),write("\t"),write(Pay_data), nl,fail, give_info(_). Якщо введено «2», то користувачу надається можливість змінити деяку інформацію у базі даних. Наприклад, змінити прізвище. item(2):-nl,change_member, write("The information was changed."), nl,!. change_member:- nl,write("Change information about club member: "),nl, 32 В. Є. Стрілець, С. І. Шматков write("of Surname/Enter 1\n"),write("of Age/Enter 2\n"), write("of Payment/Enter 3"),read(N), change(N), db_save, nl. change(1):-write("Enter member’s Surname "),read(Surname),nl, write("Enter new Surname "),read(New_Surname), member(Surname,Age,Pay), A=Age, P=Pay, retract(member(Surname,_,_)), asserta(member(New_Surname,A,P)). Змінювати інформацію можна за будь-яким параметром, наприклад, якщо внесок був сплачений, то необхідно змінити відповідний статус. Якщо введено «3», то користувач має можливість додати новий запис. item(3):-nl,write("Enter information about new club member"),nl, write("Surname "),read(Surname), write("Age"),read(Age), write("Contribution payment stamp "),read(Pay_data), add_member(member(Surname,Age,Pay_data)),!. add_member(Member):-assertz(Member). Якщо введено «4», то користувач має можливість видалити запис за деяким параметром (наприклад, без сплати внеску при N=3). item(4):-nl,write("Delete information about club member"),nl, write("of Surname/Enter 1\n"),write("of Age/Enter 2\n"), write("of Payment/Enter 3"),read(N), ((N=1,write("Enter Surname"), read(Surname), delete_member(member(Surname,_,_))); (N=2,write("Enter Age"),read(Age),delete_member(member(_,Age,_))); (N=3,write("Delete all without payment"), delete_member(member(_,_,no_pay)))),!. delete_member(Member):-retractall(Member). Для збереження оновленої бази даних у файл передбачений предикат db_save. db_save:- tell(‘club_members.txt’), %відкрити файл для запису listing(member), %записати дані про членів клубу у файл told. %закрити файл На рис. 1–2 показаний приклад запуску і роботи з наведеним меню. На рис. 1 показаний початок роботи з програмою і виведення користувачу інформації з бази даних. Системи штучного інтелекту 33 Рис. 1 – Виведення інформації про членів студентського клубу На рис. 2 показано, як видалені з бази даних записи з прізвищем «Ivanenko». Рис. 2 – Видалення записів за прізвищем Після видалення можна знов вивести оновлену інформацію для перевірки роботи програми (рис. 3). 34 В. Є. Стрілець, С. І. Шматков Рис. 3 – Перевірка видалення записів і вихід з меню Таким чином, створене достатньо просте і зрозуміле меню для роботи з простою базою даних. Наведений приклад бази даних є показовим, оскільки не містить ключові елементи, які б ідентифікували конкретного члена клубу. Завдання для практичної роботи 1. Розробити програму для роботи з базою даних за варіантом. 2. Створити меню для обробки бази даних. Обов’язково мають бути запити: додавання нового рядка, зміна запису та видалення запису з бази даних. Кількість фактів у базі даних повинна бути 10 і більше. 3. Скласти звіт з роботи, в який додати лістинг програми та копію вікна з результатом виклику пунктів меню. Варіанти тем баз даних: 1. Конфігурація персонального комп’ютера. 2. Програмне забезпечення для персонального комп’ютера користувача. 3. Тарифні плани операторів мобільного зв’язку. 4. Обладнання для комп’ютерної мережі. 5. Програмне забезпечення для підприємства. 6. Пакети прикладних програм для розв’язання задач. 7. Програмне забезпечення для комп’ютерної мережі. 8. Наукова література у бібліотеці (для написання реферату тощо). 9. Спеціальності для навчання у вищому навчальному закладі. 10. Тури для відпочинку або подорожі. 11. Поточна успішність студентів на факультеті. 12. Результати сесії на факультеті. 13. Розклад занять у семестрі. 14. Інформація про пацієнта у лікарні. Системи штучного інтелекту 35 15. Забезпеченість літературою навчального процесу. 16. Інформація про співробітників на підприємстві (декілька відділів). 17. Розклад руху поїздів на станції. 18. Художня література у бібліотеці (для школярів). 19. Інформація про навчальні заклади у регіоні. 20. За вибором студента. Контрольні питання 1. Особливості бази даних у SWI-Prolog. 2. Як вказати, що база даних є динамічною? 3. Які є предикати для додавання записів? 4. Які є предикати для видалення записів? 5. Як змінити запис у базі даних? 6. Як зберегти зміни у базі даних? 36 В. Є. Стрілець, С. І. Шматков Практична робота № 6 Пошук у просторі станів Мета роботи: ознайомитися з алгоритмами пошуку у просторі станів; реалізувати алгоритми пошуку у шир, у глибину та жадібний пошук мовою SWI-Prolog. Теоретичні відомості Пошук у глибину Пошук у глибину просто шукає будь-який шлях між двома станами, тому немає ніяких гарантій, що він буде найкоротшим. Цей пошук можна використовувати для пошуку всіх шляхів між двома станами. Застосовується для незважених графів. Припустимо, що заданий неорієнтований граф (рис. 4). І потрібно знайти всі шляхи від вершини «а» до вершини «с». Спочатку задаємо набір фактів, які будуть відображати ребра графа, а також визначаємо правило одного кроку move. m(a,b). m(b,c). m(a,d). m(b,d). m(c,d). m(c,e). m(d,e). move(A,B):-m(A,B);m(B,A). %оскільки граф неорієнтований Шлях, який пройшли, зберігаємо у вигляді списку станів, але у зворотному порядку, тобто стартова вершина буде розташовуватися вкінці, а поточна – на початку. Щоб подовжити шлях на один крок, необхідно знайти, який крок можна зробити, і щоб не було зациклювання – перевірити, щоб цей крок не привів до стану, у якому вже були. prolong([Temp|Tail],[New,Temp|Tail]):- move(Temp,New),not(member(New,[Temp|Tail])). Предикат пошуку у глибину: dpth([Finish|Tail],Finish,[Finish|Tail]). %якщо поточна вершина %співпадає з кінцевою, то шлях знайдений dpth(TempWay,Finish,Way):- prolong(TempWay,NewWay), %намагаємося зробити крок dpth(NewWay,Finish,Way).%продовжуємо пошук уже з урахуванням %зробленого кроку Рис. 4 – Неорієнтований граф Системи штучного інтелекту 37 Допоміжний предикат для зручності користувача: search_dpth(Start,Finish):- dpth([Start],Finish,Way),%викликаємо пошук у глибину, вважаючи, що %шлях складається лише з початкової вершини show_answer(Way).%виводимо шлях на екран у наочному вигляді Для виводу на екран використовуємо спеціальний предикат, у якому враховується, що шлях зберігається у зворотному порядку: show_answer([_]):-!. show_answer([A,B|Tail]):- show_answer([B|Tail]),nl,write(B),write(‘ -> ‘),write(A). Результат роботи методу ?- search_dpth(a,c). a -> b b -> c true Пошук усіх шляхів ?- search_dpth(a,c),nl,nl,nl,fail. a -> b b -> c a -> b b -> d d -> e e -> c a -> b b -> d d -> c a -> d d -> e e -> c a -> d d -> b b -> c a -> d d -> c false. Пошук у ширину Цей вид пошуку також застосовується для незважених графів, але може знаходити найкоротший шлях (або за бажанням найдовший). Будемо зберігати не один шлях, який був пройдений, а список усіх можливих шляхів, які можна було б пройти. Вони будуть розташовані від більш коротких до більш довгих. Кожний з них, як і у пошуку у глибину, буде записаний у зворотному порядку. %якщо у поточного шляха перша вершина співпадає з кінцевою, %то даний шлях є відповіддю bdth([[Finish|Tail]|_],Finish,[Finish|Tail]). 38 В. Є. Стрілець, С. І. Шматков bdth([TempWay|OtherWays],Finish,Way):- findall(W,prolong(TempWay,W),Ways),%також можна знайти всі %способи, за якими можна зробити крок з поточного стану першого шляху append(OtherWays,Ways,NewWays),%додаємо всі ці способи у кінець %списку шляхів bdth(NewWays,Finish,Way).%і продовжуємо пошук Оскільки всі шляхи у списку розташовуються від більш коротких до більш довгих (хоча їхня довжина найчастіше відмінна лише на один крок, оскільки після огляду шлях відразу відкидається), то коли вперше виконується правило bdth([[Finish|Tail]|_], Finish, [Finish|Tail]), знайдений шлях гарантовано буде найкоротшим. Також потрібно змінити допоміжний предикат search_bdth(Start,Finish):- bdth([[Start]],Finish,Way),%спочатку список шляхів складається %з одного шляху, який містить початкову вершину show_answer(Way). Усі шляхи у графі у порядку збільшення довжини ?- search_bdth(a,c),nl,nl,nl,fail. a -> d d -> c a -> b b -> c a -> d d -> e e -> c a -> d d -> b b -> c a -> b b -> d d -> c a -> b b -> d d -> e e -> c false. Якщо потрібний навпаки найдовший шлях, то необхідно поміняти місцями bdth. Усі шляхи у графі у порядку зменшення довжини ?- search_bdth(a,c),nl,nl,nl,fail. Системи штучного інтелекту 39 a -> b b -> d d -> e e -> c a -> b b -> d d -> c a -> d d -> b b -> c a -> d d -> e e -> c a -> b b -> c a -> d d -> c false. Пошук з ітераційним заглибленням Також створений для незважених графів. Головним недоліком пошуку у ширину є великий об’єм використаної пам’яті, а пошук з ітераційним заглиб- ленням навпаки використовують її економно. Сенс даного пошуку полягає у тому, що перебираємо максимальну глибину пошуку, починаючи з 1 і до якогось обмежувального числа, і для кожної такої максимальної глибини запускається пошук у глибину з відповідним обмеженням. Таким чином спочатку шукають усі шляхи довжини 1, потім усі шляхи довжини 2, усі шляхи довжини 3 і т. д. Як тільки знайдеться розв’язок, цей знайдений шлях і буде найкоротшим. Спочатку визначимо предикат, який генерує максимальну глибину пошуку, тобто цілі числа від 1 і далі. int(1). int(N):-int(M),N is M+1. Змінюємо предикат dpth з пошуку у глибину з урахуванням того, що глибина пошуку буде обмежена. id([Finish|Tail],Finish,[Finish|Tail],0). id(TempWay,Finish,Way,N):-N>0, prolong(TempWay,NewWay),N1 is N-1, id(NewWay,Finish,Way,N1). Зрештою створюємо головний предикат, який перебирає обмеження глибини і визиває предикат id. search_id(Start,Finish):- int(Level),%вибираємо наступне значення обмеження глибини (Level>100,!;%обов’язково треба поставити обмеження на неї оскільки %якщо шлях взагалі не існує, то без перевірки програми зациклюється 40 В. Є. Стрілець, С. І. Шматков id([Start],Finish,Way,Level),%якщо глибина допустима, то %викликається пошук show_answer(Way)). Пошук на основі вагової функції Розглянемо пошук для зважених графів. Нехай заданий зважений граф (рис. 5). Задамо довжини ребер. m(a,b,10). m(b,c,7). m(a,d,3). m(b,d,5). m(c,d,15). m(c,e,7). m(d,e,5). move(A,B,C):-m(A,B,C);m(B,A,C). Будемо зберігати не тільки шлях, який був пройдений, але й його довжину у вигляді Довжина:[ПоточнаВершина, ПопередняВершина ... ПочатковаВершина]. Усі розглянуті шляхи будуть відсортовані у списку не за кількістю вузлів, а за їх довжиною, для цього введемо додаткові предикати. Предикат, який додає новий шлях у список уже згенерованих шляхів на потрібне місце. %предикат placeone приймає як параметр новий шлях, а також отримані до %цього шляхи, які вже відсортовані відносно їх довжини, і повертає %новий список шляхів, отриманий після додатку першого параметру у %список шляхів на потрібне місце, тобто зберігаючи відсортованість %якщо довжина нового шляху не більша довжини шляху, який знаходиться %на першому місце, тоді цей новий шлях розташовуємо на перше місце placeone(Length:Way,[LengthH:WayH|Tail],[Length:Way,LengthH:Wa yH|Tail]):-Length= d d -> e e -> c Length of way: 15 true Усі шляхи в порядку зростання довжини ?- search_bst(a,c),nl,nl,nl,fail. a -> d d -> e e -> c Length of way: 15 a -> d d -> b b -> c Length of way: 15 a -> b b -> c Length of way: 17 a -> d d -> c Length of way: 18 42 В. Є. Стрілець, С. І. Шматков a -> b b -> d d -> e e -> c Length of way: 27 a -> b b -> d d -> c Length of way: 30 false. Жадібний алгоритм При пошуку шляху можна враховувати наскільки близько від фінішного стану (у сенсі якогось критерію) знаходиться поточний стан. Цей критерій називається евристичною функцією або евристикою. Він ставить у відповідність двом станам деяке число, яке характеризує «відстань» між ними. Наприклад, для відомої задачі про переміщення меблів евристикою може бути кількість пред- метів, які на даному етапі стоять на небажаних місцях, а для точок на площині просто геометрична відстань між ними. У даному алгоритмі пріоритет визначається не його сумарною довжиною (вона взагалі не підраховується), а близькістю кінцевої вершини шляху і заданою фінішною вершиною. Припустимо, є набір точок на площині, деякі з яких поєднані між собою (рис. 6). Евристикою вважаємо геометричну відстані між точками. Задамо дану структуру як набір точок з їх координатами і набір ліній, які зв’язують їх. point(a,2,5). point(b,4,5). point(c,0,0). point(d,4,10). point(e,7,8). point(f,12,7). point(g,14,4). r(a,c). r(c,b). r(b,g). r(g,f). r(g,d). r(f,d). r(e,d). r(a,e). road(A,B):-r(A,B);r(B,A). Шлях буде представлений списком вершин prolong([Temp|Tail],[New,Temp|Tail]):- road(Temp,New),not(member(New,[Temp|Tail])). І вводимо евристичну функцію, у якій важливими є поточна і кінцева вершини шляху. Рис. 6 – Набір точок на площині Системи штучного інтелекту 43 wt([TempPoint|_],FinishPoint,L):- point(TempPoint,XA,YA),point(FinishPoint,XB,YB), Sum is (XA-XB)*(XA-XB)+(YA-YB)*(YA-YB), L is sqrt(Sum). Предикат додавання нового шляху на потрібне місце у списку шляхів %порівнюється евристики кінцевих вершин шляхів placeone(Way,[WayH|Tail],Finish,[Way,WayH|Tail]):- wt(Way,Finish,A),wt(WayH,Finish,B),A= b b -> c c -> a true . Але цей результат неправильний, вірною відповіддю є ?- search_bst(g,a). g -> d d -> e e -> a Length of way: 21.0984 true Тобто цей алгоритм не гарантує правильності результатів. Програма отримала таку відповідь, тому що за одним зі шляхів більш пріоритетним є шлях g-b, оскільки b ближча до фінішної вершини, ніж f або d. Шлях g-b можна продовжити лише одним способом g-b-c, і вершина c знов-таки стає не менш пріоритетною, ніж f або d, після чого просто завершується шлях. І ось отримане, що b близька до фінішної, c недалека від фінішної, але те, що вони одна від одної далекі зовсім не враховувалось, що й призвело до помилки. Але на практиці цей алгоритм можна використовувати, адже, наприклад, якщо б виконувався пошук шляху між двома реальним містами, то результат був би вірним, через рівномірне розташування міст/селищ і відповідних доріг між ними. Завдання для практичної роботи 1. Запрограмувати методи пошуку у глибину, у ширину та жадібний пошук для незважених графів і метод пошуку найкоротшого шляху для зваженого графа. 2. Застосувати функції для пошуку шляхів для графів відповідно до варіантів. 3. Скласти звіт з роботи. Він повинен містити лістинг всіх функцій та їх застосування для пошуку у графі. Для зваженого графу вивести найкоротший шлях і всі можливі шляхи і їх довжини. 44 В. Є. Стрілець, С. І. Шматков Варіанти завдань 1. Незважені графи № Граф № Граф 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Системи штучного інтелекту 45 15 16 17 18 19 20 2. Зважені графи № Граф № Граф 1 2 3 4 5 6 46 В. Є. Стрілець, С. І. Шматков 7 8 9 10 11 12 Контрольні питання 1. Методи пошуку у глибину і ширину. 2. Метод пошуку з ітераційним заглибленням. 3. Жадібний пошук. 4. Пошук А*. Системи штучного інтелекту 47 Практична робота № 7 Віконні додатки у SWI-Prolog Мета роботи: ознайомитися з можливостями розробки віконних додатків мовою SWI-Prolog та навчитися створювати прості віконні додатки. Теоретичні відомості Існує більше 20-ти програмних реалізацій мови Prolog, всі вони мають свої особливості, переваги і недоліки. Не так багато з них надають можливість створювати віконні додатки, SWI-Prolog є однією з таких реалізацій. SWI-Prolog дозволяє створювати прості віконні додатки та багатовіконні з переходами між вікнами. Для того щоб мати можливість створювати і обробляти запити з використанням діалогових вікон, необхідно підключити бібліотеку pce: :-use_module(library(pce)). Розглянемо створення діалогового вікна на прикладі роботи з даними про працівників деякої організації. Спочатку створюємо основне діалогове вікно: new(D,dialog(‘Define employee’)), % D – змінна, яка відповідає об’єкту %«вікно», dialog(‘Define employee’) – тип об’єкта діалогове вікно, у дужках %можна записати заголовок вікна. … send(D,open). %відкрити діалогове вікно, рядок є обов’язковим, %без нього вікно не з’явиться на екрані Далі додаємо об’єкти, це можуть бути: кнопки, елементи для вводу тексту, списки, меню, текст або надписи та ін. Наприклад, для вводу текстової інформації елемент text_item: new(N1, text_item(first_name)) % N1 – ім’я змінної об’єкта, % first_name – пояснюючий текст Для вибору з двох елементів можна використати елемент menu: new(S, menu(sex)),% вказуємо стать send_list(S, append, [male, female]), %додаємо значення у menu у вигляді списку Для вводу числової інформації з точного діапазону можна використати елемент int_item: new(A, int_item(age, low := 18, high := 65)) % low – найменше значення, high - найбільше Якщо потрібно додати список, що розкривається, для вибору, то можна використати також елемент menu з параметром cycle: new(D, menu(department, cycle)), % список, що розкривається, з назвами відділів send_list(D, append, [research, development, marketing]) %список відділів 48 В. Є. Стрілець, С. І. Шматков Основним елементом керування та для обробки запитів використовуються кнопки button. Наприклад, дві кнопки: для виходу з вікна (закрити) та обробки даних, які були введені у вікні. button(cancel, message(Dialog, destroy)),%кнопка закриття діалогу button(enter, and(message(@prolog, %кнопка, яка викликає запит assert_employee assert_employee, N1?selection, %зчитування з відповідних елементів N2?selection, %введеної інформації S?selection, A?selection, D?selection), message(Dialog, destroy))) %закриття діалогу Якщо кнопку треба визначити як «за замовчуванням», це можна вказати так: send(Dialog, default_button, enter) Запит, який буде зчитувати введену інформацію про робітника і виводить повідомлення на консольний екран: assert_employee(FirstName, FamilyName, Sex, Age, Depth) :- format(‘Adding ~w ~w ~w, age ~w, working at ~w~n’, [Sex, FirstName, FamilyName, Age, Depth]). Далі на рис. 7 показаний повний код для створення діалогового вікна «Define employee». На рис. 8 і 9 показаний результат запуску коду та введення даних. Рис. 7 – Програмний код діалогового вікна «Define employee» Системи штучного інтелекту 49 Рис. 8 – Діалогове вікно Рис. 9 – Введення даних На рис. 10 показане повідомлення на консолі, яке з’являється після натискання кнопки «Enter». Рис. 10 – Результат роботи запиту assert_employee Далі розглянемо створення віконного додатку для роботи з базою даних з інформацією про членів клубу (розглянута у практичній роботі № 5). Програмна реалізація буде мати декілька вікон: для вибору дії з базою даних, для виводу інформації на екран, для вводу нових даних тощо. У першому вікні, яке з’явля- ється при роботі з додатком, необхідно обрати потрібну дію для роботи з базою даних (рис. 11). У меню Action треба обрати одну з можливих дій: ‘View the database’,’Add record to the database’, ‘Delete record from the database’ або ‘Change record in the database’, і натиснути кнопку Ok. Програмний код для цього вікна доволі зрозумілий: start:-new(D,dialog(‘Club members data’)), send(D,append,new(L1,label)),%пояснююче повідомлення send(L1,append,’This window is intended to work with the club database’), send(D,append,new(L2,text)), send(L2,append,’Select Database action’), send(D,append,new(Act,menu(action,cycle))),%меню вибору дій send_list(Act,append,[‘ ‘,’View the database’, ‘Add record to the database’, ‘Delete record from the database’, ‘Change record in the database’]), send(D,append,button(choice,message(@prolog,work_item,Act?selectio n))), send(D,append,button(ok,message(D,destroy))), send(D,open). Рис. 11 – Вікно вибору дії 50 В. Є. Стрілець, С. І. Шматков При натисненні кнопки «Choice» викликається запит work_item(), який є основним, і за обраною дією здійснює перехід до відповідних дій. work_item(Item):-((Item=‘View the database’,X is 1); (Item=‘Add record to the database’,X is 2); (Item=‘Delete record from the database’,X is 3); (Item=‘Change record in the database’,X is 4)), process(X). process(X):-retractall(member/3),%завантажує базу даних reconsult(‘club_members.pl’), dynamic(member/3), item(X).%викликає запит відповідний X При виборі «View the database» (переглянути базу даних), з’явля- ється вікно з відповідною інформацією (рис. 12). Код створення цього вікна: item(1):-new(D1,dialog(‘Information about club members’)), send(D1,append,new(L,label)), send(L,append,’All information about club members’), send(D1,append,new(Lb,list_browser)),%поле виводу списку send(Lb,size,size(50,20)),%розмір поля send(Lb,alignment,center), send_list(Lb,append,[‘Club members\n Surname Age Payment’]),%додавання записів на поле member(Surname,Age,Pay_data), string_concat(Surname," ",S1), string_concat(Age," ",S2), string_concat(S1,S2,S3),string_concat(S3,Pay_data,S4), send_list(Lb,append, [S4]), send(D1,append,button(ok,message(D1,destroy))), send(D1,open),fail. При виборі «Add record to the database» (додати запис) з’являється вікно для вводу інформації про нового члена клубу (рис. 13). Після натиснення кнопки «Add record» з’являється повідом- лення, що запис був доданий (рис. 14). Код створення вікна вводу нових даних: item(2):- new(D2,dialog(‘Add new club member’)), send(D2,append,new(L,label)), send(L,append,’Enter data about new club member’), send(D2,append,new(S1,text_it em(surname))), send(D2,append,new(S2,int_item(age,low:=1, high:=99))), send(D2,append,new(S3,menu(payment))), Рис. 12 – Вивід інформації з бази даних Системи штучного інтелекту 51 send_list(S3,append,[‘pay’,’no_pay’]), send(D2,append,button(add_record,message(@prolog, add_record,S1?selection, S2?selection, S3?selection))), send(D2,append,button(cancel,message(D2,destroy))), send(D2,open). add_record(Surname,Age,Pay):- add_member(member(Surname,Age,Pay)), new(M,dialog(‘Add result’)), send(M,append,new(L,label)), send(L,append,’New record is saved!’), send(M,open). Рис. 13 – Вікно вводу нових даних Рис. 14 – Повідомлення про збереження даних Аналогічно створюються вікна для зміни та видалення інформації з бази даних. Також у SWI-Prolog є можливість додавати графічні об’єкти на діалогове вікно, наприклад, зображення: send(W,append, new(bitmap(‘web1.bmp’))) Крім того, можлива робота з простими графічними об’єктами (додаток Б). Завдання до практичної роботи 1. Створити віконний додаток для роботи з базою даних за варіантом. Дій для роботи з базою даних має бути не менше трьох. Обов’язково має бути перегляд поточної інформації, додавання нової і видалення запису з бази даних. 2. Скласти звіт з роботи, в який додати лістинг програми та копії вікна з результатом виклику дій. Варіанти 1. Конфігурація персонального комп’ютера. 2. Програмне забезпечення для персонального комп’ютера користувача. 3. Тарифні плани операторів мобільного зв’язку. 52 В. Є. Стрілець, С. І. Шматков 4. Обладнання для комп’ютерної мережі. 5. Програмне забезпечення для підприємства. 6. Пакети прикладних програм для розв’язання задач. 7. Програмне забезпечення для комп’ютерної мережі. 8. Наукова література у бібліотеці (для написання реферату тощо). 9. Спеціальності для навчання у вищому навчальному закладі. 10. Тури для відпочинку або подорожі. 11. Поточна успішність студентів на факультеті. 12. Результати сесії на факультеті. 13. Розклад занять у семестрі. 14. Інформація про пацієнта у лікарні. 15. Забезпеченість літературою навчального процесу. 16. Інформація про співробітників на підприємстві (декілька відділів). 17. Розклад руху поїздів на станції. 18. Художня література у бібліотеці (для школярів). 19. Інформація про навчальні заклади у регіоні. 20. За вибором студента. Контрольні питання 1. Які об’єкти можна додавати на діалогове вікно? 2. Який предикат обов’язково має бути вказаний для відображення будь- якого вікна? 3. З якого предиката починається створення будь-якого об’єкта? 4. Як вказати, що кнопка має бути за замовчуванням? 5. Яким чином викликається запит при натисканні кнопки? 6. Чи можна викликати нове вікно при натисканні кнопки? 7. Чи є можливість роботи з графічними об’єктами? Системи штучного інтелекту 53 Додатки Додаток А Початок роботи у SWI-Prolog. Найпростіша програма Для встановлення SWI-Prolog на персональний комп’ютер необхідно завантажити з офіційного сайту https://www.swi-prolog.org/download/daily/bin/ файл swipl_w32.exe (swipl_w64.exe) безкоштовно і запустити його. Після встановлення можна приступати до роботи. Запускаємо програмне середовище SWI-Prolog. З’являється головне вікно (рис. А.1). Через головне меню можна створити, відкрити, запустити файли програм, а також у розділі Debug відстежити виконання програм. Рис. А.1 – Головне вікно SWI-Prolog Програма мовою SWI-Prolog складається з фактів і правил, які створюють базу знань програми, і запиту до цієї бази знань, який задає ціль пошуку рішень. Предикати описують відношення між об’єктами, які є аргументами предиката. Факти констатують наявність заданого предикатом відношення між вказа- ними об’єктами. Наприклад, констатація факту у реченні «Еллен любить теніс» у синтак- сисі SWI-Prolog має вигляд любить(‘Еллен’, теніс). Де «любить» – ім’я відношення (предиката), «Еллен, теніс» – імена об’єктів (значення аргументів). 54 В. Є. Стрілець, С. І. Шматков Імена предикатів (функторів) і об’єктів повинні починатися з маленької літери і можуть містити латинські літери, кирилицю, цифри і знак підкреслю- вання «_». Зазвичай предикатам дають такі імена, щоб вони відображали сенс відношення, наприклад: main, start, add_file. Два предикати можуть мати однакові імена, тоді система розпізнає їх як різні предикати, якщо вони мають різну кількість аргументів (арність). Наприклад, like/2, like/3. Ім’я предиката може співпадати з іменем якогось вбудованого у SWI- Prolog предиката. У такому випадку при звернені до нього буде викликаний предикат користувача, тобто визначення предиката користувачем є більш пріоритетним для інтерпретатора. Правила описують зв’язки між предикатами. Наприклад, речення: «Білл любить все, що любить Том», – у синтаксисі SWI-Prolog любить(‘Білл’,Щось):-любить(‘Том’,Щось). Правило В:-А відповідає імплікації А→В («Якщо А, то В»). У загальному вигляді правило – це конструкція виду: P0:-P1,P2,…,Pn, яку читаємо «P0 істино, якщо P1,P2,…,Pn є істинними». Предикат P0 називається заголовком правила, вираз «P1,P2,…,Pn» – тілом правила, предикати Pі – підцілями правила. Кома між предикатами означає логічне «І». Якщо необхідно записати диз’юнктивне правило (логічне «АБО»), то правила розділяють крапкою з комою «;». Факти і правила називаються твердженнями. Факт можна розглядати як правило, яке має заголовок і пусте тіло. Процедура – це сукупність тверджень, заголовки яких мають однаковий функтор і однакову арність. Процедура задає визначення предиката. У кінці речення завжди ставлять крапку, тому всі факти, правила, запити повинні закінчуватися крапкою. Необхідно зазначити також, що між іменем предиката і дужкою не повинно бути пробілів. Змінна – це названа область пам’яті, де може зберігатися значення. Якщо змінна не пов’язана зі значенням, вона називається вільною. Поняття змінної у логічному програмуванні відрізняється від базового поняття змінної у структурному програмуванні. Насамперед, ця відмінність полягає у тому, що змінна у SWI-Prolog, отримавши своє значення одного разу при уніфікації під час роботи програми, не може його змінити, тобто вона є, швидше, аналогом математичного поняття «змінна» – невідома величина. Змінна у SWI-Prolog не має завчасно визначеного типу даних і не може бути пов’язана зі значенням будь-якого типу даних. Змінна у SWI-Prolog позначається як послідовність латинських літер, кирилиці й цифр, яка починається з великої літери або символу підкреслення «_». Відмітимо, що значення аргументу предиката пишеться з великої літери, його потрібно записувати в одинарних лапках. У SWI-Prolog розрізняється регістр, тобто імена предикатів або змінних записані великими і малими літерами будуть різні. Системи штучного інтелекту 55 Розглянемо просту програму на SWI-Prolog для ілюстрації процесу створення, збереження і запуску. Приклад 1. likes(‘Ellen’,’tennis’). %Еллен любить теніс likes(‘John’,’football’). %Джон любить футбол likes(‘Tom’,’baseball’). %Том любить бейсбол likes(‘Erick’,’swimming’). %Ерік любить плавання likes(‘Mark’,’tennis’). %Марк любить теніс likes(‘Mary’,’dancing’). %Мері любить танці likes(‘Bill’,X):-likes(‘Tom’,X). %Білл любить те, що любить Том Коментарі у рядку програми починаються з символу «%» і закінчуються кінцем рядка. Блок коментарів можна виділить спеціальними дужками /* і */. Для того щоб набрати текст програми, використовується вбудований редактор. Щоб створити новий файл оберіть File/New у рядку меню головного вікна, у діалоговому вікні введіть ім’я нового файлу, наприклад, ex1. Для редагування вже створеного файлу з використанням вбудованого редактора використовується команда File/Edit (рис. А.2). Після того як програма була набрана або змінена, необхідно зберегти її (File/Save buffer). Рис. А.2 – Зовнішній вигляд редактора Червоним кольором підсвічуються предикати у заголовках, які з точки зору синтаксису SWI-Prolog є коректними. Покажчик «курсор» можна використовувати для перевірки розстановки дужок тощо. Зеленим кольором виділяються коментарі, темно-червоним – змінні. Підкреслюванням виділяються предикати у тілі правила, які співпадають з предикатом заголовка, – таким чином акцентується увага на можливому зациклюванні програми. Щоб запустити програму, спочатку її потрібно завантажити у SWI-Prolog на виконання. Це можна зробити у вікні редактора, вибравши Compile/Compile buffer. Результат компіляції відобразиться у вікні інтерпретатора SWI-Prolog. Там же будуть указані помилки, які можуть виникнути у процесі компіляції, частіше вони відображаються в окремому вікні помилок. Зазвичай перед компіляцією треба зберегти файл. Інший спосіб завантажити вже існуючий файл – виконати команду Consult у підменю File головного вікна SWI-Prolog. У діалоговому вікні, що з’явиться, 56 В. Є. Стрілець, С. І. Шматков необхідно вказати ім’я файлу і натиснути кнопку «Відкрити». Якщо у файлі, який завантажується, будуть синтаксичні помилки, він не завантажиться, і у головному вікні з’являться повідомлення про помилки. За замовчуванням файли SWI-Prolog мають розширення .pl. Файли також можна завантажити, використовуючи вбудований предикат consult (ім’я файлу або декількох файлів). Наприклад: consult(test). consult([test1, test2]). % завантаження двох файлів consult(‘test.pl’). Для виконання завантаження цей предикат необхідно написати у голов- ному вікні після запрошення інтерпретатора (?-), яке означає, що інтерпретатор чекає на запит. Запит – це конструкція виду: ?- P1,P2,…,Pn, яку читаємо «Чи є вірним P1 і P2 і … Pn?». Предикати Pі є підцілями запиту. Запит є способом запуску механізму логічного виводу, тобто фактично запускає програму. Для перевірки речень завантаженої бази знань можна використати вбудо- ваний предикат listing. Приклад 2. Введемо кілька запитів до створеної бази знань. ?-likes(‘Bill’,’tennis’). ?-likes(Who,’tennis’). ?-likes(‘Mark’,What),likes(‘Ellen’,What). ?-likes(Who,What). ?-likes(Who,_). Результати запитів показані на рис. А.3 (а – в). Якщо необхідно продовжити пошук у базі за цим же запитом і отримати альтернативні розв’язки, то вводиться крапка з комою «;». Якщо необхідно перервати виконання запиту, необхідно ввести b. Якщо необхідно повторити один з попередніх запитів, можна скористатись клавішами «Стрілка вгору» або «Стрілка вниз». Перезавантажити файли, які були змінені у зовнішньому редакторі, можна використовуючи вбудований предикат make. Наприклад, так: ?-make. Системи штучного інтелекту 57 а) б) в) Рис. А.3 – Результат запитів 58 В. Є. Стрілець, С. І. Шматков Додаток Б Приклади Prolog-програм Приклад 1. Організація логічного виводу Бутсі – коричнева кішка. Корні – чорна кішка. Мак – рижа кішка. Флеш, Ровер, Спот – собаки, Ровер – рижа, а Спот – біла. Усі тварини, якими воло- діють Том і Кейт, мають родословні. Том володіє усіма чорними і коричневими тваринами, а Кейт володіє усіма собаками небілого кольору, які не є власністю Тома. Алан володіє Мак, якщо Кейт не володіє Бутсі, і якщо Спот не має родословної. Флеш – плямистий собака. Визначити, які тварини не мають господарів. Розв’язок задачі мовою SWI-Prolog cat(‘Butsi’). %предикат cat – кішка, аргумент – ім’я кішки cat(‘Korni’). cat(‘Mac’). dog(‘Rover’). %предикат dog – собака, аргумент – ім’я собаки dog(‘Flesh’). dog(‘Spot’). color(‘Butsi’,’brown’).%предикат, який визначає колір тварини color(‘Korni’,’black’). color(‘Mac’,’red’). color(‘Rover’,’red’). color(‘Spot’,’white’). color(‘Flesh’,’black_white’). animal(X):-cat(X);dog(X).%предикат який задає правило, визначення тварини rodoslovnaya(X):-animal(X),have(‘Tom’,X).%правило визначення тварини з родословною rodoslovnaya(X):-animal(X),have(‘Kate’,X). have(‘Tom’,X):-color(X,’black’);color(X,’brown’).%правило, яке визначає тварин Тома have(‘Kate’,X):- dog(X),not(color(X,’white’)),not(have(‘Tom’,X)).%ким володіє Кейт have(‘Alan’,’Mac’):- not(have(‘Kate’,’Butsi’)),not(rodoslovnaya(‘Spot’)).% чи володіє Алан Маком no_owner:-animal(X),not(have(_,X)),write(X).%правило, яке визначає тварину без господаря Виклик запиту ?- no_owner. Spot true. Відповідь: господаря не має Спот. Приклад 2. Задача Ейнштейна П’ять різних людей живуть у п’яти різних будинках, палять п’ять різних марок цигарок, люблять п’ять різних видів тварин, п’ють п’ять різних напоїв. Питання: хто любить рибок? Системи штучного інтелекту 59 Підказки:  Норвежець живе у першому будинку.  Англієць живе у червоному будинку.  Зелений будинок знаходиться зліва від білого.  Данець п’є зелений чай.  Той, хто палить Marlboro, живе поряд з тим, хто любить кішок.  Той, хто живе у жовтому будинку, палить Dunhill.  Німець палить Rothmans.  Той, хто живе у центрі, п’є молоко.  Сусід, того хто палить Marlboro, п’є воду.  Той, хто палить Pall Mall, любить пташок.  Швед любить собак.  Норвежець живе поряд із синім будинком.  Той, хто любить коней, живе у синьому будинку.  Той, хто палить Winfield, п’є вино.  У зеленому будинку п’ють каву. Розв’язок задачі мовою SWI-Prolog із використанням списків: einstein :- /* 0. Усього 5 будинків */ Houses = [_,_,_,_,_], /* 1. Норвежець живе у першому будинку. */ nth1(1, Houses, [norwegian,_,_,_,_]), /* 2. Англієць живе у червоному будинку. */ member([englishman,_,_,_,red], Houses), /* 3. Зелений будинок знаходиться зліва від білого. */ nextto([_,_,_,_,green], [_,_,_,_,white], Houses), /* 4. Данець п’є зелений чай. */ member([dane,_,_,tea,_], Houses), /* 5. Той, хто палить Marlboro, живе поряд з тим, хто любить кішок. */ neighbors([_,_,marlboro,_,_], [_,cat,_,_,_], Houses), /* 6. Той, хто живе у жовтому будинку, палить Dunhill. */ member([_,_,dunhill,_,yellow], Houses), /* 7. Німець палить Rothmans. */ member([german,_,rothmans,_,_], Houses), /* 8. Той, хто живе у центрі, п’є молоко. */ nth1(3, Houses, [_,_,_,milk,_]), /* 9. Сусід, того хто палить Marlboro, п’є воду. */ neighbors([_,_,marlboro,_,_], [_,_,_,water,_], Houses), /* 10. Той, хто палить Pall Mall, любить пташок. */ member([_,bird,pallmall,_,_], Houses), /* 11. Швед любить собак */ member([swede,dog,_,_,_], Houses), /* 12. Норвежець живе поряд із синім будинком. */ neighbors([norwegian,_,_,_,_], [_,_,_,_,blue], Houses), /* 13. Той, хто любить коней, живе у синьому будинку. */ member([_,horse,_,_,blue], Houses), /* 14. Той, хто палить Winfield, п’є вино. */ member([_,_,winfield,wine,_], Houses), 60 В. Є. Стрілець, С. І. Шматков /* 15. У зеленому будинку п’ють каву. */ member([_,_,_,coffee,green], Houses), /* Увага, питання: у кого рибки?*/ member([Owner,fish,_,_,_], Houses), /* Отримаємо розв’язок */ print(‘Owner of the fish: ‘), print(Owner), nl, print(‘Full Solution: ‘), print(Houses), nl. /* Допоміжне правило: */ neighbors(X, Y, List) :- nextto(X, Y, List) ; nextto(Y, X, List) . Результат роботи програми ‘Owner of the fish: ‘german ‘Full Solution:’ [[norwegian,cat,dunhill,water,yellow], [dane,horse,marlboro,tea,blue], [englishman,bird,pallmall,milk,red], [german,fish,rothmans,coffee,green], [swede,dog,winfield,beer,white]] Відповідь: рибок любить німець. Приклад 3. Логічний вивід із використанням списків Студенти факультету комп’ютерних наук Артур, Василь, Надія і Еліна на канікулах вирушили до м. Дрезден на екскурсію. У дорозі стало відомо, що їм подобаються твори різних митців: Моне, Рафаеля, Родена і Рембрандта. Тому, приїхавши, троє з них вирушили до різних музеїв (Галерея нових майстрів, Галерея старих майстрів, Зібрання скульптур), а Василь вирішив піти до фізико-математичного салону, оскільки тих картин, які йому подобаються, у музеях Дрездена немає. Відомо, що: у Зібранні скульптур можна знайти роботи Родена, у Галереї старих майстрів немає картин імпресіоністів. Надія цікавиться імпресіоністами і більш за всіх їй подобається Моне, а Еліна надає перевагу Рафаелю. Визначте, куди пішов кожен зі студентів та які їхні смаки. Розв’язок задачі мовою SWI-Prolog student(‘Vasil’). student(‘Artur’). student(‘Nadia’). student(‘Elina’). painter(‘Mone’). painter(‘Rafael’). painter(‘Roden’). painter(‘Rembrandt’). museum(‘Galerie Neue Meister’). museum(‘Gemäldegalerie Alte Meister’). museum(‘Skulpturensammlung’). museum(‘Mathematisch-Physikalischer Salon’). unique([]):-!. %перевірка, що у списку немає елементів, які повторюються unique([Head|Tail]):- member(Head, Tail), !, fail; unique(Tail). choice(Students):- Students=[like(Name1, Museum1, Painter1), like(Name2, Museum2, Painter2), Системи штучного інтелекту 61 like(Name3, Museum3, Painter3), like(Name4, Museum4, Painter4)], student(Name1),student(Name2),student(Name3),student(Name4), unique([Name1,Name2,Name3,Name4]), painter(Painter1),painter(Painter2),painter(Painter3),painter(Pain ter4), unique([Painter1,Painter2,Painter3,Painter4]), museum(Museum1),museum(Museum2),museum(Museum3),museum(Museum4), unique([Museum1,Museum2,Museum3,Museum4]), /*Василь пішов до фізико-математичного салону */ member(like(‘Vasil’,’Mathematisch-Physikalischer Salon’,Painter1),Students), /*У Зібранні скульптур виставка робіт Родена*/ member(like(Name2,’Skulpturensammlung’,’Roden’),Students), /*Надія любить Моне*/ member(like(‘Nadia’,Museum3,’Mone’),Students), /*Еліна любить Рафаеля*/ member(like(‘Elina’,Museum4,’Rafael’),Students), /*У Галереї старих майстрів немає картин імпресіоністів та скульптур*/ not(member(like(_,’Gemäldegalerie Alte Meister’, ‘Mone’), Students)), not(member(like(_,’Gemäldegalerie Alte Meister’, ‘Roden’), Students)), /*У Галереї нових майстрів має роботи XX століття*/ not(member(like(_,’Galerie Neue Meister’, ‘Rafael’), Students)), not(member(like(_,’Galerie Neue Meister’, ‘Rembrandt’), Students)). Результат роботи програми ?- choice(Std). Std = [like(‘Vasil’, ‘Mathematisch-Physikalischer Salon’, ‘Rembrandt’), like(‘Artur’, ‘Skulpturensammlung’, ‘Roden’), like(‘Nadia’, ‘Galerie Neue Meister’, ‘Mone’), like(‘Elina’, ‘Gemaldegalerie Alte Meister’, ‘Rafael’)] Приклад 4. Віконний додаток Створити діалогове вікно для малювання простих геометричних фігур (прямокутник і еліпс). Розв’язок задачі мовою SWI-Prolog :- use_module(library(pce)). start:-new(DW,dialog(‘Прості графічні фігури’)), new(Picture,picture), send(Picture,width(350)), send(Picture, height(350)), send_list(DW, append, [Picture, new(Width, int_item(width, low:=10, high:=300, default:=150)), new(Height, int_item(height, low:=10, 62 В. Є. Стрілець, С. І. Шматков high:=300, default:=150))]), send(DW, append, new(X, int_item(x_coord, default:=10))), send(DW, append, new(Y,int_item(y_coord, default:=10))), send_list(DW,append,[button(‘намалювати прямокутник’, message(@prolog, mybox, Picture, Width?selection, Height?selection, X?selection, Y?selection)), button(‘намалювати еліпс’, message(@prolog, myellipse, Picture, Width?selection, Height?selection, X?selection, Y?selection)), button(‘витерти’,message(Picture, clear))]), send(DW, append, button(exit, and(message(DW, destroy), message(Picture, destroy)))), send(Picture, open), send(DW, open). mybox(Picture,Width,Height,X,Y):-send(Picture, display, new(Box,box(Width,Height)), point(X,Y)), send(Box,colour,colour(green)), send(Box,fill_pattern,colour(red)). myellipse(Picture,Width,Height,X,Y):-send(Picture, clear), send(Picture, display, new(Ellip,ellipse(Width,Height)), point(X,Y)), send(Ellip,fill_pattern,colour(yellow)). Приклад запуску вікна Рис. Б.1 – Вікно після запуску програми Рис. Б.2 – Зображення прямокутника Системи штучного інтелекту 63 Рис. Б.3 – Зображення еліпса 64 В. Є. Стрілець, С. І. Шматков Додаток В Вбудовані предикати і оператори SWI-Prolog Предикат/Оператор Опис write(Term) вивести Term у потік виводу read(Term) вилучити з потоку виводу терм і уніфікувати його з Term. Введення закінчується крапкою tell(File) відкрити файл для запису і перевести в нього потік виводу told перевести потік виводу у стандартний вивід (закрити файл) see(File) відкрити файл для читання і перевести в нього потік введення seen перевести потік введення у стандартний (не з файлу) режим append(List1, List2, List3) успішний, коли список List3 уніфікуємо з об’єд- нанням списків List1 і List2. Усі аргументи можуть бути вільними змінними. Результат – уніфікація відповідних списків append(ListOfList, List) успішний, коли об’єднання списку зі списків ListOfList уніфікуємо зі списком List. Результат – уніфікація відповідних списків member(Elem, List) успішний, коли Elem уніфікуємо з одним з елемен- тів списку List. Результат – уніфікація відповідного елементу списку з Elem nextto(X, Y, List) успішний, коли Y йде за X у списку List delete(List1, Elem, List2) видалити усі елементи списку List1, які уніфіку- ються з Elem. Результат розміщується у List2. select(Elem, List, Rest) успішний, коли Rest є списком List з видаленим елементом Elem. Тобто цим предикатом можна видаляти і вставляти елементи списку. Наприклад: ?-select[a,L,[1,2,3]]. L=[a,1,2,3]; L=[1,a,2,3]; L=[1,2,a,3]; L=[1,2,3,a]; false. nth0(Index, List, Elem) успішний, коли елемент списку List з номером Index уніфікуємо з Elem. Відлік номерів елементів починається з 0 nth1(Index, List, Elem) як і nth0/3, але відлік номерів починається з 1 last(List, Elem) успішний, коли Elem уніфікується з останнім елементом списку List. Якщо хвіст списку List не визначений, то під час бектрекінгу хвіст буде збільшуватися Системи штучного інтелекту 65 reverse(List1, List2) змінює порядок елементів List1 і уніфікує резуль- тат з List2 permutation(List1, List2) успішний, коли список List1 створений зі списку List2 перестановкою елементів sumlist(List, Sum) уніфікує Sum з сумою елементів списку List max_list(List, Max) уніфікує Max з максимальним елементом списку List min