Задача 01A. One Rule ≡

Условие

Требуется реализовать классификатор, использующий алгоритм One Rule.

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

Первая строка входных данных содержит два целых числа N и K — количество примеров в обучающей выборке и количество признаков соответственно.

Вторая строка содержит K слов, разделённых пробелом — названия признаков объектов.

Следующие N строк содержат обучающую выборку, каждая строка содержит по K + 1 слов, первые K слов описывают значения признаков, слово номер K + 1 содержит метку класса — 0 или 1.

Следующая строка содержит одно целое число M — количество примеров в тестовой выборке.

Далее идёт тестовая выборка, содержащая M строк по K слов. Гарантируется, что каждое значение каждого признака встречается в обучающей выборке хотя бы один раз.

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

Выходные данные должны содержать M чисел — результаты классификации алгоритма One Rule после обучения на первых N примерах.

В случае если несколько признаков дают одинаковый результат на обучающей выборке, то следует выбрать тот, который встречается раньше.

Если по какому-то значению можно с одинаковой вероятностью предсказать как 0 так и 1, то следует предсказывать 1.

Ограничения

1 ≤ N, M, K ≤ 100

Суммарная длина строк не превосходит 10⁵

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

10 4
Outlook Temperature Humidity Windy
overcast hot high FALSE 1
sunny mild high FALSE 0
overcast mild high TRUE 1
rainy mild normal FALSE 1
overcast hot normal FALSE 1
rainy mild high FALSE 1
rainy cool normal FALSE 1
rainy mild high TRUE 0
sunny hot high FALSE 0
sunny hot high TRUE 0
4
rainy cool normal TRUE
sunny cool normal FALSE
overcast cool normal TRUE
sunny mild normal TRUE

1
0
1
0

Задача 01B. Экстраполяция ≡

Условие

Имеется фиксированная неизвестная функция f(x), она одинаковая для всех тестов. Даны значения функции f(x), f(x + 1), f(x + 2), …, f(x + N − 1). Требуется определить значение функции f в точке x + N.

Для понимания структуры функции следует воспользоваться двумя тестами: первый из них приведён в примере. Второй тест можно скачать ЗДЕСЬ.

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

Первая строка входного файла содержит одно целое число N.

Вторая строка входного файла содержит N вещественных чисел — значения функции f в точках x, x + 1, x + 2, …, x + N − 1.

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

Выходной файл должен содержать одно число — f(x + N) с точностью не менее двух знаков после запятой.

Ограничения

3 ≤ N ≤ 10⁵

 − 10⁸ ≤ x ≤ 10⁸

 − 10⁹ ≤ f(x) ≤ 10⁹

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

5
700.949074 715.616206 726.958614 730.983909 730.427020

732.2357177317001

Задача 02A. Деловые люди (Pandas) ≡

Условие

Требуется на языке Python реализовать функцию get_businessmen(df: pd.DataFrame) Функция принимает на вход объект DataFrame библиотеки Pandas и возвращает DataFrame пользователей, совершивших 20 и более международных звонков.

В объекте DataFrame присутствуют следующие поля:

• ID — идентификатор пользователя, целое уникальное число
• Total day minutes — сумма минут дневных звонков, вещественное число
• Total day calls — количество дневных звонков, целое число
• Total night minutes — сумма минут ночных звонков, вещественное число
• Total night calls — количество ночных звонков, целое число
• Total intl minutes — сумма минут международных звонков, вещественное число
• Total intl calls — количество международных звонков, целое число
• Customer service calls — количество обращений в техническую поддержку, целое число

Функция имеет следующий интерфейс

import pandas as pd

def get_businessmen(df: pd.DataFrame) -> pd.DataFrame:
    """
    Возвращает DataFrame, оставляя в нём только пользователей из df,
    совершивших 20 и более международных звонков

    Параметры:
      df: исходный DataFrame

    Возвращаемое значение:
      отфильтрованный DataFrame
    """
    pass
        

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

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

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

# Пример вызывающего кода
import pandas as pd

df = pd.read_csv('data.csv')
businessmen = get_businessmen(df)

Задача 02B. Самый деловой штат (Pandas) ≡

Условие

Требуется на языке Python реализовать функцию get_busiest_states(data: pd.DataFrame)Функция принимает на вход объект DataFrame и возвращает Series, отсортированный по убыванию, в котором штаты являются индексами, а значения — количеством международных звонков в данном штате.

Функция имеет следующий интерфейс

import pandas as pd

def get_busiest_states(data: pd.DataFrame) -> pd.Series:
    """
    Вычисляет Series, в котором индексы - наименования штатов, а значение - количество совершённых международных звонов. 

    Параметры:
      data: DataFrame с данными

    Возвращаемое значение:
      Series отсортированный по убыванию значений.
    """
    pass
        

Формат входного файла

Пример датасета

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

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

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

import pandas as pd
df = pd.read_csv('data.csv')
busiest_states = get_busiest_states(df)
      

State
OH    12
KS     6

Задача 02C. Соединение таблиц (Pandas) ≡

Условие

Требуется на языке Python реализовать функцию join_dataframes(users_df: pd.DataFrame, states_df: pd.DataFrame) Функция принимает на вход два объекта DataFrame и возвращает объединённый DataFrame пользователей и штатов.

Пример таблицы штатов

Пример таблицы пользователей

Функция имеет следующий интерфейс

import pandas as pd

def join_dataframes(data: pd.DataFrame, states: pd.DataFrame) -> pd.DataFrame:
    """
    Возвращает объединённый DataFrame

    Параметры:
      data: DataFrame с пользователями
      states: DataFrame с штатами

    Возвращаемое значение:
      объединённый DataFrame, содержащий поля 'Total day calls', 'Total night calls', 'State' в данном порядке
    """
    pass
        

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

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

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

