Лаб. работа “Логическое программирование”

Разработка и оптимизация интеллектуальных информационных систем
Логическое программирование
Практика
Автор

Бирюк Андрей

Дата публикации

1 апреля 2025 г.

Задание №1: Введение в логическое программирование

Цель: Ознакомиться с основами логического программирования, средой разработки SWI-Prolog (SWI), основными операторами и принципами работы.

Теоретические сведения

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

Методические указания

  1. Установите SWI-Prolog с официального сайта SWI-Prolog и убедитесь, что среда разработки работает корректно.

  2. Ознакомьтесь с основными командами консоли SWI-Prolog:

    • consult('файл.pl'). — загрузка программы
    • listing. — просмотр загруженных предикатов
    • trace. — включение пошаговой отладки
    • halt. — завершение работы интерпретатора

  3. Изучите формат записи фактов и правил. Например, определение семейных отношений:

    родитель(иван, мария).
родитель(мария, андрей).
предок(X, Y) :- родитель(X, Y).
предок(X, Y) :- родитель(X, Z), предок(Z, Y).

  4. Попробуйте выполнять простые запросы, например:

    ?- родитель(иван, мария).
?- предок(иван, андрей).

  5. Используйте отладку (trace.) для анализа работы программы.

Задания

  1. Установить SWI-Prolog и настроить среду.
  2. Определить простые факты и правила для предметной области «Семья» (родители, дети, братья, сестры).
  3. Реализовать простые запросы на выборку информации (например, “Кто является родителем Васи?”).
  4. Написать правила для определения предков и потомков.

Задание №2: Операции с фактами и правилами

Цель: Научиться работать с фактами, правилами и предикатами, применять логические выражения в Prolog.

Теоретические сведения

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

Задания

  1. Определить базу знаний для предметной области «Студенты и курсы» (студент, курс, оценки).
  2. Написать правила для определения успешности студентов.
  3. Реализовать предикат, проверяющий, сдал ли студент определенный курс.
  4. Написать запросы для получения списка студентов, сдавших конкретный курс.

Дополненная теоретическая информация для выполнения задания №2

2.1. Факты в Prolog

Определение: Факты — это базовые утверждения, описывающие статические знания. Они состоят из предиката и его аргументов.
Синтаксис:

предикат(аргумент1, аргумент2, ..., аргументN).

Пример для предметной области “Студенты и курсы”:

student(anna, math, [4,5,4]).   % Анна изучает математику с оценками [4,5,4]
course(math, 2023).             % Курс математики проводится в 2023 году

Важно:

  • Аргументы могут быть атомами, числами, строками или списками.
  • Каждый факт заканчивается точкой.
  • Регистр имеет значение: math и Math — разные атомы.

2.2. Правила в Prolog

Определение: Правила позволяют выводить новые знания на основе фактов и других правил. Они состоят из головы и тела, разделенных символом :-.
Синтаксис:

голова :- тело.

Пример правила для успешности студента:

% Студент успешен, если все его оценки >= 4
successful(Student, Course) :-
    student(Student, Course, Grades),
    forall(member(Grade, Grades), Grade >= 4).

Объяснение:

  • successful(Student, Course) — голова правила.
  • student(Student, Course, Grades) — извлечение оценок студента.
  • forall(member(Grade, Grades), Grade >= 4) — проверка, что все оценки ≥ 4.

2.3. Предикаты и логические выражения

Предикат — это именованная логическая функция, возвращающая true или false.
Логические операторы:

  • , — логическое И (конъюнкция).
  • ; — логическое ИЛИ (дизъюнкция).
  • not или \+ — отрицание.

Пример предиката для проверки сдачи курса:

% Студент сдал курс, если средний балл >= 3.5
passed(Student, Course) :-
    student(Student, Course, Grades),
    sum_list(Grades, Sum),
    length(Grades, N),
    Average is Sum / N,
    Average >= 3.5.

Разбор:

  • sum_list/2 и length/2 — встроенные предикаты для работы со списками.
  • is — оператор вычисления арифметических выражений.

2.4. Запросы к базе знаний

Запросы — это вопросы к базе знаний, которые проверяют истинность утверждений.
Пример запроса для списка студентов, сдавших курс математики:

?- student(Name, math, _), passed(Name, math).

