Задание N3. Поиск решений в пространстве состояний

ЗАДАНИЕ

на расчетные работы

по дисциплине Системы искусственного интеллекта

Направление подготовки:

Компьютерные науки

Специальность:

6.080400

Компьютерный эколого-экономический мониторинг

Севастополь

Севастопольский национальный УНИВЕРСИТЕТ ядерной энергии и промышленности

Задание

на расчетные работы

по дисциплине «Системы искусственного интеллекта»

для студентов дневного и заочного отделения

специальности 6.080400

Компьютерный эколого-экономический мониторинг

Севастополь

200 г.

ОБЩИЕ ТРЕБОВАНИЯ

К ВЫПОЛНЕНИЮ РАСЧЕТНЫХ РАБОТ

Цель и задачи расчетных работ

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

     Задачами выполнения расчетных работ являются:

- углубленное изучение основных теоретических положений дисциплины «Основы проектирования систем искусственного интеллекта»;

- получение практических навыков разработки программ на языке систем искусственного интеллекта – ЛИСП.

Описание лабораторной установки

Объектом исследования в расчетных работах являются методы и алгоритмы, применяемые в системах искусственного интеллекта, а также сам язык ЛИСП, представляющие программные системы и реализующие две различные парадигмы программирования систем искусственного интеллекта.

Инструментом исследования указанных программных систем является ЭВМ. В качестве операционной системы могут использоваться ОС MS-DOS или Windows. Программная система ЛИСП представлена реализацией Common Lisp. Описание системы Common приведено в «Методических указаниях к проведению практических занятий по дисциплине Системы искусственного интеллекта».

Порядок выполнения расчетных работ

Варианты заданий студенты выбирают по списочному номеру в классном журнале.

При выполнении расчетной работы необходимо:

- разработать алгоритм решения задачи;

- запрограммировать его средствами соответствующего языка, применяемого в лабораторной работе;

- ввести программу в ЭВМ и отладить ее;

- получить результаты обработки исходных данных в различных режимах работы программы;

- получить распечатки текстов, разработанных программ и результатов обработки.

Студенты заочной формы обучения выполняют данные расчетные работы в два этапа. Вариант выбирается по номеру студента в классном списке.

Содержание отчета

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

Задание на расчетные работы №1,2

по дисциплине Системы искусственного элемента

для студентов 3 курса специальности Компьютерный эколого-экономический мониторинг

Выдано студенту (ке) _______ класса ________________________________

Тема: Разработка программ на языке систем искусственного интеллекта – ЛИСП.

Задание

1. Исследовать основных функций языка Лисп.

2. Организовать циклических вычислений на языке ЛИСП.

3. Поиск решений в пространстве состояний.

4. Алгоритм сопоставления с образцом.

5. Исследовать семантических сетей.

6. Исследование сети фреймов

Отчет выполняется в соответствии с ГОСТами на оформление курсовых и дипломных работ.

Утверждено на заседании

каф «КЭЭМ» Протокол №___                           Зав кафедрой КЭЭМ

от ___________________                                             Шумейко И.П.

РАСЧЕТНАЯ РАБОТА №1

Задание N1. Исследование основных функций языка Лисп

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

Описать функцию f (x y z), которая содержит три аргумента, формирует из аргументов список и проверяет или находит:

Варианты заданий

1) является ли первый элемент списка списком и находит его длину;

2) является ли второй элемент списка вещественным или рациональным числом;

3) является ли третий элемент списка целым числом или символом;

4) является ли первый элемент списка четным числом;

5) является ли второй элемент списка отрицательным числом;

6) является ли третий элемент списка рациональным числом;

7) находит среднее арифметическое первого и второго элемента списка;

8) находит среднее арифметическое первого и третьего элемента списка;

9) находит среднее арифметическое второго и третьего элемента списка;

10) является ли хотя бы один из элементов списка числом;

11) является ли хотя бы один из элементов списка списком;

12) заменяет первый элемент списка на Bilbo;

13) заменяет второй элемент списка на Baggins;

14) заменяет третий элемент списка на Hobbit;

15) является ли второй элемент списка отрицательным нечетным числом;

16) является ли элементы списка кратными 3;

17) является ли элементы списка отрицательными числами;

18) является ли элементы списка четными числами;

19) является ли первый элемент списка строкой или символом;

20) является ли второй элемент списком и находит его длину;

21) является ли третий элемент списка целым или вещественным числом;

22) является ли первый элемент списка кратным 3 и не кратным 5;

23) является ли второй элемент списка кратным 5 или кратным 7;

24) является ли третий элемент списка кратным 7 и кратным 3;

25) является ли первый элемент списка квадратом четного числа;

26) является ли третий элемент списка квадратом нечетного числа;

27) является ли хотя один элемент списка строкой;

28) является ли все элементы списка символами;

29) является ли третий элемент списка строкой и находит ее длину;

30) находит среднее арифметическое элементов списка.

Контрольные вопросы

1) дайте определение атома, списка, точечной пары.

2) представьте список в виде точечной пары.

3) что такое ЛИСП-ячейка?

4) дайте определение функции и предиката.

5) существует ли различие в представлении данных и программ на языке Лисп?

6) назовите базовые функции работы со списками.

7) назовите известные вам арифметические функции.

8) в чем отличие функций EQ, EQUAL и =?

9) в чем отличие функций CONS, LIST и APPEND?