import pandas as pd

states = pd.read_csv('states.csv', index_col='ID')
data = pd.read_csv('data.csv', index_col='ID')
joined_df = join_dataframes(data, states)

    Total day calls  Total night calls State
ID                                          
1               110                 91    OK
2               123                103    OK
3               114                104    OK
4                71                 89    OK
5               113                121    OK
6                98                118    KS
7                88                118    OH
8                79                 96    NJ
9                70                 12    OK
10               61                311    AL

Задача 02D. fillna_date ≡

Условие

Требуется на языке Python реализовать функцию fillna_date. Функция должна иметь следующий интерфейс:

import pandas as pd

def fillna_date(data: pd.DataFrame, function: str = 'mean') -> pd.DataFrame:
    '''Fills NaN values in every column in `data` with values obtained by applying aggregate `function` over a month.
       If every value within a month is NaN the fill value is obtained over a year.
       If every value within a year is NaN the fill value is obtained over the whole column.

    Arguments:
        data: a pandas DataFrame, with datetime index
        function: aggregate function to be used for obtaining fill value.
            Possible values are: "mean", "median", "max", "min"

    Returns:
        a new pandas DataFrame with NaN values replaced
        '''
    pass

Датафрейм data содержит несколько вещественнозначных колонок, индексируемых объектами типа datetime. Функция fillna_date заменяет значения NaN в каждом столбце датафрейма data на значение, полученное путём применения функции агрегации function внутри соответствующего месяца. Если все значения в этом месяцы равны NaN, новое значение получается из соответствующего года. Если же и все значения в году равны NaN, значение получается из всего столбца. Гарантируется, что в каждом столбце хотя бы одно значение не равно NaN.

Допустимыми значениями параметра function являются строки: "mean", "median", "max", "min".

При решении задачи запрещено применять операторы циклов и условий языка Python для обработки датафрейма.

Входные данные из примера можно скачать здесь.

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

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

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

Задача 03A. Простой график ≡

Условие

Требуется реализовать на языке Python функцию

import matplotlib.pyplot

def draw(plt: matplotlib.pyplot, x: list) -> None:
    pass

График должен быть нарисован зелёным цветом 'green' и содержать координатную сетку. Оси должны быть подписаны, выражение для оси ординат должно быть выражением на языке LaTeX, таким же, как в тексте задачи, в inline режиме отображения математических выражений $...$.

Формат выходного файла

Код решения должен содержать только реализацию функции. Код НЕ должен самостоятельно сохранять изображение в файл или выводить изображение на экран.

Задача 03B. График плотности распределения ≡

Условие

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

import pandas as pd
from typing import Union

def draw_pdf(data: pd.DataFrame, column: str, bins: Union[int, str] = 10) -> None:
    """
        Отображает оценку плотности распределения столбца данных

        Параметры:
            data: таблица данных.
            column: название столбца для отображения.
            bins: спецификация интервалов разбиения, аналогично matplotlib.pyplot.hist.
    """
    pass

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

Формат выходного файла

Код решения должен содержать только реализацию функции и импортируемые модули. Код НЕ должен самостоятельно создавать фигуры или сохранять изображение в файл.

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

См. изображение в тексте задачи

Задача 03C. Столбчатая диаграмма ≡

Условие

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

import pandas as pd

def draw_bars(data: pd.DataFrame, column: str, target_column: str) -> None:
    """
        Отображает долю целевых значений `target_column` при каждом уникальном значении категориального признака `column` в виде слолбчатой диаграммы.

        Параметры:
            data: таблица данных.
            column: название категориального признака.
            target_column: название целевой переменной.
    """
    pass

Стиль оформления графика (цвета, границы, подписи, ширина колонок и т.п.) должен соответствовать представленному ниже. Цвета столбцов должны быть получены из палитры tab10. Вклад долей менее 5% не должен быть подписан на графике.

Формат выходного файла

Код решения должен содержать только реализацию функции и импортируемые модули. Код НЕ должен самостоятельно создавать фигуры или сохранять изображение в файл.

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

См. изображение в тексте задачи

Задача 04A. Градиентный спуск ≡

Условие

Требуется реализовать класс на языке Python, который соответствует следующему интерфейсу.

class GradientOptimizer: def __init__(self, oracle, x0): self.oracle = oracle self.x0 = x0 def optimize(self, iterations, eps, alpha): pass

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

Метод optimize принимает максимальное число итераций для критерия остановки, L2-норму градиента, которую можно считать оптимальной, а также learning rate. Метод возвращает оптимальную точку.

Оракул имеет следующий интерфейс:

class Oracle: def get_func(self, x): pass def get_grad(self, x): pass

x имеет тип np.array вещественных чисел.

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

Код должен содержать только класс и его реализацию. Он не должен ничего выводить на экран.

Задача 04B. Gradient Descent with Momentum ≡

Условие

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

Параметрами алгоритма являются:

• alpha — скорость затухания момента,
• eta — learning rate.

• oracle — оптимизируемая функция,
• x0 — начальная точка,
• max_iter — максимальное количество итераций,
• eps — пороговое значение L2 нормы градиента.

Класс Oracle описывает оптимизируемую функцию:

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

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

Задача 04C. Nesterov Accelerated Gradient ≡

Условие

Требуется реализовать на языке Python класс NesterovAG, который описывает алгоритм ускоренного градиента Нестерова и имеет следующий интерфейс

import numpy as np

