Учебно-методический комплекс дисциплины специальность: 050202

Лабораторная работа №3

Рекурсия и поиск, составные объекты («ход конём» запоминая в БД)

Учебные материалы

1. 
   Адаменко А.Н., Кучуков А.М. Логическое программирование и Visual Prolog. – СПб.: БХВ-Петербург, 2003. – 992с.
   
   1. 
      Глава 12. Простые и составные объекты
      
   2. 
      Глава 13. Повтор и рекурсия
      
   3. 
      Глава 14. Списки и рекурсия
      
2. 
   Люгер Дж.Ф. Искусственный интеллект: стратегии и методы решения сложных проблем, 4-е издание.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 864с.
   
   1. 
      5.2.1. Пример рекурсивного поиска: вариант задачи хода конём
      

Задачи

11. 
    Вычисление факториала. Вычислить факториал числа, заданного в цели.
    

    Указание: Использовать двухместный предикат factorial(заданное_число, значение_факториала_от_заданного_числа), который истинен только при тех парах аргументов, у которых второй является факториалом от первого. Записать рекурсивное правило для предиката factorial, которое выражает истинность заголовка правила при аргументах N и F, если в теле будет истинен предикат factorial(X,Y) у которого X на единицу меньше, чем N, а Y=X! Условие окончания рекурсии выражает известный факт, что 1!=1 Изменять значение переменной в теле правила можно предикатом сравнения, например, X=N-1, F=N*Y

12. 
    Решить задачу «ход конём» на поле размером 3 на 3 клетки, не запоминая, посещённые конём ранее клетки. Использовать простую нумерацию клеток поля.
    

    Описание задачи «ход конём»: В одной из клеток шахматного поля находится шахматный конь. Найти, может ли конь из начальной клетки попасть в заданную клетку, и если да, то вывести путь (т.е. последовательность посещённых клеток), по которому конь может перейти из начальной клетки в заданную клетку. Для описания положения коня на поле можно использовать простую нумерацию (все клетки пронумерованы, т.е. каждой клетке соответствует целое число), или стандартную шахматную (каждая клетка имеет буквенно-циферную координату, например, е2, е4 и т.д.)

    Указания: Задача описывается в терминах «пространства состояний». Состояние – есть положение коня на поле, и выражается одним числом. Допустимые переходы между состояниями за один ход (т.е. правила «как ходит конь») описываются двухместным предикатом move(предыдущее_состояние, последующее_состояние), например, факт move(1,6) означает, что конь за один ход может перейти из клетки с номером 1 в клетку с номером 6. Возможность коня перейти за несколько ходов (возможно за 0 ходов) из одной клетки в другую описывается двухместным предикатом path(начальное_состояние, конечное_состояние). Например, если значение path(1,4) истинно, то конь может перейти из клетки с номером 1 в клетку с номером 4, а если ложно – то нет. Процедура, описывающая предикат path, должна состоять из рекурсивного правила: можно перейти из состояния X в состояние Y за несколько шагов (возможно за 0), если можно перейти из X за один шаг в некое такое промежуточное состояние Z, что из него можно за несколько шагов (возможно за 0) перейти в состояние Y. Условие окончания рекурсии – истинность path для случая 0 шагов. Вопрос о том, может ли конь перейти из клетки с номером 1 в клетку с номером 4 формулируется как цель: path(1,4).

    1. 
       Поместить в базе данных 16 фактов на основе предиката move
       
    2. 
       Поместить в базе данных 8 фактов на основе предиката move, и правило move(X,Y):-move(Y,X)
       
13. 
    Решить задачу «ход конём» на поле размером 3 на 3 клетки, запоминая, посещённые конём ранее клетки. Запоминать, добавляя в базу данных факта о том, что эта клетка уже посещена. Использовать простую нумерацию клеток поля.
    

14. 
    Решить задачу «ход конём» на поле размером 3 на 3 клетки, запоминая, посещённые конём ранее клетки. Запоминать, добавляя в базу данных факты о том, что эта клетка уже посещена. Использовать шахматную нумерацию клеток поля.
    

Лабораторная работа №4

Рекурсия и поиск, составные объекты («ход конём» запоминая в списке)

Учебные материалы

3. 
   Адаменко А.Н., Кучуков А.М. Логическое программирование и Visual Prolog. – СПб.: БХВ-Петербург, 2003. – 992с.
   
   1. 
      Глава 12. Простые и составные объекты
      
   2. 
      Глава 13. Повтор и рекурсия
      
   3. 
      Глава 14. Списки и рекурсия
      
4. 
   Люгер Дж.Ф. Искусственный интеллект: стратегии и методы решения сложных проблем, 4-е издание.: Пер. с англ. – М.: Издательский дом «Вильямс», 2003. – 864с.
   
   1. 
      5.2.1. Пример рекурсивного поиска: вариант задачи хода конём
      

Задачи

15. 
    Решить задачу «ход конём» на поле размером 3 на 3 клетки, запоминая, посещённые конём ранее клетки. Запоминать, добавляя посещённое состояние в список посещённых состояний. Использовать простую нумерацию клеток поля.
    

    Указания: Информация о том, что конь уже побывал в некоторой клетке, выражается наличием номера этой клетки в списке посещённых состояний. Этот список должен передаваться из цели в подцель как третий аргумент предиката path. После перехода коня в клетку Z, она должна быть добавлена к списку уже посещённых состояний L, и должна быть сформулирована новая цель (подцель): может ли конь перейти из клетки Z в конечную клетку Y, не посетив ни одного из состояний из списка [Z|L], т.е. подцель – path(Z,Y,[Z|L]). Список [Z|L] – список, состоящий из ранее посещённых состояний L и текущего состояния Z. Новое промежуточное состояние Z не должно быть одним из уже посещённых конём состояний. Т.е. нового значения Z не должно быть в списке ранее посещённых состояний L, т.е. обращение в теле правила к предикату member(Z,L) должно возвращать значение «ложь».

