Лабораторна робота №2

Тема: мова програмування PRL як засіб розв’язку логічних задач.

Мета: За допомогою PRL розв’язати задачу на розміщення.

 

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

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

Визначення. В розділі дискретної математики, який називається «комбінаторика» введено поняття розміщень (arrangement) з N елементів по M. Фактично, розміщенням можна вважати впорядковану вибірку M елементів з множини N елементів (N ³ M). Кількість можливих розміщень можна знайти так:

P(N, N – M) = N! / (N – M)! = N*(N–1)*(N–2)*…*(N–M+1).

Якщо N = M, то розміщення перетворюється на перестановку елементів (permutation) без повторень. Кількість таких перестановок дорівнює:

P(N) = N! = N*(N–1)*(N–2)*…*1.

Інколи розглядаються перестановки, в яких елементи мають повторення (repetitions), наприклад: <1,2,2,3,3,3,3>. В таких перестановках кількість різних варіантів зменшується пропорційно кількості комбінацій, що задають повторення, для даного прикладу кількість різних комбінацій буде: P(7, 2, 4) = 105. Для k груп з кількістю однакових елементів M_k отримуємо:

P(N, M₁, M₂,… M_k) = N! /(M₁! * M₂! * …* M_k! ).

Інтерпретація. Кожна формула в комбінаторному аналізі може бути інтерпретована як процес нумерації або вибору елементів. Наприклад, факторіал N! можна трактувати як процес вибору одного елементу з N, після якого залишилося N–1 елементів, і ми знову вибираємо один елемент, залишається N–2, і так далі, доки не заберемо всі елементи. Цей процес можна описати наступною програмою:

 

goal:- permutation, prn, fail.

permutation:- list(X), suppose(list2(X)), permutation.

permutation:- not(list(X)).

prn:- list2(X), X>0, write(X), fail.

prn:- write().

list(1). list(2). list(3). list(4). list2(0).

Процес генерування розміщень можна трактувати як перебір перестановок з N елементів, з яких перші елементи мають номери 1, 2, … M, а решта – пробіли. При такій перестановці числа 1, 2, … M будуть інтерпретуватися як номери місць вибраних елементів { 1, 2, … N }, а пробіли будуть інтерпретуватися як елементи, які не потрапили у вибірку:

                                                   1 2 3 4 5 6 7 8

при N=8, M=4 перестановка 3 _ _ 1 _ 2 4 _ означає розміщення 4, 6, 1, 7.

Завдання 1. Для закріплення матеріалу модифікувати програму permutation так, щоб вона виводила всі можливі розміщення з множини list кількістю 5 елементів по 3. Для цього ввести додаткове твердження arrangement та goal (див. далі). Переробити prn так, щоб він виводив замість номерів місць фрагменти з IMEI вашого мобільного телефону.

 

goal:- n=3, arrangement(n), prn, fail.

arrangement(n):- n>0, list(X), suppose(list2(X)), n1=n-1, arrangement(n1).

arrangement(n):- n=0.

Завдання 2. На сьогоднішній лабораторній роботі також необхідно придумати та розв’язати просту задачу на розміщення по типу відомої жартівливої «задачі Ейнштейна». Вона задає початкову неповну інформацією про деяких персонажів та логічні обмеження, які дозволяють перейти від неповних даних до повністю визначених. Суть задачі у наступному. Існує п’ять будинків (з номерами 1..5), які розташовані по одній вулиці. Будинки мають різні кольори. Відомо, що в них мешкають персонажі, які умовно називаються: Англієць, Німець, Француз, Швед, Датчанин. Вони мають різні звички, мають різних домашніх тварин, їздять на різних автомобілях. Необхідно визначити повну інформацію про кожного персонажа за допомогою 16 логічних умов (див. далі).

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

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

Для того, щоб зробити припущення в інтерпретатор введено ключове слово «suppose()» при якому в дужках вказується факт, який припускається. Зручність метода припущень є у тому, що про безпеку даних турбується не програміст, а інтерпретатор. Щоразу при переході до наступного твердження після успішного виконання дані уточнюються. Така концепція дозволяє уточняти невідомі значення та працювати з неповною інформацією.

Приклад розв’язку дається наступною програмою:

 