class NesterovAG:
    '''Represents a Nesterov Accelerated Gradient optimizer

    Fields:
        eta: learning rate
        alpha: exponential decay factor
    '''

    eta: float
    alpha: float

    def __init__(self, *, alpha: float = 0.9, eta: float = 0.1):
        '''Initalizes `eta` and `aplha` fields'''
        raise NotImplementedError()

    def optimize(self, oracle: Oracle, x0: np.ndarray, *,
                 max_iter: int = 100, eps: float = 1e-5) -> np.ndarray:
        '''Optimizes a function specified as `oracle` starting from point `x0`.
        The optimizations stops when `max_iter` iterations were completed or 
        the L2-norm of the current gradient is less than `eps`

        Args:
            oracle: function to optimize
            x0: point to start from
            max_iter: maximal number of iterations
            eps: threshold for L2-norm of gradient

        Returns:
            A point at which the optimization stopped
        '''
        raise NotImplementedError()

• alpha — скорость затухания момента,
• eta — learning rate.

• oracle — оптимизируемая функция,
• x0 — начальная точка,
• max_iter — максимальное количество итераций,
• eps — пороговое значение L2 нормы градиента.

Класс Oracle описывает оптимизируемую функцию

import numpy as np

class Oracle:
    '''Provides an interface for evaluating a function and its derivative at arbitrary point'''
    
    def value(self, x: np.ndarray) -> float:
        '''Evaluates the underlying function at point `x`

        Args:
            x: a point to evaluate funciton at

        Returns:
            Function value
        '''
        raise NotImplementedError()
        
    def gradient(self, x: np.ndarray) -> np.ndarray:
        '''Evaluates the underlying function derivative at point `x`

        Args:
            x: a point to evaluate derivative at

        Returns:
            Function derivative
        '''
        raise NotImplementedError()

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

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

Задача 04D. AdaGrad ≡

Условие

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

import numpy as np

class AdaGrad:
    '''Represents an AdaGrad optimizer

    Fields:
        eta: learning rate
        epsilon: smoothing term
    '''

    eta: float
    epsilon: float

    def __init__(self, *, eta: float = 0.1, epsilon: float = 1e-8):
        '''Initalizes `eta` and `epsilon` fields'''
        raise NotImplementedError()

    def optimize(self, oracle: Oracle, x0: np.ndarray, *,
                 max_iter: int = 100, eps: float = 1e-5) -> np.ndarray:
        '''Optimizes a function specified as `oracle` starting from point `x0`.
        The optimizations stops when `max_iter` iterations were completed or 
        the L2-norm of the gradient at current point is less than `eps`

        Args:
            oracle: function to optimize
            x0: point to start from
            max_iter: maximal number of iterations
            eps: threshold for L2-norm of gradient

        Returns:
            A point at which the optimization stopped
        '''
        raise NotImplementedError()

• eta — learning rate,
• epsilon — сглаживающий коэффициент.

• oracle — оптимизируемая функция,
• x0 — начальная точка,
• max_iter — максимальное количество итераций,
• eps — пороговое значение L2 нормы градиента.

Класс Oracle описывает оптимизируемую функцию

import numpy as np

class Oracle:
    '''Provides an interface for evaluating a function and its derivative at arbitrary point'''
    
    def value(self, x: np.ndarray) -> float:
        '''Evaluates the underlying function at point `x`

        Args:
            x: a point to evaluate funciton at

        Returns:
            Function value
        '''
        raise NotImplementedError()
        
    def gradient(self, x: np.ndarray) -> np.ndarray:
        '''Evaluates the underlying function derivative at point `x`

        Args:
            x: a point to evaluate derivative at

        Returns:
            Function derivative
        '''
        raise NotImplementedError()

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

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

Задача 04E. RMSProp ≡

Условие

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

import numpy as np

class RMSProp:
    '''Represents an RMSProp optimizer

    Fields:
        eta: learning rate
        gamma: exponential decay factor
        epsilon: smoothing term
    '''

    eta: float
    gamma: float
    epsilon: float

    def __init__(self, *, eta: float = 0.1, gamma: float = 0.9, epsilon: float = 1e-8):
        '''Initalizes `eta`, `gamma` and `epsilon` fields'''
        raise NotImplementedError()

    def optimize(self, oracle: Oracle, x0: np.ndarray, *,
                 max_iter: int = 100, eps: float = 1e-5) -> np.ndarray:
        '''Optimizes a function specified as `oracle` starting from point `x0`.
        The optimizations stops when `max_iter` iterations were completed or 
        the L2-norm of the gradient at current point is less than `eps`

        Args:
            oracle: function to optimize
            x0: point to start from
            max_iter: maximal number of iterations
            eps: threshold for L2-norm of gradient

        Returns:
            A point at which the optimization stopped
        '''
        raise NotImplementedError()

• eta — learning rate,
• gamma — коэффициент затухания,
• epsilon — сглаживающий коэффициент.

• oracle — оптимизируемая функция,
• x0 — начальная точка,
• max_iter — максимальное количество итераций,
• eps — пороговое значение L2 нормы градиента.

Класс Oracle описывает оптимизируемую функцию

import numpy as np

class Oracle:
    '''Provides an interface for evaluating a function and its derivative at arbitrary point'''
    
    def value(self, x: np.ndarray) -> float:
        '''Evaluates the underlying function at point `x`

        Args:
            x: a point to evaluate funciton at

        Returns:
            Function value
        '''
        raise NotImplementedError()
        
    def gradient(self, x: np.ndarray) -> np.ndarray:
        '''Evaluates the underlying function derivative at point `x`

        Args:
            x: a point to evaluate derivative at

        Returns:
            Function derivative
        '''
        raise NotImplementedError()

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

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

Задача 04F. Adam ≡

Условие

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

import numpy as np

