Розв’язування математичнихзадач за допомогою мови логічного програмування - Prolog

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

Національний педагогічний університет імені М.П. Драгоманова

Інститут інформатики

 

 

 

 

Курсова робота на тему:

«Розв’язування математичнихзадач за допомогою мови логічного програмування - Prolog»

 

 

 

Автор: студент 31 ІА групи  
Капуста Вадим Юрійович

Науковий керівник: 
доцент Умрик Марія Анатоліївна

Робота захищена 16 грудня 2013р.

Оцінка   

 

Комісія: 1.  

2.  

3.  

 

Київ – 2013

Зміст

Вступ…………………………………………………….…………………………4

Розділ І. Мова логічного програмування – Пролог.…………………………….7

1. Переваги і недоліки мови Пролог………………………………....7
1. Числення предикатів – математична основа Прологу…………….9
1. Порівняльна характеристика середовищ програмування Prolog..11
1. Структура пролог-програми………………………………………22

1.5 Синтаксис мови програмування Prolog………………………..….27

Висновки до І розділу…………………………………………………….30

Розділ ІІ. Розв’язування задач мовою Prolog………………………………….31

2. Розв’язування логічних задач……………………………..………32
2. Розв’язування математичних задач……………………………...35

Висновки до ІІ розділу………………………………………..………….37

Загальні висновки………………………………………………………………..39

Список використаних джерел………………………………………..………...41

Додатки…………………………………………………………………………...42

Вступ

Майже всі сучасні комп’ютери засновані на ранніх, розроблених у 40-х роках ідеях Фон Неймана та його колег. Машина Фон Неймана має більшу пам’ять і процесор, оснащений локальною пам’яттю і комірками, що називаються регістрами. Процесор може завантажувати дані з пам’яті в регістри, виконувати арифметичні та логічні операції над вмістом регістрів і надсилати значення регістрів на згадку. Програма машини Фон Неймана являє собою послідовність команд виконання перерахованих операцій разом з додатковою більшістю команд управління, які впливають на вибір наступної команди. В міру подолання технічних проблем створення комп’ютерів накопичувалися проблеми пов’язані з їх використанням. Труднощі змістилися з області виконання програм комп’ютера в область створення програм для нього. Почалися пошуки мов програмування, які були зрозумілі людині. Починаючи з мови, яка сприймається комп’ютером (машинної мови), стали з’являтися більш зручні формалізми і системи позначень. І хоч ступінь абстракції мов зріс, починаючи з нібито асемблера і далі до Фортрана, Алгола, Паскаля і Ади,всі вони несуть друк машини з архітектурою Фон Неймана. Характерні особливості програмування на комп’ютерах Фон Неймана призводять до розподілу праці: є люди, які думають як вирішити задачу, і розробляють відповідні методи, а є люди-кодувальщики, які пишуть тексти програм, тобто виконують прозаїчну і стомлюючу роботу з перекладом інструкції розроблювачів у команди, які сприймаються комп’ютером.

У логіці, і в програмуванні потрібне явне вираження знань і методів у потрібному формалізмі. Явне формулювання яких-небудь відомостей є стомлюючою роботою. Але формалізація в логіці є часто інтелектуальною працею, оскільки при цьому задача стає більш зрозумілою. На відміну від цього формалізація задачі і метода її вирішення у вигляді набору інструкцій машини Фон Неймана рідко приводить до потрібного ефекту.

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

На сьогоднішній день існує багато мов програмування, та їх варіантів, які використовуються як починаючими програмістами, так і професіоналами.

Програміст тільки повідомляє системі те, що йому відомо та задає питання. Його в більшій мірі цікавлять знання і в меншій – алгоритми, за допомогою яких з цих знань вилучається необхідна інформація. Саме цьому для програмування мовою Пролог необхідно свіже логічне мислення, при якому знання таких мов програмування як Паскаль або Бейсик може бути справжньою поміхою. До речі, назва мови ПРОЛОГ є скороченням «ПРОграмування мовою ЛОГіки»1

Метою роботи є створення програм для моделювання математичних задач за допомогою мови логічного програмування Prolog

