Шекет В.І. Конспект лекцій по логічному програмуванню

Подождите немного. Документ загружается.

ІВАНО-ФРАНКІВСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ

УНІВЕРСИТЕТ НАФТИ І ГАЗУ

ЛОГІЧНЕ ПРОГРАМУВАННЯ

КОНСПЕКТ ЛЕКЦІЙ

2005

МВ 02070855-1565-2005

Пролог - мова

логічного програмування Конспект лекцій. – Івано-Франківськ:

Факел, 2005. – 138с.

Методичні вказівки складено згідно з програмою курсу “Логічне

програмування” для студентів спеціальності “Програмне

забезпечення автоматизованих систем” і призначені для

самостійної роботи при вивченні дисципліни студентами денної

та заочної форми навчання.

Рецензент: зав. Кафедри комп’ютерних технологій в системах

управління та автоматики

Дане видання – власність ІФНТУНГ. Забороняється тиражування

та розповсюдження

МВ

Юрчишин В.М., Шекета В.І., Гобир Л.М. Пролог - мова

логічного програмування: Конспект лекцій. – Івано-Франківськ:

Факел, 2005 – 138с.

Методичні вказівки складено згідно з

програмою курсу “ ” для студентів спеціальності

“Програмне забезпечення автоматизованих систем”

і призначені для самостійної роботи при

вивченні дисципліни студентами денної та

заочної форми навчання.

Рецензент: зав. kафедри комп’ютерних технологій в системах

управління та автоматики

Член експертно-рецензійної комісії

університету Я.Р.Когуч

Нормоконтролер О.Г.Гургула

Коректор Н.Ф.Будуйкевич

Дане видання – власність ІФНТУНГ.

Забороняється тиражування та розповсюдження

ЗМІСТ

Bступ............................................................................................6

1 Пролог - мова логічного програмування................................7

1.1 Загальний огляд мови Пролог ................................................7

1.2 Переваги і недоліки мови Пролог..........................................9

1.3 Числення предикатів - математична основа мови................10

1.4 Побудова теорії деякої області знань ....................................12

1.5 Від формальної логіки до логічного програмування...........14

1.6 Механізм логічного виведення і керування..........................17

2 Основні концепції прологу........................................................20

2.1 Факти та правила .....................................................................20

2.2 Як змінні отримують свої значення.......................................22

2.3 Анонімні змінні .......................................................................24

2.4 Складні цілі: кон`юнкція та диз`юнкція................................25

2.5 Способи cпівставлення ..........................................................28

3 Структура програми pdc прологу .............................................30

3.1 Основні розділи програми ......................................................30

3.2 Стандартні домени ..................................................................31

3.3 Синтаксис правила ..................................................................33

3.4 Директиви комп`ютеру ...........................................................33

3.5 Бектрекінг.................................................................................34

3.5.1Бектрекінг з внутрішньою ціллю.........................................35

4 Контроль пошуку рішень...........................................................38

4.1 Використання предикату fail..................................................38

4.2 Відміна бектрекінгу.................................................................38

4.3 предикат not - заперечення як неуспіх ..................................44

4.4 Труднощі у використанні відтинання і заперечення ...........46

4.5 Засоби керування.....................................................................47

5 Прості та складні об'єкти ...........................................................50

5.1 Прості дані................................................................................50

5.1.1 Константи як об'єкти даних.................................................50

5.2 Складні об'єкти даних і функтори .........................................51

5.2.1Уніфікація складних об`єктів...............................................52

5.2.2 Приклад застосування функторів .......................................54

5.3 Приклад використання складних об'зктів .............................55

5.4 Опис доменів складних об'єктів.............................................60

5.5 Багаторівневі складні об'єкти.................................................63

5.6 Приклад, який ілюструє задання структури

речення англійської мови .............................................................64

5.7 Опис змішаних складних об'єктів..........................................65

5.7.1 Аргументи, які можуть мати різний тип ............................65

5.7.2 Cписковий тип ......................................................................66

