ФИЛП. Программа содержит описание проблемы в терминах фактов и логических формул, а решение проблемы система выполняет с помощью механизмов логического вывода. Концепция логического программирования. Механизмы Пролога

• Название: Программа содержит описание проблемы в терминах фактов и логических формул, а решение проблемы система выполняет с помощью механизмов логического вывода. Концепция логического программирования. Механизмы Пролога
• Дата: 24.03.2023
• Размер: 32.6 Kb.
• Имя файла: ФИЛП.docx
• Тип: Программа; #1012926

Концепция логического программирования. Механизмы Пролога.

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

1. 
   Концепция логического программирования. Механизмы Пролога.
   
   1. 
      Концепция логического программирования
      
      1. 
         Процедурные языки описывают процесс действий («как »что-лито делаем ),логическое программирование определяет («что» надо сделать),то есть в логическом программирование мы описываем известные нам факты и правила , а дальше задаем вопросы, все предикаты имеют два значения истина или лож.
         
   2. 
      Механизмы Пролога.
      
      1. 
         Автоматический перебора, можно собрать данные, удовлетворяющие некоторому свойству, из базы данных в список для последующей их обработки
         
      2. 
         отсечение
         
   3. 
      Механизмы Пролога.
      
      1. 
         Сопоставление образцов(Унификация).
         
      2. 
         Древовидное представление структур данных.
         
      3. 
         Автоматический возврат (при поиске решения)
         

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

3. 
   Пролог. Объекты (термы) и утверждения (предикаты).
   
   1. 
      Термы.
      
      1. 
         Простые
         
      2. 
         Сложные
         
   2. 
      Утверждения (предикаты)
      
      1. 
         Факт – безусловно истинное утверждение
         
         1. 
            <предикат>(объет1, ... , объектN) или родитель(иван, ольга).
            
      2. 
         Правило –условно истинное утверждение.
         
         1. 
            [A]:-[B].,А – заголовок , В – тело правила состоит из фактов и правил.
            
      3. 
         Вопрос – обращение к Пролог-программе определяющее достижимость цели
         

4. 
   Объекты Пролога: простые и сложные термы. Переменные и константы.
   
   1. 
      Термы .
      
      1. 
         Простые термы .
         
         1. 
            Констнты.
            
            1. 
               Атомы(со строчной буквы или в кавычках) .
               
               1. 
                  Char( отдельный символ в апострофах).
                  
               2. 
                  Symbol.
                  
               3. 
                  String.
                  
            2. 
               Числа.
               
               1. 
                  Integer.
                  
               2. 
                  Real.
                  
         2. 
            Переменные (с прописной буквы или подчеркиванием)
            
      2. 
         Сложные термы
         
         1. 
            Структуры.
            
            1. 
               Описание структуры T = S(X1,X2,... ,XN)
               
         2. 
            Перечислимые термы.
            
            1. 
               пример: sp = integer*
               
         3. 
            Списки
            

5. 
   Общая структура программы на Прологе. Описание сложных термов.
   
   1. 
      Общая структура программы на Прологе
      
      1. 
         [inclide «файл, добавляемый к модулю»]
         
      2. 
         [global domains]
         
      3. 
         [Domains]<описание сложных термов>
         
      4. 
         [global predicates]
         
      5. 
         Predicates<описание предикатов>
         
      6. 
         Clauses<набор правил и фактов>
         
      7. 
         Goal <цель – задаваемый вопрос>
         
   2. 
      Описание сложных термов.
      
      1. 
         Перечислимые термы
         
         1. 
            T=k1;k3;...;kN
            
            1. 
               T – имя типа
               
            2. 
               Ki –одно из возможных значений(атом,)
               
      2. 
         Списки
         
         1. 
            T=<тип элементов списка>
            

6. 
   Правила построения предикатов (факты, предложения, процедуры).
   
   1. 
      факты
      
      1. 
         Факт – безусловно истинное утверждение.
         
         1. 
            <предикат>(объкт1,...,объктN) – родитель (иван,ольга)
            
   2. 
      Предложение
      
      1. 
         Предложение набор фактов заканчиваются точкой
         
         1. 
            p (X):-q(X),s(X),r(X).
            
   3. 
      Процедуры
      
      1. 
         Процедуры – Набор правил с одним именем предиката, сгруппированных в одном месте .
         
         1. 
            p(X):-q(X),s(X),r(X). p(X):-r(X).
            

7. 
   Унификация термов.
   
   1. 
      Унификация (сопоставимы)
      
      1. 
         Два терма унифицируемы(сопоставимы), если:
         
         1. 
            Термы абсолютно одинаковы (константы);
            
         2. 
            1-й терм – переменная , 2-й – любой атом;
            
         3. 
            У них одни и те же функтор(заголовок) и арность(количество аргументов) и все их аргументы сопоставимы (структуры).
            
      2. 
         Если в предложение есть Y=2 проверяется
         