Объяснение:

  • Переменная Name автоматически связывается с именами студентов.
  • Символ _ означает анонимную переменную (значение не важно).
  • Запрос вернет всех студентов, для которых выполнится passed(Name, math).

Использование findall для сбора результатов:

% Получить список всех сдавших математику
?- findall(Name, (student(Name, math, _), passed(Name, math)), Students).

2.5. Советы по реализации

  1. Структура базы знаний:

    • Разместите факты в начале файла, затем правила.
    • Используйте списки для хранения оценок: [4,5,3].

  2. Типичные ошибки:

    • Забытая точка в конце факта/правила.
    • Несовпадение числа аргументов в предикатах.

  3. Отладка:

    • Используйте trace. для пошагового выполнения.
    • Проверяйте типы данных: например, [4,5,3] — список, а 4 — число.

Пример полной программы:

% Факты
student(anna, math, [4,5,4]).
student(bob, math, [3,4,5]).
course(math, 2023).

% Правило для проверки успешности
successful(Student, Course) :-
    student(Student, Course, Grades),
    forall(member(Grade, Grades), Grade >= 4).

% Предикат для проверки сдачи курса
passed(Student, Course) :-
    student(Student, Course, Grades),
    sum_list(Grades, Sum),
    length(Grades, N),
    Average is Sum / N,
    Average >= 3.5.

% Запрос: Найти всех, кто сдал математику
% ?- findall(Name, (student(Name, math, _), passed(Name, math)), Students).

Результат выполнения запроса:

Students = [anna, bob].

Самостоятельные задания для закрепления материала

Задание 2.1: Расширение базы знаний

Цель: Научиться структурировать данные и добавлять факты.
Описание:

  1. Добавьте в базу знаний 5 новых студентов с разными курсами и оценками.
  2. Создайте факты для 3 дополнительных курсов (например, physics, history, programming).
  3. Включите информацию о годе обучения для каждого студента (например, year(anna, 2)).

Пример:

student(oleg, physics, [5,5,4]).
course(physics, 2023).
year(oleg, 3).

Задание 2.2: Правила с условиями

Цель: Написать правила с использованием логических операторов.
Задачи:

  1. Создайте правило can_graduate(Student), которое возвращает true, если студент сдал все свои курсы.
  2. Определите предикат has_scholarship(Student), который проверяет, что у студента средний балл ≥ 4.5.
  3. Реализуйте правило retake(Student, Course), которое возвращает true, если студент имеет хотя бы одну оценку < 3 по курсу.

Подсказка:

  • Используйте встроенные предикаты findall, sum_list, length.

  • Пример для has_scholarship:

    has_scholarship(Student) :-
    findall(Grade, (student(Student, Course, Grades), member(Grade, Grades)), AllGrades),
    sum_list(AllGrades, Sum),
    length(AllGrades, N),
    Sum / N >= 4.5.

Задание 2.3: Работа со списками

Цель: Освоить обработку списков в Prolog.
Задачи:

  1. Напишите предикат best_student(Student), который находит студента с максимальным средним баллом.
  2. Создайте правило passed_all(Students), возвращающее список студентов, сдавших все курсы.
  3. Реализуйте предикат top_course(Course), который определяет курс с наивысшим средним баллом среди всех студентов.

Пример запроса:

?- best_student(X).  
X = anna.

Задание 2.4: Динамическое изменение базы знаний

Цель: Изучить модификацию фактов в runtime.
Задачи:

  1. Напишите правило add_grade(Student, Course, Grade), добавляющее оценку в список оценок студента.
  2. Создайте предикат remove_course(Student, Course), удаляющий курс из базы знаний.
  3. Реализуйте проверку на корректность оценок (например, оценка должна быть от 1 до 5).

Подсказка:

  • Используйте assertz, retract для изменения базы знаний.

  • Пример для add_grade:

    add_grade(Student, Course, Grade) :-
    Grade >= 1, Grade =< 5,  % Проверка корректности
    retract(student(Student, Course, Grades)),
    append(Grades, [Grade], NewGrades),
    assertz(student(Student, Course, NewGrades)).

Задание 2.5: Творческое задание

