Домашнее задание 1. Бинарный поиск

1. Реализуйте итеративный и рекурсивный варианты бинарного поиска в массиве.
2. На вход подается целое число x и массив целых чисел a, отсортированный по невозрастанию. Требуется найти минимальное значение индекса i, при котором a[i] <= x.
3. Для функций бинарного поиска и вспомогательных функций должны быть указаны, пред- и постусловия. Для реализаций методов должны быть приведены доказательства соблюдения контрактов в терминах троек Хоара.
4. Интерфейс программы.
   • Имя основного класса — BinarySearch.
   • Первый аргумент командной строки — число x.
   • Последующие аргументы командной строки — элементы массива a.
5. Пример запуска: java BinarySearch 3 5 4 3 2 1. Ожидаемый результат: 2.

Модификации

• Базовая

  • Класс BinarySearch должен находиться в пакете search
  • Исходный код тестов
  • Откомпилированные тесты

• Min

  • На вход подается циклический сдвиг отсортированного (строго) по возрастанию массива. Требуется найти в нем минимальное значение.
  • Класс должен иметь имя BinarySearchMin
  • Исходный код тестов
  • Откомпилированные тесты

Домашнее задание 2. Очередь на массиве

1. Найдите инвариант структуры данных «очередь». Определите функции, которые необходимы для реализации очереди. Найдите их пред- и постусловия, при условии что очередь не содержит null.
2. Реализуйте классы, представляющие циклическую очередь с применением массива.
   • Класс ArrayQueueModule должен реализовывать один экземпляр очереди с использованием переменных класса.
   • Класс ArrayQueueADT должен реализовывать очередь в виде абстрактного типа данных (с явной передачей ссылки на экземпляр очереди).
   • Класс ArrayQueue должен реализовывать очередь в виде класса (с неявной передачей ссылки на экземпляр очереди).
   • Должны быть реализованы следующие функции (процедуры) / методы:
     • enqueue – добавить элемент в очередь;
     • element – первый элемент в очереди;
     • dequeue – удалить и вернуть первый элемент в очереди;
     • size – текущий размер очереди;
     • isEmpty – является ли очередь пустой;
     • clear – удалить все элементы из очереди.
   • Инвариант, пред- и постусловия записываются в исходном коде в виде комментариев.
   • Обратите внимание на инкапсуляцию данных и кода во всех трех реализациях.
3. Напишите тесты к реализованным классам.

Модификации

• Базовая

  • Классы должны находиться в пакете queue
  • Исходный код тестов
  • Откомпилированные тесты

• Indexed

  • Реализовать методы
    • get – получить элемент по индексу, отсчитываемому с головы
    • set – заменить элемент по индексу, отсчитываемому с головы
  • Исходный код тестов
  • Откомпилированные тесты

Домашнее задание 3. Очередь на связном списке

1. Определите интерфейс очереди Queue и опишите его контракт.
2. Реализуйте класс LinkedQueue — очередь на связном списке.
3. Выделите общие части классов LinkedQueue и ArrayQueue в базовый класс AbstractQueue.

Модификации

• Базовая

  • Исходный код тестов
  • Откомпилированные тесты

• IndexedToArray

  • Реализовать методы
    • get – получить элемент по индексу, отсчитываемому с головы;
    • set – заменить элемент по индексу, отсчитываемому с головы;
    • toArray, возвращающий массив, содержащий элементы, лежащие в очереди в порядке от головы к хвосту.
  • Исходный код тестов
  • Откомпилированные тесты

Домашнее задание 4. Вычисление в различных типах

1. Добавьте в программу разбирающую и вычисляющую выражения поддержку различных типов.
   • Первым аргументом командной строки программа должна принимать указание на тип, в котором будут производится вычисления
   • Вторым аргументом командной строки программа должна принимать выражение для вычисления.
   • Реализация не должна содержать непроверяемых преобразований типов.
   • Реализация не должна использовать аннотацию @SuppressWarnings.