8. 
   Поиск решения. Понятие резольвенты. Завершение поиска.
   
   1. 
      Поиск решения
      
      1. 
         формируется резольвента;
         
      2. 
         выбирается очередная цель из резольвенты;
         
      3. 
         ищется предложение в программе, чей заголовок унифицируется с целью;
         
      4. 
         цель заменяется на тело выбранного предложения; если тела нет (цель – факт), резольвента укорачивается;
         
      5. 
         поиск продолжается с новой резольвентой, полученной из старой.
         
   2. 
      Резольвента – множество целей, которые необходимо выполнить.
      
   3. 
      Завершение поиска
      
      1. 
         резольвента пуста – решение найдено;
         
      2. 
         все предложения просмотрены – решение не найдено.
         

9. 
   Рекурсия и итерации. Отложенные вычисления.
   
   1. 
      Рекурсия
      
      1. 
         Формирование на подъеме
         
      2. 
         Формирование на спуске
         
   2. 
      итерации
      
      1. 
         итерации отсутствуют отложные вычисления
         
   3. 
      Отложенные вычисления
      
      1. 
         Формируется при возврат на верх
         
10. 
    Отсечение. Правило применения. Примеры.
    
    1. 
       Отсечение - Механизм, позволяющий отбросить ненужные решения.
       
    2. 
       Правило применения
       
       1. 
          Фиксируется предложение где есть предикат;
          
       2. 
          После отсечение есть только возвраты
          
       3. 
          Если до отсечение лож, то отсечение не отрабатывает
          
11. 
    Списки: представление списков, возможные операции над списками.
    
    1. 
       представление списков
       
       1. 
          Голова
          
       2. 
          Тело
          
    2. 
       возможные операции над списками
       
       1. 
          Member (X, L)
          
       2. 
          Member_n (X, Y, N)
          
       3. 
          Append (X, Y, Z)
          
       4. 
          Delete (X, Y, Z)
          
       5. 
          Reverse (X,Y)
          
       6. 
          Insert_N (X, N, Lold, Lnew)
          
       7. 
          permutation (X, Y)
          
       8. 
          del_double (X, Y)
          
12. 
    Работа со списками: предикаты APPEND, MEMBER.
    
    1. 
       member(X,L)
       
       1. 
          member(X,L).
          
       2. 
          member(X,[X|_])
          
       3. 
          Member(X|[_|T]):-member(X,T).
          
    2. 
       Append(X,Y,Z)
       
       1. 
          Append([],Y,Y).
          
       2. 
          Append([X|T],Y,[X|Z]):-append(T,Y,Z).
          
13. 
    Работа с базой фактов. Предикат FINDALL.
    
    1. 
       FINDALL (X, Y, L)
       
14. 
    Встроенные предикаты: ввод/вывод, преобразование типов, работа со строками.
    
    1. 
       ввод/вывод
       
       1. 
          вывод
          
          1. 
             write
             
       2. 
          ввода
          
          1. 
             readln
             
          2. 
             readreal
             
          3. 
             readint
             
15. 
    Работа с динамической базой фактов. Хранение фактов в файле.
    
    1. 
       Работа с динамической базой фактов
       
       1. 
          Объявление facts mysik(string,string,integer,integer)
          
       2. 
          retract() удаление первого элемента
          
       3. 
          retractall() удаление всех элементов
          
       4. 
          assert() в конец БД
          
       5. 
          assertz() в конец БД
          
       6. 
          asserta()в начало БД
          
       7. 
          Save()
          
16. 
    Технологии программирования: метод «образовать и проверить»,циклы и повторения
    
    1. 
       метод «образовать и проверить»
       
       1. 
          find (X) :- generate (X), test (X).
          
       2. 
          generate (X) – генерация множества предполагаемых решений задачи
          
       3. 
          test (X) – проверка предполагаемого решения
          
    2. 
       циклы и повторения
       
       1. 
          
          
17. 
    Графы: возможные способы представления.
    
    1. 
       Список смежностей: G=[ [a, b, c], [b, d], [c, d, b], …]
       
    2. 
       База предикатов смежностей: edge (a, [b, c]). edge (b, [d]).
       
    3. 
       База предикатов ребер: edge (a, b). edge (a, c). edge (b, d).
       
