Задание 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	1.а, 1	11	1.б, 3	21	1.г, 2
2	2.а, 1	12	2.б, 3	22	2.г, 2
3	1.а, 2	13	1.в, 1	23	1.г, 3
4	2.а, 2	14	2.в, 1	24	2.г, 3
5	1.а, 3	15	1.в, 2	25	1.д, 1
6	2.а, 3	16	2.в, 2	26	2.д, 1
7	1.б, 1	17	1.в, 3	27	1.д, 2
8	2.б, 1	18	2.в, 3	28	2.д, 2
9	1.б, 2	19	1.г, 1	29	1.д, 3
10	2.б, 2	20	2.г, 1	30	2.д, 3

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

Задача 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”. В игре используется восемь фишек, пронумерованных от одного до восьми. Фишки располагаются в девяти ячейках, образующих матрицу размером 33. Одна из ячеек всегда пустая. Любая фишка, смежная с пустой ячейкой, может быть передвинута в позицию, соответствующую пустой ячейке. Фишки должны быть расставлены следующим образом:

1	2	3
8		4
7	6	5

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

а)	8	1	3		б)	1	3	4		в)	2	6	3
	7		4			8		5			1		4
	6	2	5			7	2	6			8	7	5

		г)	1	6	2			д)	8	1	6
			8		3				3		2
			7	5	4				7	5	4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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