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

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

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

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

Достижимые вершины. Дан ориентированный граф, заданный в виде списка рёбер. Написать функцию, возвращающую список вершин, достижимых из данной.
> (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)