Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

Информатика->Задача
В настоящее время все более актуальными становятся задачи оптимизации, поиска, реализации распределенных и (или) параллельных систем. Многие из них ле...полностью>>
Информатика->Реферат
Как отмечалось, инфологическая модель отображает реальный мир в некоторые понятные человеку концепции, полностью независимые от параметров среды хране...полностью>>
Информатика->Реферат
Современные компьютерные мониторы делятся на две большие группы: CRT мониторы (от Cathode Ray Tube, электронно-лучевая трубка – самый обычный тип мони...полностью>>
Информатика->Реферат
Актуальность темы исследования состоит в том, что динамичность процессов, происходящих в переходной экономике, требует постоянного анализа информации ...полностью>>

Главная > Курсовая работа >Информатика

Сохрани ссылку в одной из сетей:

5. Рекурсия.

Существует огромное количество задач, в которых отношения между объектами можно определить, только используя сами определяемые соотношения. При этом получаются правила, называемые рекурсивными. Применение рекурсии для описания задач при работе с системами логического программирования широко распространенный прием. Рекурсия будет проиллюстрирована несколькими примерами построения программ, как вычислительных, так и логических. Первым примером будет пример вычисления наибольшего общего делителя (НОД) двух чисел. Предикат, который выполняется, если найден НОД двух данных чисел будет иметь имя нод и три аргумента: числа a,b и значение НОД - c. Для описания вычисления НОД используются следующие соображения. Во-первых, если, а=b, то c=a=b; Во-вторых, если, а>b, то необходимо вычислить НОД для чисел b и a-b; В-третьих, если b>a, то необходимо вычислить НОД для чисел a и b-a. Эти три утверждения естественным образом могут быть записаны на Прологе-Д.:

нод(а,а,а);

нод(а,b,c)<-БОЛЬШЕ(а,b),ВЫЧИТАНИЕ(a,b,d),нод(b,d,c);

нод(а,b,c)<-БОЛЬШЕ(b,а),ВЫЧИТАНИЕ(b,a,d),нод(a,d,c);

ВЫЧИТАНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(1,X,Z,Y);

Если к этой базе знаний задать вопрос:

?нод(10,15,x);

ответ системы Пролог-Д:

x=5 ДРУГИХ РЕШЕНИЙ НЕТ

Предикат нод, определенный выше оказывается обратимым. В качестве второго примера рассматривается задача о вычислении элементов последовательности: 0, 1, 1, 2, 3, 5, 8, 13, 21 ,34, 55, 89, 144,... , известной как последовательность Фибоначчи. Каждый элемент ее определяется следующими правилами:

f0 =0,

f1 =1,

fn =fn-1+fn-2, при n>1

Первая формула соответствует утверждению о том, что значение нулевого элемента последовательности равно нулю. Это можно записать в виде факта: Фиб(0,0);. Вторая строка соответствует утверждению: первый элемент равен 1. На Прологе-Д это можно записать так: Фиб(1,1);. Третья строка представляет собой запись рекурсивного соотношения:

Фиб(N,X)<-БОЛЬШЕ(N,1),ВЫЧИТАНИЕ(N,1,М),

ВЫЧИТАНИЕ(N,2,К), Фиб(М,Y), Фиб(K,Z),

СЛОЖЕНИЕ(Y,Z,X);

ВЫЧИТАНИЕ и СЛОЖЕНИЕ - имена предикатов вычитание и сложение, определяемых с помощью правил:

СЛОЖЕНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(1,X,Y,Z);

ВЫЧИТАНИЕ(X,Y,Z)<-УМНОЖЕНИЕ(1,X,Z,Y);.

Данные предложения представляют собой базу данных на языке Пролог-Д, позволяющую вычислять значения элементов последовательности. B ответ на вопрос:

?Фиб(10,X);

ответ системы Пролог-Д:

x=55 ДРУГИХ РЕШЕНИЙ НЕТ

Необходимо сказать, что такой путь решения данной задачи не самый лучший. Для нахождения N+1 числа Фибоначчи требуется 2* (N+1)-1 рекурсивное обращение. Однако этого можно избежать, если перейти к другой базе знаний, в которой предикат с именем "Фиб" определен как трехарный, то есть имеющий три аргумента, включающий в себя в качестве аргумента значения N-ого и N-1- ого элементов последовательности. Такая база знаний получается в результате перевода на язык Пролог-Д утверждений.

1. 0-ой элемент последовательности есть 0, а (-1) -ый элемент не определен. Фиб(0,x,0);.

Второй аргумент обозначен x. В данном случае значение x может быть любым.

2. 1-й элемент последовательности есть 1, а нулевой-0. Фиб(1,0,1);. 3. N -й член последовательности Фибоначчи определяется через (N-1) -Й член последовательности.

Фиб(N,F,f)<-БОЛЬШЕ(N,1),ВЫЧИТАНИЕ(N,1,M),Фиб (M,Ф,F), СЛОЖЕНИЕ (Ф, F, f);.

Обращение к этой базе знаний будет иметь вид:

?Фиб(10,F,f);.

ответ системы Пролог-Д:

F=55, f=34 ДРУГИХ РЕШЕНИЙ НЕТ

При работе с этой базой знаний для вычисления N - го числа Фибоначчи необходимо всего лишь N рекурсивных обращений. Для системы Пролог-Д характерна особенность, проявляющаяся при работе с рекурсивными программами. В общем случае, порядок предложений в базе знаний не имеет значения. Однако, в нижеследующем примере это не так

родитель(X)<- родитель(Y),отец(Y,Z);

родитель(Коля);

отец(Коля, Петя);

родитель(Петя);

В первом предложении голова имеет то же имя, что и одна из целей - "родитель". В процессе поиска ответа в этой базе знаний будет применено правило: предложение, стоящее первым, будет и применено первым - известное как принцип поиска в глубину. Это приведет к тому, что система будет обращаться только к первому предложению базы знаний и ответ на вопрос ?родитель(Петя); не будет найден никогда. Вместе с тем, небольшое изменение базы знаний, перестановка двух предложений местами, приводит к удачному поиску решения:

родитель(Коля);

родитель(X)<-родитель(Y), отец(Y,X);

отец(Коля, Петя);

?родитель(Петя);.

Неограниченно-повторное обращение к предложению может быть и более замаскированным так, как это получается в примере:

ВЫШЕ(А,В)<-НИЖЕ(В,А);

НИЖЕ(В,А)<-ВЫШЕ(А,В);

ВЫШЕ(Коля, Петя);

?НИЖЕ(Петя, Коля);.

Однако если третье предложение стоит на первом месте, то повторного обращения не произойдет и ответ будет найден. Такая ситуация называется петля. При вычислении элементов последовательности Фибоначчи, может появляться бесконечная петля при исполнении программы. В самом деле, если вопрос имеет вид:

?Фиб(0,x,y);,

то первый возможный результат x =_0, y =1. Далее в попытке отыскать следующее решение возникает бесконечная петля, так как будет отыскиваться Фиб(-1,x,y), Фиб(-2,...),... . Для контроля за подобной ситуацией необходима модификация базы знаний. Первые два предложения должны быть записаны в виде:

Фиб(0,x,1)<-!;

Фиб(1,1,1)<-!;,

тогда при поиске альтернативного решения после получения ответа на вопрос:

?Фиб(0,x,y); x=_0, y =1

будет получен результат:

ДРУГИХ РЕШЕНИЙ НЕТ.

Данный пример иллюстрирует первое возможное использование предиката "отсечение". И еще одно чисто эстетическое предложение. База знаний на Прологе-Д будет выглядеть лучше, если предложения с одинаковыми именами расположены в одном месте. Для сравнения приводится две базы знаний:

1. 2.

мама(Таня, Надя); мама(Таня, Надя);

бабушка(X,Y)<-мама(X,Z), мама(Надя, Катя);

мама(Z,Y), бабушка(X,Y)<-мама(X,Z),

мама(Надя, Катя); мама(Z,Y);.

6. Графические возможности системы Пролог-Д.

Когда речь идет о компьютерной графике, построение изображения на экране интерпретируется серией команд. Таким образом, всякое изображение ассоциируется с алгоритмом его построения. Однако, эта концепция не укладывается в принципы декларативного программирования, принятые в системе Пролог-Д. Если последовать этой концепции то необходимым становится описание элементов рисунка в виде совокупности графических объектов, соотношений и связей между ними. В этом случае описание последовательности действий художника - исполнителя становится излишним. В системе Пролог-Д определен набор графических примитивов, отображающих графические объекты и построенных таким образом, что с точки зрения синтаксиса каждый из них может быть только целью, и принимает значение "истина" (выполняется), если на экране появляется графическое изображение объекта. При записи в правиле нескольких графических примитивов и выполнении данного правила на экране появляется объединение графических образов в той последовательности, как они описаны в правиле. Во всех графических встроенных предикатах аргументами должны быть целыми или переменными, конкретизированными целыми, или не конкретизированными переменными. Если это требование не выполнено, то появится сообщение об ошибке. Параметр v - вертикальный размер, а h - горизонтальный размер экрана. Для стандартной платы видеоадаптера VGA v=349, h=639. В предикатах ТОЧКА, ЛИНИЯ, ОКРУЖНОСТЬ, ЗАКРАСКА последний параметр задает цвет. Как правило, если на этом месте стоит не конкретизированная переменная, то также выводится сообщение об ошибке. Для обозначения цвета при использовании видеоадаптера VGA принята кодировка цветов, изображенная в таблице 3.4.1. В системе Пролог-Д имеет место особенность использования встроенных предикатов, обусловленная спецификой графических средств системы IBM-PC. Для использования графики необходимо открыть графический файл с помощью предиката ЗАПИСЬ_В(“grp:”). После завершения работы необходимо открыть файл для вывода текста ЗАПИСЬ_В(“con:”).

0

черный

8

темно серый

1

синий

9

светло синий

2

зеленый

10

светло зеленый

3

голубой

11

светло голубой

4

коричневый

12

красный

5

фиолетовый

13

сиреневый

6

темно желтый

14

желтый

7

серый

15

белый

Таблица 1. Таблица кодирования цвета в системе Пролог-Д.

В системе Пролог-Д предусмотрены следующие встроенные графические предикаты:



Загрузить файл

Похожие страницы:

  1. Интеллектуальные информационные системы (2)

    Реферат >> Информатика
    ... можно представить этапами: «информационные системы» (ИС), «автоматизированные информационные системы» (АИС), «интеллектуальные информационные системы» (ИИС). Интеллектуальная информационная система - это компьютерная модель ...
  2. Интеллектуальные информационные системы (3)

    Реферат >> Информатика
    ... имеют дело. Перечисленные недостатки устраняются в интеллектуальных информационных системах (ИИС). Анализ структуры программы показывает ...
  3. Интеллектуальные информационные системы (4)

    Курсовая работа >> Информатика
    ... Курсовая работа по дисциплине: Информационные системы по теме: Интеллектуальные информационные системы Выполнил: студент 4 курса ... статистика», 2001. – 368 с. Луценко, Е.В. Интеллектуальные информационные системы/ Е.В. Луценко, Краснодар: КубГАУ, 2006. – 615 ...
  4. Интеллектуальные информационные системы в профессиональной деятельности

    Лекция >> Информатика, программирование
    ЛЕКЦИЯ Интеллектуальные информационные системы в профессиональной деятельности Учебные и воспитательные цели: 1. Ознакомить курсантов с понятием и классификацией интеллектуальных информационных систем ...
  5. Разработка алгоритма работы и реализация интеллектуальной информационной системы

    Курсовая работа >> Информатика
    ... «Интеллектуальные информационные системы» Тема: «Разработка алгоритма работы и реализация интеллектуальной информационной системы» ... различные дополнения, повышающие значимость интеллектуальной информационной системы как в информативном (наглядном) ...

Хочу больше похожих работ...

Generated in 0.0072009563446045