Цель: Применить знания для моделирования реальных сценариев.
Задачи:

  1. Добавьте предикат prerequisite(Course, RequiredCourse), который определяет обязательный курс для зачисления на другой (например, для курса ai требуется programming).
  2. Реализуйте правило can_enroll(Student, Course), проверяющее, может ли студент записаться на курс (есть ли у него необходимые знания).
  3. Создайте предикат recommend_course(Student, Course), который рекомендует курс на основе оценок студента (например, если студент хорошо знает математику, предложить physics).

Пример:

prerequisite(ai, programming).  
can_enroll(Student, ai) :-  
    passed(Student, programming).

Задание 2.6: Тестирование

Цель: Научиться проверять корректность правил.
Задачи:

  1. Напишите 3 тестовых запроса для предиката passed(Student, Course), которые проверяют:
    • Студент с оценками [5,5,5] сдал курс.
    • Студент с оценками [3,3,4] не сдал курс.
    • Студент с несуществующим курсом возвращает false.
  2. Проверьте правило successful на крайних случаях (например, пустой список оценок).

Пример теста:

?- passed(anna, math).  
true.

Задание 2.7: Оптимизация

Цель: Улучшить производительность запросов.
Задачи:

  1. Перепишите правило passed без использования forall, заменив его на рекурсию.
  2. Реализуйте кэширование результатов для предиката best_student, чтобы избежать повторных вычислений.

Подсказка:

  • Используйте мемоизацию через assertz.

Задание 2.8: Визуализация

Цель: Выводить результаты в удобном формате.
Задачи:

  1. Напишите правило print_students(Students), которое выводит список студентов в формате:

    Студент: Анна, Курс: math, Средний балл: 4.5

  2. Создайте предикат generate_report(Course), который сохраняет в файл список сдавших курс.

Пример:

?- generate_report(math), open('report.txt', read, F).

Бонусное задание: ИИ-ассистент

Цель: Реализовать простой диалог с пользователем.
Задачи:

  1. Напишите правило ask_about_student, которое запрашивает имя студента и выводит его средний балл.
  2. Реализуйте диалог, где пользователь может задавать вопросы вида:
    • «Кто сдал курс математики?»
    • «Какой курс самый популярный?»

Пример:

?- ask_about_student.  
Введите имя студента: anna.  
Анна: средний балл 4.8.

Задание №3: Рекурсия в Prolog

Цель: Освоить работу с рекурсией в логическом программировании.

Теоретические сведения

Рекурсия является основным механизмом итерации в Prolog. Предикаты могут вызывать сами себя, что позволяет реализовывать сложные вычисления без явного использования циклов.

Задания

  1. Реализовать предикат вычисления факториала числа.
  2. Написать предикат вычисления чисел Фибоначчи.
  3. Реализовать рекурсивный предикат для проверки, является ли список палиндромом.
  4. Написать предикат, находящий сумму элементов списка.

Дополненная теоретическая информация для задания №3

3.1. Основы рекурсии в Prolog

Рекурсия — это механизм, при котором предикат вызывает сам себя для решения подзадач. В Prolog рекурсия заменяет традиционные циклы и используется для:

  • Обработки списков.
  • Вычислений с накоплением (факториал, числа Фибоначчи).
  • Работы с древовидными структурами.

Структура рекурсивных правил:

  • Базовый случай — условие завершения рекурсии (например, факториал 0 равен 1).
  • Шаг рекурсии — вызов предиката с уменьшенной задачей (например, N-1 для факториала).

3.2. Примеры рекурсивных предикатов

3.2.1. Факториал числа

% Базовый случай: факториал 0 равен 1
factorial(0, 1).

% Рекурсивный случай: factorial(N, Result) = N * factorial(N-1, ...)
factorial(N, Result) :-
    N > 0,
    Prev is N - 1,
    factorial(Prev, R1),
    Result is N * R1.

Пояснение:

  • При N = 0 возвращается 1.
  • При N > 0 вычисляется факториал для N-1, затем умножается на N.

Пример запроса:

?- factorial(5, X).  
X = 120.

3.2.2. Числа Фибоначчи

% Базовые случаи: fib(0)=0, fib(1)=1
fib(0, 0).
fib(1, 1).

% Рекурсивный случай: fib(N) = fib(N-1) + fib(N-2)
fib(N, Result) :-
    N > 1,
    N1 is N - 1,
    N2 is N - 2,
    fib(N1, R1),
    fib(N2, R2),
    Result is R1 + R2.

Важно: Эта реализация неэффективна для N > 20. Для оптимизации используйте аккумуляторы или мемоизацию (см. советы ниже).

