Skip to content

Latest commit

 

History

History

small-tasks

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
chi-square.cpp
chi-square.cpp
 
 
conditional-entropy.cpp
conditional-entropy.cpp
 
 
conditional-variance.cpp
conditional-variance.cpp
 
 
cross-validation.cpp
cross-validation.cpp
 
 
cross-validation.py
cross-validation.py
 
 
decision-tree.cpp
decision-tree.cpp
 
 
distances.cpp
distances.cpp
 
 
f-score.cpp
f-score.cpp
 
 
f-score.py
f-score.py
 
 
linear-regression.cpp
linear-regression.cpp
 
 
linear-regression.py
linear-regression.py
 
 
logical-expression.cpp
logical-expression.cpp
 
 
naive-bayes-classifier.cpp
naive-bayes-classifier.cpp
 
 
nonparametric-regression.py
nonparametric-regression.py
 
 
pearson-correlation-coefficient.cpp
pearson-correlation-coefficient.cpp
 
 
spearmans-rank.cpp
spearmans-rank.cpp
 
 
support-vector-machine.cpp
support-vector-machine.cpp
 
 

README.md

A. Перекрёстная проверка


ограничение по времени на тест: 1 секунда
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод

Условие: Разбейте множество из $N$ объектов, каждый из которых принадлежит к одному из $M$ классов, на $K$ частей. Каждый объект должен попасть ровно в одну часть так, чтобы размеры частей, а также распределение классов по этим частям было сбалансировано. Формально, пусть $cnt(x,c)$ — число объектов с классом $c$ попавших в часть $x$, тогда должно выполняться $\forall x,y,c : \left | cnt(x,c) - cnt(y,c) \right | \leq 1$ и $\forall x,y : \left | \sum_c cnt(x,c) - \sum_c cnt(y,c) \right | \leq 1$.

Входные данные: Первая строка: три целых числа $N$, $M$, $K$ ($1 \leq N \leq 10^5$, $1 \leq M,K \leq N$) — число объектов, классов и частей.

Выходные данные: Выведите $K$ строк. Каждая строка $x$ начинается с целого числа $S$ — размера части $x$. Далее идут $S$ целых чисел — номера объектов попавших в часть $x$. Объекты нумеруются с единицы.

Пример

Входные данные 10 4 3 1 2 3 4 1 2 3 1 2 1 Выходные данные 4 1 4 9 10 3 2 3 5 3 6 7 8

B. F-мера


ограничение по времени на тест: 1 секунда
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод

Условие: В результате эксперимента по классификации на $K$ классов была получена матрица неточностей (Confusion matrix) $CM$, где $CM[c,t]$ — число объектов класса $c$, которые были классифицированы как $t$. Посчитайте по данной матрице неточностей средневзвешенную по классам макро и микро F-меру.

Входные данные: Первая строка содержит целое число $K$ — число классов ($1 \leq K \leq 20$). Далее идёт $K$ строк — описание матрицы неточностей. Каждая строка $c$ содержит $K$ целых чисел — $c$-тая строка матрицы неточностей. $\forall c,t : 0 \leq CM[c,t] \leq 100$ и $\exists c,t : CM[c,t] \geq 1$.

Выходные данные: Выведите два вещественных числа с плавающей точкой — взвешенно усреднённую по классам макро и микро F-меру. Абсолютная погрешность ответа не должна превышать $10^{-6}$.

Пример

Входные данные 2 0 1 1 3 Выходные данные 0.6 0.6

Входные данные 3 3 1 1 3 1 1 1 3 1 Выходные данные 0.326860841 0.316666667

C. Непараметрическая регрессия


ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод

Условие: Реализуйте алгоритм непараметрической регрессии, который бы поддерживал различные функции расстояний, ядер и окон. Описание ядер можно найти здесь: https://en.wikipedia.org/w/index.php?oldid=911077090

Входные данные: Первая строка содержит два целых числа $N$ и $M$ — число объектов и признаков ($1 \leq N \leq 100$, $1 \leq M \leq 10$).

Выходные данные: Выведите одно вещественное число с плавающей точкой — результат запроса.

Пример

Входные данные 3 2 0 2 1 1 1 0 2 0 1 0 0 euclidean uniform fixed 2 Выходные данные 0.0000000000

Входные данные 3 2 0 2 1 1 1 0 2 0 1 0 0 euclidean gaussian variable 2 Выходные данные 0.6090086848

D. Линейная регрессия


ограничение по времени на тест: 0.75 секунд
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод

Условие: Найдите уравнения прямой аппроксимирующей положение объектов из заданного набора данных.

Входные данные: Первая строка содержит два целых числа $N$ ($1 \leq N \leq 10^4$) — число объектов в обучающем множестве, и $M$ ($1 \leq M \leq \min (N, 1000)$) — число признаков у объектов исключая зависимую переменную.

Выходные данные: Выведите $M + 1$ вещественных чисел с плавающей точкой $A_j$ — коэффициенты прямой из уравнения $Y = A_0 \cdot X_0 + A_1 \cdot X_1 + \dots + A_{M-1} \cdot X_{M-1} + A_M$

Пример

E. Метод опорных векторов


ограничение по времени на тест: 1 секунда
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод

Условие: Найдите коэффициенты $\lambda_i$ опорных векторов и сдвиг $b$, для классификации по формуле $class(x) = sign(\sum_i y_i \cdot \lambda_i \cdot k(x, x_i) + b)$, где $x$ — это векторное описание запрашиваемого объекта, а $k$ — функция ядра.

Входные данные: В первой строке находится целое число $N$ ($1 \leq N \leq 100$) — число объектов в обучающем множестве.

Выходные данные: Выведите $N+1$ число с плавающей точкой: первые $N$ чисел — коэффициенты $\lambda_i$ ($0 \leq \lambda_i \leq C$, $\sum \lambda_i \cdot Y_i = 0$) соответствующие объектам из тренировочного множества, последнее число $b$ ($\left | b \right | \leq 10^{12}$) — коэффициент сдвига.

Пример

F. Наивный байесовский классификатор


ограничение по времени на тест: 1 секунда
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод

Условие: Реализуйте оптимальный наивный байесовский классификатор.Априорные вероятности классов оцениваются обыкновенным частотным методом.Вероятности встречи отдельных слов в каждом классе оцениваются с использованием аддитивного сглаживания (сглаживание Лапласа) https://en.wikipedia.org/wiki/Additive_smoothing Словари для каждого класса вычисляются независимо.

Входные данные: В первой строке содержится целое положительное число $K$ ($1 \leq K \leq 10$) — число классов.

Выходные данные: Выведите $M$ строк — результаты мягкой классификации оптимального наивного байесовского классификатора соответствующих сообщений из проверочной выборки.

Пример

Входные данные 3 1 1 1 1 3 1 4 a b c d 2 3 a b c 3 2 a b 4 1 a 2 a b 3 a b c 1 f Выходные данные 0.2553191489 0.3191489362 0.4255319149 0.1872561769 0.2925877763 0.5201560468 0.1898275294 0.3707568933 0.4394155773 0.2553191489 0.3191489362 0.4255319149

G. Дерево принятия решений


ограничение по времени на тест: 1.5 секунд
ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод

Условие: Постройте дерево принятия решений.

Входные данные: Первая строка содержит три целых положительных числа $M$ ($1 \leq M \leq 100$) — число признаков у объектов (исключая класс), $K$ ($1 \leq K \leq 20$) — число классов и $H$ ($1 \leq H \leq 10$) — максимальная глубина (в рёбрах) дерева принятия решений.

Выходные данные: Выведите построенное дерево принятия решений.