2. При выполнении задания следует обратить внимание на легкость добавления новых типов и операциий.

Модификации

• Базовая

  • Класс GenericTabulator должен реализовывать интерфейс Tabulator и сроить трехмерную таблицу значений заданного выражения.
    • mode – режим вычислений:
      • i – вычисления в int с проверкой на переполнение;
      • d – вычисления в double без проверки на переполнение;
      • bi – вычисления в BigInteger.
    • expression – выражение, для которого надо построить таблицу;
    • x1, x2 – минимальное и максимальное значения переменной x (включительно)
    • y1, y2, z1, z2 – аналогично для y и z.
    • Результат: элемент result[i][j][k] должен содержать значение выражения для x = x1 + i, y = y1 + j, z = z1 + k. Если значение не определено (например, по причине переполнения), то соответствующий элемент должен быть равен null.
  • Исходный код тестов

• Uls

  • Дополнительно реализовать поддержку режимов:
    • u – вычисления в int без проверки на переполнение;
    • l – вычисления в long без проверки на переполнение;
    • s – вычисления в short без проверки на переполнение.
  • Исходный код тестов

Домашнее задание 5. Функциональные выражения на 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. При выполнение задания следует обратить внимание на:

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

Модификации

• Базовая

  • Код должен находиться в файле javascript-solutions/functionalExpression.js.
  • Исходный код тестов
    • Запускать c аргументом hard или easy;

• Mini (для тестирования)

  • Не поддерживаются бинарные операции
  • Код находится в файле functionalMiniExpression.js.
  • Исходный код тестов
    • Запускать c аргументом hard или easy;

• OneTwo. Дополнительно реализовать поддержку:

  • переменных: y, z;
  • констант:
    • one – 1;
    • two – 2;
  • Исходный код тестов

Домашнее задание 6. Объектные выражения на 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. При выполнение задания следует обратить внимание на:

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

Модификации

• Base

  • Код должен находиться в файле javascript-solutions/objectExpression.js.
  • Исходный код тестов
    • Запускать c указанием модификации и сложности (easy, hard или bonus).

• AvgMed. Дополнительно реализовать поддержку:

  • функций:
    • Avg5 (avg5) – арифметическое среднее пяти аргументов, 1 2 3 4 5 avg5 равно 3;
    • Med3 (med3) – медиана трех аргументов, 1 2 -10 med3 равно 1.

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

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

Модификации

• Base

  • Код должен находиться в файле javascript-solutions/objectExpression.js.
  • Исходный код тестов
    • Запускать c указанием модификации и сложности (easy или hard).

• Prefix: Means. Дополнительно реализовать поддержку:

  • операций произвольного числа аргументов:
    • ArithMean (arith-mean) – арифметическое среднее (arith-mean 1 2 6) равно 3;
    • GeomMean (geom-mean) – геометрическое среднее (geom-mean 1 2 4) равно 2;
    • HarmMean (harm-mean) – гармоническое среднее, (harm-mean 2 3 6) равно 3;
  • Исходный код тестов

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

1. Разработайте функции для работы с объектами линейной алгебры, которые представляются следующим образом:

   • скаляры – числа
   • векторы – векторы чисел;
   • матрицы – векторы векторов чисел.

2. Функции над векторами:

   • v+/v-/v* – покоординатное сложение/вычитание/умножение;
   • scalar/vect – скалярное/векторное произведение;
   • v*s – умножение на скаляр.

3. Функции над матрицами:

   • m+/m-/m* – поэлементное сложение/вычитание/умножение;
   • m*s – умножение на скаляр;
   • m*v – умножение на вектор;
   • m*m – матричное умножение;
   • transpose – траспонирование;

4. Все функции должны поддерживать произвольное число аргументов. Например (v+ [1 2] [3 4] [5 6]) должно быть равно [9 12].

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

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

Модификации