Einstein:-

s1,s2,s3,s4,s5,s6,s7,s8,s9,s10,s11,s12,s13,s14,s15,s16,prn,fail.

Нац(Нац):- Нац=_,write("Невідома особа"),!.

Нац(Нац):- Нац=1,write("живе Англієць").

Нац(Нац):- Нац=2,write("живе Німець").

Нац(Нац):- Нац=3,write("живе Француз").

Нац(Нац):- Нац=4,write("живе Швед").

Нац(Нац):- Нац=5,write("живе Датчанин").

Ном_будинку(Ном_будинку):- write("будинок №",Ном_будинку).

Колір_буд(Колір_буд):- Колір_буд=_,write("Невідомий колір"),!.

Колір_буд(Колір_буд):- Колір_буд=1,write("Червоний").

Колір_буд(Колір_буд):- Колір_буд=2,write("Зелений").

Колір_буд(Колір_буд):- Колір_буд=3,write("Синій").

Колір_буд(Колір_буд):- Колір_буд=4,write("Білий").

Колір_буд(Колір_буд):- Колір_буд=5,write("жовтий").

Напій(Напій):- Напій=_,write("Напій невідомий"),!.

Напій(Напій):- Напій=1,write("любить молоко").

Напій(Напій):- Напій=2,write("любить каву").

Напій(Напій):- Напій=3,write("любить чай").

Напій(Напій):- Напій=4,write("любить сік").

Напій(Напій):- Напій=5,write("любить пиво").

Тварина(Тварина):- Тварина=_, write("Невідома тварина"),!.

Тварина(Тварина):- Тварина=1, write("має собаку").

Тварина(Тварина):- Тварина=2, write("має кота").

Тварина(Тварина):- Тварина=3, write("має папугу").

Тварина(Тварина):- Тварина=4, write("має рибок").

Тварина(Тварина):- Тварина=5, write("має коня").

Авто(Авто):- Авто=_, write("Авто невідомо"),!.

Авто(Авто):- Авто=1, write("їздить на тойоті").

Авто(Авто):- Авто=2, write("їздить на опелі").

Авто(Авто):- Авто=3, write("їздить на мерседесі").

Авто(Авто):- Авто=4, write("їздить на лексусі").

Авто(Авто):- Авто=5, write("їздить на ферарі").

; Француз живе або в третьому або в четвертому будинку:

s1:- Нац=3, Ном_будинку=3,

 home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто),

 suppose(home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто)).

s1:- Нац=3, Ном_будинку=4,

 home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто),

 suppose(home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто)).

; Англієць живе у червоному будинку:

s2:- Нац=1, Колір_буд=1,

 home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто),

 suppose(home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто)).

; Зелений будинок знаходиться зліва від білого:

s3:- Колір_буд1=2, Колір_буд2=4,

home(Нац1,Ном_будинку1,Колір_буд1,Напій1,Тварина1,Авто1),

home(Нац2,Ном_будинку2,Колір_буд2,Напій2,Тварина2,Авто2),

X=Ном_будинку1-Ном_будинку2, X=1,

suppose(home(Нац1,Ном_будинку1,Колір_буд1,Напій1,Тварина1,Авто1)),

suppose(home(Нац2,Ном_будинку2,Колір_буд2,Напій2,Тварина2,Авто2)).

; Датчанин завжди купляє чай:

s4:- Нац=5, Напій=3,

home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто),

suppose(home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто)).

; Той, хто їздить на тойоті відганяє сусідського кота:

s5:- Тварина1=2, Авто2=1,

home(Нац1,Ном_будинку1,Колір_буд1,Напій1,Тварина1,Авто1),

home(Нац2,Ном_будинку2,Колір_буд2,Напій2,Тварина2,Авто2),

neighbour(Ном_будинку1,Ном_будинку2),

suppose(home(Нац1,Ном_будинку1,Колір_буд1,Напій1,Тварина1,Авто1)),

suppose(home(Нац2,Ном_будинку2,Колір_буд2,Напій2,Тварина2,Авто2)).

; Біля жовтого будинку зажди стоїть опель:

s6:- Колір_буд=5, Авто=2,

home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто),

suppose(home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто)).

