Задача A. Наивный байесовский классификатор

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Пусть задан некоторый язык, описываемый множеством слов W, |W| = mmN. Требуется построить наивный байесовский классификатор f: B↦ C = {i}k − 1i = 0, где {0, 1}m⊇ B = lN∈ Wlw(μ)|w∈ W} — множество представлений всех возможных сообщений составленных на языке W в виде мешка слов, δw — мера Дирака, δx(A) = {1,x∈ A,0,x∉ A..

При этом процесс классификации происходит следующим образом

  1. Сформировать базовый классификатор с априорными вероятностями классов p(c∈ C) = 1k и условными вероятностями слов p(w∈ W|c∈ C) = 1m;
  2. Для каждого поступившего сообщения μi и его класса ci
    1. Получить предсказание ^ci по μi с использованием текущего классификатора;
    2. Обновить классификатор с использованием сообщения μi и настоящего значения его класса ci.

Формат входных данных

Первая строка входного файла содержит натуральные числа n, m, k — количество сообщений, мощность языка и количество классов соответственно. В каждой их следующих n строк содержится m чисел 0 или 1 и одно натуральное число ci — представление сообщения в виде мешка слов и значение его класса.

Формат выходных данных

Выходной файл должен содержать n натуральных чисел — предсказанное значение класса каждого сообщения на момент его получения.

Ограничения

10⩽ n⩽ 7500

8⩽ m⩽ 100

2⩽ k⩽ 10

Примеры тестов

Стандартный вход Стандартный выход
1
10 8 2
0 1 1 1 1 0 0 1 1
1 0 1 0 0 1 0 0 0
1 1 1 1 1 0 1 0 1
1 0 1 0 0 1 0 1 0
0 1 0 1 1 1 1 0 1
1 0 1 0 0 1 0 0 0
0 1 0 1 1 0 0 1 1
1 0 0 0 0 1 0 1 0
1 1 1 1 0 1 1 1 0
0 1 0 1 1 0 0 0 1
0
0
1
0
1
0
1
0
1
1

Задача B. Kernel trick

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Пусть заданы 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). Функции проверяются в порядке их определения в задаче.

Формат выходных данных

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


Задача C. Canny

Входной файл:input.jpg   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Требуется реализовать на языке 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.
    
    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
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

Задача D. Dense

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Требуется реализовать на языке Python класс, описывающий полносвязный слой нейронной сети:


import numpy as np
from typing import Optional, Tuple

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, Optional[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, Optional[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.

Формат выходных данных

Код решения должен содержать только импортируемые модули, определение и реализацию класса.


0.578s 0.013s 27