16. 
    Решить задачу «ход конём» на поле размером 3 на 3 клетки, запоминая, посещённые конём ранее клетки. Запоминать, добавляя посещённое состояние в список посещённых состояний. Использовать шахматную нумерацию клеток поля.
    

1. 
   
   
   1. 
      Структура программы на Prolog: разделы программы, домены (стандартные), предикаты, факты, правила.
      
   2. 
      Эвристический поиск: эвристическая мера и эвристическое значение. Алгоритм эвристического поиска: приоритетная очередь и текущая граница поиска. Пример эвристического поиска для игры 8-головоломка.
      
2. 
   
   
   1. 
      Prolog: составные объекты данных (составной тип данных); списки: объявление, операция |
      
   2. 
      Использование эвристик в играх: минимакс для пространств состояний, допускающих полный перебор. Пример: игра «ним».
      
3. 
   
   
   1. 
      Выполнение программы на Prolog: связывание переменных, выполнение цели, формирование подцелей.
      
   2. 
      Использование эвристик в играх: минимакс при фиксированной глубине поиска. Пример: крестики-нолики.
      
4. 
   
   
   1. 
      Алгоритмы на Prolog: печать списка.
      
   2. 
      Продукционная система: продукционные правила (условная часть, образец, шаблон, часть действия), рабочая память, текущее состояние мира, конфликтное множество. Пример: «простая продукционная система»
      
5. 
   
   
   1. 
      Алгоритмы на Prolog: подсчёт числа элементов списка и суммирование элементов списка.
      
   2. 
      Продукционная система: цикл «распознавание-действие», конфликтное множество, допустимые продукции, разрешение конфликта. Пример: 8-головоломка. Использование эвристик: рефракция, новизна, специфичность.
      
6. 
   
   
   1. 
      Алгоритмы на Prolog: объединение списков.
      
   2. 
      Эксперимент Квиллиана и Коллинза по хранению информации у человека, модель хранения информации, предложенная ими. Формализм семантических сетей: структурные элементы, присущие всем семантическим сетям.
      
7. 
   
   
   1. 
      Алгоритмы на Prolog: определение принадлежности к списку.
      
   2. 
      Концептуальные графы: концептуальные понятия, концептуальные отношения. Типы, иерархия типов. Метка типа, маркер объекта. Операции над концептуальными графами: специализация, обобщение; копирование, ограничение, объединение, упрощение.
      
8. 
   
   
   1. 
      Алгоритмы на Prolog: динамическое изменение базы данных.
      
   2. 
      Экспертные системы. Архитектура типовой экспертной системы. Критерии оправданности применения экспертной системы.
      
9. 
   
   
   1. 
      Решение задачи о «ходе конём» на Prolog с использованием списка.
      
   2. 
      Построение экспертных систем: инженер по знаниям, эксперт, пользователь – их роли в построении экспертной системы.
      
10. 
    
    
    1. 
       Решение задачи «обезьяна и банан» на Prolog с запоминанием посещённых состояний в списке.
       
    2. 
       Искусственные нейронные сети: модель нейрона, весовые коэффициенты, уровень активации нейрона, взвешенная сумма входных сигналов, функция активации.
       
11. 
    
    
    1. 
       Решение задачи о «козе, капусте и волке» на Prolog с запоминанием посещённых состояний в списке.
       
    2. 
       Искусственные нейронные сети: топология сети, обучение сети, схема кодирования.
       
12. 
    
    
    1. 
       Решение задачи о «козе, капусте и волке» на Prolog с использованием динамического изменения базы данных.
       
    2. 
       Нейрон Мак-Каллока-Питтса. Вычисление логических функций И и ИЛИ.
       
13. 
    
    
    1. 
       Поиск в пространстве состояний: состояние, пространство состояний, начальное состояние, целевое условие, путь решения. Пример: крестики-нолики.
       
    2. 
       Персептрон. Пороговая функция. Алгоритм обучения. Ограниченность персептрона.
       
14. 
    
    
    1. 
       Граф пространства состояний: вершины, дуги, состояния, переходы; размеченный граф, ориентированный граф; путь; корневой граф, корень, дерево, листья, петли, циклы; предок, родитель, потомок, вершины-братья. Пример: 8-головоломка.
       
    2. 
       Искусственные нейронные сети: сигмоидальная функция, логистическая функция, дельта-правило. Система NETtalk.
       
15. 
    
    
    1. 
       Стратегии поиска в пространстве состояний: поиск с возвратами (последовательность рассмотрения узлов, использование списков).
       
    2. 
       Понимание естественного языка. Уровни анализа естественного языка. Синтаксический разбор, семантическая интерпретация. Стадии создания внутреннего представления предложения.
       
16. 
    
    
    1. 
       Стратегии поиска в пространстве состояний: поиск в ширину (последовательность рассмотрения узлов, использование списков). Поиск на основе данных и от цели.
       
    2. 
       Синтаксический анализ. Контекстно-свободная грамматика: правила вывода, терминалы, нетерминалы, трансформации сверху вниз и снизу вверх, дерево грамматического разбора.
       
17. 
    
    
    1. 
       Стратегии поиска в пространстве состояний: поиск в глубину (последовательность рассмотрения узлов, использование списков). Предельное значение глубины поиска, поиск в глубину с итерационным заглублением.
       
    2. 
       Синтаксический анализ: анализатор на основе сети переходов.