class Adam:
    '''Represents an Adam optimizer

    Fields:
        eta: learning rate
        beta1: first moment decay rate
        beta2: second moment decay rate
        epsilon: smoothing term
    '''

    eta: float
    beta1: float
    beta2: float
    epsilon: float

    def __init__(self, *, eta: float = 0.1, beta1: float = 0.9, beta2: float = 0.999, epsilon: float = 1e-8):
        '''Initalizes `eta`, `beta1` and `beta2` fields'''
        raise NotImplementedError()

    def optimize(self, oracle: Oracle, x0: np.ndarray, *,
                 max_iter: int = 100, eps: float = 1e-5) -> np.ndarray:
        '''Optimizes a function specified as `oracle` starting from point `x0`.
        The optimizations stops when `max_iter` iterations were completed or 
        the L2-norm of the gradient at current point is less than `eps`

        Args:
            oracle: function to optimize
            x0: point to start from
            max_iter: maximal number of iterations
            eps: threshold for L2-norm of gradient

        Returns:
            A point at which the optimization stopped
        '''
        raise NotImplementedError()

• eta — learning rate,
• beta1 — коэффициент затухания первого момента,
• beta2 — коэффициент затухания второго момента,
• epsilon — сглаживающий коэффициент.

• oracle — оптимизируемая функция,
• x0 — начальная точка,
• max_iter — максимальное количество итераций,
• eps — пороговое значение L2 нормы градиента.

Класс Oracle описывает оптимизируемую функцию

import numpy as np

class Oracle:
    '''Provides an interface for evaluating a function and its derivative at arbitrary point'''
    
    def value(self, x: np.ndarray) -> float:
        '''Evaluates the underlying function at point `x`

        Args:
            x: a point to evaluate funciton at

        Returns:
            Function value
        '''
        raise NotImplementedError()
        
    def gradient(self, x: np.ndarray) -> np.ndarray:
        '''Evaluates the underlying function derivative at point `x`

        Args:
            x: a point to evaluate derivative at

        Returns:
            Function derivative
        '''
        raise NotImplementedError()

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

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

Задача 05A. Линейная регрессия. Основы ≡

Условие

Требуется реализовать следующие функции на языке Python.

def linear_func(theta, x)                  # function value
def linear_func_all(theta, X)              # 1-d np.array of function values of all rows of the matrix X
def mean_squared_error(theta, X, y)        # MSE value of current regression
def grad_mean_squared_error(theta, X, y)   # 1-d array of gradient by theta

theta — одномерный np.array

x — одномерный np.array

X — двумерный np.array. Каждая строка соответствует по размерности вектору theta

y — реальные значения предсказываемой величины

Матрица X имеет размер M × N. M строк и N столбцов.

Используется линейная функция вида: h_θ(x) = θ₁ x₁ + θ₂ x₂ + ...  + θ_n x_N

Mean squared error (MSE) как функция от θ: J(θ) = 1MM∑i = 1(y_i − h_θ(x⁽ⁱ⁾))². Где x⁽ⁱ⁾ — i-я строка матрицы X

Градиент функции MSE: ∇ J(θ) = { ∂ J∂ θ₁, ∂ J∂ θ₂, ..., ∂ J∂ θ_N}

Пример

X = np.array([[1,2],[3,4],[4,5]])

theta = np.array([5, 6])

y = np.array([1, 2, 1])

linear_func_all(theta, X) # --> array([17, 39, 50])

mean_squared_error(theta, X, y) # --> 1342.0

grad_mean_squared_error(theta, X, y) # --> array([215.33333333, 283.33333333])

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

Код должен содержать только реализацию функций.

Задача 05B. Найти линейную регрессию ≡

Условие

Требуется реализовать функцию на языке Python, которая находит линейную регрессию заданных векторов, используя метрику MSE.

def fit_linear_regression(X, y)   # np.array of linear regression coefs

X — двумерный np.array. Каждая строка соответствует отдельному примеру.

y — реальные значения предсказываемой величины

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

Код должен содержать только реализацию функций.

Задача 05C. МНК: квадратичная зависимость ≡

Условие

Некоторая теоретическая модель предполагает зависимость переменной Y от переменной X по следующему закону: Y = a * X² + b * X + c.

Требуется по N наблюдениям методом наименьших квадратов оценить параметры a, b и c данной модели.

Формат входного файла

Первая строка входного файла содержит одно целое число N.

Следующие N строк содержат по два числа — x_i и y_i

Формат выходного файла

Выходной файл должен содержать три вещественных числа a, b и c с точностью до двух знаков после десятичной точки.

Ограничения

3 ≤ N ≤ 1000

1 ≤ |x_i|, |y_i| ≤ 5000

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

5
4 1
2 3
0 5
3 2
1 4

0.000000 -1.000000 5.000000

6
3 1
4 2
6 2
1 1
5 1
2 10

-0.142857 0.400000 3.600000

Задача 05D. Lasso ≡

Условие

Пусть имеется задача регрессии f(x) = a ⋅ x + b ≈ y. Требуется найти коэффициенты регрессии a, такие, что |{a_i | a_i ∈ a, a_i = 0}| = k,  0 < k ⩽ |a| = m. При этом должно выполняться условие R² = 1 − n∑i = 1(y_i − f(X_i))²n∑i = 1(y_i − y)² ⩾ s. При решении задачи предполагается использование алгоритма Lasso.

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

Данные для обучения содержатся в файле. Качество модели будет рассчитано на скрытом наборе данных

Первая строка входных данных содержит натуральное число N — количество тестов. В следующих N блоках содержится описание тестов. Первая строка блока содержит целые числа n — количество примеров обучающей выборки, m — размерность пространства, k — необходимое количество нулевых коэффициентов, и вещественное число s — минимальное значение метрики R². Следующие n строк содержат по m + 1 вещественному числу — координаты точки пространства и значение целевой переменной y.

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

Решение должно представлять собой текстовый файл содержащий N строк — коэффициенты a и b линейной регрессии разделённые символом пробел.

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

