Экзаменационные билеты по Прологу (Билеты к экзамену)

Вопросы к экзамену Экзамен 16.06 15³⁰ 409³

1. Понятие предиката.

2. Понятие клаузы (утверждение).

3. Формальная система. Признаки ФС. Требования к ФС.

4. Исчисление высказываний (Булева алгебра).

5. Исчисление предикатов (1-го порядка).

6. Формальная арифметика. Системы 1^ого порядка.

7. Ограничения формализма. Логические парадоксы.

8. Метод Эрбрана. Метод автоматического доказательства теорем.

9. Алгоритм резолюции.

10. Алгоритм унификации. Понятие терма.

11. Декларативный принцип программирования. АЯП сверхвысокого уровня.

12. Задачи Гильберта формализации математики. Роль логики в формализации математики.

13. Законы дедуктивного мышления. Доказательство от противного.

14. Основные конструкции логической программы (Turbo Prolog, Visual Prolog).

15. Встроенные типы данных.

16. Факты и правила. Предикаты и переменные. Анонимная переменная.

17. Переход к клаузальной форме логики.

18. Структурированная информация на Прологе. Функторы и термы. (Различие между предикатными символами и функторами. л/б 2)

19. Рекурсивные динамические структуры данных. Альтернативные доменные структуры. (л/б 3)

20. Арифметика на Прологе

21. Рекурсивные вычисления.

22. Оптимизация рекурсивных вычислений (левая и правая рекурсия). Итерационные вычисления. Переменные - накопители.

23. Повторяющиеся вычисления и предикат fail. Интеративные циклы.

24. Обработка списков. Создание списков с помощью предиката findall.

25. Отсечение (предикат cut).

26. Предикат динамических БД (принцип самопрограммирования).

27. Т повые металогические предикаты. (л/б 4)

28. Встроенные вспомогательные предикаты и примеры прикладных программ.

Понятие предиката.

1. Понятие клаузы (утверждение).

2. Формальная система.

   1. Признаки ФС.

   2. Требования к ФС.

Непротиворечивость, полнота, разрешимость.

1. Исчисление высказываний (Булева алгебра).

Алфавит, аксиомы (не доказывается), теоремы (доказывается), формулы, правила вывода, леммы и т.п. в формальной логике не применяются. Разрешимость - любая формула может быть проверена с помощью таблицы истинности.

1. Исчисление предикатов (1-го порядка).

1-й – предикат не зависит от предиката. Отвечает всем 3.а, но не всем 3.б, т.к.она неразрешима (единым способом нельзя проверить правильность формулы).Сверх язык, силен универсальностью.

1. Формальная арифметика.

Неполна. Можно написать формулу, но никогда нельзя будет ее доказать (теорема Гёделя).

Система 1-го порядка. Это система исчисления предикатов + новые символы и аксиомы.

1. Ограничения формализма.

Парадоксы – признак ограничения формальных систем. Логические ошибки и уловки. Парадокс Критянина – мнимый (все критяне лжецы – значит, что есть некоторые правдивые). Это предложение ложно – реальный парадокс. Парадокс Рассела (Брадобрей) - реальный.

1. Метод Эрбрана. Метод автоматического доказательства теорем.

2 примера.

1. Алгоритм резолюции.

В основе Пролога. Показать как он действует по головам клауз и внутри клаузы. Внутри АР всегда стремится к пустой клаузе.

1. Алгоритм унификации. Терм.

Терм – структурированная единица, в общем виде это любой аргумент предиката. АГ нужен что бы работал АР. (унификации – сопоставления, в клаузе 2 переменные должны сопоставляться). Без АГ нельзя автоматизировать АР.

1. Декларативный принцип программирования.

Дает возможность создать АЯ сверхвысокого уровня. (Сверх – т.е. абстрагируется не только от оборудования, но и от программирования – к решению задачи)

1. Задачи Гильберта формализации математики. Роль логики в формализации математики.

Сформулировал Давид Г. в 1900 году.

1. Законы индуктивного мышления. Доказательство от противного.

1. Основные конструкции логической программы.

Turbo и Visual Prolog.

1. Встроенные типы данных.

Symbol, string, char, integer, real. Списки.

1. Факты и правила. Предикаты. Переменные.

Анонимная переменная.

1. Переход к клаузальной форме логики.

2. Структурированная информация на Прологе. Функторы и термы.

Свои типы данных. Различия - предикат всегда снаружи (кроме not, asset и т.п.), функтор всегда внутри (в скобках).

1. Рекурсивные динамические структуры данных. Альтернативные доменные структуры.

Списки, деревья, встроенные, но можно создавать собственные.

1. Арифметика на Прологе

Правильнее Алгебра. + - / * div mod, trunc, round, sin, cos, exp, log, tg. Предикаты сравнения ><=<>. I=I+1 – нельзя, переменные ничего не хранят. I1=I+1 – идет не присвоение, а подбор. В Прологе нет раздела объявления переменных.

1. Рекурсивные вычисления.

Однократные, многократные, вложенные.

1. Оптимизация рекурсивных вычислений. Итерация. Переменные накопители.

Левые -> правые рекурсии. Избавляемся от вложенных и многократных рекурсий.

1. Повторяющиеся вычисления и предикат fail.

Дает всегда ложь и заставляет искать дальше.

1. Обработка списков. Создание списков с помощью предиката findall.

2. Отсечение (предикат cut).

Красное и зеленое. Красное всегда изменяет результат, зеленое – ускоряет скорость. Примеры.

1. Предикат динамических (внутренних) БД.

Assert, retract, save, consult. ЛР8

1. Типовые металогические предикаты.

bound(var)-связанная, free(var)-свободная.

1. Встроенные вспомогательные предикаты. Примеры прикладных программ.