Пример запроса:

?- fib(10, X).  
X = 55.

3.2.3. Проверка списка на палиндром

% Базовые случаи:
% 1) Пустой список — палиндром.
% 2) Список из одного элемента — палиндром.
is_palindrome([]).
is_palindrome([_]).

% Рекурсивный случай: сравниваем первый и последний элементы
is_palindrome([H|T]) :-
    append(Middle, [H], T), % Отделяем последний элемент
    is_palindrome(Middle).

Пример запроса:

?- is_palindrome([1,2,3,2,1]).  
true.

3.2.4. Сумма элементов списка

% Базовый случай: сумма пустого списка = 0
sum_list([], 0).

% Рекурсивный случай: sum([H|T]) = H + sum(T)
sum_list([H|T], Sum) :-
    sum_list(T, TempSum),
    Sum is H + TempSum.

Пример запроса:

?- sum_list([1,2,3,4], X).  
X = 10.

3.3. Важные замечания

3.3.1. Условия остановки

  • Всегда определяйте базовый случай, иначе рекурсия станет бесконечной.
  • Проверяйте корректность входных данных (например, N >= 0 для факториала).

3.3.2. Порядок аргументов

  • Первый аргумент — входной, второй — выходной (например, factorial(N, Result)).
  • Используйте is для арифметических операций: Result is N * R1.

3.3.3. Хвостовая рекурсия

Для оптимизации (например, в сумме списка) используйте аккумулятор:

sum_list(List, Sum) :- sum_list(List, 0, Sum).

sum_list([], Acc, Acc).
sum_list([H|T], Acc, Sum) :-
    NewAcc is Acc + H,
    sum_list(T, NewAcc, Sum).

Это предотвращает переполнение стека.

3.4. Типичные ошибки

  1. Бесконечная рекурсия:

    factorial(N, Result) :- Result is N * factorial(N-1, _). % Ошибка: нет базового случая!

  2. Некорректные арифметические операции:

    Используйте is, а не =:

    Sum = H + TempSum. % Ошибка (нужно Sum is ...)

  3. Неверный порядок условий:

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

    factorial(N, Result) :-
    factorial(Prev, R1), % Ошибка: Prev не вычислен
    Prev is N - 1.

3.5. Советы по отладке

  • Используйте trace. для пошагового выполнения:

    ?- trace, factorial(3, X).

  • Проверяйте промежуточные значения:

    factorial(N, Result) :-
    write('Вычисляю факториал для '), writeln(N),
    ...

Самостоятельные задания к заданию №3

Задание 3.1: Рекурсия с аккумуляторами

Цель: Научиться оптимизировать рекурсию с использованием хвостового вызова.
Задачи:

  1. Перепишите предикат sum_list/2 (сумма элементов списка) с использованием аккумулятора.
  2. Реализуйте предикат factorial_tail/2 для вычисления факториала с хвостовой рекурсией.

Пример для factorial_tail:

factorial_tail(N, Result) :- factorial_tail(N, 1, Result).
factorial_tail(0, Acc, Acc).
factorial_tail(N, Acc, Result) :-
    N > 0,
    NewAcc is Acc * N,
    NewN is N - 1,
    factorial_tail(NewN, NewAcc, Result).

Задание 3.2: Обработка вложенных структур