; Німець приїзджає на мерседесі:

s7:- Нац=2, Авто=3,

home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто),

suppose(home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто)).

; Той, хто живе в центрі завжди вживає молоко:

s8:- Ном_будинку=3, Напій=1,

home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто),

suppose(home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто)).

; Сусід того, хто їздить на тойоті любить пиво:

s9:- Напій1=5, Авто2=1,

home(Нац1,Ном_будинку1,Колір_буд1,Напій1,Тварина1,Авто1),

home(Нац2,Ном_будинку2,Колір_буд2,Напій2,Тварина2,Авто2),

neighbour(Ном_будинку1,Ном_будинку2),

suppose(home(Нац1,Ном_будинку1,Колір_буд1,Напій1,Тварина1,Авто1)),

suppose(home(Нац2,Ном_будинку2,Колір_буд2,Напій2,Тварина2,Авто2)).

; Той, хто має лексус, купляє корм для папуги;

s10:- Тварина=3, Авто=4,

home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто),

suppose(home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто)).

; Швед любить собак:

s11:- Нац=4, Тварина=1,

home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто),

suppose(home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто)).

; Датчанину подобається синій колір сусіднього будинку:

s12:- Нац1=5, Колір_буд2=3,

home(Нац1,Ном_будинку1,Колір_буд1,Напій1,Тварина1,Авто1),

home(Нац2,Ном_будинку2,Колір_буд2,Напій2,Тварина2,Авто2),

neighbour(Ном_будинку1,Ном_будинку2),

suppose(home(Нац1,Ном_будинку1,Колір_буд1,Напій1,Тварина1,Авто1)),

suppose(home(Нац2,Ном_будинку2,Колір_буд2,Напій2,Тварина2,Авто2)).

; Власник синього будинку виїзджає на коні:

s13:- Колір_буд=3, Тварина=5,

home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто),

suppose(home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто)).

; Той, хто їздить на ферарі вживає сік:

s14:- Авто=5, Напій=4,

home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто),

suppose(home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто)).

; У зеленому будинку часто заварюють каву:

s15:- Колір_буд=2, Напій=2,

home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто),

suppose(home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто)).

; Один з мешканців розводить рибок:

s16:- Тварина=4,

home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто),

suppose(home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто)).

; Роздрук рішення

 prn:- write("    Рішення:"),write("________________________"),

home(Нац,Ном_будинку,Колір_буд,Напій,Тварина,Авто),

Колір_буд(Колір_буд),Ном_будинку(Ном_будинку),Нац(Нац),

Авто(Авто),Напій(Напій),Тварина(Тварина),write(),fail.

 prn:- write().

; Початкові факти: відомий лише номер будинку

home(_,1,_,_,_,_). home(_,2,_,_,_,_). home(_,3,_,_,_,_). home(_,4,_,_,_,_).

home(_,5,_,_,_,_).

; Сусід по будинку

 neighbour(Ном_буд1,Ном_буд2):- X= Ном_буд1-Ном_буд2, X=1.

 neighbour(Ном_буд1,Ном_буд2):- X= Ном_буд2-Ном_буд1, X=1.

 

Програма починається з опису головного предикату «Einstein», для розв’язку якого необхідно виконати умови s1 … s16, після чого вказано роздрукувати знайдені дані за допомогою prn, та перебрати всі можливі варіанти рішень за допомогою fail.

Кожна умова s1 … s16 виглядає стандартно: знаходимо рядок таблиці, параметри якого не суперечать заданій умові, припускаємо для порожніх значень нові дані, та записуємо назад в таблицю. Програма закінчується коли реалізована остання умова s16.

Вам необхідно придумати та розв’язати свій варіант цієї задачі на будь-яку тему. Кількість невідомих не зв’язано з кількістю умов. Наприклад, якщо виключити з головного предикатного виразу умову s16 - «Один з мешканців розводить рибок», то у Датчанина з’явиться невідома домашня тварина. Якщо послабити умову s3 - «Зелений будинок знаходиться зліва від білого» так, що будинки не повинні бути поруч (в умові s3 замість X=1 поставити X>0), то рішень може бути декілька. В індивідуальному завданні задача повинна містити не менше 5 змінних.