Входной файл: | Стандартный вход | Ограничение времени: | 2 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 1 |
Требуется реализовать на языке Python функцию, вычисляющую значение энтропии заданной выборки.
entropy(y) = − ∑v = set(y)p(v)log p(v)
где set(y) — множество уникальных значений вектора y.
import numpy as np
def entropy(y: np.ndarray) -> float:
"""Computes entropy value for labels `y`.
Arguments:
y: 1d array of integers, sample labels
Returns:
float, entropy value for labels `y`"""
pass
Функция принимает единственный параметр y
— одномерный np.array
, значения классов в обучающей выборке.
При решении задачи следует использовать натуральный логарифм.
Код должен содержать только реализацию функции. Запрещено пользоваться любыми готовыми реализациями вычисления функции entropy
.
Входной файл: | Стандартный вход | Ограничение времени: | 2 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 1 |
Требуется реализовать на языке Python функцию, вычисляющую значение gini impurity заданной выборки.
gini(y) = 1 − ∑v = set(y)p2(v)
где set(y) — множество уникальных значений вектора y.
import numpy as np
def gini(y: np.ndarray) -> float:
"""Computes gini impurity value for labels `y`.
Arguments:
y: 1d array of integers, sample labels
Returns:
float, gini impurity value for labels `y`"""
pass
y
— одномерный np.array
— значения классов в выборке
Код должен содержать только реализацию функции. Запрещено пользоваться любыми готовыми реализациями вычисления функции gini
.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Входной файл: | Стандартный вход | Ограничение времени: | 10 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 1 |
Требуется реализовать следующие функцию на языке Python.
def tree_split(X, y, criterion) # col, row of best split
X
— двумерный np.array
— обучающая выборка
y
— одномерный np.array
— значения классов в обучающей выборке
criterion
— строковое значение — вид критерия 'var'
, 'gini'
или 'entropy'
tree_split
должен возвращать номер признака и номер значения из обучающей выборки, которое будет использоваться в качестве порогового
Таким образом, tree_split
возвращает наилучшее бинарное разделение по правилу вида xcol ≤ X[row, col]
Код должен содержать только реализацию функции.
Входной файл: | Стандартный вход | Ограничение времени: | 2 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 1 |
Пусть имеется задача классификации f(x) = y, x ∈ Nn, y ∈ {0,1}. Требуется написать программу, строящую классификатор методом градиентного бустинга, используя в качестве базовой модели OneRule регрессор. Получаемый классификатор имеет вид F(x) = 11 + e − H(x), где H(x) = h0 + k∑i = 1hi(x), 1 ⩽ k ⩽ n, h0 — независимое приближение, hi обученные OneRule регрессоры. В качестве функции ошибки используется L(y, F(x)) = − (ylog(F(x)) + (1 − y)log(1 − F(x))).
При построении классификатора необходимо использовать следующий алгоритм
Входные данные:
Алгоритм:
Первая строка входного файла содержит натуральные числа m,n,k — количество примеров, признаков и базовых регрессоров соответственно. В следующих m строках содержится n + 1 целое число — значения признаков и номер класса примера. Гарантируется, что уникальные значения каждого признака образуют множество {i|i ∈ 0,s − 1}.
Первая строка выходного файла должна содержать независимое приближение h0. В следующих k строках необходимо вывести описания базовых регрессоров — номер признака, на котором был обучен регрессор, и список предсказываемых регрессором значений в порядке возрастания значения признака. Вещественные числа необходимо вывести с точностью не менее трёх знаков после запятой.
10 ⩽ m ⩽ 1750
5 ⩽ n ⩽ 60, 34n ⩽ k ⩽ n
3 ⩽ s < 50
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Входной файл: | Стандартный вход | Ограничение времени: | 2 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 1 |
Пусть заданы 4 набора точек: squares, circles, moons, spirals, которые можно скачать здесь.
Требуется на языке Python реализовать 4 функции,
преобразующие соответствующие наборы точек так,
чтобы они были идеально разделимы линейным
методом опорных векторов,
а именно sklearn.svm.SVC(kernel='linear')
.
import numpy as np
def transform_squares(X: np.ndarray) -> np.ndarray:
pass
def transform_circles(X: np.ndarray) -> np.ndarray:
pass
def transform_moons(X: np.ndarray) -> np.ndarray:
pass
def transform_spirals(X: np.ndarray) -> np.ndarray:
pass
При решении задачи запрещено использовать условные операторы и операторы сравнения.
Каждая функция принимает двумерный np.array
,
имеющий размеры (1200, 2).
Функции проверяются в порядке их определения в задаче.
Результатом работы функции должен являться двумерный массив преобразованных точек, имеющий тот же размер, что и исходный.
Входной файл: | Стандартный вход | Ограничение времени: | 2 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 1 |
Спектакль многомерного театра теней проходит следующим образом
Первая строка входного файла содержит натуральные числа n, m, l, k — количество актёров, размерность пространства, количество экранов и индекс, для которого нужно изменить расположение. В следующих n строках содержится по m вещественных чисел — текущее положение актёра, и l чисел 0 или 1 — положение актёра относительно экрана.
Выходной файл должен содержать n строк по m вещественных чисел — новые положения актёров. Так как размер файла может оказаться очень большим, числа необходимо выводить не более чем с тремя знаками после запятой.
25 ⩽ n ⩽ 7500
10 ⩽ m ⩽ 175
2 ⩽ l ⩽ 5
0 ⩽ k < l
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Входной файл: | input.jpg | Ограничение времени: | 2 сек | |
Выходной файл: | output.txt | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 1 |
Требуется реализовать на языке Python набор функций, выполняющие этапы применения оператора Кэнни:
import numpy as np
from typing import Tuple
def gaussian_blur(img: np.ndarray, kernel: Tuple[int, int], sigma: float) -> np.ndarray:
'''Blurs an image using Gaussian filter.
Arguments:
img: input image, a 2d np.ndarray.
kernel: gaussian kernel size.
sigma: gaussian kernel standard deviation.
Returns:
Blurred image, a 2d np.ndarray of the same size and dtype as `img`.
'''
pass
def magnitude_and_direction(img: np.ndarray, kernel: np.ndarray) -> Tuple[np.ndarray, np.ndarray]:
'''Applies a filter to the image and computes magnitude and direction of the gradient.
The filter is applied using 'reflect' mode for border pixels, i.e. dcb|abcd|cba
Arguments:
img: input image, a 2d np.ndarray.
kernel: the filter kernel, a 2d np.ndarray with odd dimension sizes.
The kernel is applied over x dimension, kernel.T is applied over y
Returns:
Magnitude and direction of the gradient, two 2d np.ndarray objects of the same size and dtype as `img`.
The direction values lie in range [0, 2 * pi].
'''
pass
def edge_thinning(magnitude: np.ndarray, direction: np.ndarray) -> np.ndarray:
'''Performs edge thinning step of Canny algorithm using 0°, 45°, 90°, 135°, 180° (=0°) gradient direction
as described here https://en.wikipedia.org/wiki/Canny_edge_detector#Gradient_magnitude_thresholding_or_lower_bound_cut-off_suppression.
If the angle is equally close to two groups, the group with lower angle value is selected.
Arguments:
magnitude: magnitude of image gradient, a 2d np.ndarray.
direction: direction of image gradient, a 2d np.ndarray.
Returns:
Boolean mask of suppressed pixels (False if a pixel is suppresed, True if preserved), a 2d np.ndarray of the same size as `magnitude` and dtype bool.
'''
pass
def edge_tracking(magnitude: np.ndarray, mask: np.ndarray, low_threshold: float, high_threshold: float) -> np.ndarray:
'''Performs edge tracking step of Canny algorithm. The thresholds are inclusive.
Arguments:
magnitude: magnitude of image gradient, a 2d np.ndarray.
mask: pixel suppression mask, obtained by edge_thinning function.
low_threshold: weak pixel threshold.
high_threshold: strong pixel threshold.
Returns:
A 2d np.ndarray of the same size as `magnitude` and dtype bool, representing detected edges.
'''
pass
Код решения должен содержать только импортируемые модули, определение и реализацию функций.
№ | Входной файл (input.jpg ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
input.jpg img = cv.imread('input.jpg')
img = cv.cvtColor(img, cv.COLOR_BGR2GRAY).astype(float)
blur = gaussian_blur(img, (5, 5), 1)
magnitude, direction = magnitude_and_direction(blur, np.array([[1, 0, -1], [2, 0, -2], [1, 0, -1]]))
mask = edge_thinning(magnitude, direction)
edges = edge_tracking(magnitude, mask, 0.1 * np.max(magnitude), 0.2 * np.max(magnitude))
cv.imwrite('sample.png', edges.astype(int) * 255)
|
sample.png |
Входной файл: | Стандартный вход | Ограничение времени: | 4 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 1024 Мб | |
Максимальный балл: | 3000 |
Требуется реализовать на языке Python функцию, выполняющую классическое преобразование Хаффа для поиска прямых. Функция должна иметь следующий интерфейс
import numpy as np
from typing import List, Tuple
def hough_lines(
image: np.ndarray,
rho: float,
theta: float,
threshold: int,
min_theta: float = 0,
max_theta: float = np.pi) -> list[tuple[float, float, int]]:
"""Finds lines in a binary image using the standard Hough transform.
Arguments:
image: 2d np.ndarray of bool
rho: distance resolution
theta: angle resolution
theshold: only lines with votes > `threshold` are returned
min_theta: minimal angle value
max_theta: maximal angle value
Returns:
lines: a list of tuples (distance, angle, votes), detected lines sorted by votes in descending order
"""
pass
При реализации функции сетка по расстоянию должна строиться на интервале [ − (w + h), w + h + rho). При построении аккумулятора голос отдаётся за расстояние, округлённое к ближайшему индексу (round half to even). После построения аккумулятора должна проводиться его фильтрация согласно правилу âi,j = {ai,j,ai − 1,j < ai,j,ai,j − 1 < ai,j,ai + 1,j ⩽ ai,j,ai,j + 1 ⩽ ai,j0,else..
При решении задачи запрещено использовать любые готовые реализации алгоритма.
Аргументы функции:
Функция возвращает список троек (расстояние, угол, количество голосов) для каждой прямой в порядке убывания по количеству голосов.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
lines.jpg image = cv2.Canny(cv2.imread('lines.jpg'), 500, 550).astype(bool)
print(*(f'{i} {j:.3f} {k}' for i, j, k in hough_lines(image, 1, np.pi / 360, 210)), sep='\n')
|
|
Входной файл: | Стандартный вход | Ограничение времени: | 3 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 3000 |
Требуется реализовать на языке Python функцию, выполняющую преобразование Хаффа для поиска окружностей. Функция должна иметь следующий интерфейс
import numpy as np
from typing import List, Tuple
def hough_circles(
image: np.ndarray,
accumulator_resolution: float,
min_distance: int,
canny_threshold: int,
center_threshold: int,
radius_threshold: int,
min_radius: int,
max_radius: int) -> List[Tuple[float, float, float, int]]:
"""Finds circles in a gray image using Hough transform
Arguments:
image: 2d np.ndarray of float
accumulator_resolution: step size for accumulators
min_distance: minial distance between circle centers
canny_threshold: upper threshold for Canny edge detector
center_threshold: minimal number of votes for a center to be accepted
radius_threshold: minimal number of votes for a radius to be accepted
min_radius: minimal circle radius
max_radius: maximal circle radius
Returns:
circles: a list of tuples (x, y, radius, votes), detected circles sorted by votes in descending order
"""
pass
При построении аккумуляторов, голос отдаётся за индекс, округлённый к ближайшему целому (rounding half to even).
После построения аккумулятора для центров окружностей должна проводиться его фильтрация согласно правилу âi,j = {ai,j,ai − 1,j < ai,j,ai,j − 1 < ai,j,ai + 1,j ⩽ ai,j,ai,j + 1 ⩽ ai,j0,else..
При выборе радиуса окружности лучшим считается такой радиус r с количеством голосов c, для которого частное cr является максимальным.
При решении задачи запрещено использовать любые готовые реализации алгоритма.
Аргументы функции:
Функция возвращает список четвёрок (x, y, радиус, количество голосов) для каждой окружности в порядке убывания по количеству голосов.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
circles.png image = cv2.cvtColor(cv2.imread('circles.png'), cv2.COLOR_BGR2GRAY)
print(*(f'{x} {y} {r} {c}' for x, y, r, c in hough_circles(image, 1, 50, 250, 50, 50, 50, 250)), sep='\n')
|
|
Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 1 |
Требуется реализовать на языке Python класс, описывающий полносвязный слой нейронной сети:
import numpy as np
from typing import Optional, Tuple, Union
class Dense:
"""Implements fully-connected layer"""
def __init__(self, n_in: int, n_out: int, use_bias: bool = True):
"""Initializes Dense layer.
The weights are initialized using uniformly distributed values in range [-1, 1]. Bias vector is not initialized if `use_bias` is False.
Weigths matrix has the shape (`n_in`, `n_out`), bias vector has the shape (`n_out`, ).
Arguments:
n_in: Positive integer, dimensionality of input space.
n_out: Positive integer, dimensionality of output space.
use_bias: Whether the layer uses a bias vector."""
pass
@property
def weights(self) -> tuple[np.ndarray, np.ndarray] | tuple[np.ndarray]:
"""Returns weights used by the layer."""
pass
@property
def input(self) -> np.ndarray:
"""Returns the last input received by the layer"""
pass
def __call__(self, x: np.ndarray) -> np.ndarray:
"""Performs the layer forward pass.
Arguments:
x: Input array of shape (`batch_size`, `n_in`)
Returns:
An array of shape (`batch_size`, `n_out`)"""
pass
def grad(self, gradOutput: np.ndarray) -> tuple[np.ndarray, tuple[np.ndarray, np.ndarray]] | tuple[np.ndarray, tuple[np.ndarray]]:
"""Computes layer gradients
Arguments:
gradOutput: Gradient of loss function with respect to the layer output, an array of shape (`batch_size`, `n_out`).
Returns:
A tuple object:
Gradient of loss function with respect to the layer input, an array of shape (`batch_size`, `n_in`)
Gradient of loss function with respect to the layer's weights:
An array of shape (`n_in`, `n_out`).
Optional array of shape (`n_out`, )."""
pass
Для реализации класса разрешено использовать только модуль numpy
.
Код решения должен содержать только импортируемые модули, определение и реализацию класса.
Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 18 |
Требуется реализовать на языке Python классы, описывающие различные функции активации:
import numpy as np
class Activation:
"""Base activation class"""
def __init__(self):
self._input = None
@property
def input(self):
"""Returns the last input received by the activation"""
return self._input
def __call__(self, x: np.ndarray) -> np.ndarray:
"""Computes activation output
Arguments:
x: Input array of shape (`batch_size`, ...)
Returns:
An array of the same shape as `x`"""
raise NotImplementedError()
def grad(self, gradOutput: np.ndarray) -> np.ndarray:
"""Computes loss gradient with respect to the activation input.
Arguments:
gradOutput: Gradient of loss function with recpect to the activation output.
An array of the same shape as the array received in `__call__` method.
Returns:
An array of the same shape as `gradOutput`"""
raise NotImplementedError()
class ReLU(Activation):
"""Implements ReLU activation layer"""
def __call__(self, x: np.ndarray) -> np.ndarray:
pass
def grad(self, gradOutput: np.ndarray) -> np.ndarray:
pass
class LeakyReLU(Activation):
"""Implements LeakyReLU activation layer"""
def __init__(self, slope: float = 0.03):
"""Initializes LeakyReLU layer.
Arguments:
slope: the slope coeffitient of the activation."""
pass
def __call__(self, x: np.ndarray) -> np.ndarray:
pass
def grad(self, gradOutput: np.ndarray) -> np.ndarray:
pass
class GeLU(Activation):
"""Implements GeLU activation layer"""
def __call__(self, x: np.ndarray) -> np.ndarray:
pass
def grad(self, gradOutput: np.ndarray) -> np.ndarray:
pass
class SiLU(Activation):
"""Implements SiLU (swish) activation layer"""
def __call__(self, x: np.ndarray) -> np.ndarray:
pass
def grad(self, gradOutput: np.ndarray) -> np.ndarray:
pass
class Softplus(Activation):
"""Implements Softplus (SmoothReLU) activation layer"""
def __call__(self, x: np.ndarray) -> np.ndarray:
pass
def grad(self, gradOutput: np.ndarray) -> np.ndarray:
pass
class ELU(Activation):
"""Implements ELU activation layer"""
def __init__(self, alpha: float = 1):
"""Initializes ELU layer.
Arguments:
alpha: the alpha coeffitient of the activation."""
pass
def __call__(self, x: np.ndarray) -> np.ndarray:
pass
def grad(self, gradOutput: np.ndarray) -> np.ndarray:
pass
class Sigmoid(Activation):
"""Implements Sigmoid activation layer"""
def __call__(self, x: np.ndarray) -> np.ndarray:
pass
def grad(self, gradOutput: np.ndarray) -> np.ndarray:
pass
class Tanh(Activation):
"""Implements Tanh activation layer"""
def __call__(self, x: np.ndarray) -> np.ndarray:
pass
def grad(self, gradOutput: np.ndarray) -> np.ndarray:
pass
class Softmax(Activation):
"""Implements Softmax activation layer"""
def __call__(self, x: np.ndarray) -> np.ndarray:
"""Computes Softmax activation output
Arguments:
x: Input array of shape (`batch_size`, `n_features`)
Returns:
An array of the same shape as `x`"""
pass
def grad(self, gradOutput: np.ndarray) -> np.ndarray:
pass
Функции активации тестируются в порядке их определения в задаче циклично, то есть activation_idx = (test_idx − 1) mod 9.
Код решения должен содержать только импортируемые модули, определение и реализацию классов.
Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 25 |
Требуется реализовать на языке Python класс, описывающий двумерный свёрточный слой нейронной сети:
import numpy as np
class Conv2D:
"""Implements 2d convolution layer"""
def __init__(self,
n_in: int,
n_out: int,
kernel_size: tuple[int, int],
strides: tuple[int, int] = (1, 1),
padding: str = 'valid',
use_bias: bool = True,
dilations: tuple[int, int] = (1, 1)
):
"""Initialized Conv2D layer.
The weights are initialized using uniformly distributed values in range [-1, 1]. Bias vector is not initialized if `use_bias` is False.
Weights tensor has the shape (`kernel_size[0]`, `kernel_size[1]`, `n_in`, `n_out`), bias vector has the shape (`n_out`, ).
Arguments:
n_in: Positive integer, dimensionality of input space.
n_out: Positive integer, dimensionality of output space.
kernel_size: Pair of positive integers, convolution kernel dimensions.
strides: Pair of positive integers, convolution strides along each dimension.
padding: Either 'valid' or 'same', padding to be used by the layer, see explanation below.
use_bias: Whether the layer uses a bias vector.
dilations: Pair of positive integers, convolution kernel dilations along each dimension.
Padding:
'valid': no padding is applied.
'same': padding along every dimension is computed as follows
if dimension_size % stride == 0:
total_pad = max((kernel_size - 1) * dilation + 1 - stride)
else:
total_pad = max((kernel_size - 1) * dilation + 1 - dimension_size % stride)
pad_before = total_pad // 2
pad_after = total_pad - pad_before"""
pass
@property
def weights(self) -> tuple[np.ndarray, np.ndarray] | tuple[np.ndarray]:
"""Returns weights used by the layer. Weight tensor and bias vector if use_bias is True"""
pass
def __call__(self, x: np.ndarray) -> np.ndarray:
"""Performs the layer forward pass.
Arguments:
x: Input array of shape (`batch_size`, `height`, `width`, `n_in`).
Returns:
An array of shape (`batch_size`, `new_height`, `new_width`, `n_out`)."""
pass
def grad(self, x: np.ndarray, gradOutput: np.ndarray) -> tuple[np.ndarray, tuple[np.ndarray, np.ndarray] | tuple[np.ndarray]]:
"""Computes layer gradients
Arguments:
gradOutput: Gradient of loss function with respect to the layer output, an array of shape (`batch_size`, `new_height`, `new_width`, `n_out`).
Returns:
A tuple object:
Gradient of loss function with respect to the layer input, an array of shape (`batch_size`, `height`, `width`, `n_in`)
Gradient of loss function with respect to the layer's weights:
An array of shape (`kernel_size[0]`, `kernel_size[1]`, `n_in`, `n_out`).
Optional array of shape (`n_out`, )."""
pass
Для реализации класса разрешено использовать только модуль numpy
.
Код решения должен содержать только импортируемые модули, определение и реализацию класса.
Максимальный балл: | 10 | Ограничение времени: | 1 сек | |
Ограничение памяти: | 512 Мб |
Требуется решить задачу классификации табличных данных с использованием изученных моделей машинного обучения.
Требуется использовать следующие модели машинного обучения:
Максимальное количество баллов за задачу — 10.
В качестве решения принимается файл с исходным кодом, например jupyter notebook. В систему требуется отправить ссылку на файл, размещённый в открытом доступе (Google Colab, Github, Google Drive и др.), указав среду разработки "Answer text
". После отправки решение необходимо сдать преподавателю лично до начала зачётной недели.
Максимальный балл: | 10 | Ограничение времени: | 1 сек | |
Ограничение памяти: | 512 Мб |
Билет выбирается независимо и случайно из следующего списка:
Экзамен проводится очно. В случае невозможности очного присутствия необходимо заранее договориться с преподавателем о дистанционной сдаче.
После взятия билета студент готовится в ответу. При подготовке можно использовать произвольные материалы и доступ в Интернет.
В докладе необходимо максимально кратко упомянуть все важные элементы доставшейся темы/вопроса. После доклада преподаватель задаёт несколько уточняющих вопросов.