В 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. Подробности о том, как сгенерировать отчёт о покрытии кода тестами для обнаружения непокрытых строк кода, приведены в этом сообщении.

В случае, если при проверке реализации конечного автомата ЦАП обнаружена ошибка, для её локального воспроизведения можно воспользоваться данными из ЦАП и следующим кодом:

def trace(x, y):
    tr = str.maketrans({'[': '(', ']': ')'})
    for (op, *args), o in zip(x, y[:-1]):
        call = f'obj.{op}{args} # {repr(o)}'
        yield call.translate(tr)

# Получено:
y = [None, None, False, None, 'unknown',
     'X1', False, 'X1', 'unsupported',
     '<<< Ошибка!']

# Входные данные: 
x = (('assign_r', 0), ('assign_z', 1),
     ('seen_edge', 'C4', 'C1'),
     ('assign_k', 0), ('run', 'begin'),
     ('run', 'step'),
     ('seen_edge', 'C0', 'C1'),
     ('run', 'make'), ('run', 'step'),
     ('assign_r', 1), ...)

# Генерация трассы:
print('\n'.join(trace(x, y)))

При помощи функции trace можно сгенерировать код на Python, воспроизводящий ошибку, возникшую при проверке решения в ЦАП:

obj.assign_r(0) # None
obj.assign_z(1) # None
obj.seen_edge('C4', 'C1') # False
obj.assign_k(0) # None
obj.run('begin') # 'unknown'
obj.run('step') # 'X1'
obj.seen_edge('C0', 'C1') # False
obj.run('make') # 'X1'
obj.run('step') # 'unsupported'
# ^^^ Ошибка!

Из полученной выше трассы следует, что вызов obj.run('step') вернул ошибочное значение unsupported после изменения состояния системы вызовами методов выше.

На следующем шаге отладки кода необходимо сравнить вашу реализацию конечного автомата с графом переходов между состояниями из постановки задачи, найти несоответствие в методе run('step') и устранить его. После устранения всех несоответствий решение будет зачтено ЦАП.

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

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

💡 На примере отечественной СУБД 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. Реализовать функцию для преобразования битовых полей.

Послезавтра начинаются зачеты по нашей дисциплине. В этой связи всем желаю успеха!

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

ИКБО-70-23
ИКБО-71-23
ИКБО-72-23
ИКБО-73-23
ИКБО-74-23
ИКБО-75-23
ИНБО-10-23
ИНБО-11-23
ИНБО-12-23
ИНБО-13-23

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

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

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

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

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

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

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

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

⚙ За весенний семестр 2025-го года ЦАП было проверено более 235 000 программ. Подробности приведены в PDF-файле, графики построены кодом на Python с использованием matplotlib.