5.8.Порівняння складних об`єктів................................................67

6 Ітерація і рекурсія.......................................................................70

6.1 Реалізація ітераційного процесу за допомогою

бектрекінгу.....................................................................................70

6.2 Дії типу до і після ....................................................................71

6.3 Застосування бектрекінгу для реалізації циклів...................71

6.4 Рекурсивні процедури.............................................................73

6.5 Використання аргументів в якості параметрів циклу..........73

7 Рекурсивні структури даних....................................................77

7.1 Структура даних типу дерева.................................................77

7.2 Обходи дерева..........................................................................78

7.3 Створення дерева.....................................................................79

7.4 Бінарний пошук на дереві.......................................................82

7.5 Сортування по дереву ............................................................83

7.5.1 програмна реалазація лексикографічного

впорядкування при символьному вхідному потоці ...................84

8 Робота з списками в пролозі..................................................87

8.1 Рекурсивна сутність списку ...................................................87

8.2 Обробка списків.......................................................................88

8.2.1 Друк списків..........................................................................89

8.2.2 Підрахунок кількості елементів ..........................................89

8.2.3 Іще один варіант підрахунку довжини списку ..................91

8.2.4 Модифікація списку .............................................................93

8.2.5 Належність елемента списку ...............................................94

8.3 Використання одного й того ж предикату для

вирішення різних задач.................................................................95

8.4 Знаходження зразу всіх розв`язків........................................97

8.5 Складні списки.........................................................................98

8.6 Реалізація синтаксичного аналізу за допомогою

списків ............................................................................................100

9. Техніка програмування в пролозі .........................................105

9.1 Принципи побудови експертної системи..............................105

9.2 Макетування: задача маршрутизації .....................................111

9.3 Пригоди в дивних печерах......................................................113

9.4 Моделювання апаратних засобів ..........................................116

9.5 Задача про ханойські башні....................................................117

9.6 Ділення слів на склади............................................................119

9.7 Задача про N королев ..............................................................123

10 Особливі технічні прийоми для професіоналів.................130

10.1 Потоковий аналіз...................................................................130

10.2 Керування потоковим аналізом............................................131

10.3 Стиль програмування...........................................................132

Перелік використаних джерел.............................................138

ВCТУП

Мета курсу “Логічне програмування”— засвоїти основні

положення та підходи логічних програм та набути практичних

навичок при написанні логічних програм на основі знань

нафтогазової предметної області.

Нафтогазопромислова справа є однією із сфер діяльності

людини, де вагомі наукові та технічні рішення отриманні

засобами логічного програмування. Це в першу чергу, пов’язане з

унікальністю та великомасштабністю об’єктів досліджень.

В нафтогазовій галузі матеріальні збитки від помилкового

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

не стільки на реалізацію прийнятого рішення, стільки на

ліквідацію його наслідків. Немало прикладів, коли ліквідація

відкритого фонтанування нафтової або газової свердловини

тривали більше року, а затрати на його ліквідацію сягали

декілька десятків мільйонів доларів. Значні неявні витрати

отримують . наприклад, при зниженні коефіцієнта нафтовіддачі

невеликої ділянки родовища на один відсотокок , що тягне за

собою сотні тисяч тон нафти.

Тому для прийняття раціонального технологічного рішення

має важливе значення логічний підхід.

Поняття “логіка” має глибокі філософські корені. Для теорії і

практики штучного інтелекту особливе значення має таке

питання : яким чином можна організувати логічні набудови так,

щоб вони могли здійснюватися автоматично без участі людини.

Логічне виведення за дедукцією є одним із основних

механізмів мислення . Саме цей вид логічного виведення

найбільш вивчений і найкраще піддається формалізації.

Можна розглянути як мінімум дві задачі кожна з них з

автоматизацією дедуктивних побудов:

- задача виведення наслідків , яка формується так : знайти

всі вірно побудовані формули, які можна логічним шляхом

вивести з аксіом на основні правил виведення, або у практичній

інтерпретації— знайти усі наслідки із заданих фактів.

- задача автоматичного доведення теорем , або задача

перевірки справедливісті даного твердження і формулюється

таким чином: дана деяка теорія (логічна модель) ; потрібно

встановити чи є певне твердження теоремою , тобто чи можна

його вивести з аксіом даної теорії.

Механізм автоматичного доведення теорем

покладено в основу

логічного програмування. .

Програма розглядається як набір логічних формул

разом з теоремою, що має бути доведена найвідомішим

представником логічного програмування є мова

Пролог.

Назву Пролог (Prolog) утворено з двох англійських слів

PROgramming LOGig. Ця мова створена професором Аленом

Колмеросом , який працював в 1970 році в рамках проекту зі

створення методів швидкого виявлення синтаксичних помилок в

програмах. Сьогодні Пролог— це широко відома мова, яка

орієнтована на розуміння природної мови, формування баз

знань розробку експертних систем та інші проблеми штучного

інтелекту. Мова Пролог принципово відрізняється від

традиційних мов програмування, оскільки програма мовою

