- •Міністерство освіти і науки, молоді та спорту україни Тернопільський національний технічний університет імені Ів. Пулюя
- •Лабораторне заняття №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
6.1 Визначення поняття рекурсії
Рекурсія – алгоритмічний метод, що часто використовується у Пролозі. Рекурсію застосовують для тих же цілей, що і циклічні конструкції в процедурних мовах. У рекурсивних правилах більш складні вхідні аргументи виражаються через менш складні. Наприклад, рекурсивний набір інструкцій з завантаження контейнерів може мати такий вид:
Для того, щоб завантажити N контейнерів, потрібно:
Якщо N=0, то зупинитися.
Якщо N>0, то завантажити один контейнер, потім завантажити ще N–1 контейнер.
Будемо вважати, що тут дано визначення процедури “завантаження N контейнерів”, де N – аргумент процедури і позначає деяке ціле число.
Дана процедура рекурсивна, тому що останній рядок – “завантажити N–1 контейнер” – є викликом процедурою самої себе. Слід відмітити, що аргумент при рекурсивному виклику простіший, ніж вихідний аргумент N, у тому розумінні, що (N–1) – це число менше, ніж число N. Тому “завантаження N контейнерів” є більш складний випадок, що виражається через менш складний випадок виконання тих же самих дій, тобто через “завантажити N–1 контейнер”.
Класичним прикладом рекурсивного визначення в Пролозі може бути процедура “предок”, що складається з двох правил:
предок(А, Б):-батько(А,Б).
предок(А, Б):-батько(В, Б), предок(А, В)
Сукупність цих правил визначає два способи, відповідно до яких одна особа (А) може бути предком іншої особи (Б).
Відповідно до першого правила, А є предком Б, якщо А – батько Б, тобто А є найближчим предком Б (рис.6.1,а).
Відповідно до другого правила А буде предком Б, якщо є дехто В, що, будучи батьком Б, має своїм предком А. Іншими словами, А – предок Б, якщо А – предок батька Б, тобто А – віддаленим предком Б (рис.6.1,б). У такий спосіб друге правило залежить від більш простої версії самого себе, тобто від підмети “предок”.
Рисунок 6.1 – Приклади відношення “предок” і його зв'язок з відношенням “батько”: а) А найближчий предок Б; б) А віддалений предок Б; в) приклад схеми програми.
Завдання 1.
У програму 5.2 введіть опис процедури “предок”. Виконайте ряд довільних запитів до програми. Використовуючи режим трасування, прослідкуйте послідовність обробки в Пролозі процедури “предок”. Збережіть програму у файлі “lab6.pro”
6.2 Склад рекурсивної процедури
Будь-яка рекурсивна процедура повинна включати принаймні по одній з перерахованих нижче компонент:
1. Нерекурсивна пропозиція (правило або факт), що визначає вихідний вид процедури, тобто вид процедури в момент, припинення рекурсії. Це, так називані, граничні умови.
2. Рекурсивне правило. Початкові підцілі, що розташовуються в тілі цього правила, продукують нові значення аргументів. Далі розміщується рекурсивна підмета, у якій використовуються нові значення аргументів.
Перша пропозиція процедури “предок” визначає вихідний вид процедури. Як тільки дана пропозиція стає істинною, подальша рекурсія припиниться. Тобто, перша пропозиція є граничною умовою.
Друга пропозиція – це рекурсивне правило. При кожному виклику дане правило піднімається на одне покоління вгору. Підмета батько(В, Б), що входить у тіло правила, уніфікує значення змінної В. Потім розташовується рекурсивна підмета предок(А, В), де використовується новий аргумент.
Розглянемо ще один приклад побудови рекурсивної процедури для обчислення факторіала будь-якого цілого числа.
З визначення факторіала відомо, що 0!=1, а факторіал будь-якого числа N може бути обчислений як факторіал N–1, помножений на N. Це визначення є рекурсивним, оскільки зводить задачу знаходження N! до більш простої задачі знаходження факторіалу (N–1)! і потім множення отриманого значення на N.
Для позначення факту, що факторіал числа N рівний R, використовуємо предикат f(N, R). Його рекурсивне визначення буде мати вигляд, що приведений у програмі 6.1.
/* програма 6.1 */
predicates
f(integer,integer)
clauses
f(1,1) :-!.
f(N,R) :- M=N-1, f(M,V), R=V*N.
Тут перше правило визначає граничну умову для рекурсивної процедури. Друге правило є рекурсивним, тому що друга підмета цього правила містить виклик самої процедури, правда з зміненими першої підметою значеннями аргументів.
Реалізація виконання даної програми Пролог-системою для випадку обчислення факторіала числа 3 (тобто 3!) приведена на рис.6.2.
З рис.6.2, видно, що при виконанні заданої мети f(3,X) Пролог тричі звертається до процедури. При цьому перші два рази узгоджується друге правило, а на третьому кроці – перше. Особливість узгодження другого правила полягає в тому, що обидва рази виконання третьої підмети відкладається (заноситься в стек запитів) у вигляді рекурсії другої підмети. І тільки після узгодження на третьому кроці першого правила Пролог повертається до виконання третьої підмети. Вони послідовно, починаючи з останньої, витягаються зі стека запитів і виконуються.
Рисунок 6.2 – Схема виконання рекурсивної процедури f(N,R).
Завдання 2.
Використовуючи режим трасування, прослідкуйте послідовність обробки рекурсивних процедур на прикладі обчислення факторіала. Змініть програму таким чином, щоб вона обчислювала суму заданої послідовності цілих чисел. Налагодьте програму, а потім обчисліть суму першої тисячі чисел, суму перших 10 тисяч чисел. Який вийшов результат? Як його можна пояснити?