Skip to content

Latest commit

 

History

History
653 lines (589 loc) · 46.2 KB

README.md

File metadata and controls

653 lines (589 loc) · 46.2 KB
Raw

Часть условий можно найти здесь.

Тесты к курсу «Парадигмы программирования»

Условия домашних заданий

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

Модификации

  • Базовая
  • MinMax
    • Добавьте правила:
      • map_minKey(Map, Key), возвращающее минимальный ключ в дереве,
      • map_maxKey(Map, Key), возвращающее максимальный ключ в дереве.
    • Исходный код тестов
  • Replace
    • Добавьте правило map_replace(Map, Key, Value, Result), заменяющего значения ключа на указанное, если ключ присутствует.
    • Исходный код тестов
  • FloorKey
    • Добавьте правило map_floorKey(Map, Key, FloorKey), возвращающее максимальный ключ, меньший либо равный заданному.
    • Исходный код тестов
  • CeilingKey
    • Добавьте правило map_ceilingKey(Map, Key, CeilingKey), возвращающее минимальный ключ, больший либо равный заданному.
    • Исходный код тестов
  • SubmapSize
    • Добавьте правило map_submapSize(Map, FromKey, ToKey, Size), возвращающее число ключей в диапазоне [FromKey, ToKey).
    • Исходный код тестов

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

Модификации

  • Базовая
  • Unique
    • Добавьте правило unique_prime_divisors(N, Divisors), возвращающее простые делители без повторов
    • Исходный код тестов
  • Palindrome
    • Добавьте правило prime_palindrome(N, K), определяющее, является ли N простым палиндромом в K-ичной системе счисления
    • Исходный код тестов
  • Nth
  • Lcm
    • Добавьте правило lcm(A, B, LCM), подсчитывающее НОК(A, B) через разложение на простые множители
    • Исходный код тестов

Для запуска тестов можно использовать скрипты TestProlog.cmd и TestProlog.sh

  • Репозиторий должен быть скачан целиком.
  • Скрипты должны находиться в каталоге prolog (их нельзя перемещать, но можно вызывать из других каталогов).
  • Полное имя класса теста указывается в качестве первого аргумента командной строки, например, prtest.primes.PrologPrimesTest.
  • Тестируемое решение должно находиться в текущем каталоге.

Исходный код к лекциям по Prolog

Запуск Prolog

Лекция 1. Введение в Пролог

Лекция 2. ООП в Prolog

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