1
10 5 1 0.8
-0.5  -0.26 -0.11 -0.66  0.49 -24.89
 0.08 -0.38  0.6   1.29  0.42  62.2
 0.82  0.12  0.54  1.33 -0.82  47.55
-0.36  0.54 -0.6   0.55 -0.01 -15.96
-0.91 -0.71  0.59  1.0   0.43 -11.11
-0.97 -0.78  0.2  -0.93  1.24 -17.04
 0.29  0.77 -0.87 -0.05 -0.71 -38.97
 0.19 -0.16  1.0   0.63  1.79 188.63
 0.22 -2.38  3.0   0.22 -0.53  23.32
 0.36 -0.84  1.05 -1.06 -0.06  15.31

43.69 0.0 10.48 16.86 46.25 6.39

Задача 06A. k-point crossover ≡

Условие

Требуется на языке Python реализовать методы точечного кроссовера.

Функция single_point_crossover(a, b, point) выполняет одноточечный кроссовер, значения справа от точки кроссовера меняются местами.

Функция two_point_crossover(a, b, first, second) выполняет двухточечный кроссовер, значения между точек кроссовера меняются местами.

Функция k_point_crossover(a, b, points) выполняет k-точечный кроссовер, значения между каждой чётной парой точек меняются местами.

Функции должны иметь следующий интерфейс

import numpy as np

def single_point_crossover(a: np.ndarray, b: np.ndarray, point: int) -> tuple[np.ndarray, np.ndarray]:
    """Performs single point crossover of `a` and `b` using `point` as crossover point.
    Chromosomes to the right of the `point` are swapped

    Args:
        a: one-dimensional array, first parent
        b: one-dimensional array, second parent
        point: crossover point

    Return:
        Two np.ndarray objects -- the offspring"""

    raise NotImplemetnedError()


def two_point_crossover(a: np.ndarray, b: np.ndarray, first: int, second: int) -> tuple[np.ndarray, np.ndarray]:
    """Performs two point crossover of `a` and `b` using `first` and `second` as crossover points.
    Chromosomes between `first` and `second` are swapped

    Args:
        a: one-dimensional array, first parent
        b: one-dimensional array, second parent
        first: first crossover point
        second: second crossover point

    Return:
        Two np.ndarray objects -- the offspring"""

    raise NotImplemetnedError()


def k_point_crossover(a: np.ndarray, b: np.ndarray, points: np.ndarray) -> tuple[np.ndarray, np.ndarray]:
    """Performs k point crossover of `a` and `b` using `points` as crossover points.
    Chromosomes between each even pair of points are swapped

    Args:
        a: one-dimensional array, first parent
        b: one-dimensional array, second parent
        points: one-dimensional array, crossover points

    Return:
        Two np.ndarray objects -- the offspring"""

    raise NotImplemetnedError()

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

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

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

0 1 2 3 4 4 3 2 1 0
9 8 7 6 5 5 6 7 8 9

0 1 2 6 5 4 3 7 8 9
9 8 7 3 4 5 6 2 1 0

0 1 7 6 5 5 6 7 8 0
9 8 2 3 4 4 3 2 1 9
            

Задача 06B. Stochastic universal sampling ≡

Условие

Требуется на языке Python реализовать алгоритм Stochastic universal sampling.

Функция должна иметь следующий интерфейс

import numpy as np

def sus(fitness: np.ndarray, n: int, start: float) -> list:
    """Selects exactly `n` indices of `fitness` using Stochastic universal sampling alpgorithm. 

    Args:
        fitness: one-dimensional array, fitness values of the population, sorted in descending order
        n: number of individuals to keep
        start: minimal cumulative fitness value

    Return:
        Indices of the new population"""

    raise NotImplementedError()

Параметрами функции являются:

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

Функция возвращает список индексов выбранных особей

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

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

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

10 4 1
            

Задача 06C. Распределение задач ≡

Условие

Группа разработчиков работает над проектом. Весь проект разбит на задачи, для каждой задачи указывается ее категория сложности (1, 2, 3 или 4), а также оценочное время выполнения задачи в часах. Проект считается выполненным, если выполнены все задачи. Для каждого разработчика и для каждой категории сложности задачи указывается коэффициент, с которым, как ожидается, будет соотноситься реальное время выполнения задачи данным разработчиком к оценочному времени. Считается, что все разработчики начинают работать с проектом в одно и тоже время и выделяют для работы одинаковое время. Необходимо реализовать программу, распределяющую задачи по разработчикам, с целью минимизировать время выполнения проекта (получить готовый проект за минимальный промежуток времени). Поиск решения необходимо реализовать с помощью генетического алгоритма.

Отправка решения и тестирование

В качестве решения принимается текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

Решение набирает количество баллов, вычисляемое по следующей формуле: Score = 10⁶T_max. T_max — наибольшее среди всех разработчиков время, затраченное на выполнение выданных соответствующему разработчику задач.

Формат входного файла

Первая строка входного файла содержит целое число N количество задач.

Вторая строка — N целых чисел от 1 до 4 категорий сложности задач.

Третья строка — N вещественных положительных чисел оценочного времени для задач.

Четвертая строка – целое число M, количество разработчиков .

Следующие M строк содержат по 4 вещественных положительных числа — коэффициенты каждого разработчика.

Формат выходного файла

Первая и единственная строка выходного файла содержит N целых чисел w_i — номер разработчика, назначенного на i - ю задачу.

Ограничения

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

3
1 1 4
5.2 3.4 4
2
1 1 2 5
0.7 1 1.2 1.5

1 2 2

Задача 06D. Распределение задач. Загрузка решения ≡

Условие

Требуется загрузить решение задачи Распределение задач. Баллы за задачу устанавливаются после ручной проверки отправленного решения.

