Домашнее задание 1. Функциональные выражения на JavaScript

1. Разработайте функции cnst, variable, add, subtract, multiply, divide, negate для вычисления выражений с одной переменной.

2. Функции должны позволять производить вычисления вида:

   let expr = subtract(
       multiply(
           cnst(2),
           variable("x")
       ),
       cnst(3)
   );
   println(expr(5));
   

   При вычислении такого выражения вместо каждой переменной подставляется значение, переданное в качестве параметра функции expr (на данном этапе имена переменных игнорируются). Таким образом, результатом вычисления приведенного примера должно стать число 7.

3. Тестовая программа должна вычислять выражение x2−2x+1, для x от 0 до 10.

4. Требуется написать функцию parse, осуществляющую разбор выражений, записанных в обратной польской записи. Например, результатом

   parse("x x 2 - \* x \* 1 +")(5)

   должно быть число 76.

5. При выполнение задания следует обратить внимание на:

   • Применение функций высшего порядка.
   • Выделение общего кода для бинарных операций.

Домашнее задание 2. Объектные выражения на JavaScript

1. Разработайте классы Const, Variable, Add, Subtract, Multiply, Divide, Negate для представления выражений с одной переменной.

   1. Пример описания выражения 2x-3:

      let expr = new Subtract(
          new Multiply(
              new Const(2),
              new Variable("x")
          ),
          new Const(3)
      );
      

   2. Метод evaluate(x) должен производить вычисления вида: При вычислении такого выражения вместо каждой переменной подставляется значение x, переданное в качестве параметра функции evaluate (на данном этапе имена переменных игнорируются). Таким образом, результатом вычисления приведенного примера должно стать число 7.

   3. Метод toString() должен выдавать запись выражения в обратной польской записи. Например, expr.toString() должен выдавать 2 x * 3 -.

2. Метод diff("x") должен возвращать выражение, представляющее производную исходного выражения по переменной x. Например, expr.diff("x") должен возвращать выражение, эквивалентное new Const(2) (выражения new Subtract(new Const(2), new Const(0)) и

   new Subtract(
       new Add(
           new Multiply(new Const(0), new Variable("x")),
           new Multiply(new Const(2), new Const(1))
       )
       new Const(0)
   )
   

   так же будут считаться правильным ответом).

   Функция parse должна выдавать разобранное объектное выражение.

3. При выполнение задания следует обратить внимание на:

   • Применение инкапсуляции.
   • Выделение общего кода для операций.

Домашнее задание 3. Обработка ошибок на JavaScript

1. Добавьте в предыдущее домашнее задание функцию parsePrefix(string), разбирающую выражения, задаваемые записью вида (- (* 2 x) 3). Если разбираемое выражение некорректно, метод parsePrefix должен бросать человеко-читаемое сообщение об ошибке.
2. Добавьте в предыдущее домашнее задание метод prefix(), выдающий выражение в формате, ожидаемом функцией parsePrefix.
3. При выполнение задания следует обратить внимание на:
   • Применение инкапсуляции.
   • Выделение общего кода для бинарных операций.
   • Обработку ошибок.
   • Минимизацию необходимой памяти.

Домашнее задание 4. Линейная алгебра на Clojure

1. Разработайте функции для работы с объектами линейной алгебры, которые представляются следующим образом:
   • скаляры – числа
   • векторы – векторы чисел;
   • матрицы – векторы векторов чисел.
2. Функции над векторами:
   • v+/v-/v* – покоординатное сложение/вычитание/умножение;
   • scalar/vect – скалярное/векторное произведение;
   • v*s – умножение на скаляр.
3. Функции над матрицами:
   • m+/m-/m* – поэлементное сложение/вычитание/умножение;
   • m*s – умножение на скаляр;
   • m*v – умножение на вектор;
   • m*m – матричное умножение;
   • transpose – траспонирование;
4. Ко всем функциям должны быть указаны контракты. Например, нельзя складывать вектора разной длины.
5. Все функции должны поддерживать произвольное число аргументов. Например (v+ [1 2] [3 4] [5 6]) должно быть равно [9 12].
6. При выполнение задания следует обратить внимание на:
   • Применение функций высшего порядка.
   • Выделение общего кода для операций.