10) в чем отличие функций /, DIVIDE, TRUNCATE и REM?

11) переопределите заданную преподавателем стандартную функцию работы со списками с помощью функции defun и базовых функций и предикатов.

Задание N2. Организация циклических вычислений на языке ЛИСП

Цель работы:Исследование способов организации циклических вычислений с помощью средств языка ЛИСП. Проектирование определяемых функций языка ЛИСП для обработки последовательностей.

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

Варианты заданий

1) вычислить произведение двух прямоугольных матриц;

2) определить номер столбца, произведение абсолютных величин которого максимально;

3) вычислить произведение матрицы на число;

4) определить номер строки матрицы, сумма элементов которой наибольшая;

5) вычислить сумму элементов на главной диагонали;

6) определить количество нулевых элементов матрицы;

7) вычислить сумму всех элементов матрицы, расположенных не на главной диагонали;

8) определить, является ли матрица симметричной;

9) преобразовать заданный столбец матрицы в список;

10) определить номер строки, все элементы которой отрицательны;

11) преобразовать заданный столбец матрицы в вектор;

12) транспонировать матрицу;

13) вычислить произведение матрицы на вектор;

14) переставить две заданные строки матрицы;

15) определить номер столбца матрицы, сумма элементов которого минимальна;

16) вычислить среднее арифметическое заданного столбца матрицы;

17) найти максимальный и минимальный элемент матрицы;

18) вычислить произведение вектора на матрицу;

19) преобразовать главную диагональ матрицы в список;

20) определить номер столбца с максимальным элементом;

21) переставить два заданных столбца матрицы;

22) определить номер строки с минимальным элементом;

23) определить количество отрицательных элементов матрицы;

24) вычислить среднее арифметическое заданной строки матрицы;

25) определить номер строки, сумма абсолютных величин которой минимальна;

26) вычислить произведение двух квадратных матриц;

27) определить номер столбца, в котором нет отрицательных элементов;

28) преобразовать заданную строку матрицы в список;

29) создать точечную пару из индексов максимального элемента матрицы;

30) преобразовать заданную строку матрицы в вектор.

Контрольные вопросы

1) расскажите, как работают те функции языка ЛИСП, которые вы использовали при выполнении работы?

2) каким образом в языке ЛИСП создаются векторы, массивы?

3) как получить доступ к элементам массива?

4) как организуют циклические алгоритмы на языке ЛИСП?

5) опишите условное предложение COND.

6) какие функции языка ЛИСП используются для формирования списков?

7) опишите функцию, позволяющую открывать поток.

8) каким образом можно осуществить чтение/запись в файл?

9) опишите функцию, вычисляющую факториал числа, используя циклические вычисления.

10)  опишите функцию, вычисляющую сумму чисел от 1 до N.

Задание N3. Поиск решений в пространстве состояний

Цель работы:Исследование методов поиска решений в пространстве состояний. Программирование основных алгоритмов поиска решений, используемых в системах искусственного интеллекта, на языке ЛИСП

Представить задачу, в соответствии с вариантом задания, в пространстве состояний. Написать программы, которые находят решение задачи двумя методами: в соответствии с заданным методом полного перебора и с помощью А-алгоритма. Для реализации А-алгоритма разработать систему правил, обеспечивающих вычисление эвристических функций h(n). Задание выбирается по варианту из таблицы 1. Например, задание в, 3 означает, что выбирается задача с исходной расстановкой “в”, алгоритм поиска 3. 

 Варианты заданий

Таблица 1 – Варианты заданий

Содержание задач:

     Задача 1. Необходимо отсортировать строку, состоящую из букв d, e, f и g, согласно следующим правилам сортировки: 1) ed Þ de; 2) fd Þ df;      3) gd Þ dg; 4) fe Þ ef; 5) ge Þ eg; 6) gf Þ fg. Если образец, заданный предпосылкой правила, сопоставим с частью сортируемой строки, то правило активизируется. В результате подстрока, которая совпала с условием правила, замещается подстрокой из заключительной части правила. Варианты:

     а) fedgd;                    г) gfdef;

     б) egfde;                    д) feegd.

     в) dgfed;     

     Задача 2. Игра-головоломка “8”. В игре используется восемь фишек, пронумерованных от одного до восьми. Фишки располагаются в девяти ячейках, образующих матрицу размером 353. Одна из ячеек всегда пустая. Любая фишка, смежная с пустой ячейкой, может быть передвинута в позицию, соответствующую пустой ячейке. Фишки должны быть расставлены следующим образом:

         Варианты заданий:

Для решения задач используются следующие алгоритмы полного перебора:

1) поиск в ширину;

2) поиск в глубину;

3) алгоритм равных цен.

Контрольные вопросы

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

2) дайте характеристику методам "слепого" перебора.

3) дайте характеристику методам эвристического поиска.

4) объясните алгоритм поиска в ширину.

5) объясните алгоритм поиска в глубину.

6) объясните алгоритм равных цен.

7) объясните А-алгоритм.

8) напишите ядро программы поиска в глубину.

9) напишите ядро программы поиска в ширину.

10) напишите ядро программы поиска в соответствии с методом равных цен.

11) напишите ядро программы А-алгоритма.

12) напишите рекурсивную функцию, вычисляющую факториал целого числа.

13) напишите рекурсивную функцию, обращающую список.

РАСЧЕТНАЯ РАБОТА №2