В качестве решения принимается файл с исходным кодом, которым был получен ответ к задаче. В систему требуется отправить ссылку на файл, размещённый в открытом доступе (Google Colab, Github, Google Drive и др.), указав среду разработки "Answer text". После отправки решение необходимо сдать преподавателю лично до начала зачётной недели.

Распределение баллов

Максимальное количество баллов за задачу — 5.

• По одному баллу выставляется за преодоление каждого из порогов 0.155, 0.16, 0.165.
• Два балла за качество, эффективность решения и использованных методов.

Задача 07A. Логистическая регрессия. Основы ≡

Условие

Пусть задана логистическая регрессия для задачи бинарной классификации

f: X↦ y, X ⊆ Rⁿ, y = { − 1, 1}

f(x, θ) = σ(nx∑iθ_i)

σ(x) = 11 + e^− x

Требуется реализовать следующие функции на языке Python.

import numpy as np

def logistic_func(theta: np.ndarray, x: np.ndarray) -> float:
    """Computes logistic regression value for sample x.
    
    Arguments:
        theta: 1d array of float, regression coefficients
        x: 1d array of float, sample to compute value for
    
    Returns:
        float, logistic regression value
    """
    pass

def logistic_func_all(theta: np.ndarray, X: np.ndarray) -> np.ndarray:
    """Computes logistic regression value for all samples in matrix X.
    
    Arguments:
        theta: 1d array of float, regression coefficients
        X: 2d array of float, row-major matrix of samples
        
    Returns:
        1d array of float, logistic regression values for all samples in matrix X
    """
    pass
    
def cross_entropy_loss(theta: np.ndarray, X: np.ndarray, y: np.ndarray) -> float:
    """Computes binary cross entropy loss for logistric regression with parameters `theta`
    on samples `X` and true labels `y`.
    
    Arguments:
        theta: 1d array of float, regression coefficients
        X: 2d array of float, row-major matrix of samples
        y: 1d array of int, true class lables from set {-1, 1}
        
    Returns:
        float, cross entropy loss value
    """
    pass
    

def grad_cross_entropy_loss(theta: np.ndarray, X: np.ndarray, y: np.ndarray) -> np.ndarray:
    """Computes gradient of binary cross entropy loss for logistic regression
    with parameters `theta` on samples `X` and true values `y`.
    
    Arguments:
        theta: 1d array of float, regresion coefficients
        X: 2d array of float, row-major matrix of samples
        y: 1d array of int, true class labels from set {-1, 1}
        
    Returns:
        1d array of float, cross entorpy gradient with respect to `theta`
    """
    pass

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

Код должен содержать только реализацию функций.

Задача 07B. Poisson regression ≡

Условие

Требуется написать на языке Python класс PoissonRegression, реализующий обобщённую линейную модель, использующую логарифмическую функцию связи

f(x, θ) = exp(n∑i = 1θ_i x_i + θ₀) ,

где n — количество признаков.

Модель оптимизирует следующую функцию потерь

l(X, y, θ) = 1mm∑i = 1(y_ilogy_if(X_i, θ) − y_i + f(X_i, θ)) + α2n∑i = 1θ2i ,

где m — количество примеров, α — параметр регуляризации.

Для оценки качества модели используется метрика D²

D² = 1 − D(y, ŷ)D(y, y) ,

где y — среднее значение вектора y,

D(y, ŷ) = 2mm∑i = 1(y_ilogy_iŷ_i − y_i + ŷ_i) .

Класс должен иметь следующий интерфейс

from __future__ import annotations

import numpy as np


class PoissonRegression:
    r"""Implements a generalized linear model with log link function[1]

        f(x, \theta) = \exp(\sum\limits_{i=1}^n\theta_ix_i + \theta_0)

    The model optimizes the following loss

        l(X, y, \theta) = \frac{1}{m}\sum\limits_{i=1}^n(y_i\log\frac{y_i}{f(X_i, \theta)} - y_i + f(X_i, \theta)) + \frac{\alpha}{2}\sum\limits_{i=1}^n\theta_i^2

    where n, m are numbers of features and samples respectively, $\alpha$ -- regularization strength.

    Parameters:

        use_bias: bool, default = True
            Whether the model uses bias term.

        alpha: float, default = 1
            L2 regularization strength.

    References:

        [1]: https://en.wikipedia.org/wiki/Generalized_linear_model#Link_function
    """
    
    def __init__(self, use_bias: bool = True, alpha: float = 1):
        """Initializes `use_bias` and `alpha` fields."""
        pass


    def predict(self, X: np.ndarray) -> np.ndarray:
        """Computes model value on feature matrix `X`.

        Arguments:

            X: 2d array of float, feature matrix.

        Returns:

            1d array of float, predicted values.
        """
        pass


    def loss(self, X: np.ndarray, y: np.ndarray) -> float:
        """Computes loss value on feature matrix `X` with target values `y`.

        Arguments:

            X: 2d array of float, feature matrix.
            y: 1d array of int, target values.

        Returns:

            loss value
        """
        pass


    def score(self, X: np.ndarray, y: np.ndarray) -> float:
        r"""Computes D^2 score on feature matrix `X` with target values `y`.

        The score is defined as

            D^2 = 1 - \frac{D(y, \hat{y})}{D(y, \overline{y})}

        where D(y, \hat{y}) = 2(y\log\frac{y}{\hat{y}} - y + \hat{y}).

        Arguments:
            
            X: 2d array of float, feature matrix.
            y: 1d array of int, target values.

        Returns:

            score value
        """
        pass


    def fit(self, X: np.ndarray, y: np.ndarray, *,
            eta: float = 1e-3, beta1: float = 0.9, beta2: float = 0.999,
            epsilon: float = 1e-8, tol: float = 1e-3, max_iter: int = 1000) -> PoissonRegression:
        """Optimizes model loss w.r.t model coefficitents using Adam[1] optimization algorithm.
        Initially model coefficients are initialized with zeros.

        Arguments:

            X: 2d array of float, feature matrix.
            y: 1d array of int, target values.
            eta: learning rate.
            beta1: first moment decay rate.
            beta2: second moment decay rate.
            tol: threshold for L2-norm of gradient.
            max_iter: maximal number of iterations.

        Returns:

            self

        References:

            [1]: https://ruder.io/optimizing-gradient-descent/index.html#adam
        """
        pass


    @property
    def coeffs(self) -> np.ndarray:
        """Returns 1d array of float, coefficients used by the model excluding bias term."""
        pass
    

    @property
    def bias(self) -> float:
        """Returns bias term used by the model. If `use_bias = False` returns 0."""
        pass