Домашнее задание 5. Функциональные выражения на Clojure

1. Разработайте функции constant, variable, add, subtract, multiply и divide для представления арифметических выражений.

   1. Пример описания выражения 2x-3:

      (def expr
        (subtract
          (multiply
            (constant 2)
            (variable "x"))
          (constant 3)))
      

   2. Выражение должно быть функцией, возвращающей значение выражение при подстановке элементов, заданных отображением. Например, (expr {"x" 2}) должно быть равно 1.

2. Разработайте разборщик выражений, читающий выражения в стандартной для Clojure форме. Например,

   (parseFunction "(- (\* 2 x) 3)")

   должно быть эквивалентно expr.

3. Функции add, subtract, multiply и divide должны принимать произвольное число аргументов. Разборщик так же должен допускать произвольное число аргументов для +, -, *.

4. При выполнение задания следует обратить внимание на:

   • Выделение общего кода для операций.

Домашнее задание 6. Объектные выражения на Clojure

1. Разработайте конструкторы Constant, Variable, Add, Subtract, Multiply и Divide для представления выражений с одной переменной.

   1. Пример описания выражения 2x-3:

      (def expr
        (Subtract
          (Multiply
            (Constant 2)
            (Variable "x"))
          (Const 3)))
      

   2. Функция (evaluate expression vars) должна производить вычисление выражения expression для значений переменных, заданных отображением vars. Например, (evaluate expr {"x" 2}) должно быть равно 1.

   3. Функция (toString expression) должна выдавать запись выражения в стандартной для Clojure форме.

   4. Функция (parseObject "expression") должна разбирать выражения, записанные в стандартной для Clojure форме. Например,

      (parseObject "(- (\* 2 x) 3)")

      должно быть эквивалентно expr.

   5. Функция (diff expression "variable") должена возвращать выражение, представляющее производную исходного выражения по заданой пермененной. Например, (diff expression "x") должен возвращать выражение, эквивалентное (Constant 2), при этом выражения (Subtract (Const 2) (Const 0)) и

      (Subtract
        (Add
          (Multiply (Const 0) (Variable "x"))
          (Multiply (Const 2) (Const 1)))
        (Const 0))
      

      так же будут считаться правильным ответом.

2. Констуркторы Add, Subtract, Multiply и Divide должны принимать произвольное число аргументов. Разборщик так же должен допускать произвольное число аргументов для +, -, *, /.
3. При выполнение задания можно использовать любой способ преставления объектов.

Домашнее задание 7. Комбинаторные парсеры

1. Реализуйте функцию (parseObjectInfix "expression"), разбирающую выражения, записанные в инфиксной форме, и функцию toStringInfix, возвращающую строковое представление выражения в этой форме. Например,

   (toStringInfix (parseObjectInfix "2 \* x - 3"))

   должно возвращать ((2 * x) - 3).

2. Функции разбора должны базироваться на библиотеке комбинаторов, разработанной на лекции.

Домашнее задание 8. Простые числа на Prolog

1. Разработайте правила:

   • prime(N), проверяющее, что N – простое число.
   • composite(N), проверяющее, что N – составное число.
   • prime_divisors(N, Divisors), проверяющее, что список Divisors содержит все простые делители числа N, упорядоченные по возрастанию. Если N делится на простое число P несколько раз, то Divisors должен содержать соответствующее число копий P.

2. Варианты

   • Простой: N ≤ 1000.
   • Сложный: N ≤ 10^5.
   • Бонусный: N ≤ 10^7.

3. Вы можете рассчитывать, на то, что до первого запроса будет выполнено правило init(MAX_N).

Домашнее задание 9. Деревья поиска на Prolog

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

2. Разработайте правила:

   • map_get(TreeMap, Key, Value), проверяющее, что массив содержит заданную пару ключ-значение (O(log n)).
   • map_put(TreeMap, Key, Value, Result); добавляющее пару ключ-значение в массив, или заменяющее текущее значение для ключа (O(log n));
   • map_remove(TreeMap, Key, Result) удаляющее отображение для ключа (O(log n));
   • map_build(ListMap, TreeMap), строящее дерево из неупорядоченного списка пар ключ-значение (O(n log n)).