« Назад

Мета: отримання основних навичок роботи з обробки списків

Хід виконання роботи

1. Запустити систему Пролог-Д.

На практиці часто зустрічаються завдання, пов'язані з перерахуванням об'єктів. Для опису таких об'єктів використаються списки. Наприклад, список учнів першого класу: [Саша,Петя,Дима,Ксюша,Лена,Оля,Катя].

Елементами списку можуть бути не тільки атоми, але й функції й, взагалі, будь-які елементи, навіть списки. Наприклад, список, що складається з функцій – список зупинок поїзда із вказанням часу стоянки:

Прикладом списку, що складається зі списків, може бути прямокутна таблиця (матриця), що представляє собою список рядків, кожний з яких є списком елементів у даному рядку. Наприклад, таблиця: 23 45 56 2 78 89 66 45 56 12 3 75 2 3 6 5 2 1 56 2 5 8 9 22 2 1 56 2 5 8 9 22 23 22 33 5 6 9 1 33 може бути представлена наступним списком, що складається зі списків: [[23,45,56,2,78,89,66,45],[56,12,3,75,2,3,6,5], [2,1,56,2,5,8,9,22],[2,1,56,2,5,8,9,22],[23,22,33,5,6,9,1,33]].

У всіх прикладах квадратні дужки означають, що даний об'єкт є списком.

Список може бути визначений двома способами: перерахуванням елементів списку, тобто так, як це було зроблено вище й визначенням голови й хвоста списку. Наприклад, список [X|Y] визначений саме таким шляхом. X - це голова списку, а Y – його хвіст. Різні шаблони визначають різне внутрішнє подання.

Шаблону [x,y] відповідає внутрішнє подання:

Шаблону [x|y] відповідає внутрішнє подання:

Різні шаблони – різні внутрішні подання – спричиняють розходження в уніфікації. Використовуючи подання списку можна вирішити ряд завдань.

1. Приналежність елемента до списку

Це завдання можна описати за допомогою наступних виразів:

а) Основний випадок можна сформулювати в такий спосіб: терм Р принадлежит списку [X..Y], если P=X..

б) Рекурсивна ситуація описується за допомогою висловлення "терм Р принадлежит списку [X..Y], если Р принадлежит Y". Мовою Пролог-Д ці два висловлення можна записати у вигляді двох речень:

принадлежит(P,L)<- равно(L,[X|Y]),равно(P,X);

принадлежит(P,L)<- равно(L,[X|Y]),принадлежит(P,Y);.

Ці визначення можна вдосконалити, якщо згадати, що, відповідно до процедурної семантики, Пролог-Д уніфікує спочатку голову правила, а потім його цілі. Удосконалена програма буде виглядати так:

элемент(P,[P|T]);

элемент(P,[X|Y])<- элемент(P,Y);.

2. Склеювання двох списків

Це завдання можна описати за допомогою наступних виразів:

а) основна ситуація полягає в тому, що якщо до порожнього списку [ ] додати список Р, то в результаті вийде Р.

б) рекурсивна ситуація полягає в тому, що можна список Р додати до кінця списку С, якщо Р буде доданий до хвоста С і потім приєднаний до голови В. На Пролог-Д ці предикати можна записати так:

Користуючись вищезгаданою властивістю процедурної семантики Пролог-Д, цю програму теж можна спростити:

Наприклад, якщо задано питання до цієї бази знань:

Завдання

1. Напишіть базу знань, що описує сортування списку цілих чисел по зростанню.

2. Напишіть базу знань, що описує обертання списку (перший елемент стає останнім).

3. Напишіть базу знань, що описує знаходження елемента списку з номером n.

4. Напишіть базу знань, що описує видалення n-oго елемента списку.

 

2. Оформити звіт, в який включити виконання завдань, Пролог- програму, ПИТАННЯ, представлені засобами Прологу, і відповіді на дані ПИТАННЯ, видані Пролог-системою.