В 4-й задаче ЦАП предлагается реализовать функцию по рекуррентной формуле. Простейший способ решения задачи — реализовать формулу в виде рекурсивной функции:

from math import sin


def main(n):
    if n == 0:
        return 0.37
    p = main(n - 1)
    return p**3 - p**2 - sin(p)

Временная сложность этой функции равна O(n). Пространственная сложность также равна O(n), так как при каждом рекурсивном вызове main на стек вызовов добавляется новый кадр.

От рекурсивных вызовов легко избавиться, запоминая вычисленные значения функции в списке:

from math import sin


def main(n):
    vals = [0.37]
    for _ in range(n):
        p = vals[-1]
        vals.append(p**3-p**2-sin(p))
    return vals[-1]

Легко заметить, что запоминать все вычисленные значения в списке совсем не обязательно, достаточно запомнить последнее вычисленное значение:

from math import sin


def main(n):
    p = 0.37
    for _ in range(n):
        p = p**3 - p**2 - sin(p)
    return p

Вычислительная сложность функции по-прежнему равна O(n), а пространственная сложность функции снизилась и теперь равна O(1).

6-я задача ЦАП посвящена работе с множествами. Перечень общепринятых математических обозначений, которые можно встретить в постановке этой задачи, мы уже публиковали ранее.

Для решения задачи полезно воспользоваться set comprehensions, синтаксис которых близок к математической форме записи множества.

Пригодятся также агрегирующие функции, такие как len, sum, math.prod, any, all:

from math import floor


def main(Ω):
    E = {floor(w / 7) - abs(w)
         for w in Ω
         if not 26 < w < 76}
    O = {w ** 2 - 7 * w
         for w in Ω
         if not -8 <= w <= 52}
    Λ = {floor(e / 9)
         for e in E
         if not -43 <= e < 48}
    H = {3 * o
         for o in O
         if any(λ < o for λ in Λ)}
    Δ = {7 * λ
         for λ in Λ
         if all(η >= λ for η in H)}
    return len(H | Δ) - sum(Δ)

Внимательный читатель заметит, что ЦАП отклонит код выше, поскольку одна из переменных называется O и программист может спутать такое имя с нулём 0 (правило E741). Исправить код легко — достаточно изменить имя переменной.

Эту задачу можно решить и без set comprehensions, заполняя множества элементами в обычном цикле. В этом случае код, вычисляющий множества, придётся разделить на отдельные функции, чтобы снизить когнитивную сложность функции main.

Сегодня разберём 7-ю задачу. В этой задаче предлагается реализовать дерево решений. При выборе пути по дереву от корня к листьям необходимо сравнивать значения в метках вершин с метками ребер.

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

Для упрощения функции полезно преобразовать код, вычислять поддеревья в отдельных функциях:

def f2(x, left, middle, right):
    if x[2] == 1998:
        return left
    if x[2] == 2018:
        return middle
    return right


def f1(x, left, right):
    if x[1] == "BISON":
        return left
    return right


def f0(x):
    if x[0] == 2006:
        return 1
    return 2


def f3(x):
    if x[3] == 2001:
        return f1(x, f0(x), f2(x, 3, 4, 5))
    if x[3] == 1959:
        return 6
    return f2(x, 7, 8, f1(x, 9, 10))
  

def main(x):
    if x[4] == 1981:
        return f3(x)
    if x[4] == 1987:
        return 11
    return 12

При таком подходе функции легко переиспользовать, если поддерево встречается в дереве несколько раз (см. f1 и f2). Преобразования кода такого рода называются рефакторингом.

В приведённом коде условный оператор может быть заменён оператором match. В других способах решения деревья описываются вложенными словарями, списками, иерархиями объектов.

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

Для решения этой задачи необходимо воспользоваться побитовыми операциями — сдвигом бит влево <<, сдвигом бит вправо >>, побитовым «и» &, побитовым «или» |:

def main(q):
    q1 = q & 0b1
    q2 = q >> 1 & 0b11111
    q4 = q >> 15 & 0b111111
    q5 = q >> 21 & 0b111111111
    p = 0
    p |= q1 << 29
    p |= q2 << 15
    p |= q4
    p |= q5 << 6
    return hex(p)

