Логическое программирование. Программирование в Psharp

Содержание

 

 

1.Введение……………………………………………………………………..2

2.Основы логистического  программирования………………………………3

3.Программирование в ограничениях………………………………………..4

4.Удовлетворение в ограничениях…………………………………………...6

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

Программирование в ограничениях (или программирование ограничениями) является парадигмой программирования, в которой отношения между переменными указаны в форме ограничений. Ограничения отличаются от общих примитивов языков императивного программирования тем, что они определяют не последовательность шагов для исполнения, а свойства искомого решения. Это делает программирование в ограничениях формой декларативного программирования. Ограничения, которые используются в программировании в ограничениях, бывают различных видов: те, которые используются в задачах удовлетворения ограничений (например, «А или В истинно»), те, которые решаются симплекс-алгоритмом (например, «x ≤ 5») и другие. Ограничения, как правило, встроены в язык программирования или осуществляются через отдельные программные библиотеки.

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

Программирование в ограничениях началась с логического программирования с ограничениями (ЛПО), которое является вкладыванием ограничений в логическое программирование. Появление этого варианта логического программирования связано с именами Jaffar и Lassez, которые расширили в 1987 году определенный класс ограничений, которые были введены в Prolog II. Первыми реализациями логического программирование в ограничениях были Пролог III, CLP (R) и CHIP. Некоторые интерпретаторы логического программирования в ограничениях существуют и сегодня, например GNU Prolog.

Помимо логического программирования, ограничения могут быть смешаны с функциональным программированием, переписыванием и императивным языком. Языки программирования с встроенной поддержкой ограничений включаютOz (функциональное программирование) и Kaleidoscope (императивное программирование). Главным образом, ограничения осуществляются в императивных языках через инструментальные средства для решения задач с ограничениями, которые являются отдельными библиотеками для существующих императивных языков.

 

 

 

ОСНОВЫ ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

 

Логическое программирование — парадигма программирования, основанная на автоматическом доказательстве теорем, а также раздел дискретной математики, изучающий принципы логического вывода информации на основе заданных фактов и правил вывода. Логическое программирование основано на теории и аппарате математической логики с использованием математических принципов резолюций.

Самым известным языком логического программирования является Prolog.

Парадигма программирования — это совокупность идей и понятий, определяющих стиль написания компьютерных программ. Это способ концептуализации, определяющий организацию вычислений и структурирование работы, выполняемой компьютером.

Важно отметить, что парадигма программирования не определяется однозначно языком программирования; практически все современные языки программирования в той или иной мере допускают использование различных парадигм (мультипарадигмальное программирование).

Пролог (фр. Programmation en Logique) — язык и система логического программирования, основанные на языке предикатов математической логики дизъюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка.

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

Факты в языке Пролог описываются логическими предикатами с конкретными значениями. Правила в Прологе записываются в форме правил логического вывода с логическими заключениями и списком логических условий.

Особую роль в интерпретаторе Пролога играют конкретные запросы к базам знаний, на которые система логического программирования генерирует ответы «истина» и «ложь». Для обобщённых запросов с переменными в качестве аргументов созданная система Пролог выводит конкретные данные в подтверждение истинности обобщённых сведений и правил вывода.

Факты в базах знаний на языке Пролог представляют конкретные сведения (знания). Обобщённые сведения и знания в языке Пролог задаются правилами логического вывода (определениями) и наборами таких правил вывода (определений) над конкретными фактами и обобщёнными сведениями.

 

 

ПРОГРАММИРОВАНИЕ В ОГРАНИЧЕНИЯХ.

 

Программирование в ограничениях (constraint programming)- достаточно новое направление в декларативном программировании. Появилось оно во многом в результате развития систем символьных вычислений, искусственного интеллекта и исследования операций.

Программирование в ограничениях - это программирование в терминах "постановок задач".

Постановка задачи - это конечный набор переменных V = {v[1], ..., v[n]}, соответствующих им конечных (перечислимых) множеств значений D = {D[1], ...,D[n]}, и набор ограничений С = {C[1],...,C[m]}. Ограничения представлены как утверждения, в которые входят в качестве "параметров" переменные из некоторого подмножества V[j],j=1..m набора V. Решение такой задачи - набор значений переменных, удовлетворяющий всем ограничениям C[j].

Синтаксически такую постановку задачи можно записать как "правило" для "типизированного" Пролога:

problem(V1:D1, ..., Vn:Dn) :-  
    С1, ... Cm.

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

В качестве примера, мы можем задать системе программирования в ограничениях следующий запрос:

? (X : integer) X>1, member(X, [1,2,3]).

Типичная Пролог-система на таком запросе выдаст ошибку: Х является неинициализированной переменной, и его нельзя сравнивать с числом 1. Система, поддерживающая программирование в ограничениях, воспримет эти "утверждения" как ограничения (а не как цели, которые требуется доказать), и выдаст нам требуемые решения: Х=2 и Х=3.Это может быть реализовано, например, следующим образом: при "прологовом" доказательстве утверждения Х>1 будет выведено ограничение на переменную Х (естественно, Х>1). Результаты доказательства следующей подцели (member(...)) будут проверяться на удовлетворение этому ограничению (фактически, будет пере доказываться утверждение X>1 для конкретных значений Х). Первый вариант (Х=1) не пройдет эту проверку, остальные будут приняты как удовлетворяющие выведенному ограничению.Задачу в ограничениях можно рассматривать и как задачу о минимальном необходимом наборе ограничений, что позволяет в некоторых случаях описать в явном виде бесконечные множества решений. Так, минимальным необходимым набором ограничений для задачи X:integer, X>2, X<4 будет Х=3; для задачи X,Y:integer, X*2=Y таким набором будет X:integer, Y mod 2 = 0.Системы символьных вычислений нередко позволяют использовать "допущения" - по сути, те же ограничения. И на следующий (простой) запрос:

assume X>0. 
when X+1<10 ?

выдавать ответ:

X in (0..9).

Как правило, такие системы могут доказывать достаточно нетривиальные математические утверждения, выводя "минимальными необходимыми ограничениями", и проверяя эти ограничения на совместность.В задачах исследования операций и реализации искусственного интеллекта часто используется некоторое "пространство решений", сужением которого достигается необходимый результат. Такие "сужения" естественным образом представляются как ограничения.Кроме этого, программирование в ограничениях естественным образом приложимо к задаче автоматического вывода типов: выведенные ограничения на переменные, соответствующие типам подвыражений, будут задавать "минимальный набор требований на типы". Так, удовлетворение ограничения type_correct("lambda x -> x+1") потребует выполнения набора ограничений{number(x.type_of)}, что, буквально, обозначает, что для того, чтобы прибавить к х единицу, х должно быть числом.

Как и логическое программирование, программирование в ограничениях предполагает совершенно аналогичную "естественную" реализацию на параллельных платформах.

 

УДОВЛЕТВОРЕНИЕ В ОГРАНИЧЕНИЯХ.

Одной из важных задач искусственного интеллекта (ИИ) является задача удовлетворения ограничений (УО) (constraint satisfaction problem). Теория УО предлагает удобный аппарат и простую формальную схему для представления и решения комбинаторных задач ИИ.

Целью решения задачи УО является нахождение значений переменных, удовлетворяющих заданным ограничениям.

Проблема существования решений задачи УО является NP-полной.

Тесно связано с теорией УО программирование в ограничениях, которое является парадигмой программирования для декларативного описания и эффективного решения комбинаторных задач. Многие классические комбинаторные задачи, такие как известная теорема Ферма, задача выполнимости (SAT) из пропозициональной логики, задача раскраски графа и задача изоморфизма графов из теории графов могут формулироваться в виде задач УО (ЗУО). Остановимся подробнее на одной из давно поставленных задач в математике - задаче о раскраске графа, частным случаем которой является известная задача о раскраске карты. Формулировка задачи о раскраске в виде задачи УО ставит в соответствие вершинам раскрашиваемого графа переменные, возможные цвета представляют собой домены (области определения) переменных, а ограничения-неравенства между смежными вершинами являются ограничениями задачи.

 

 

РЕШЕНИЕ ПОСТАВЛЕННОЙ ЗАДАЧИ

 

Задание:

На одной улице стоят 4 дома. В каждом из них живет один из 4-х людей: Семен, Николай, Артур и Роман. Каждый из них владеет профессией: Врач, Художник, Егерь, Тренер. Определить, кто в каком доме живет, и кто какой профессией владеет. Известно, что:

• Художник живет рядом с тренером
• Врач живет рядом с Художником
• Егерь левее врача
• Тренер не рядом с Егерем
• Художник правее Семена
• Роман не тренер
• Семен рядом с Николаем
• Артур не рядом с Романом

 

Вид главного окна:

 

 

 

 

 

Исходный код программы

houses([house(1, _, _ ),house(2, _, _ ),house(3, _, _ ),house(4, _,_ )]).

 

left_of(A, B, [A, B | _]).

left_of(A, B, [_ | Y]) :- left_of(A, B, Y).

right_of(A, B, [B, A | _]).

right_of(A, B, [_ | Y]) :- right_of(A, B, Y).

next_to(A, B, [A, B | _]).

next_to(A, B, [B, A | _]).

next_to(A, B, [_ | Y]) :- next_to(A, B, Y).

member(X, [X|_]).

member(X, [_|Y]) :- member(X, Y).

ne_in(_,[]).

ne_in(X,[X|_]):-!,fail.

ne_in(X,[_|A]):-ne_in(X,A).

ne_trener(H):-member(house(_,roman,oxotnic),H).

ne_trener(H):-member(house(_,roman,doctor),H).

ne_trener(H):-member(house(_,roman,paint),H).

ne_trener(H):-member(house(_,roman,trener),H),!,fail.

print_houses([]).

print_houses([A|B]) :-

write(A),

print_houses(B).

false(X):-X,!,fail.

false(_).

solve(H):-houses(H),

next_to(house(_,_,paint),

house(_,_,trener),H),

next_to(house(_,_,doctor),

house(_,_,paint),H),

%  Егерь живет левее Врача

left_of(house(_,_,oxotnic),

house(_,_,doctor),H),

false(next_to(house(_,_,trener),

house(_,_,hunter),H)),

right_of(house(_,_,paint),

house(_,semen,_),H),

next_to(house(_,semen,_),

house(_,nikolay,_),H),

false(next_to(house(_,artur,_),

house(_,roman,_),H

)),

ne_trener(H),

member(house(_,roman,_), H),

member(house(_,artur,_), H),

member(house(_,semen,_), H),

member(house(_,nikolay,_), H),

print_houses(H).

:-solve(_).

 

ВЫВОД

 

В результате выполнения данной курсовой работы:

• Был изучен язык логического программирования «Пролог»;
• Была создана работающая программа на языке программирования «Пролог».