Міністерство освіти і науки України, молоді та спорту

Національний університет «Львівська політехніка»

Інститут екології, природоохоронної діяльності та туризму ім. В.Чорновола

Кафедра загальної екології та екоінформаційних систем

РЕФЕРАТ

З дисципліни: «Логічне і функцій не програмування»

на тему:

Способи використання механічної відсічки

Виконала:

ст..гр. КН-49

Оприщенко О.Л.

Прийняв:

Заяць В.М.

ЛЬВІВ – 2011

ЗМІСТ

ВСТУП………………………………………………………………………...3

Розділ Ι. МЕХАНІЗМ ПОВЕРНЕННЯ ТА ВІДСІЧКИ В ЛОГІЧНОМУ ПРОГРАМУВАННІ………………………………………………………………......4

1. Механізм перепогодження цільових тверджень …………4

2. Суть механізму відсічки у логічному програмуванні …..6

3. Основні випадки застосування механізму відсічки……....9

Розділ ΙΙ. ТИПОВІ СПОСОБИ ВИКОРИСТАННЯ МЕХАНІЗМУ ВІДСІЧКИ ТА ПОВЕРНЕННЯ……..……………………………………………..11

1. Комбінація відсічки та предиката fail….………………..11

2. Типові випадки використання механізму генерування розв'язків та перевірки ……...……………………………..12

ВИСНОВОК………………………………………………………………………14

ВИКОРИСТАНІ ДЖЕРЕЛА……………………………………………………..15

ВСТУП

Логічне програмування – це програмування мовою логічних висловлювань або тверджень. Серед мов логічного програмування найпоширеніша мова Пролог.

Щодо історії її виникнення, можна назвати декілька фактів: Пролог з’явилася в 1970 р. одночасно з такими мовами як СІ, Паскаль.

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

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

Саме ж слово "відсічка" походить від англійського слова cut, що означає скорочення. Але термін "відсікання" використовувався в перших роботах з логічного програмування і використовується досі.

Саме про механізм відсічки й йтиметься у даній роботі. В подальшому ми розглянемо всі можливі способи використання механічної відсічки та її застосування у логічному програмуванні.

Розділ ι. Механізм повернення та відсічки в логічному програмуванні

1. Механізм перепогодження цільових тверджень.

За наявності деякого цільового твердження (цілі) в базі даних Прологу можуть виникати такі ситуації:

1. Спроба довести погодженість цілі з базою даних, починаючи з її вершини. Необхідно виділити два випадки:

а) Знайдений факт (або заголовок правила), який може бути порівняний з ціллю. Це місце в базі даних відмічається спеціальним маркером і одночасно змінні конкретизуються. Якщо ж порівнюється з заголовком правила, то насамперед робиться спроба погодити підцілі, які породжені цим правилом. Пролог здійснює погодження підцілей поступово, рухаючись зліва направо від крайньої лівої підцілі до крайньої правої в тілі правила.

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

2. Спроба перепогодити цільовий запит приводить до руху маркера знизу вверх по базі даних.

Якщо при перепогодженні деякого цільового твердження не знаходиться альтернативного розв'язку, то Пролог робить спробу перепогодити всі попередні цілі, повертаючись до самої вихідної. Одночасно всі змінні розконкретизовуються, стають невизначеними і всі результати знищуються. Маркер починає рух знову вниз по базі даних, намагаючись по новому погодити цільові твердження, можуть знову виникати ситуації а) або б).

Розглянемо більш детально механізм перепогодження цілей на конкретних прикладах.

Найпростіший випадок, коли породжується множина розв'язків, ілюструє така база даних:

батько(марія,іван).

батько(петро,іван).

батько(ігор,михайло).

батько(іра,михайло).

Тоді Пролог на запит

? - батько(X,У).

Видасть відповіді:

X = марія У = іван

X = петро У = іван

X = ігор У = михайло

X = іра У = михайло

Розглянемо цікавіший випадок, коли в запиті є дві підцілі, для яких можливі альтернативні розв'язки:

можлива__пара (X, У) - хлопець (X) , дівчина (У) .

хлопець(іван). дівчина(іра).

хлопець(петро). дівчина(ольга).

хлопець(дмитро). дівчина(оксана).

Відповіді Прологу на запит:

? - можлива_пара(X,У).

будуть такі:

X = іван У = іра

X = іван У = ольга

X = іван У = оксана

X = петро У = іра

Ці приклади є доволі простими, оскільки породжують скінченну множину розв'язків. В прикладних задачах, як правило, апріорі невідома кількість розв'язків, оскільки їх може існувати цілий континіум. В таких випадках використовується рекурсивне представлення програми. Розглянемо предикат, який породжує множину цілих чисел:

ціле__число (0) .

ціле_число (X) : -ціле_число (У) ,Х = У+1.

На запит

? - ціле_число(Z).

буде породжуватися множина цілих чисел від 0 доти, доки це вичерпається весь машинний ресурс.

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

Так, правило визначення належності деякого об'єкта до списку:

належить(X,[X| _]).

належить(X,[_|У]):- належить(X,У).

на запит:

? - належить(а,X).

породжує цілий континіум розв'язків

[а|_];

[_а|_];

[_а|_];

………………

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