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

Автор работы: Пользователь скрыл имя, 22 Декабря 2014 в 13:39, курсовая работа

Краткое описание

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

Содержание

Вступ…………………………………………………….…………………………4
Розділ І. Мова логічного програмування – Пролог.…………………………….7
Переваги і недоліки мови Пролог………………………………....7
Числення предикатів – математична основа Прологу…………….9
Порівняльна характеристика середовищ програмування Prolog..11
Структура пролог-програми………………………………………22
1.5 Синтаксис мови програмування Prolog………………………..….27
Висновки до І розділу…………………………………………………….30
Розділ ІІ. Розв’язування задач мовою Prolog………………………………….31
Розв’язування логічних задач……………………………..………32
Розв’язування математичних задач……………………………...35
Висновки до ІІ розділу………………………………………..………….37
Загальні висновки………………………………………………………………..39
Список використаних джерел…………

Вложенные файлы: 1 файл

Курсова Пролог.docx

— 264.60 Кб (Скачать файл)

Число аргументів предикату називається арністю предикату. Пролог допускає предикати з однаковою назвою, але різною арністю.

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

1) між рядками і символами;

2) між цілим, символьним  і дійсним доменом.

Як ми вже зазначали, синтаксис правила складається з трьох частин:

голова: - <підціль>, <підціль>, ... , <підціль>.

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

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

Ви можете включити в програму деякі директиви комп’ютера безпосередньо або ж зробити це, вибравши пункт меню Options /CompilerDirectives. Наприклад, директиву include. За її допомогою можна підключити до програми написані попередньо процедури. Додамо рядок include “my.pro” на початок програми. А у файлі my.pro описуються процедури, які використовуються у програмі розв’язку задачі. Якщо розглянутий шлях не дає відповіді, необхідно переглянути альтернативний. Такий підхід  дістав назву бектрекінг.

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

Розглянемо програму:

domains

name, thing = symbol

 

predicates

likes(name, thing)

reads(name)

is_inquisitive(name)

clauses

likes(john, wine).

likes(lance, skiing).

likes(Z,books) :-reads(Z),

is_inquisitive(Z).

likes(lance, books).

likes(lance, films).

reads(john).

is_inquisitive(join).

Задамо системі запитання у вигляді мети, яка складається з двох підцілей:

likes(X,wine), likes(X,books)

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

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

Підціль likes(X, wine) відповідає факту likes(john, wine). Тому Х зв’язується з john. Потім Пролог робить спробу задовольнити наступну підціль справа. Виклик другої підцілі розпочинає новий пошук з Х = john. Перший пункт likes(john,wine) не відповідає підцілі likes(X,books), тому що wine не є тим же, що й books. Тому Пролог намагається підібрати наступний пункт. Подальший пошук визначається третім правилом бектрекінгу. Коли підціль відповідає голові, тоді наступним повинно задовольнятися тіло даного правила. Тіло правила у свою чергу створює нові підцілі, котрі повинні бути задоволені.

І нарешті, четвертий принцип бектрекінгу такий. Мету буде задоволено, коли будуть знайдені відповідні факти для кожного рівня дерева мети.2

Бектерінг з внутрішньою метою ілюструється програмою:

predicates

type(symbol, symbol)

is_a(symbol, symbol)

lives(symbol, symbol)

can_swim(symbol)

goal

can_swim(What) ,

write("A ", What, " canswim.").

 

clauses

type(ungulate, animal).

type(fish, animal).

is_a(zebra, ungulate).

is_a(herring, fish).

is_a(shark,fish).

lives(zebra, on_land).

lives(frog, on_land).

lives(frog,in_water).

lives(shark, in_water).

can_swim(Y) :-

type(X, animal) ,

is_a(Y, X) , lives(Y,in_water).

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

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

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

Команда – формат оператора;

Введення - даних INPUT< список змінних>;

Команда – PRINT<список змінних>;

Присвоювання – LET<змінна> = <арифметичне вираження>;

Команда розгалуження – IF <умова> THEN <оператори> ELSE <оператори>;

Команда циклу - <оператори>NEXT<змінна>;

Команда циклу – FOR<змінна>FROM<арифметичне вираження>TO<арифметичне вираження>.

Арифметичні вираження можуть містити в собі: числа, змінні, знаки арифметичних виражень, стандартні функції й круглі дужки.

Мова програмування характеризується властивими йому механізмами керування й обробки даних. Пролог як універсальну мову програмування можна розглядати й із цих точок зору. При успішному виконанні обчислення засобу керування програм мовою Пролог подібний до засобів керування у звичайних процедурних мовах. Звертання до деякої мети відповідає виклику процедури, порядок цілей у тілі правила відповідає послідовності операторів. Точніше, правило А В1,В2,…,Вn можна розглядати як визначення процедури:

Procedure A

Call B1

Call B2

.

.

.

CallBn

End.

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

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

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

У логічному програмуванні обробка даних повністю укладена в алгоритмі уніфікації. В уніфікації реалізовані:

-         однократне присвоювання,

-         передача параметрів,

-         розміщення записів,

-         доступ до полів записів для одночасних читання/запису.

Традиційні мови, як правило, містять різного ступеня складності засоби обробки помилкових і виняткових ситуацій. Чистий Пролог не містить механізм обробки помилок і виняткових ситуацій, вбудованих в опис мови. На відміну від традиційних мов ситуації, що призводять до помилки (наприклад, відсутність потрібної галузі в операторі case, розподіл на нуль), у чистому Пролозі призводять до “відмови”.

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

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

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

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

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

ІІ. Розв’язування математичних задач мовою Prolog

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

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

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

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

  1. Аналізуються дані умови задачі (або ще кажуть, предметна область): факти, функції, відношення. Вибираються позначення для них.
  2. Описуються природною мовою з точки зору істинності відношення та функції.
  3. Описані відношення оформлюються як аксіоми у вигляді фраз (фактів, правил), зрозумілих Прологу для роботи з ними. Множина таких фраз складає структуру предметної області. Програма вводиться у робоче поле компілятора.
  4. Формулюються та виконуються запити до введеної програми, завдяки чому досягається результат розв’язку задачі.
    1. Розв’язування логічних задач

Приклади деяких логічних задач мовою Prolog:

Приклад1.

Написати та реалізував програму встановлення родинних зв'язків: Василь має дочку Ольгу, у якої два сини Михайло і Максим. Використовувати зовнішні і внутрішні цілі.

domains

name = symbol

divdicates

men (name)

mama (name)

sons (name, name)

doughter (name, name)

deda (name, name)

brother (name, name).

goal

doughter (Z, Y),

write (Z, Y),

nl.

clauses

men ("Vaciliy").

men ("Michail").

men ("Maxim").

mama ("Olga").

sons ("Michail", "Olga").

sons ("Maxim", "Olga").

doughter ("Olga", "Vasiliy").

deda (X, Y): - men (X), men (Y), sons (X, Y), doughter (Z, Y).

brother (X, Y): - men (X), men (Y), sons (X, Z), sons (Y, Z), X <> Y.

Результат: Olga, Vaciliy

Приклад 2.Написати програму, що створює список міст. Виконати програму з різними внутрішніми і зовнішніми цілями.

domains

town_list = town

town = symbol

divdicates

towns (town_list)

goal

towns ([A, B, C, D, E]),

write (A ,",", B ,",", C ,",", D ,",", E).

clauses

towns (["Kazan", "Nignekamsk", "Elabuga", "Bugulma", "Almetevsk"]).

Результат: Kazan, Nignekamsk, Elabuga, Bugulma, Almetevsk

Приклад 3. Hello, World! - Prolog:

Visual Prolog створює проекти автоматично . Для запуску прикладу слід створити новий проект, вибравши "Console" як UIStrategy, перейти до редагування файлу main.pro і замінити його вміст наведеними кодом.

implement main

open core

constants

class Name = "main".

Class Version = "".

clauses

clas sInfo Cclass Name, class Version).

clauses

run():-

console::init(),

stdio::write("Hello, World!"),

program Control::sleep(1000),

succeed(). end implement main

goal

mainExe::run(main::run)

 

Приклад 4. Відомо те, що Петро та Ольга навчаються у десятому класі, Хома та Леся – у 9 класі. Один учень знає іншого, якщо вони вчаться в одному класі. Вважається, що певний учень не може знати сам себе.

domains

учень = symbol

клас = integer

predicates

вчиться (учень, клас)

знає (учень, клас)

clauses

вчиться (хома, 9).

вчиться (петро, 10).

вчиться (ольга, 10).

вчиться (леся, 9).

знає (X, Y) :-

вчится( Х, Клас),

вчиться (Y, Клас),

X<>Y.4

Коментар: у програмі оголошуються предикати вчиться/2 і знає/2, аргументи учень типу «рядок символів» і клас типу «ціле число». Умова того, що учень Х навчається в одному і тому ж класі з учнем Y забезпечується однаковим іменем змінної у відповідних умовах правила.

    1. Розв’язування математичних задач

Наведемо приклади математичних задач, алгоритми розв’язання яких ви знаєте:

• додавання двох багатоцифрових чисел;

• ділення відрізка навпіл за допомогою циркуля і лінійки;

• розв'язування квадратного рівняння тощо.

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

  1. Числа Фібоначчі:

x Fibonacci.pl

:- dynamic(stored/1).

memo(Goal) ;-

stored(Goal) → true;

Goal, asserts(stored(Goal)).

fib(1,1) :- 1, write(‘1, ‘).

fib(2,1) :- 1, write(’1, ‘).

fib(N,F) :-

N1 is N-1, memo(fib(N1,F1)),

N2 is N-2, memo(fib(N2,F2)),

F is F1 + F2,

write(F), write(‘, ‘).

x interactive

[-fibonacci].

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