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

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

Поиск цикла в графе. Дан ориентированный граф, заданный в виде списка рёбер. Напишите функцию, проверяющую, есть ли ориентированный цикл в этом графе.

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

Достижимые вершины. Дан ориентированный граф, заданный в виде списка рёбер. Напишите функцию, возвращающую список вершин, достижимых из данной.
> (reachable '((1 2) (1 3) (4 1) (3 5)) 1) (1 2 3 5)

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

Приведение подобных. Дано S-выражение, состоящее из арифметических операций, вызовов произвольных функций и одной переменной x (например, (+ (sin x) (* 2 (sin x)) (* x x))). Приведите подобные члены.

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

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

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

Таблица результатов. Дан список результатов олимпиады по программированию: для каждого участника указано количество решённых задач и штрафное время. Определите место каждого участника. Место участника равно количеству обогнавших его участников плюс один. Участники сортируются сначала по количеству решённых задач, а затем по убыванию штрафного времени.
> (places '(vasya 1 50) '(petya 2 45) '(kolya 2 45) '(dima 2 30)) ((dima 1) (kolya 2) (petya 2) (vasya 4))

Параллельное вычисление. Реализуйте параллельное вычисление значения функции, разделив вычисления её аргументов между несколькими вычислителями по сети. Используйте функции 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)))

Шаблоны имён файлов. Проверьте соответствие имени файла шаблону, содержащему спецсимволы * и ? (см. задачи по курсу ОС, задача 19).

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

make-car-cdr again. Реализуйте функцию make-car-cdr, которая вместо ввода дополнительной переменной Q возвращает lambda-выражение, извлекающее X из S:
> (make-car-cdr '(1 (X) 2) 'X) ; возвращает (lambda (s) (car (car (cdr s)))) #<FUNCTION :LAMBDA (S) (CAR (CAR (CDR S)))> Проверка:
> (funcall (make-car-cdr '(1 (X) 2) 'X) '(1 (X) 2)) X

Автоаппликативные функции. Реализуйте анонимную рекурсивную функцию (лямбда-функцию), вычисляющую факториал числа. Не используйте 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




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

	> (check '(OR A (NOT A)))
T
> (check '(AND A B))
NIL