Модификации

  • Базовая
  • Variables. Дополнительно реализовать поддержку:
    • Переменных, состоящих из произвольного количества букв XYZ в любом регистре
      • Настоящее имя переменной определяется первой буквой ее имени
    • Исходный код тестов
  • PowLog. Дополнительно реализовать поддержку:
    • Бинарных правоассоциативных операций максимального приоритета:
      • Pow (**) – возведения в степень: 4 ** 3 ** 2 равно 4 ** (3 ** 2) равно 262144
      • Log (//) – взятия логарифма: 8 // 9 // 3 равно 8 // (9 // 3) равно 3
    • Исходный код тестов
  • Bitwise. Дополнительно реализовать поддержку:
    • Побитовых операций
      • And (&) – и: 5 & 6 равно 4
      • Or (|) - или: 5 & 6 равно 7
      • Xor (^) - исключающее или: 5 ^ 6 примерно равно 1.66881E-308
      • для реализации операций используйте doubleToLongBits и longBitsToDouble
      • операции по увеличению приоритета: ^, |, &, + и -, * и /
    • Исходный код тестов
  • ImplIff. Сделать модификацию Bitwise и дополнительно реализовать поддержку:
    • Побитовых операций
      • Impl (=>) – импликация (правоассоциативна): 4 => 1 примерно равно -2
      • Iff (<=>) - тогда и только тогда: 2 <=> 6 примерно равно -1.34827E308
      • операции по увеличению приоритета: <=>, =>, ^, |, &, + и -, * и /
    • Исходный код тестов

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

Модификации

  • Базовая
  • SquareSqrt. Дополнительно реализовать поддержку:
    • унарных операций:
      • Square (square) – возведение в квадрат, (square 3) равно 9;
      • Sqrt (sqrt) – извлечение квадратного корня из абсолютной величины аргумента, (sqrt -9) равно 3.
    • Исходный код тестов
  • PwLg. Дополнительно реализовать поддержку:
    • бинарных операций:
      • Pw (pw) – возведение в степень, (pow 2 3) равно 8;
      • Lg (lg) – логарифм абсолютной величины по основанию абсолютной величины, (lg -8 -2) равно 3.
    • Исходный код тестов
  • ExpLn. Дополнительно реализовать поддержку:
    • унарных операций:
      • Exp (exp) – экспонента, (exp 8) примерно равно 2981;
      • Ln (Ln) – натуральный логарифм абсолютной величины, (lg 2981) примерно равно 8.
    • Исходный код тестов
  • SumAvg. Дополнительно реализовать поддержку:
    • операций произвольного числа аргументов:
      • Sum (sum) – сумма, (sum 1 2 3) равно 6;
      • Avg (avg) – арифметическое среднее, (avg 1 2 3) равно 2;
    • Исходный код тестов
  • SumexpSoftmax. Дополнительно реализовать поддержку:
    • операций произвольного числа аргументов:
      • Sumexp (sumexp) – сумма экспонент, (sumexp 8 8 9) примерно равно 14065;
      • Softmax (Softmax) – softmax первого аргумента, (softmax 1 2 3) примерно равно 0.09;
    • Исходный код тестов

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

Модификации

  • Базовая
    • Код должен находиться в файле clojure-solutions/expression.clj.
    • Исходный код тестов
      • Запускать c аргументом easy или hard
  • PwLg. Дополнительно реализовать поддержку:
    • бинарных операций:
      • pw – возведение в степень, (pow 2 3) равно 8;
      • lg – логарифм абсолютной величины по основанию абсолютной величины, (lg -8 -2) равно 3.
    • Исходный код тестов
  • ExpLn. Дополнительно реализовать поддержку:
    • унарных операций:
      • exp – экспонента, (exp 8) примерно равно 2981;
      • ln – натуральный логарифм абсолютной величины, (ln -2981) примерно равно 8.
    • Исходный код тестов
  • MinMax. Дополнительно реализовать поддержку:
    • операций произвольного числа аргументов:
      • min – минимум, (min 1 2 6) равно 1;
      • max – максимум, (min 1 2 6) равно 6;
    • Исходный код тестов
  • MedAvg. Дополнительно реализовать поддержку:
    • операций произвольного числа аргументов:
      • med – медиана, (med 1 2 6) равно 2;
      • avg – среднее, (avg 1 2 6) равно 3;
    • Исходный код тестов
  • SumexpSoftmax. Дополнительно реализовать поддержку:
    • операций произвольного числа аргументов:
      • sumexp – сумма экспонент, (sumexp 8 8 9) примерно равно 14065;
      • softmax – softmax первого аргумента, (softmax 1 2 3) примерно равно 0.09;
    • Исходный код тестов

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

Модификации

  • Базовая
  • Shapeless
    • Добавьте операции поэлементного сложения (s+), вычитания (s-) и умножения (s*) чисел и векторов любой (в том числе, переменной) формы. Например, (s+ [[1 2] 3] [[4 5] 6]) должно быть равно [[5 7] 9].
    • Исходный код тестов
  • Cuboid
    • Назовем кубоидом трехмерную прямоугольную таблицу чисел.
    • Добавьте операции поэлементного сложения (c+), вычитания (c-), умножения (c*) и деления (cd) кубоидов. Например, (с+ [[[1] [2]] [[3] [4]]] [[[5] [6]] [[7] [8]]]) должно быть равно [[[6] [8]] [[10] [12]]].
    • Исходный код тестов
  • Tensor
    • Назовем тензором многомерную прямоугольную таблицу чисел.
    • Добавьте операции поэлементного сложения (t+), вычитания (t-) и умножения (t*) тензоров. Например, (t+ [[1 2] [3 4]] [[5 6] [7 8]]) должно быть равно [[6 8] [10 12]].
    • Исходный код тестов
  • Broadcast
    • Назовем тензором многомерную прямоугольную таблицу чисел.
    • Форма тензора – последовательность чисел (s1..n)=(s1, s2, …, sn), где n – размерность тензора, а si – число элементов по i-ой оси. Например, форма тензора [ [ [2 3 4] [5 6 7] ] ] равна (1, 2, 3), а форма 1 равна ().
    • Тензор формы (s1..n) может быть распространен (broadcast) до тензора формы (u1..m), если (si..n) является суффиксом (u1..m). Для этого, исходный тензор копируется по недостающим осям. Например, распространив тензор [ [2] [3] ] формы (2, 1) до формы (3, 2, 1) получим [ [ [2] [3] ] [ [2] [3] ] [ [2] [3] ] ], а распространив 1 до формы (2, 3) получим [ [1 1 1] [1 1 1] ].
    • Тензоры называются совместимыми, если один из них может быть распространен до формы другого. Например, тензоры формы (3, 2, 1) и (2, 1) совместимы, а (3, 2, 1) и (1, 2) – нет. Числа совместимы с тензорами любой формы.
    • Добавьте операции поэлементного сложения (b+), вычитания (b-), умножения (b*) и деления умножения (bd) совместимых тензоров. Если формы тензоров не совпадают, то тензоры меньшей размерности должны быть предварительно распространены до тензоров большей размерности. Например, (b+ 1 [ [10 20 30] [40 50 60] ] [100 200 300] ) должно быть равно [ [111 221 331] [141 251 361] ].
    • Исходный код тестов

Для запуска тестов можно использовать скрипты TestClojure.cmd и TestClojure.sh

  • Репозиторий должен быть скачан целиком.
  • Скрипты должны находиться в каталоге clojure (их нельзя перемещать, но можно вызывать из других каталогов).
  • Полное имя класса теста указывается в качестве аргумента командной строки, например, cljtest.linear.LinearBinaryTest.
  • Тестируемое решение должно находиться в текущем каталоге.

Исходный код к лекциям по Clojure

Запуск Clojure

  • Консоль: Windows, *nix
    • Интерактивный: RunClojure
    • С выражением: RunClojure --eval "<выражение>"
    • Скрипт: RunClojure <файл скрипта>
    • Справка: RunClojure --help
  • IDE

Скрипт со всеми примерами

Лекция 1. Функции

Лекция 2. Внешний мир

Лекция 3. Объекты и вычисления

Лекция 4. Комбинаторные парсеры

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

Модификации

  • Базовая
  • PrefixAtanExp. Дополнительно реализовать поддержку:
    • унарных операций:
      • ArcTan (atan) – арктангенс, (atan 2) примерно равно 1.1;
      • Exp (Exp) – экспонента, (exp 3) примерно равно 20;
    • Исходный код тестов
  • PrefixSinhCosh. Дополнительно реализовать поддержку:
    • унарных операций:
      • Sinh (sinh) – гиперболический синус, (sinh 3) немного больше 10;
      • Cosh (cosh) – гиперболический косинус, (cosh 3) немного меньше 10;
    • Исходный код тестов
  • PrefixSumAvg. Дополнительно реализовать поддержку:
    • операций произвольного числа аргументов:
      • Sum (sum) – сумма, (sum 1 2 3) равно 6;
      • Avg (avg) – арифметическое среднее, (avg 1 2 3) равно 2;
    • Исходный код тестов
  • PostfixSumAvg. Дополнительно реализовать поддержку:
    • выражений в постфиксной записи: (2 3 +) равно 5
    • унарных операций:
      • Sum (sum) – сумма, (1 2 3 sum) равно 6;
      • Avg (avg) – арифметическое среднее, (1 2 3 avg) равно 2;
    • Исходный код тестов
  • PostfixSumexpSoftmax. Дополнительно реализовать поддержку:
    • выражений в постфиксной записи: (2 3 +) равно 5
    • унарных операций:
      • Sumexp (sumexp) – сумма экспонент, (8 8 9 sumexp) примерно равно 14065;
      • Softmax (softmax) – softmax первого аргумента, (1 2 3 softmax) примерно 0.09;
    • Исходный код тестов
  • PostfixMeanVar. Дополнительно реализовать поддержку:
    • выражений в постфиксной записи: (2 3 +) равно 5
    • операций произвольного числа аргументов:
      • Mean (mean) – математическое ожидание аргументов, (1 2 6 mean) равно 3;
      • Var (var) – дисперсию аргументов, (2 5 11 var) равно 14;
    • Исходный код тестов

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

Модификации

  • Базовая
    • Код должен находиться в файле objectExpression.js.
    • Исходный код тестов
      • Запускать c аргументом easy, hard или bonus.
  • PowLog. Дополнительно реализовать поддержку:
    • бинарных операций:
      • Power (pow) – возведение в степень, 2 3 pow равно 8;
      • Log (log) – логарифм абсолютного значения аргумента по абсолютному значению основания -2 -8 log равно 3;
    • Исходный код тестов
  • SinhCosh. Дополнительно реализовать поддержку:
    • унарных функций:
      • Sinh (sinh) – гиперболический синус, 3 sinh немного больше 10;
      • Cosh (cosh) – гиперболический косинус, 3 cosh немного меньше 10;
    • Исходный код тестов
  • MinMax. Дополнительно реализовать поддержку:
    • функций:
      • Min3 (min3) – минимум из трех аргументов, 1 2 3 min равно 1;
      • Max5 (max5) – максимум из пяти аргументов, 1 2 3 4 5 max равно 5;
    • Исходный код тестов
  • Gauss. Дополнительно реализовать поддержку:

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

Модификации

  • Базовая
  • Mini
  • Cube. Дополнительно реализовать поддержку:
    • переменных: y, z;
    • унарных функций:
      • cube – возведение в куб, 2 cube равно 8;
      • cuberoot – кубический корень, -8 cuberoot равно -2;
    • Исходный код тестов
  • OneIffAbs. Дополнительно реализовать поддержку:
    • переменных: y, z;
    • констант:
      • one – 1;
      • two – 2;
    • операций:
      • abs – абсолютное значение, -2 abs равно 2;
      • iff – условный выбор: если первый аргумент неотрицательный, вернуть второй аргумент, иначе вернуть первый третий аргумент.
        • one two 3 iff равно 2
        • -1 -2 -3 iff равно -3
        • 0 one two iff равно 1;
    • Исходный код тестов
      • Запускать c аргументом hard или easy
  • PieAvgMed. Дополнительно реализовать поддержку:
    • переменных: y, z;
    • констант:
      • pi – π;
      • e – основание натурального логарифма;
    • операций:
      • avg5 – арифметическое среднее пяти аргументов, 1 2 3 4 5 avg5 равно 7.5;
      • med3 – медиана трех аргументов, 1 2 -10 med3 равно 1.
    • Исходный код тестов
      • Запускать c аргументом hard или easy
  • PieSinCos. Дополнительно реализовать поддержку:
    • переменных: y, z;
    • констант:
      • pi – π;
      • e – основание натурального логарифма;
    • операций:
      • sin – синус, pi sin равно 0;
      • cos – косинус, pi cos равно -1.
    • Исходный код тестов
      • Запускать c аргументом hard или easy

Запуск тестов

  • Для запуска тестов используется GraalJS (часть проекта GraalVM, вам не требуется их скачивать отдельно)
  • Для запуска тестов можно использовать скрипты TestJS.cmd и TestJS.sh
    • Репозиторий должен быть скачан целиком.
    • Скрипты должны находиться в каталоге javascript (их нельзя перемещать, но можно вызывать из других каталогов).
  • Для самостоятельно запуска из консоли необходимо использовать командную строку вида: java -ea --module-path=<js>/graal --class-path <js> jstest.functional.FunctionalExpressionTest {hard|easy}, где
    • -ea – включение проверок времени исполнения;
    • --module-path=<js>/graal путь к модулям Graal (здесь и далее <js> путь к каталогу javascript этого репозитория);
    • --class-path <js> путь к откомпилированным тестам;
    • {hard|easy} указание тестируемой модификации.
  • При запуске из IDE, обычно не требуется указывать --class-path, так как он формируется автоматически. Остальные опции все равно необходимо указать.
  • Troubleshooting
    • Error occurred during initialization of boot layer java.lang.module.FindException: Module org.graalvm.truffle not found, required by jdk.internal.vm.compiler – неверно указан --module-path;
    • Graal.js not found – неверно указаны --module-path
    • Error: Could not find or load main class jstest.functional.FunctionalExpressionTest – неверно указан --class-path;
    • Error: Could not find or load main class <other class> – неверно указано полное имя класса теста;
    • Exception in thread "main" java.lang.AssertionError: You should enable assertions by running 'java -ea jstest.functional.FunctionalExpressionTest' – не указана опция -ea;
    • First argument should be one of: "easy", "hard", found: XXX – неверно указана сложность;
    • Exception in thread "main" jstest.EngineException: Script 'functionalExpression.js' not found – в текущем каталоге отсутствует решение (functionalExpression.js)

Исходный код к лекциям по JavaScript

Скрипт с примерами

Запуск примеров

Лекция 1. Типы и функции

Лекция 2. Объекты и методы

Лекция 3. Другие возможности

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

Модификации

  • Базовая
    • Класс 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.
    • Исходный код тестов
  • Сmm
    • Дополнительно реализовать унарные операции:
      • count – число установленных битов, count 5 равно 2.
    • Дополнительно реализовать бинарную операцию (минимальный приоритет):
      • min – минимум, 2 min 3 равно 2;
      • max – максимум, 2 max 3 равно 3.
    • Исходный код тестов
  • Ls
    • Дополнительно реализовать поддержку режимов:
      • l – вычисления в long без проверки на переполнение;
      • s – вычисления в short без проверки на переполнение.
    • Исходный код тестов
  • CmmUls
    • Реализовать операции из модификации Cmm.
    • Дополнительно реализовать поддержку режимов:
      • u – вычисления в int без проверки на переполнение;
      • l – вычисления в long без проверки на переполнение;
      • s – вычисления в s без проверки на переполнение.
    • Исходный код тестов
  • CmmUfb
    • Реализовать операции из модификации Cmm.
    • Дополнительно реализовать поддержку режимов:
      • u – вычисления в int без проверки на переполнение;
      • f – вычисления в float без проверки на переполнение;
      • b – вычисления в byte без проверки на переполнение.
    • Исходный код тестов

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

Модификации

  • Базовая
  • ToArray
    • Добавить в интерфейс очереди и реализовать метод toArray, возвращающий массив, содержащий элементы, лежащие в очереди в порядке от головы к хвосту
    • Исходная очередь должна оставаться неизменной
    • Дублирования кода быть не должно
    • Исходный код тестов
    • Откомпилированные тесты
  • Functions
    • Добавить в интерфейс очереди и реализовать методы
      • filter(predicate) – создать очередь, содержащую элементы, удовлетворяющие предикату
      • map(function) – создать очередь, содержащую результаты применения функции
    • Исходная очередь должна остаться неизменной
    • Тип возвращаемой очереди должен соответствовать типу исходной очереди
    • Взаимный порядок элементов должен сохраняться
    • Дублирования кода быть не должно
    • Исходный код тестов
    • Откомпилированные тесты
  • IfWhile
    • Добавить в интерфейс очереди и реализовать методы
      • removeIf(predicate) – удалить элементы, удовлетворяющие предикату
      • retainIf(predicate) – удалить элементы, не удовлетворяющие предикату
      • takeWhile(predicate) – сохранить подряд идущие элементы, удовлетворяющие предикату
      • dropWhile(predicate) – удалить подряд идущие элементы, не удовлетворяющие предикату
    • Взаимный порядок элементов должен сохраняться
    • Дублирования кода быть не должно
    • Исходный код тестов
    • Откомпилированные тесты

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

Модификации

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

Модификации

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

Модификации

  • Базовая
    • Класс ExpressionParser должен реализовывать интерфейс Parser
    • Классы CheckedAdd, CheckedSubtract, CheckedMultiply, CheckedDivide и CheckedNegate должны реализовывать интерфейс TripleExpression
    • Нельзя использовать типы long и double
    • Нельзя использовать методы классов Math и StrictMath
    • Исходный код тестов
  • PowLog2
    • Дополнительно реализуйте унарные операции:
      • log2 – логарифм по уснованию 2, log2 10 равно 3;
      • pow2 – два в степени, pow2 4 равно 16.
    • Исходный код тестов
  • PowLog
    • Дополнительно реализуйте бинарные операции (максимальный приоритет):
      • ** – возведение в степень, 2 ** 3 равно 8;
      • // – логарифм, 10 // 2 равно 3.
    • Исходный код тестов