Сдвиг вправо a >> b возвращает новое число на основе числа a, биты которого сдвинуты на b позиций вправо, b младших бит числа при этом отбрасываются. Этот вариант сдвига вправо называется логическим (освободившиеся старшие b позиций заполнены нулями), существует еще и арифметический сдвиг вправо, но в этой задаче он не требуется.

Сдвиг влево a << b возвращает новое число на основе числа a, биты которого сдвинуты на b позиций влево, b младших бит числа после сдвига заполняются нулевыми битами.

Для извлечения бит с нужными номерами из исходного числа используются специально подготовленные константы — битовые маски. Побитовое «и» a & mask позволяет выбрать из a только те биты, которые являются единичными в mask. Битовые маски можно генерировать и автоматически.

Побитовое «или» a | b позволяет выбрать все единичные биты из a и b, запись a |= b эквивалентна записи a = a | b. Таким образом можно «собрать» несколько битовых полей воедино.

Для отладки решений этой задачи полезно воспользоваться функцией bin, возвращающей двоичное представление числа:

>>> bin(42)
0b101010
>>> 0b101010
42

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

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

Для решения этой задачи полезно воспользоваться регулярными выражениями, а для их отладки пригодятся такие сервисы, как regex101.com и regexr.com:

import re


def main(s):
    r = r'declare\s*(\w+)\s*=\s*(\w+)'
    return re.findall(r, s)

Приведённое в коде выше регулярное выражение сначала распознаёт строку declare, после чего пропускает от 0 до ∞ пробельных символов \s за счёт использования звезды Клини * после \s. Круглые скобки в регулярном выражении (\w+) позволяют сгруппировать символы, распознанные шаблоном внутри скобок. Шаблон \w+ распознаёт последовательность символов, содержащую от 1 до ∞ цифр, букв или символов нижнего подчеркивания _. Шаблон \w — это краткая форма записи шаблона [a-zA-Z0-9_].

Затем шаблоном \s* вновь распознаётся от 0 до ∞ пробельных символов, после чего распознаётся символ =, за которым могут следовать пробелы \s*. После этого создаётся ещё одна группа из букв, цифр, нижних подчеркиваний (\w+).

В результате вызова функции findall из модуля re из строки s извлекаются все подстроки, распознанные регулярным выражением r, в виде списка пар. Поскольку по постановке задачи функция main должна возвратить список пар, результат работы findall в этом варианте задачи не нужно дополнительно обрабатывать.

Другой способ решения задачи основан на разборе текста без использования модуля re, при помощи стандартных методов — split, replace и др.

💡 Попробуйте догадаться, из какой семинарской задачи были получены эти необычные имена во входных строках!

В 10-й задаче ЦАП необходимо реализовать функцию для обработки табличных данных. Таблицы заданы в построчной форме, с помощью списков:

[[None, '17/07/99', '6435068741', 'Нет',
  None, 'domasak69@mail.ru', 'Нет'],
 [None, '09/05/04', '4212116149', 'Нет',
  None, 'georgij1@gmail.com', 'Нет'],
 [None, None, None, None, None, None, None],
 [None, '10/04/02', '4684345477', 'Да',
  None, 'miroslav51@gmail.com', 'Да']]

Функция main принимает на вход и возвращает list[list[str]]. Для решения задачи можно воспользоваться циклами и условными операторами — обойти все строки таблицы и определённым образом их обработать, но для упрощения кода мы воспользуемся списковыми включениями:

def transpose(m):
    size = len(min(m, key=len))
    return [[row[i] for row in m]
            for i in range(size)]


def main(m):
    m = [[val for val in row if val]
         for row in m if any(row)]
    m = [[f'{d[6:]}/{d[3:5]}/{d[:2]}',
          f'{p[:3]}-{p[3:6]}-{p[6:]}',
          str(mark == 'Да').lower(),
          mail.split('@')[1]]
         for d, p, mark, mail, _ in m]
    return transpose(m)

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

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

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