• Базовая

  • Код должен находиться в файле clojure-solutions/linear.clj.
  • Исходный код тестов
    • Запускать c аргументом easy или hard

• Tensor

  • Назовем тензором многомерную прямоугольную таблицу чисел.
  • Добавьте операции поэлементного сложения (t+), вычитания (t-) и умножения (t*) тензоров. Например, (t+ [[1 2] [3 4]] [[5 6] [7 8]]) должно быть равно [[6 8] [10 12]].
  • Исходный код тестов

Домашнее задание 9. Функциональные выражения на 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. При выполнение задания следует обратить внимание на:

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

Модификации

• Base

  • Код должен находиться в файле clojure-solutions/expression.clj.
  • Исходный код тестов
    • Запускать c указанием модификации и сложности (easy или hard).

• SinhCosh. Дополнительно реализовать поддержку:

  • унарных операций:
    • sinh – гиперболический синус, (sinh 3) немного больше 10;
    • cosh – гиперболический косинус, (cosh 3) немного меньше 10.

Домашнее задание 10. Объектные выражения на 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. При выполнение задания можно использовать любой способ преставления объектов.

Модификации

• Base

  • Код должен находиться в файле clojure-solutions/expression.clj.
  • Исходный код тестов
    • Запускать c указанием модификации и сложности (easy или hard).

• SinhCosh. Дополнительно реализовать поддержку:

  • унарных операций:
    • Sinh (sinh) – гиперболический синус, (sinh 3) немного больше 10;
    • Cosh (cosh) – гиперболический косинус, (cosh 3) немного меньше 10.

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

1. Реализуйте функцию (parseObjectSuffix "expression"), разбирающую выражения, записанные в суффиксной форме, и функцию toStringSuffix, возвращающую строковое представление выражения в этой форме. Например, (toStringSuffix (parseObjectSuffix "( ( 2 x * ) 3 - )")) должно возвращать ((2 x *) 3 -).
2. Функции разбора должны базироваться на библиотеке комбинаторов, разработанной на лекции.

Модификации

• Базовая

  • Код должен находиться в файле clojure-solutions/expression.clj.
  • Исходный код тестов
    • Запускать c указанием модификации и сложности (easy или hard).

• Boolean. Сделать модификацию Variables и дополнительно реализовать поддержку:

  • Булевских операций
    • Аргументы: число больше 0 → true, иначе → false
    • Результат: true → 1, false → 0
    • And (&&) – и: 5 & -6 равно 0
    • Or (||) - или: 5 & -6 равно 1
    • Xor (^^) - исключающее или: 5 ^ -6 равно 1
    • операции по увеличению приоритета: ^^, ||, &&, операции базовой модификации

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

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

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

2. Вариант N <= 1000.

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

Модификации

• Базовая

  • Код должен находиться в файле prolog-solutions/primes.pl.
  • Исходный код тестов
    • Запускать c аргументом easy, hard или bonus

• Power

  • Добавьте правило power_divisors(N, I, D), возвращающее делители Nⁱ: power_divisors(6, 2, [2, 2, 3, 3]).
  • Исходный код тестов

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

1. Реализуйте ассоциативный массив (map) на основе деревьев поиска. Для решения можно реализовать любое дерево поиска логарифмической высоты.
2. Разработайте правила:
   • map_build(ListMap, TreeMap), строящее дерево из упорядоченного списка пар ключ-значение (O(n));
   • map_get(TreeMap, Key, Value), проверяющее, что массив содержит заданную пару ключ-значение (O(log n)).

Модификации

• Базовая

  • Код должен находиться в файле prolog-solutions/tree-map.pl.
  • Исходный код тестов
    • Запускать c аргументом easy или hard

• KeysValues

  • Добавьте правила:
    • map_Keys(Map, Keys), возвращающее ключи в порядке возрастания;
    • map_Values(Map, Values), возвращающее значения в порядке возрастания ключей.