- •Міністерство освіти і науки, молоді та спорту україни Тернопільський національний технічний університет імені Ів. Пулюя
- •Лабораторне заняття №1 Ознайомлення з мовою програмування Пролог
- •1.1 Загальні відомості про мову Пролог
- •1.2 Елементи мови Турбо-Пролог
- •1.3 Структура програм Турбо-Пролога
- •1.3.1 Секція domains Пролог-програми
- •1.3.2 Секція predicates
- •1.3.3 Секція clauses
- •1.3.4 Секція goal
- •1.3.5 Секція database
- •1.4 Оболонка системи Турбо-Пролог
- •1.5 Налагодження і трасування програм
- •Лабораторна робота №2 Робота з найпростішими програмами в системі Турбо-Пролог
- •2.1 Вступ
- •2.2 Завантаження системи Турбо-Пролог, ввід і запуск програм
- •2.3 Робота з Пролог-програмами в режимі діалогу
- •2.4 Трасування програм у середовищі системи Турбо-Пролог
- •2.5 Робота з програмами, що містять внутрішню мету
- •2.6. Найпростіша програма вводу-виводу даних
- •2.7 Побудова найпростішого інтерфейсу для виводу результатів запитів
- •8. Зміст звіту по лабораторній роботі
- •Лабораторна робота №3 Пролог-програми як найпростіші бази даних і знань
- •3.1 Вступ
- •3.2 Запити до бази даних
- •3.2.1 Прості запити
- •3.2.2 Складені запити
- •3.2.3 Запити з анонімними змінними
- •3.3. Статичні і динамічні бази даних
- •3.4. Явні і неявні бази даних. Правила логічного висновку
- •3.5 Використання структур у якості доменів відношень
- •6. Процедури як елемент представлення знань
- •3.7 Цілісність і несуперечність баз даних і знань
- •3.8. Зміст звіту по лабораторній роботі
- •Лабораторна робота №4. Керування ходом виконання програм у системі Турбо-Пролог
- •4.1 Робота системи Турбо-Пролог при виконанні запитів
- •4.2 Уніфікація термів
- •4.3 Пошук з поверненням при виконанні Пролог-програм
- •4.4 Використання відкату після невдачі при використанні внутрішньої мети для організації найпростішого інтерфейсу виводу
- •4.5 Зміст звіту по лабораторній роботі
- •Лабораторна робота №5 Керування ходом виконання Пролог-програм
- •5.1 Організація повторюваних процесів
- •5.2 Керування пошуком з поверненням
- •5.3 Керування ходом виконання програм з використанням відсікання
- •5.4 Застосування предикату not - заперечення як неуспіх
- •5.5 Використання методу відкату і відсікання
- •5.6 Відкат і відсікання при реалізації відносин типу „один-до-багатьох”
- •5.7 Ступінчаті функції і відсікання
- •5.8 Труднощі у використанні відсікання і заперечення
- •5.9 Зміст звіту по лабораторній роботі
- •Лабораторна робота №6 Рекурсія і рекурсивні процедури в Пролозі
- •6.1 Визначення поняття рекурсії
- •6.2 Склад рекурсивної процедури
- •6.3 Особливості виконання рекурсивних процедур Прологом-системою
- •6.4 Приклад рекурсивної процедури пошуку довжини маршруту на графі
- •6.5 Обмеження і властивості, що забезпечують цілісність відношень
- •6.6 Реалізація циклічних процедур за допомогою бектрекінгу
- •6.6.1. Реалізація ітераційного процесу за допомогою бектрекінгу
- •6.6.2 Дії типу ’до’ і ’після’
- •6.6.3. Застосування бектрекінгу для реалізації циклів
- •6.7 Зміст звіту по лабораторній роботі
- •Лабораторна робота №7 Списки і процедури їх обробки
- •7.1 Списки як рекурсивні структури даних
- •7.2 Використання списків в Пролог-програмах
- •7.3. Найпростіші процедури роботи зі списками
- •7.4 Процедури обробки списків
- •7.5. Компонування даних у список
- •7.6. Зміст звіту по лабораторній роботі
- •Лабораторна робота №8 Способи представлення баз даних у Пролог-програмах
- •8.1 Вступ
- •8.2 Представлення відносин у виді фактів
- •8.3 Представлення атрибутів у виді фактів
- •8.4 Представлення бази даних у виді списку структур
- •8.5 Представлення бази даних у виді лінійної рекурсивної структури
- •8.6 Представлення бази даних у виді двійкового дерева
- •8.7 Порівняння різних видів представлення бази даних
- •Лабораторна робота №9 Динамічні бази даних
- •9.1 Вступ
- •9.2 Прості прийоми роботи з динамічними бд
- •9.3 Зв’язок статичних і динамічних баз даних
- •9.4 Процедура роботи з динамічною бд, що навчається у користувача
- •9.5 Розширення бази даних у файли
- •9.6. Організації файлових бд на основі файлів прямого доступу
- •9.6. Особливості представлення динамічних баз даних у Visual Prolog
- •9.7 Зміст звіту по лабораторній роботі
- •Лабораторна робота №10 робота з складно структурованими базами даних
- •10.1 Опис логічної моделі даних
- •10.3 Отримання структурованої інформації з бази даних
- •10.4 Абстракція даних і побудова баз знань
- •10.5. Зміст звіту по лабораторній роботі
- •Лабораторна робота №11 дослідження методів представлення і обробки знань
- •11.1 Структура експертних систем
- •11.2 Представлення знань
- •11.3 Система інтерфейсу користувача
- •11.4 Експертна система на правилах
- •11.5 Експертні системи, що базуються на логіці
- •11.6 Структура бази знань експертної системи для вибору породи дерева
- •11.7 Зміст звіту
- •Список використаних джерел
- •Додаток а Службові предикати Турбо-Пролога
- •Додаток б Службові предикати Турбо-Пролога для роботи з файлами
- •Додаток в
- •Таблиця в.1 – Варіанти завдань
- •6. До лабораторної роботи №7
- •7. До лабораторної роботи №8
- •8. До лабораторної роботи №9
- •9. До лабораторної роботи №10
- •10. До лабораторної роботи №11
7.4 Процедури обробки списків
Списки можна застосовувати для представлення множин, хоча і є деяке розходження між цими поняттями. Порядок елементів множини не важливий, у той час як для списку цей порядок має значення. Крім того, той самий об'єкт R списку може зустрітися декілька раз. Однак, найбільш використовувані операції над списками аналогічні операціям над множинами. Це перевірка об’єкту на належність множині, об’єднання двох множин, видалення з множини деякого об’єкту.
Належність до списку. Представимо відношення належності у виді member(R, L), де R – терм, a L – список. Ціль member(R, L) щира, якщо терм R зустрічається в L. Задача перевірки входження терму в список формулюється у вигляді:
Гранична умова: Терм R знаходиться в списку, якщо R є голова списку L.
Рекурсивна умова: Терм R знаходиться в списку, якщо R належить хвостові L.
Один з варіантів Пролог-процедури можна представити в наступному виді:
member(R,L):-L=[H|], H=R.
member(R,L):- L=[H|], member(R,T).
Ціль L=[H|] у тілі обох правил служить для того, щоб розділити список L на голову і хвіст. Можна поліпшити процедуру, якщо врахувати той факт, що Пролог спочатку зіставляє з метою заголовок правила, а потім намагається погодити його тіло. Тоді поліпшений варіант цієї ж процедури може бути записаний у виді:
member(R, [R |_]).
member(R,[_ | Т]) :- member(R, Т).
Використання анонімних pмінних (_) викликане тим, що при застосуванні першого правила нас не цікавить хвіст списку, а при застосуванні другого – голова списку.
Як приклад розглянемо роботу процедури при виконанні мети:
member(d,[a,b,d,c]).
Ціль починає зіставлятися з першого правила, але тому що d це не а, то відбувається відкат до другого правила.
Змінна Т одержує значення [b,d,c], і породжується нова мета: member(d,[b,d,c]). Тому що перше правило не уніфікується з метою, відбувається повторне зіставлення другого правила і виділення нового хвоста списку.
Поточною метою стає member(d,[d,c]). Використання першого правила приводить до того, що елемент, який перевіряється, d зіставляється з головою списку. [d,c]. Перше правило стає щирим, тобто ціль досягнута.
Якщо вихідна мета member(d,[a,b,c,e]), то процес зіставлення з другим правилом буде рекурсивно повторюватися дотих пір, поки не буде досягнута мета member(d,[]). Жодне з правил не уніфікується з цією метою і, тому вихідна мета виявляється помилковою.
З’єднання двох списків. Для з’єднання двох списків визначимо відношення append(L1, L2, L3), де L1 – вихідний список, L2 – список, що приєднується (додається), a L3 – список, одержуваний при їхньому з’єднанні. Задача з’єднання списків формулюється в такий спосіб:
Гранична умова: Приєднання списку L2 до [] дає той же список L2.
Рекурсивна умова: Список L2 приєднується до хвоста L1, а потім попереду додається голова L1.
Тоді безпосередньо з постановки задачі можна написати процедуру виду:
аppend([], L2, L3).
append(L1, L2, L3):- L1=[H|], append(T, L2, X), L3=[H|X]
Однак, як і в попередньому випадку, скористаємося тим, що Пролог спочатку , зіставляє з метою заголовок правила, а потім намагається погодити його тіло. Тоді удосконалений варіант цієї ж процедури буде записаний у виді:
append([ ], L2, L2 ).
append([Н|L1 ], L2, [Н|L3]):- append(L1, L2, L3).
На запит append([a,b,c], [d,e], L) буде отримана відповідь L=[a,b,c,d,e], а на запит append([a,b],[c],[a,c,d]) відповіддю буде “ні”.
Дану процедуру можна також використовувати для пошуку в списку комбінацій елементів, що відповідає деякій умові, що задається у виді шаблона. Наприклад, можна знайти всі місяці, що передують даному, і всі, наступні за ним, сформулювавши таку мету:
Goal: append(X,[“квітень”|Y ], [“січень”, “лютий”, “березень”, “квітень”, “травень”, “червень”] )
X=[“січень”, “лютий”, “березень”, “квітень”]
Y=[“травень”, “червень”]
Видалення елементу. Для видалення елемента Х зі списку L введемо відношення delete(X, L, L1), де L1 – скорочений список. Задача буде сформульована у виді:
Гранична умова: Якщо Х – голова, то результатом видалення буде хвіст списку.
Рекурсивна умова: Якщо Х знаходиться в хвості списку, тоді його варто видалити з хвоста списку.
delete(X, [X | Т], Т).
delete(X, [Y | T ], [Y, T1]):- delete(X, T, T1).
Одержання n-го терма зі списку. Задача доступу до заданого номером елементу списку формулюється наступним чином:
Гранична умова: Перший терм у списку [H|] є Н.
Рекурсивну умову: N-й терм у списку [H|] є (N-1)-шим термом у списку Т.
term_in_list( [Н | _],1,Н ).
term_in_list([ _ |], N, X ) :- M=N-1, term_in_list(T, M, X).
Визначення довжини списку. Задача формулюється в такий спосіб:
Гранична умова: Довжина порожнього списку дорівнює нулеві.
Рекурсивна умова: Довжина списку [H|] на одиницю більше довжини списку Т.
list_len([],0).
list_len([_|],Len):- list_len(T,Len1), Len = Len1+1.
У предикаті list_len другий аргумент приймає значення рівне довжині списку. Якщо другий аргумент є зв'язаної змінної, то йде перевірка на її збіг з довжиною списку.
Завдання 5.
Використовуючи кожну з моделей опису предметної області списковими структурами, розробити програму, що дозволяє виконувати над списками всі елементарні дії, процедури яких приведені вище.