Зміст дисципліни
РОЗДІЛ 1.Мови створення систем штучного інтелекту. Введення в логічне програмування.
РОЗДІЛ 2. Логічна парадигма програмування.
Синтаксис та семантика Пролог-програм
РОЗДІЛ 3. Структура програми Прологу.
РОЗДІЛ 4. Застосування файлів на зовнішніх носіях.
РОЗДІЛ 5 Механізми створення повторів та рекурсій.
Розділ 6. Абстрактні типи даних мови Пролог.
Розділ 7. Метаінтерпретатори, експертні системи в мові Пролог.
Розділ 8. Динамічні бази даних (БД), контекстно-вільний (КВ) аналіз засобами мови Пролог.
Розділ 9. Алгоритми навчання в мові Пролог.
Розділ 10. Обробка природної мови засобами Прологу.
Розділ 11. Функціональна парадигма програмування.
Мови функціонального програмування.
Розділ 12. Основи функціонального програмування.
Розділ 13. Lisp та імперативне програмування.
Розділ 14. Елементи процедурного програмування в Lisp.
Розділ 15. Стратегії пошуку в Lispі.
Розділ 16. Об’єктно-орієнтоване програмування засобами Common LISP Object System/
Робота кп №1. Вступ до мови програмування Пролог: синтаксис та семантика Пролог-програм
Мета роботи: ознайомлення з основними поняттями та механiзмами роботи
Прологу.
Послiдовнiсть виконання роботи:
1) Опрацювати методичнi рекомендації та з’ясувати вимоги до роботи.
2) Скласти програму, яка реалiзує визначений викладачем варiант завдання.
3) Вимоги до запитів:
запити мають бути зовнішними;
поекспериментувати з простими та складними запитами до фактів і правил.
4) Вiдлагодити програму та перевiрити її працеспроможнiсть за допомогою тестових прикладiв.
5) Скласти звiт про роботу.
Змiст звiту:
Iндивiдуальне завдання.
Опис програми, що містить опис предикатів.
Опис предметної області, що запрограмовано фактами, представлений у вигляді дерева.
Опис контрольних прикладiв.
Лiстинг коду програми та протокол розв’язку задачи.
Аналiз одержаних результатiв.
Методичнi рекомендації
За лекцiйним матерiалом чи за допомiжною лiтературою ознайомитись з основними принципами програмування на мовi Prolog.
(Рекомендується ознайомитись з наведеним далі прикладом)
Вимоги до виконання роботи з комп’ютерного практикуму
Cтворити програму, яка має вiдображати iндивiдуальний варiант завдання та мiстити у собi певнi правила та факти.
Iндивiдуальнi завдання:
Визначити на мовi Пролог наступнi вiдношення:
1) Дiдусь (через Рiдна тiтка та Рiдний дядько )
2) Бабуся (через Батьки )
3) Дворiдний брат
4) Рiдний брат
5) Рiдна сестра
6) Належнiсть одному роду через одного з батькiв
7) Прабатько
8) Нащадок
9) Абориген
10) Червоний диплом
11) Функцiонал (через Функцiя)
12) Родич (через Спiльний прабатько)
13) Спiльний нащадок
14) Родич по однiй з лiнiй (3-4 колiна)
15) Дiти
16) Небiж (рос.Племянник)
17) Небога
18) Внучатий небiж
19) Вступ до iнституту
20) Троєрiдний брат
21) Троєрiдна сестра
22) Inf (Iнфiнум)
23) Sup (Супремум)
24) Гiльбертiв простiр
25) Просте число
Поради до виконанняроботи з комп’ютерного практикуму 1
Розглянемо короткий приклади та на їх основi дамо деякi пояснення щодо загальної побудови програм в мові Prolog:
Приклад 1. Потенційний претендент на пост президента USA
/* This program define predicate potential_USA_president */
domains
person = symbol
year = integer
predicates
potential_USA_president(person)
citizen(person)
age(person,year)
goal
write(“Input name of potential pretendent : “) , readln(Name),potential_USA_presedent(Name).
clauses
potential_USA_president(N) if citizen(N) and age(N,X) and X>40 and
write( N, “ can be the president “).
potential_USA_president(_) if write( N ,” can't be the president “).
citizen(johanson).
citizen(smith).
age(johanson,50).
age(smith,12).
age(greenwood,67).
Програма складається з наступних роздiлiв роздiлiв:
а). Роздiл описання доменiв (domains)
Цей розділ мiстить визначення доменiв, якi описують рiзнi класи об'єктiв, що використовуються програмою. В наведеному прикладi вiн не є обов'язковим, але надає певну наочнiсть програмi.
Тобто, при визначеннi предикату citizen можна писати citizen(string), а при визначеннi age -
age (string,integer).
б). Роздiл описання предикатiв (predicates)
Предикат можна розглядати як деяке твердження про об'єкт(и) цього предикату.
Наприклад, предикат citizen(person) будемо тлумачити як факт про те, що об'єкт цього предикату, який до речi належить до стандартного типу string, тобто рядок символiв, є громадянином країни: сitizen (johanson) є <пан johanson — громадянин (США)> (Див. роздiл clauses)
Ненабагато складнiшою є справа з предикатом potential_USA_president. Цей предикат являє собою правило, тобто вiн визначається через факти сitizen та age (Див. роздiл clauses).
в). Роздiл внутрiшньої цiлi (goal) - його доречнiше розглянути наприкiнцi.
г). Роздiл тверджень(clauses).
В цьому роздiлi власне й знаходяться факти та правила. В нашому прикладi присутнi факти про те, що персони johanson та smith є громадянами, також маємо iнформацiю про вiк певних осiб :
наприклад age(greenwood,67) є <пану greenwoodу 67 рокiв>.
Розглянемо правило potential_USA_president. Формально його можна записати так :
<N може претендувати на посаду президента, якщо N — громадянин країни та його вiк не менше 40 рокiв>
Перейдемо тепер до розгляду функцiювання програми.
Треба зауважити, що Пролог має своєю метою досягнення “iстини” цiльовим твердженням.
Цiльове твердження можна задати як в самiй програмi (Див. приклад), так i пiсля запуску програми, що не мiстить цiльового твердження. У цьому разi Турбо-Пролог видає слово-запит goal: , пiсля якого потрiбно ввести з клавiатури текст Вашого запиту. Мiж цими двома шляхами запиту (внутрішним та зовнішним) є певна рiзниця, яка полягає у тому, що при наявностi цiльового твердження у програмi (внутрішний) Пролог шукає перший задовольняючий “ iстинi “ випадок й припиняє наступний пошук. Якщо ж запит реалiзовано з зовнi, то Пролог видає на екран всi можливi задовольняючi варiанти. Для нашої програми цей запит може виглядати так: goal : citizen(X). Пролог надрукує на екранi всi прiзвища громадян з нашої бази даних — johanson smith Yes. Вiдповiдь Yes означає, що Прологу вдалося знайти задовольняючi факту citizen об'єкти. Як Ви вже зрозумiли, змiннi в Пролозi завжди повиннi починатись з великої лiтери.
Приклад 2. Опис сімейних відносин
domains
person = symbol
predicates
mail(person)
female(person)
father(person,person)
mother(person,person)
parent(person,person)
sister(person,person)
brother(person,person)
uncle(person,person)
grandfather(person,person)
clauses
male(alan).
male(charles).
male(bob).
male(ivan).
female(beverly).
female(fay).
female(merilyn).
female(sally).
mother(marilyn,beverly).
mother(alan,sally).
father(alan,bob).
father(beverly,charles).
father(fay,bob).
father(marilyn,alan).
parent(X,Y) if mother(X,Y).
parent(X,Y) if father(X,Y).
brother(X,Y) if /*The brother of X is Y if */
male(Y) and /*Y is a male and */
parent(X,P) and /*the parent of X is P and */
parent(Y,P) and /*the parent of Y is P and */
X <> Y . /* X and Y are not the same*/
sister(X,Y) if /*The sister of X is Y if */
female(Y) and /*Y is female and */
parent(X,P) and /*the parent of X is P and */
parent(Y,P) and /*the parent of Y is P and */
X <> Y . /*X and Y are not same */
uncle(X,U) if /*The uncle of X is U if */
mother(X,P) and /*the mother of X is P and */
brother(P,U) . /*the brother of P is U */
uncle(X,U) if /*The uncle of X is U if */
father(X,P) and /*the father of X is P and */
brother(P,U) . /*the brother of P is U */
grandfather(X,G) if /*The grandfather of X is G*/
father(P,G) and /*if the father of P is G */
mother(X,P) . /*and the mother of X is P */
grandfather(X,G) if /*the grandfather of X is G*/
father(X,P) and /*if the father of X is P */
father(P,G) . /*the father of P is G */
Контрольні запитання
Зв’язок формальної логіки та логічного програмування: фрази Хорна; метод резолюцій.
Структура програми мовою Prolog.
Типи запитів: з константами, змінними; прості, складені.
Квантифікація змінної в запиті. Квантифікація змінної у правилі.
Визначення поняття рекурсії. Класичні приклади рекурсії.
Декларативна та процедурна семантика мови Пролог.
Семантична модель Прологу в вигляді абстрактної машини.
Лiт-ра: [1]: С. 25-75; [2]: С. 8-104; [3]: С. 35-136, С. 165-263; [4]: С. 528-560, С. 609-633; [5]: С. 32-87.
РОБОТА КП №2. Механізми створення повторів та рекурсій
Мета роботи: 1. набуття навичок у використанні стандартних предикатів введення/виведення та файловою системою.
опанування механізмів створення повторів та рекурсій.
створення віконного інтерфейсу.
Послідовність виконання роботи
Опрацювати методичні рекомендації та з’ясувати вимоги до роботи.
Скласти програму, яка реалізує визначений викладачем варіант завдання (запити мають бути реалізовані за допомогою відповідного розділу goal).
Відлагодити програму та перевірити її працеспроможність за допомогою тестових прикладів.
Скласти звіт про роботу.
Зміст звіту
Індивідуальне завдання.
Опис програми (предикатів), вхідних та вихідних параметрів.
Опис контрольних прикладів.
Листінг коду програми та протокол розв’язку (завдання задачі) проблеми.
Аналіз одержаних результатів.
Методичні рекомендації
При створенні програми необхідно використати стандартні предикати Пролога: предикати роботи з екраном, файлами, введення та виведення даних, обробка символів та строк, предикати управління програмою.
Вимоги до виконання
Створити «власне» вікно для відображення даних, які вводять у програму, наприклад: ім’я файла, кількості елементів, що обробляються та інше в залежності від змісту завдання. Передбачити запити для введення цих даних.
Індивідуальні завдання
Для варіантів з 1 по 13 завдання
Маємо файл, компоненти якого цілі числа. Знайти та вивести у другий файл
1. Кількість парних компонент
2. Кількість квадратів непарних чисел серед компонент
3. Кількість подвоєних непарних чисел серед компонент
4. Компоненти, які є парними числами
5. Компоненти, які кратні 3 та некратні 7
6. Компоненти, які є простими числами
7. Компоненти, які є точними квадратами
8. Компоненти, які є непарними числами
9. Кількість однакових компонент
(починаючи з першої зустрінутої збіжності)
10. Суму компонент
11. Компоненти-«близнюки» (прості числа, різниця між якими дорівнює 2)
12. Компоненти, які подаються у вигляді суми квадратів натуральних чисел
13. Компоненти, які єчислами Армстронга, що складаються з 2 або 3 цифр.
(Натуральне
число, що складається з n
цифр є числом Армстронга, якщо
сума його
цифр, піднесених до n-го
ступеня, дорівнює самому числу:
наприклад,
).
Для варіантів з 14 по 21 загальне завдання
Маємо файл, компоненти якого дійсні числа. Вивести у другий файл
14. Добуток компонент
15. Суму квадратів компонент
16. Модуль суми компонент
17. Квадрат добутку компонент
18. Різницю першої та останньої компонент
19. Найбільше із значень компонент з парним номером
20. Найменьше із значень компонент з непарним номером
21. Найбільше по модулю значення компонент
22.
Послідовність
створюється за законом
.
Задається
дійсне
та
.
Виводити в файл члени послідовності
,
зупинившись після члену, для якого
виконується
.
Для варіантів 23 - 25 загальне завдання
Даний символьний файл. Створити новий файл,
23.
Який копіює попередній, але закінчується
символами
.
24. Що складається з цілих чисел, які є чисельними еквівалентами компонент
вихідного файла.
25. В якому всі великі букви замінено на малі.
Поради до виконання роботи з комп’ютерного практикуму 2
Сподiваючись на те, що Ви самостiйно виконали першу роботу та вже маєте певнi уявлення про програмування на Пролозi, обмежимось поданням рекомендованих вбудованих предикатiв та деякими порадами.
Створюючи другу лабораторну роботу намагайтесь обмежити кiлькiсть предикатiв, що перенаправляють введення/виведення даних, а також вiдкривають файли для читання або запису. Це набагато полегшить роботу, дасть можливiсть уникнути плутанини та полегшить викладачевi перевiрку роботи.
В цiй роботi вiд Вас вимагається створити власне вiкно введення/виведення. Для цього використайте предикати:
clearwindow
Виклик:
clearwindow
Очищує поточне активне текстове вiкно, заповнюючи його фоновим кольором.
display
Виклик:
display(S_строка)
Тип аргументiв: (string)
Режим передачi аргументiв: (i)
Виводить вмiст рядка S_рядок у поточне активне вiкно. Символи виведеного рядка можуть перевiрятись (але не змiнюватись) за допомогою команд перемiщення курсора (як в редакторi).
makewindow
Виклик:
makewindow(Q_номер_вiкна,Q_атрибут_екрана,Q_атрибут_рамки,
S_заголовок_вiкна,Q_рядок,Q_стовпчик,Q_висота,Q_ширина)
Типи аргументiв: (integer,integer,integer,string, integer,integer,integer,integer)
Режими передачi аргументiв: (i,i,i,i,i,i,i,i)
Визначає деяку область екрана в якостi iнформацiйного вiкна. Кожне вiкно iдентифiкується його номером, який визначається змiнною Q_номер_вiкна, що використовується в подальшому для активiзацiї конкретного вiкна. Змiнна Q_атрибут_екрана визначає колiр символiв i фона для даного вiкна. Якщо
змiнна Q_атрибут_рамки не дорiвнює нулю, то навколо даного вiкна малюється рамка з текстом, визначеним змiнною S_заголовок_вiкна, на верхнiй лiнiї рамки. Змiнна S_заголовок_вiкна визначає колiр символiв i фона для даної рамки. При початковому визначеннi вiкна воно очищується, а курсор
перемiщується у верхнiй лiвий кут вiкна. Позицiя верхнього лiвого кута вiкна вiдносно верхнього лiвого кута екрана визначається змiнними Q_рядок та Q_стовпчик. Розмiри вiкна визначаються змiнними Q_висота та Q_ширина. Треба пам'ятати, що розмiри та положення вiкна повиннi вiдповiдати (не
виходити за межi) розмiрам екрана дисплея (звичайно 25 рядкiв по 80 символiв).
removewindow
Виклик:
removewindow
Видаляє поточне активне iнформацiйне вiкно з екрана.
shiftwindow
Виклик:
shiftwindow(Q_номер_вiкна)
Тип аргументiв: (integer)
Режими передачi аргументiв: (i), (о)
(i) — Переводить iнформацiйне вiкно з номером Q_номер_вiкна в активний стан. Вмiст попереднього активного вiкна, що замiнюється, зберiгається в пам'ятi.
(o) — Привласнює змiннiй Q_номер_вiкна значення номера поточного
активного вiкна.
window_attr
Виклик:
window_attr(Q_атрибут)
Тип аргументiв: (integer)
Режим передачi аргументiв: (i)
Задає значення атрибута (змiнна Q_атрибут) для поточного активного вiкна.
window_str
Виклик:
window_str(S_рядок_екрана)
Тип аргументiв: (string)
Режими передачi аргументiв: (i), (o)
(i) — Привласнює рядковiй змiннiй S_рядок_екрана весь текст, який
вiдображений у поточному активному iнформацiйному вiкнi;
пiсля виконання предиката змiнна S_рядок_екрана мiстить стiльки
рядкiв символiв, скiльки рядкiв iснує в поточному активному вiкнi.
Довжина кожного рядка визначається кiлькiстю символiв у рядку до
останнього символа, вiдмiнного вiд символа пробiл.
(o) — Виводить у поточне активне вiкно всi символи, якi мiстяться в
рядковiй змiннiй S_рядок_екрана, враховуючи наступнi правила:
— якщо S_рядок_екрана мiстить бiльше рядкiв, нiж може вiдображуватись у вiкнi, то виводяться першi рядки до заповнення вiкна;
— якщо S_рядок_екрана мiстить менше рядкiв, нiж може вiдображуватись у вiкнi, то рядки вiкна, якi залишились незаповненими, заповнюються пробiлами;
— якщо який-небудь рядок мiстить бiльше символiв, нiж може вiдо-
бражуватись у вiкнi, то при виводi залишок рядка вiдсiкається;
— якщо будь-який рядок мiстить менше символiв, нiж може вiдображуватись у вiкнi, то при виведенні до рядка додаються пробiли.
Предикати роботи з файлами:
closefile
Виклик
closefile(F_символьне_iм’я_ файла)
Тип аргумента: (file)
Режим передачi аргументiв: (i)
Закриває файл с заданим iмIям. Предикат узгоджується й в тому разi, коли файл, що закривається, не був вiдкритий.
еof
Виклик:
eof(F_iм’я_файла)
Тип аргументiв: (file)
Режим передачi аргументiв: (i)
Перовiряє, чи досягнув вказiвник положення запису у файлi
openread
Виклик:
openread(F_iм’я_файла,S_iм’я_файла)
Типи аргументiв: (file,string)
Режими передачi аргументiв: (i,i)
Вiдкриває дисковий файл (ім’я фізичного файла), iм’я котрого визначається строковою змiнною S_iм’я_файла (ім’я логічного файла), для читання. Пов’язує даний файл iз змiнною F_iм’я_файла, яка в подальшому буде використовуватись в програмi для посилань на цей файл.
openwrite
Виклик:
openwrite(F_iм’я_файла,S_iм’я_файла)
Типи аргументiв: (file,string)
Режими передачi аргументiв: (i,i)
Вiдкриває дисковий файл (ім’я фізичного файла), iм’я якого визначається строковою змiнною S_iм’я_файла, для запису. Пов’язує даний файл iз змiнною F_iм’я_файлу (ім’я логічного файла), яка в подальшому буде використовуватись в програмi для посилань на цей файл.
readdevice
Виклик:
readdevice(S_iм’я_файла)
Тип аргументiв: (symbol)
Режими передачi аргументiв:(i) (o)
(i)
Призначає пристрiй або файл, iм’я якого мiститься в символьнiй змiннiй S_iм’я_файла, в якостi поточного пристрою введення. Змiнна S_iм’я_файлу може мiстити будь-яке iм’я, зрозумiле файловiй системi (в тому числi й стандартнi имена пристроїв, а саме: keyboard).
(o)
Призначає змiннiй S_iм’я_файла iм’я поточного пристроя введення.
writeddevice
Виклик :
writeddevice (S_iм’я_файла)
Тип аргументiв: (symbol)
Режими передачi аргументiв:(i) (o)
(i)
Призначає пристрiй або файл, iм’я якого мiститься в символьнiй змiннiй S_iм’я_файла, в якостi поточного пристроя виведення. Змiнна S_iм’я_файла може мiстити будь-яке iм’я, зрозумiле файловiй системi (в тому числi й стандартнi имена пристроїв: screen, printer).
(o)
Призначає змiннiй S_iм’я_файла iм’я поточного пристроя виводу.
Для запису в файл та читання iз файлу використовуйте в залежностi вiд завдання предикати:
readreal — читає дiйсне число з поточного пристроя введення;
readln — читає строку;
readint — читає цiле число;
write — записує свої аргументи у пристрiй виведення.
Контрольні запитання
Предикат fail.
Метод відкоту після неуспіху.
Предикат cut. Типи відсікань.
Метод відсікання та відкоту.
Метод повтору, визначений користувачем.
Засоби управління перебором.
Методи організації рекурсії.
Лiт-ра: [1]: С. 121-161; [3]: С. 264-297 та С. 473-507, [5]: С. 115-152 та С. 230 -287.
РОБОТА КП №3: Списки, черги, довідники в мові Prolog
Мета роботи: освоєння методів роботи з простими структурами даних
в логічних програмах.
Послідовність виконання роботи
1. Опрацювати методичні вказівки та з’ясувати вимоги до роботи.
2. Скласти програму, яка реалізує визначений викладачм варіант завдання.
3. Вимоги до запитів:
запити мають бути зовнішними
4. Відлагодити програму та перевірити її працеспроможність за допомогою
тестових прикладів.
5. Скласти звіт про лабораторну роботу.
Зміст звіту
Індивідуальне завдання.
Опис програми (предикатів), вхідних та вихідних параметрів.
Опис контрольних прикладів.
Листінг програми та протокол розв’язку (завдання задачі) проблеми.
Аналіз одержаних результатів.
Вимоги до виконання
Використати системне вікно для вводу цільового речення. Побудувати програму таким чином, щоб обмежити кількість отриманих рішень.
Індивідуальні завдання
1. Скласти процедуру злиття двох впорядкованих символьних списків.
2. Скласти процедуру ріверсування списку, компоненти якого - цілі числа.
3. Скласти процедуру вставки заданого рядка першого або останнього в черзі,
компоненти якого - довільні рядки.
4. Скласти процедуру видалення заданого рядка з списку рядків. Врахувати, що
в списку можливі копії рядків.
5. Змоделювати множину символів списком. Скласти процедуру додавання та
видалення довільного символу.
6. Скласти процедуру об’єднання множин символів. Множини моделюються
списками.
7. Скласти процедуру перетину множин символів. Множини моделюються
списком.
8. Скласти процедуру отримання різниці множин символів. Множини
моделюються списком.
9. Скласти процедуру отримання симетричної різниці множин натуральних чисел
.
Множини моделюються списком.
10. Скласти процедуру видалення першого і останнього рядків з черги довільних рядків.
11. Скласти процедуру пошуку в словнику елементів за ключем або за
значенням. Словник будується на основі лінійного списку пар (рядок, ціле), де рядок - ключ. Відображення, що реалізується 1:1.
12. Скласти процедуру вставки в словник, що реалізується лінійним списком,
елемента виду (рядок, ціле), де рядок — ключ, ціле — значення. Відображення, що реалізується 1:N. Контролювати, щоб не було елементів з однаковими ключами.
13. Скласти процедуру пошуку елемента за ключем в двійковому довіднику
(тобто організованому в вигляді впорядкованого двійкового дерева). Ключ — ціле, значення — рядок.
14. Скласти процедуру додавання елемента в двійковий довідник. Елементи
задаються у вигляді (ключ, значення), де ключ — ціле, значення — рядок.
15. Скласти процедуру додавання елемента в двійково-трійковий довідник
(Додаток). Ключі задано цілими, а значення — символами.
16. Скласти процедуру пошуку елемента в двійково-трійковому довіднику. Ключі задано цілими, а значення — рядками.
17. Скласти процедуру пошуку елемента в двійково-трійковому довіднику. Ключі задано цілими, а значення — символами. Для видалення задається ключ пошуку.
Для варіантів 18 -25 завдання
Маємо
три списки
.
Реалізувати наступні дії з ними
18.
19.
20.
21.
22.
23.
24.
25.
Поради до виконання роботи з комп’ютерного практикуму 3
Подамо деяку iнформацiю про списки в Турбо-Пролозi