Список дополнительных задач

Задачи из этого списка даются в качестве индивидуальных заданий. Распределение задач здесь.

Часть 1. Задачи по языку LISP

Детали реализации. Найдите границу, после которой предикат eq для двух равных целых чисел начинает возвращать NIL:
> (eq 1 1) T > (eq (expt 10 20) (expt 10 20)) NIL

Параллельное вычисление. Реализуйте параллельное вычисление значения функции, разделив вычисления её аргументов между несколькими вычислителями по сети. Используйте функции socket-connect, socket-server. Передавайте задания для вычисления и результаты в виде выражений LISP, читайте при помощи read. Пример клиента, отправляющего серверу S-выражение:
```
(let ((f (socket-connect PORT HOST)))
	(princ EXPR f)
)
		
```
Пример сервера, ожидающего подключение и читающего выражение от подключённого клиента:
```
(let ( (serv (socket-server PORT)) )  
	(let ( (f (socket-accept serv)) ) 
		(read f)
	)
)
		
```
На вход программе даётся список серверов для подключения (заранее запущенных) и S-выражение, которое рассматривается как вызов функции с N аргументами. На выходе — результат вычислений. Для проверки можно определить функцию (defun slow (x) (sleep 5) x) и попробовать замерить время вычисления выражения (+ (slow 1) (slow 2) (slow 3)) в последовательном и параллельном вариантах. Время вычисления выражения expr замеряется при помощи (time expr).
Пример вызова: (parallel '(("127.0.0.1" 12345) ("127.0.0.1" 12346)) '(+ (slow 1) (slow 2) (slow 3)))

Автоаппликативные функции. Реализуйте анонимную рекурсивную функцию (лямбда-функцию), вычисляющую факториал числа. Не используйте defun. Проблема здесь, очевидно, в том, что рекурсивная функция должна иметь возможность вызвать себя по имени, а имени у анонимной функции нет.
Один из вариантов решения задачи — создание автоаппликативной функции, которая принимает параметром своё описание (в виде лямбда-выражения) и вызывает себя при помощи funcall. То есть, для вычисления факториала необходимо будет сделать примерно такой вызов:
> ((lambda (func n) ...) (lambda (func n) ...) 5) ; первый параметр — сама функция, второй параметр — аргумент факториала 120

Рекурсия высших порядков. Реализуйте функцию разворота списка reverse2, используя только функции car, cdr, cons, рекурсивный вызов функции reverse2 и условные формы (if или cond). Не создавайте вспомогательных функций, не добавляйте вспомогательных параметров к функции reverse2.
> (defun reverse2 (l) ...) REVERSE2 > (reverse2 '(1 2 3)) (3 2 1) Указание. Первым элементом развёрнутого списка будет являться последний элемент аргумента, который можно вычислить выражением (car (reverse2 (cdr l))). Аналогичным образом (но несколько более громоздким выражением) вычисляется хвост развёрнутого списка.
Написав функцию, определите, сколько рекурсивных вызовов будет требоваться для разворота списка из десяти элементов.

Анонимная функция. Реализуйте функцию make-increment, принимающую параметром число x и возвращающую анонимную функцию (lambda-функцию), увеличивающую свой аргумент на число x.
> (funcall (make-increment 5) 7) 12

Часть 2. Задачи для решения на LISP'е и на каком-либо императивном языке.

Дифференцирование. Напишите функцию, выполняющую символьное дифференцирование рациональной функции по переменной x. При реализации на императивном языке допустимо сделать функцию, принимающую уже готовое дерево разбора выражения, опустив собственно разбор (хотя при желании можно его написать).
> (diff 'x) 1 > (diff '(+ x (f x))) (+ 1 (diff (f x)))

Значение инфиксного выражения. Дано S-выражение, представляющее запись арифметического выражения в инфиксной форме. Вычислите значение этого выражения. При реализации на императивном языке допустимо принимать на вход не строку, а разобранную на лексемы последовательность (хотя не запрещается сделать сразу нормально).
> (evaluate '(1 * (2 + 3) - 4)) 1

Счастливый билет. Дан список из чисел. Расставьте между ними скобки и знаки операций, чтобы получить в результате число N.
> (ticket '(1 2 5 7 2 1) 100) (* (* (* 1 2) 5) (+ 7 (+ 2 1)))

Шаблоны имён файлов. Проверьте соответствие данной строки шаблону, содержащему спецсимволы (wildcards) * и ?:
> (wildcard "ab.txt" "a?.*") T > (wildcard "a.txt" "a?.*") NIL

Подмножества. Создайте список из всех подмножеств множества {1, ..., N}. Порядок перечисления подмножеств и элементов может быть любым:
> (subsets 2) ((2 1) (2) (1) NIL)

Множители. Создайте список из всех возможных разложений натурального числа N на множители. Разложения (x y) и (y x) можно считать как различными, так и одинаковыми (постарайтесь сделать так, чтобы изменение этого поведения не требовало больших изменений кода функции).
> (factors 20) ((20) (10 2) (5 4) (5 2 2) (4 5) (2 10) (2 5 2) (2 2 5))

Размен денег. Создайте список из всех возможных способов набрать N рублей, если известны достоинства находящихся в обращении монет или банкнот. Разложения (x y) и (y x) можно считать как различными, так и одинаковыми (постарайтесь сделать так, чтобы изменение этого поведения не требовало больших изменений кода функции).
> (change 4 '(1 2 5)) ((1 1 1 1) (1 1 2) (1 2 1) (2 1 1) (2 2))

Независимые циклы. Подстановка элементов множества {1, ..., N} задаётся в виде пар
1 2 3 4 5 6 3 5 1 2 4 6 Представьте данную подстановку в виде произведения независимых циклов. Для данного примера: (1 3)(2 5 4)(6)

Большая громоздкая задача. Проверьте, является ли логическая формула, зависящая от переменных A, B, ..., Z, тождественно истинной. Формула задана в виде лисповского выражения с использованием функций AND, OR и NOT.
> (check '(OR A (NOT A))) T > (check '(AND A B)) NIL