Завдання роботи:

1. Освоїти основи мови логічного програмування Prolog;
2. Дослідити середовища розробки Prolog;
3. Опрацювати літературні і інтернет джерела з теми;
4. Опрацювати відомості про мову логічного програмування Prolog;
5. За допомогою Prolog створити програмні засоби для моделювання математичних задач.

Основними методами дослідження є:

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

 

І. Мова логічного програмування – Пролог

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

Перші повідомлення про Пролог з’явились на початку сімдесятих років. Він належить до класу логічних мов програмування, основні ідеї розробки яких запропонували Р.Ковальські та П.Хейс. Перший інтерпретатор Прологу був розроблений французами в Марселі під керівництвом А.Колмерое в 1973 р. Наступна версія, виконана Д.Уореном - Единбурзька реалізація Прологу на машині DEC-10, перевела цю мову і разом з нею логічне програмування з площини теоретичних досліджень у площину практичного програмування, зробила її корисним інструментом для розв’язання різних задач штучного інтелекту. Про великі можливості мови Пролог свідчить і той факт, що японські вчені обрали його як базову мову для створення обчислювальних систем п’ятого покоління.

Для Прологу характерним є  той факт, що програміст повинен мислити в термінах цілей. Що під цим слід розуміти? Коли програмуємо, застосовуючи мову низького рівня, то повинні описувати, що треба зробити ЕОМ. Коли ж використовується мова програмування високого рівня, тоді необхідно вказати, що саме потрібно зробити. На відміну від традиційних мов, Пролог вимагає від програміста змінити форму мислення щодо написання програм. Прологівська програма являє собою набір визначень ситуацій і формулювань задач, замість того, щоб детально описувати варіанти розв’язків останніх. Основою Прологу є обмежений, але на диво потужний і гнучкий набір програмних механізмів, який включає в себе: співставлення зразків, задавання структур даних типу дерева й автоматичне повернення. Назва Пролог утворилась як скорочення від “програмування в термінах логіки” і його можна віднести до мов програмування, що будуються на описовому або ж декларативному підході до програмування.

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

Попередньо Пролог належав до теоретичних мов програмування і  більше використовувався як інструментарій у наукових дослідженнях. На це впливало й те, що довгий час вчені  США не сприймали його переваг для розв’язання задач штучного інтелекту. Джон Малпас пояснює цей факт тим, що, по перше, серед учених США були сильними ліспівські традиції (мова ЛІСП створена в Массачусетському технологічному інституті) і, по друге, - попереднє знайомство з мовою логічного типу Мікропленнером було невдалим. Остання була реалізована дуже неефективно. Та зі створенням швидких інтерпретаторів і компіляторів Пролог зайняв почесне місце не тільки серед найбільш вживаних мов розв’язання задач штучного інтелекту, а й серед мов, які використовуються спеціалістами в реляційних базах даних, програмній інженерії, при задаванні знань, в експертних системах тощо.

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

1. Ця мова має чітку  математичну основу, близьку до  людського мислення.

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

3. Застосування відношення  як базового поняття мови надає  змогу зручно працювати з реляційними  базами даних.

4. Паралельний принцип  організації обчислень дозволяє  просто й природно реалізовувати  Пролог-програму на паралельному  комплексі.

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

6. Пролог може зберігати  за допомогою “логічних змінних”  проміжні результати обчислень  для наступного використання. Це  дозволяє природно вирішувати  проблему організації логічного  виведення.

Поряд з перевагами фахівці зазначають такі вади Прологу.

1. Складність розуміння  процесу виконання програми на Пролозі, пов’язані з “не видимим” порядком побудови виведення результату програмою.

2. Недосконалі засоби  для вияву екстра логічних властивостей (оператори динамічного приєднання та вилучення тверджень).

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

4. Недостатні засоби підтримки  модульного принципу програмування.

1.2. Числення предикатів – математична основа прологу

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

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

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

1) константні терми с1,с2,...;

2) змінні терми х1,х2,...;

3) функціональні терми  f1,f2,...;

4) предикатні букви p1,p2,...;