В результате получим следующую таблицу, имеющую тип list[list[str]]:

[['99/07/17', '04/05/09', '02/04/10'],
 ['643-506-8741', '421-211-6149', '468-434-5477'],
 ['false', 'false', 'true'],
 ['mail.ru', 'gmail.com', 'gmail.com']]

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

def transform(row):
    d, p, mark, mail, _ = row
    d = f'{d[6:]}/{d[3:5]}/{d[:2]}'
    p = f'{p[:3]}-{p[3:6]}-{p[6:]}'
    mark = str(mark == 'Да').lower()
    mail = mail.split('@')[1]
    return d, p, mark, mail


def main(m):
    m = map(lambda r: filter(bool, r), m)
    m = filter(bool, map(list, m))
    m = map(transform, m)
    return list(map(list, zip(*m)))

В правой части 1-го присваивания из таблицы удаляются пустые ячейки — функция filter возвращает генератор, возвращающий только те элементы исходного списка r, для которых выполняется поданный на вход предикат bool, используется свойство bool(None) == False. В правой части 2-го присваивания из таблицы удаляются пустые строки — используется свойство bool([]) == False.

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

В 11-й задаче ЦАП необходимо реализовать конечный автомат Мили или Мура в виде класса. Ответы на часто задаваемые вопросы по задаче приведены в этом сообщении, а ниже показан пример реализации конечного автомата Мура по графу переходов между состояниями:

class MooreMachine:
    def __init__(self):
        self.state = "d0"
        self.vs = {}

    def get(self):
        match self.state:
            case "d0":
                self.state = "d0"
            case "d5":
                self.state = "d2"
            case _:
                return "unsupported"

    def forge(self):
        match self.state:
            case "d0":
                self.state = "d5"
            case "d1":
                self.state = "d4"
            case "d2":
                self.state = "d1"
            case _:
                return "unsupported"

    def coat(self):
        match self.state:
            case "d5":
                self.state = "d4"
            case _:
                return "unsupported"

    def set_var(self, var, val):
        self.vs[var] = val

    def skip(self):
        match self.state:
            case "d1":
                self.state = "d5"
            case "d4" if self.vs["d"] == 0:
                self.state = "d3"
            case "d4" if self.vs["d"] == 1:
                self.state = "d0"
            case _:
                return "unsupported"

    def get_output(self):
        match self.state:
            case "d0" | "d2" | "d3":
                return "F1"
            case "d1" | "d4":
                return "F3"
            case "d5":
                return "F2"

    def has_max_out_edges(self):
        states = ['d5', 'd1', 'd4']
        return self.state in states

    def __getattr__(self, name):
        return lambda: "unknown"

Как видно из приведённого выше кода, меткам рёбер в графе переходов между состояниями автомата Мура соответствуют имена методов класса MooreMachine. Выходной сигнал автомата Мура зависит только от текущего состояния автомата, его можно получить, вызвав метод get_output.

При вызове методов обновляется значение поля state, причём новое состояние автомата зависит не только от вызванного метода, но и от старого состояния state. В некоторых переходах (см. skip) новое состояние автомата зависит не только от старого состояния, но и от значения дополнительной переменной d. Для установки значения d в этом варианте задачи используется метод set_var.

Для упрощения реализации класса вместо условного оператора if в методах используется оператор сопоставления с образцом match (PEP 636). Перегрузка метода getattr позволяет обработать вызовы несуществующих методов.

Обратите внимание, что в каждом варианте задачи необходимо также реализовать функцию main, возвращающую экземпляр класса конечного автомата, и функцию test, тестирующую конечный автомат. Ниже приведён пример реализации функции test:

def main():
    return MooreMachine()


def test():
    obj = main()
    obj.get()
    obj.forge()
    obj.get()
    obj.forge()
    obj.forge()
    obj.set_var('d', 0)
    obj.skip()
    assert obj.state == 'd3'
    assert obj.get_output() == 'F1'
    assert obj.dance() == 'unknown'
    assert obj.walk() == 'unknown'
    ...