Для оптимизации должен быть использован алгоритм Adam. Оптимизация начинается с нулевой начальной точки θ = {0}ni = 0.

При решении задачи запрещено использовать любые модули, кроме numpy и scipy.special.

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

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

Задача 08A. KMeans ≡

Условие

Пусть задан некоторый набор точек X = {x_i}ni = 1, x_i ∈ R^m. Требуется выполнить кластеризацию точек на k кластеров, используя наивный алгоритм KMeans.

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

Первая строка входных данных содержит натуральные числа n, m, k, t — количество точек, размерность пространства, количество кластеров и максимальное количество итераций соответственно. В каждой из следующих n строк содержится m вещественных чисел и одно натуральное число — координаты точки и начальное значение кластера точки. Значения кластеров нумеруются от 0 до k − 1.

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

Выходной данные должны содержать n натуральных чисел — номер кластера каждой точки.

Ограничения

6 ⩽ n ⩽ 1000

2 ⩽ m, k ⩽ 10

10 ⩽ t ⩽ 10⁹

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

6 2 2 10
0 0 0
0 3 1
3 0 1
2 5 0
5 2 0
5 5 1

0
0
0
1
1
1

Задача 08B. Science conference ≡

Условие

В городе Плотноскане проходит научная конференция. Студенты местного университета были приглашены на конференцию в последний момент так, что они даже не успели подготовиться и прочитать программу конференции. Конференция проходит в большом зале в m-мерном пространстве. Слушатели собираются около докладчиков, образуя группы. Все члены группы либо имеют f ∈ N соседей на расстоянии не более ε (включая себя), либо находятся на расстоянии не более ε ∈ R от такого члена группы. При этом некоторые участники конференции не слушают доклады, витая в своих мыслях, и, таким образом, не принадлежат никакой из групп. Зная позиции всех участников в зале, помогите студентам определить количество участников в каждой группе, чтобы они могли выбрать наиболее интересные из них. Также, во избежание неопределённости было решено начинать поиск групп рассматривая участников в том порядке, в котором они указаны в списке.

При решении задачи разрешено использовать только стандартные библиотеки Python и библиотеку numpy.

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

Первая строка входного файла содержит числа n, m, ε, f — количество участников конференции, размерность пространства, внутреннее расстояние в группе и минимальное количество соседей. В следующих n строках содержится m вещественных чисел — координаты участников в пространстве.

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

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

Ограничения

50 ⩽ n ⩽ 2750

2 ⩽ m ⩽ 50

0.5 ⩽ ε ⩽ 25

3 ⩽ f ⩽ 15

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

20 22

Задача 08C. Science conference 2 ≡

Условие

В городе Ксреднееве проходит научная конференция. Студенты местного университета были приглашены в последний момент, и поэтому опоздали на начало конференции. Конференция проходит в большом зале в m-мерном пространстве. Слушатели собираются вокруг докладчиков, образуя группы так, что каждый докладчик находится в центре некоторого облака слушателей, при этом с начала конференции докладчики как-то изменили свою позицию. Зная позиции всех слушателей в зале, количество докладчиков и позиции докладчиков на начало конференции, помогите студентам определить текущие координаты докладчиков.

При решении задачи разрешено использовать только стандартные библиотеки Python и библиотеку numpy.

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

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

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

Выходной файл должен содержать k строк по m целых чисел — координаты докладчиков, округлённые к ближайшему целому (половина округляется к ближайшему чётному, round half to even) и отсортированные в порядке возрастания евклидовой нормы точек.

Ограничения

50 ⩽ n ⩽ 7500

2 ⩽ m, k ⩽ 20

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

-2 -6
-8 -16

Задача 09A. Метод ближайших соседей. Основы ≡

Условие

Требуется реализовать следующие функцию на языке Python.

def knn_predict_simple(X, y, x, k)     # array of pairs -- class and number of votes of neighbors

X — двумерный np.array — обучающая выборка

y — реальные значения классов в обучающей выборке

x — одномерный np.array-- тестовый пример

k — количество соседей, которые нужно рассматривать

Функция возвращает массив пар (класс, количество голосов) только для классов которые встречаются среди k ближайших соседей!

Для поиска ближайшего примера использовать евклидово расстояние.

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

Код должен содержать только реализацию функции.

Задача 09B. Leave-one-out (метод скользящего контроля) ≡

Условие

Требуется реализовать функцию leave-one-out score на языке Python. Результат функции должен быть целочисленным, то есть его НЕ следует нормировать на размер выборки.

def loo_score(predict, X, y, k)     # integer loo score for predict function

predict — функция predict(X, y, x, k) , обучающая некоторый алгоритм на выборке X, y с параметром k и дающая предсказание на примере x

X — двумерный np.array — обучающая выборка

y — реальные значения классов в обучающей выборке

k — количество соседей, которые нужно рассматривать

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

Код должен содержать только реализацию функции.

Задача 09C. Border ratio ≡

Условие