Пролог описує не процедуру розв’язування задач, а логічну

модель предметної області : деякі факти відносно властивостей

предметної області та відношень між цими властивостями , а

також правила виведення нових властивостей і відношень на

основі вже заданих . Такий логічний підхід до програмування

створює деякі проблеми в поширенні мови ; основні поняття

мови програмістами засвоюються без особливих труднощів, в той

час практичне перетворення усього розуміння в написяні

програми викликає певні складності. Але потужність і гнучкість

баз знань утворених за допомогою мови пролог Прологу, лише

без модифікації на розширення робить цю мову дуже зручною

для логічного програмування в нафтогазовій предметній області.

На основі цієї мови на кафедрі програмного забезпечення

автоматизованих систем ІФНТУНГ розроблені експертні

системи КОЛЕКТОР , ПОКЛАД, ПЛАСТ, НАФТА.

1 ПРОЛОГ - МОВА ЛОГІЧНОГО ПРОГРАМУВАННЯ

1.1 Загальний огляд мови Пролог

Перші повідомлення про Пролог з`явились на початку

сімдесятих років. Він належить до класу логічних мов

програмування. Основні ідеї розробки яких запропонували

Р.Ковальськи і П.Хейс. Перший інтерпретатор Пролога був

розроблений французами в Марселі під керівництвом

А.Колмерое в 1973 році. Наступна версія, виконана Д.Уореном -

Единбугська реалізація Пролога на машині DEC-10, перетворила

Пролог і разом з ним логічне програмування із площини

теоретичних досліджень в площину практичного програмування,

зробила його корисним інструментом для вирішення різних задач

штучного інтелекту. Про великі можливості мови Пролог

свідчить і той факт, що японські вчені вибрали його в якості

базової мови для створення обчислювальних систем п`ятого

покоління.

Для Прологу характерним є і той факт, що програміст

повинен мислити в термінах цілей. Що ми під цим будемо

розуміти? Коли ми програмуємо, застосовуючи мову

програмування низького рівня, тоді ми повинні описувати як

дещо треба зробити ЕОМ. Коли ж використовується мова

програмування високого рівня, тоді необхідно вказати що ж

потрібно зробити. На відміну від традиційних мов

програмування, Пролог вимагає від програміста змінити форму

мислення по написанню програм. Прологівська програма являє

собою набір визначень ситуацій і формулювань задач, замість

того, щоб детально описувати варіанти рішень цих задач.

Основою Пролога є обмежений, але на диво потужний і гнучкий

набір програмних механізмів, який включає в себе: співставлення

зразків, задання структур даних типу дерева і автоматичне

повернення. Назва Пролог утворилась як скорочення від

“програмування в термінах логіки” і його можна віднести до мов

програмування, які будуються на описовому або ж

декларативному підході до програмування.

Можна виділити два рівня характеристики прологівської

програми: декларативний і процедурний. Перший з них визначає

за допомогою відношень, яким повинен бути результат роботи

програми. Другий - як цей результат був отриманий і які з

відношень реально оброблялись. Пролог-системи значну частину

процедурних деталей виконують самостійно без втручання

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

легшому декларативному аспекту програми не відволікаючись на

організацію процеса обчислень, якщо його не хвилює питання

ефективності обчислень.

Попередньо Пролог відносився до теоретичних мов

програмування і в більшості використовувався як інструментарій

в наукових дослідженнях. На це впливало і те, що довгий час

вчені із США не сприймали його переваг для вирішення задач

штучного інтелекту. Джон Малпас пояснює цей факт тим, що по

перше серед вчених США були сильними лісповські традиції

(мова ЛІСП створена в Массачусетському технологічному

інституті) і по друге - попереднє знайомство з мовою логічного

типу Мікропленнером було невдалим. Остання була реалізована

дуже не ефективно. Та з створенням швидких інтерпретаторів і

компіляторів Пролог зайняв почесне місце не тільки серед

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

інтелекту, а й серед мов, які використовуються спеціалістами в

галузях реляційних баз даних, програмної інженерії, задання

знань, експертних системах і багатьох інших.

1.2 Переваги і недоліки мови Пролог

Резюмуючи сказане раніше можна виділити наступні

переваги Прологу:

1.Пролог має чітку математичну основу, дуже близьку до

людського мислення.

2.Використання єдиної мови специфікацій (числення

предикатів) для опису вимог до програм і опису самої програми

на Пролозі дозволяє поєднувати процес написання програми і її

верифікацією.