18. 
    Бинарные деревья.
    
    1. 
       К бинарным деревьям относится класс деревьев, где каждый предок имеет не более двух потомков. Каждый переход дерева – самостоятельное дерево, именно поэтому структура рекурсивна.
       
    2. 
       Бинарное дерево либо пусто, либо состоит из левого поддерева, корня и правого поддерева.
       
    3. 
       Корень может принимать любые значения. Левое и правое поддеревья являются бинарными деревьями.
       
    4. 
       Прохождение бинарного дерева
       
       1. 
          Прямой порядок
          
          1. 
             Корень дерева
             
          2. 
             Левое поддерево в прямом порядке
             
          3. 
             Правое поддерево в прямом порядке
             
       2. 
          Обратный порядок
          
          1. 
             Левое поддерево в обратном порядке
             
          2. 
              Правое поддерево в обратном порядке
             
          3. 
             Корень
             
       3. 
          Внутренный порядок
          
          1. 
              Левое поддерево во внутреннем порядке
             
          2. 
             Корень
             
          3. 
              Правое поддерево во внутреннем порядке.
             
19. 
    Сортировки.
    
    1. 
       Сортировка списка – переупорядочение эл-ов списка в такую последовательность,когда все элементы списка расположены в порядке не возрастания или не убывания
       
    2. 
       Виды сортировки
       
       1. 
          Быстрая сортировка
          
          1. 
             Быстрая сортировка-исходнные списк разбивается на голову и хвост,хвост разбивается на 2 спискаЭ в первый список помещаются элементы меньшие, чем голова, во второй остальные;оба списка сортируются , затем упорядоченные списки сливаются вместе.
             
       2. 
          Быстрая сортировка без предиката append
          
          1. 
             Быстрая сортировка без предиката append, но с сромежуточный sort1(),кот-ый работает с промежуточным списком Q
             
       3. 
          Простоя сортировка со вставками.
          
          1. 
             Простоя сортировка со вставками.-Нупорядочные непустой список разбивается на голову и хвост, упорядочивается хвост,и далее голова вставляется в упорядоченный хвост так , чтобы получившийся список остался упорядоченным.
             
       4. 
          Пузырьковая сортировка
          
          1. 
             Пузырьковая сортировка-перестановка местами 2х эл-ов наход-ся в списке в неупорядоченом состоянии и повторение этого процесса до тех пор, пока перестановки станут ненужными
             
20. 
    Грамматики: виды грамматик, реализация грамматик на Прологе.
    
    1. 
       Грамматики – это формальная система, определяющая язык.
       
       1. 
          Пример: G =
          
          1. 
             N – множество нетерминальных символов(вспомогательные символы при порождении языка)
             
          2. 
             T - множество терминальных символов (алфавит языка)
             
          3. 
             P – множество правил вывода вида a -> b (описывают процесс порождения цепочек языка)
             
          4. 
             S – начальный или исходный символ S ∈ N Язык, определяемый грамматикой, – это множество цепочек, состоящих из терминальных символов и выводимых из одного выделенного начального символа
             
    2. 
       Виды грамматик
       
       1. 
          Регулярные грамматики
          
          1. 
             Множество правил вывода имеет вид A-> xB, A-. Bx, A->x, где A,B ∈ N, x ∈ T
             
       2. 
          Контекстно-свободные грамматики
          
          1. 
             множество правил вывода имеет вид A-> B где A ∈ (N U T)
             
       3. 
          Примечание: использовать право рекурсивные правила (Проверка с права на лева )
          
    3. 
       Алгоритм Prolog это и есть распознаватель грамматики
       
    4. 
       Пример
       

Множество цепочек из символов a, b, c, в цепочке обязательно присутствует ab.
S  -> M      P  -> a    P  -> cP

S  -> PM    P  -> b

S  -> MP    P  -> c

S  -> PMP  P  -> aP

M  -> ab     P  -> bP
m ( [a, b] ).

 p ( [a] ).

 p ( [b] ).

 p ( [c] ).

 p ( [a | X] ) :- p (X).

 p ( [b | X] ) :- p (X).

 p ( [c | X] ) : -p (X).

 s (X) :- m (X).

 s (X) :- append (A, B, X),  p (A),  m (B).

 s (X) :- append (A, B, X),  m (A),  p (B).

 s (X) :- append (A, B, X),  p(A), append (Q, W, B),  m(Q),  p(W).

goal

 s ( [a, c, b, c, c, a, b, a, c, b, c] ).

5. 
   Пример 2
   

S -> Z      Z -> 0    N -> 1

S -> N      Z -> 00    N -> 11

Z -> 0N     N -> 1Z

Z -> 00N   N -> 11Z
z([0]).

z([0,0]).

z([0|X]):-n(X).

z([0,0|X]):-n(X).

n([1]).

n([1,1]).

n([1|X]):-z(X).

n([1,1|X]):-z(X).

t(X):-z(X).

t(X):-n(X).

goal

t([1,0,0,1,0,1,1,1,0,1]).