Пусть на некотором наборе точек X = {x_i}ni = 1, x_i ∈ R^m задана функция f: R^m↦N. Требуется написать программу, вычисляющую значение border ratio α(x) = ∥x̂ − y∥₂∥ x − y∥₂, ∀ x ∈ X, где y = arg miny ∈ X, f(x) ≠ f(y)∥ x − y∥₂, x̂ = arg minx̂ ∈ X, f(x) = f(x̂)∥x̂ − y∥₂.

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

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

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

Выходной файл должен содержать n вещественных чисел — значения border ratio каждой точки с точностью не менее трёх знаков после запятой.

Ограничения

6 ⩽ n ⩽ 1500

2 ⩽ m ⩽ 50

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

6 2
0 0 0
0 2 1
1 2 0
4 2 1
3 0 1
4 0 0

0.5 1.0 1.0 0.5 1.0 1.0

10 2
0 0 0
0 2 0
4 2 0
6 2 0
4 4 1
6 1 1
6 6 1
0 5 2
0 6 2
0 7 2

0.6 1.0 1.0 1.0 1.0 1.0 0.25 1.0 0.75 0.6

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

Условие

Пусть задан некоторый язык, описываемый множеством слов W, |W| = m, m ∈ N. Требуется построить наивный байесовский классификатор f: B↦ C = {i}k − 1i = 0, где {0, 1}^m ⊇ B = ⋃l ∈ N,μ ∈ W^l{δ_w(μ)|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 и его класса c_i
1. Получить предсказание ^c_i по μ_i с использованием текущего классификатора;
2. Обновить классификатор с использованием сообщения μ_i и настоящего значения его класса c_i.

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

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

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

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

Ограничения

10 ⩽ n ⩽ 7500

8 ⩽ m ⩽ 100

2 ⩽ k ⩽ 10

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

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

Задача 10B. Байесовский классификатор ≡

Условие

Пусть задано вещественное пространство Rⁿ. Требуется написать программу, классифицирующую точки с использованием байесовского классификатора B(x) = arg maxi = 0,m − 1(π_i f_{Nk(μi, Σi)}(x)m − 1∏j = 0,i ≠ jλ_i,j), где m — количество классов, π_i — априорная вероятность класса, f_{Nk(μi, Σi)} — функция плотности многомерного нормального распределения N_k(μ_i, Σ_i) со средним μ_i и матрицей ковариации Σ_i, λ_i,j — штраф за ошибочною классификацию класса i в качестве класса j.

Формат входного файла

Первая строка входного файла содержит натуральные числа n, m, k, l — размерность пространства, количество классов, количество элементов обучающей и тестовой выборок соответственно. Далее следуют значения матрицы λ — m строк по m натуральных чисел. Далее следуют k строк обучающей выборки в формате x_i,0, x_i,1, …, x_{i,n − 1}, c_i, где x_i,j вещественные числа — координаты точки i, c_i ∈ {0,1,…,m − 1} — класс точки. Последние l строк содержат по n вещественных чисел — координаты точек тестовой выборки.

Формат выходного файла

Выходной файл должен содержать l целых чисел — предсказанные классы точек тестовой выборки.

Ограничения

n ∈ {2, 3}

2 ⩽ m ⩽ 9

2 ⩽ k, l ⩽ 10³

1 ⩽ λ_i,j ⩽ 5

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

2 2 6 2
0 1
1 0
1 1 0
1 2 0
2 1 0
-1 -1 1
-1 -2 1
-2 -1 1
2 2
-2 -2

0 1

Задача 11A. Устный экзамен ≡

Условие

Билет выбирается независимо и случайно из следующего списка:

Экзамен проводится очно. В случае невозможности очного присутствия необходимо заранее договориться с преподавателем о дистанционной сдаче.

После взятия билета студент готовится в ответу. При подготовке можно использовать произвольные материалы и доступ в Интернет.

В докладе необходимо максимально кратко упомянуть все важные элементы доставшейся темы/вопроса. После доклада преподаватель задаёт несколько уточняющих вопросов. Время на ответ 10 минут + 5 минут на вопросы.

Задача 12A. Science conference 3 ≡

Условие

В городе Оптике проходит научная конференция. Студенты местного университета были приглашены на конференцию и уже провели несколько часов на ней, при этом сама конференция проходит в большом зале в m-мерном пространстве. Преподаватель, пришедший на конференцию вместе со студентами, решил для каждого участника выяснить минимальное расстояние, на котором он может быть достигнут из позиции другого участника. При этом, чтобы сделать задачу полее интересной, преподаватель решил использовать более интересный способ определения расстояния. Каждому из участников требуется не менее f ∈ N соседей на расстоянии не более ε ∈ R (включая себя), чтобы из его позиции можно было достичь других участников. При этом, расстояние до такого участника не может быть меньше, чем расстояние, на котором могут быть достигнуты ровно f участников. Зная позиции всех участников в зале, помогите преподавателю вычислить это расстояние. Во избежание неопределённости было решено рассматривать участников в том порядке, в котором они указаны в списке, при этом достижимых участников стоит рассмотреть в первую очередь, перед переходом к следующему в списке, и не рассматривать одного и того же участника более одного раза.

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

Первая строка входного файла содержит числа n, m, ε, f — количество участников конференции, размерность пространства, максимальное достижимое расстояние и минимальное количество соседей. В следующих n строках содержится m вещественных чисел — координаты участников в пространстве.

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

В первой строке выходного файла выведите n вещественных чисел с точностью не менее 3-x знаков после запятой — расстояние на котором достижим каждый из участников. Во второй строке выведите n целых чисел — индекс участника из которого достижим данный. Если участник не достижим, следует вывести  − 1 в обоих случаях.

Ограничения

50 ⩽ n ⩽ 2500

2 ⩽ m ⩽ 50

0.5 ⩽ ε  < ∞

3 ⩽ f ⩽ 15

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