Цель: Работать с рекурсивными структурами данных.
Задачи:

  1. Напишите предикат flatten/2, преобразующий вложенный список в плоский (например, [1, [2, [3]] → [1,2,3]).
  2. Реализуйте предикат nested_sum/2, вычисляющий сумму всех чисел во вложенном списке.

Пример запроса:

?- nested_sum([1, [2, [3, 4]], X).  
X = 10.

Задание 3.3: Генерация последовательностей

Цель: Использовать рекурсию для создания списков.
Задачи:

  1. Реализуйте предикат range/3, генерирующий список чисел от N до M (например, range(2, 5, [2,3,4,5]).
  2. Напишите предикат pow_sequence/3, создающий список степеней числа: pow_sequence(2, 3, [2,4,8]).

Подсказка:
Для range используйте рекурсию с аккумулятором:

range(N, M, List) :- N =< M, range(N, M, [], List).

Задание 3.4: Рекурсивная сортировка

Цель: Применить рекурсию для сортировки данных.
Задачи:

  1. Реализуйте алгоритм сортировки пузырьком для списка чисел.
  2. Напишите предикат quick_sort/2, использующий алгоритм быстрой сортировки.

Пример для быстрой сортировки:

quick_sort([], []).
quick_sort([H|T], Sorted) :-
    partition(T, H, Less, Greater),
    quick_sort(Less, SortedLess),
    quick_sort(Greater, SortedGreater),
    append(SortedLess, [H|SortedGreater], Sorted).

Задание 3.5: Обход графа

Цель: Использовать рекурсию для работы с графами.
Задачи:

  1. Определите предикат path/3, проверяющий существование пути между двумя узлами в графе.
  2. Реализуйте поиск в глубину (DFS) для обхода графа.

Пример графа:

edge(a, b).  
edge(b, c).  
edge(c, d).  
path(X, Y) :- edge(X, Y).  
path(X, Y) :- edge(X, Z), path(Z, Y).

Задание 3.6: Отладка рекурсии

Цель: Находить и исправлять ошибки в рекурсивных предикатах.
Задачи:

  1. Даны некорректные реализации fib/2 и is_palindrome/1. Найдите ошибки и исправьте их.

  2. Объясните, почему следующий код приводит к бесконечной рекурсии:

    factorial(N, Result) :- Result is N * factorial(N-1, _).

Задание 3.7: Творческие задачи

Цель: Применить рекурсию для нестандартных задач.
Задачи:

  1. Напишите предикат balanced_brackets/1, проверяющий баланс круглых скобок в строке (например, "(()())" — сбалансировано).
  2. Реализуйте генератор всех подмножеств списка (subsets/2).

Пример для subsets:

?- subsets([1,2], X).  
X = [[], [1], [2], [1,2]].

Задание 3.8: Оптимизация рекурсии

Цель: Сравнить эффективность разных подходов.
Задачи:

  1. Реализуйте вычисление чисел Фибоначчи с использованием мемоизации (кэширования результатов).
  2. Измерьте время выполнения обычной и хвостовой рекурсии для factorial(1000).

Подсказка:
Используйте assertz для сохранения промежуточных результатов:

:- dynamic fib_cache/2.  
fib(N, Result) :- fib_cache(N, Result), !.  
fib(N, Result) :- ...

Бонусное задание: Ханойские башни

Цель: Решить классическую задачу с использованием рекурсии.
Задача:
Напишите предикат hanoi/4, который выводит последовательность перемещений для решения головоломки «Ханойские башни» с N дисками.

Пример:

?- hanoi(3, a, b, c).  
Переместить диск с a на b  
Переместить диск с a на c  
...

Задание № 4: Работа со списками

Цель: Изучить методы работы со списками в Prolog.

Теоретические сведения

Списки являются одной из основных структур данных в Prolog. Они представляются в виде [H|T], где H — голова списка, а T — хвост (подсписок).

Задания

  1. Реализовать предикат для поиска элемента в списке.
  2. Написать предикат для вычисления длины списка.
  3. Реализовать предикат для обращения списка.
  4. Написать предикат удаления элемента из списка.

Задание №5: Деревья в Prolog

Цель: Научиться представлять и обрабатывать деревья в логическом программировании.

Теоретические сведения

Деревья в Prolog представляются рекурсивными структурами, например, в виде node(Левое_поддерево, Значение, Правое_поддерево). Деревья используются для представления и обработки иерархических данных.

Задания

  1. Определить структуру бинарного дерева в Prolog.
  2. Реализовать предикат обхода дерева в глубину.
  3. Написать предикат нахождения максимального элемента в бинарном дереве.
  4. Реализовать предикат поиска элемента в дереве.

Задание №6: Поисковые алгоритмы в Prolog

Цель: Изучить основные алгоритмы поиска в логическом программировании.

Теоретические сведения

В логическом программировании используются алгоритмы поиска в ширину и глубину для обработки графов. Prolog позволяет элегантно реализовывать эти алгоритмы благодаря механизму унификации и рекурсии.

Задания

  1. Реализовать алгоритм поиска в ширину для графа.
  2. Написать алгоритм поиска в глубину.
  3. Реализовать алгоритм нахождения кратчайшего пути в графе (например, на основе алгоритма Дейкстры).
  4. Проверить работу алгоритмов на тестовых данных.
Наверх