Для достижения 100%-го покрытия кода тестами необходимо посетить все возможные ветви выполнения программы в функции test. Подробности о том, как сгенерировать отчёт о покрытии кода тестами для обнаружения непокрытых строк кода, приведены в этом сообщении.

📚 В РТУ МИРЭА пройдёт открытая встреча, посвящённая индустрии систем управления базами данных (СУБД) в России и мире.

💡 На примере отечественной СУБД Picodata её разработчики, среди которых есть выпускники МИРЭА, расскажут участникам:

• Кто использует свободно распространяемое ПО и зачем;
• Как найти свою технологическую нишу в конкурентной среде;
• Какие технологии и проблемы наиболее актуальны в области СУБД сегодня;
• Как устроены процессы разработки и тестирования в Picodata;
• Какие языки программирования применяются при разработке СУБД и где используется Python;
• Какой может быть архитектура СУБД будущего.

📅 Дата и время: 28 мая, 13:00
📍 Место проведения: Техноковоркинг
🔗 Регистрация: vk.cc/cM7w32

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

📚 28 мая Константин Осипов, основатель Picodata, управляющий директор по R&D Arenadata, создатель Tarantool и член программного комитета конференции Highload++, а в прошлом — разработчик систем управления базами данных (СУБД) MySQL и ScyllaDB, рассказал студентам института ИТ об истории развития СУБД и о современных подходах к разработке СУБД. По просьбам слушателей прикрепляем слайды с прошедшего мероприятия.

❗️ Обратите внимание, 5-го июня приём решений задач ЦАП будет остановлен.

💡 Убедительно просим старост повторно уведомить одногруппников о необходимости решения 11 задач ЦАП для получения допуска до зачёта, это касается всех студентов без исключения.

📚 Разбор решений всех 11 задач ЦАП уже опубликован на канале курса @kispython.

Информация о зачётах

❗️До зачёта допускаются только те студенты, кто решил в течение семестра все 11 домашних задач ЦАП. В зависимости от набранного числа баллов, студенту на зачёте необходимо решить 2, 1 на выбор или 0 задач. Приём решений задач ЦАП будет остановлен 5 июня в 23:00.

Вариант студента на зачёте определяется согласно списку группы. На зачёт система ЦАП выдаёт студентам ссылки на случайные задачи, определяемые тройкой (вариант, группа, номер).

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

Тип второй задачи выбирается случайно из списка:
7. Реализовать функцию для вычисления дерева решений.
8. Реализовать функцию для преобразования битовых полей.

Вы пользовались ЦАП в течение семестра и сейчас, в последние дни зачётной недели, удачное время для перечисления фактов о системе, которые интересовали студентов.

📖 1. Веб-приложение ЦАП написано на Питоне, его исходный код открыт и доступен на GitHub. См. статью в IEEE Xplore.

📚 2. Генератор задач — закрытый сторонний модуль ЦАП, в котором для порождения уникальных задач используется подход на основе программирования в ограничениях, гарантирующий, в отличие от нейронных сетей, корректность построения задач. См. статью на arXiv и запись выступления на PiterPy.

🏖 3. Проверка программ осуществляется в песочнице, реализованной в виде Docker-контейнера с ядром gVisor для безопасного запуска кода студентов.

📚 4. Для определения способов решения задач по текстам программ в ЦАП используются алгоритмы кластеризации и классификации. См. статьи в журналах Future Internet и Вестник РГРТУ.

🧑‍💻 5. В ЦАП поддерживается автоматическая проверка когнитивной сложности — сложности восприятия кода читателем. См. статью в журнале Computers.

⚙️ 6. ЦАП развёрнут на виртуальном сервере с одноядерным процессором и 1 Гб оперативной памяти с СУБД SQLite. За весенний семестр 1 593 пользователя прислали более 235 000 программ, все программы были автоматически проверены.

🏆 7. Проект «Цифровой ассистент преподавателя» вошёл в шорт-лист международной университетской премии в области искусственного интеллекта «Гравитация-2025» в номинации «Инновации в образовательном процессе и подготовке кадров».