5) логічні символи ¾>,&,È,~,",$;

6) спеціальне висловлення .

Елементарне висловлення складається з предиката і зв’язаних з ним термів. Складні висловлення будуються з елементарних за допомогою логічних зв’язок. Серед них можна виділити логічні зв’язки: “і” (and, &), “або ж” (or,È) , “ні” (not, ~) та імплікація (¾>). Остання посідає особливе місце, оскільки використовується для побудови специфічних правил і читається “якщо..., тоді...”.

Для того, щоб у численні предикатів можна було використовувати змінні терми, застосовується спеціальна структура - квантор.

Квантори використовуються для зазначення міри, в якій значення змінних повинні бути істинними для того, щоб у цілому висловлення стало істинним. Виділяють квантори узагальнення (") та існування ($).

У логіці предикатів елементарним об’єктом, що має значення “істина”, є атомарна формула. Вона включає в себе символьні позначення предиката і термів, які відіграють роль аргументів цього предиката. Загалом позначення предиката є ім’ям відношення, яке існує між аргументами.

Атомарна формула записується як позначення предикату і має вигляд Р(t1,t2,...,tn), де Р - позначення предиката, а t1,t2,...,tn- терми.

Число термів для кожного предиката фіксоване і називається його арністю. Терми визначаються наступним чином:

1) константний терм - терм;

2) змінний терм - терм;

3) якщо арність функціональної  букви є n, а t1,t2,...,tn- терми, тоді f(t1,t2,...,tn) також терм.

Правильно побудована формула (ППФ) отримується внаслідок комбінування атомарних формул за допомогою логічних зв’язок.

Символ •позначає хибну замкнуту формулу і визначає поняття “протиріччя”. Так, формула А ¾>” означає хибність А і еквівалентна формулі ~А.

Серед формул можна виділити спеціальний клас - тотожно істинні формули, які називають аксіомами. Приклад аксіоми:

~~ А <¾¾> А.

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

1.3. Порівняльна характеристика середовищ програмування Prolog

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

Arity Prolog

Arity/Prolog32

B- Prolog

B- Prolog 1.0

B- Prolog 1.2

B- Prolog 1.5

B- Prolog 1.6

B- Prolog 2.0

B- Prolog 2.1

B- Prolog 3.0

B- Prolog 3.1

B- Prolog 3.2

B- Prolog 4.0

B- Prolog 5.0

B- Prolog 5.0 - a

B- Prolog 5.0 - b

B- Prolog 6.0

B- Prolog 6.0 beta

B- Prolog 6.1

B- Prolog 6.2

B- Prolog 6.4

B- Prolog 6.5

B- Prolog 6.6

B- Prolog 6.7

B- Prolog 6.7-1

B- Prolog 6.7-3

B- Prolog 6.8

B- Prolog 6.9

B- Prolog 7.0

B- Prolog 7.1beta4

B- Prolog 7.4-3

BinProlog

Brain Aid Prolog

Ciao Prolog

CxProlog

ECLiPSe CLP

ECLiPSe CLP 6.0 # 188

EZY Prolog

EZY Prolog 1.0

EZY Prolog 1.01

EZY Prolog 2.0

EZY Prolog 2.1

EZY Prolog 3.0

EZY Prolog 4.0

EZY Prolog SUITE

EZY Prolog WYSIWYG

GNU Prolog

gprolog 1.3.0

gprolog 1.3.1

IF / Prolog

JIProlog

K- Prolog

MINERVA

Open Prolog

PDC / Turbo Prolog

PDC Prolog 3.31

Turbo Prolog 1.0

Turbo Prolog 2.0

Poplog ( Prolog )

Poplog 15.5 ( Prolog )

Qu - Prolog

SICStus Prolog

SWI - Prolog

swipl 5.6.x

Trinc - Prolog

R3B

Visual Prolog

Visual Prolog 4.0

Visual Prolog 5.0

Visual Prolog 5.1

Visual Prolog 7.2

YAP

 

Розглянемо основні з них.

 

SWI - Prolog

Реалізація мови програмування Prolog.