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

Первый блок из 6 задач ЦАП помогает увидеть связь между математическими формулами и кодом на Python. С умением переводить математические формулы в код вы сможете использовать передовые научные идеи в своих проектах.

Задача №6 ЦАП имеет отношение к операциям над множествами. Давайте попрактикуемся работать с этим типом данных.

Предположим, что требуется найти множество всех подмножеств (такое множество еще называется power set) для заданного множества. Может ли эта задача возникнуть на практике? Вполне. Например, в машинном обучении есть специальный вариант классификации под названием Label Powerset.

Вот простая реализация алгоритма нахождения power set:

def get_powerset1(sequence):
    powerset = {frozenset()}
    for elem in sequence:
        powerset |= {subset | {elem} for subset in powerset}
    return powerset

На каждой итерации мы добавляем к текущему powerset его варианты с очередным элементом elem. Попробуйте разобраться, зачем понадобилось вводить frozenset.

А вот еще одна реализация, с использованием библиотеки itertools:

from itertools import combinations

def get_powerset2(sequence):
    return {frozenset(comb)
            for size in range(len(sequence) + 1)
            for comb in combinations(sequence, size)}

Здесь combinations выдает все комбинации заданной длины из элементов последовательности.

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

Продолжаем публикацию вспомогательных материалов для задач на перевод математической нотации формы записи множества в код. Приведённые примеры кода не являются единственно возможным способом реализации указанных формул, при решении задач полезно обращаться к стандарту PEP 289, модулю functools, лекциям курса.

Успешное выполнение творческих проектов позволяет не только решить 0 задач на зачёте, но и опубликовать статью или получить опыт участия в проекте с открытым кодом.

📖 Павел Саломатин написал статью «JIT-компилятор Python в 300 строк». Его статья получила больше голосов на Habr, чем статьи многих профессиональных разработчиков.

📚 Научная статья Кирилла Павлова «Библиотека llvm2py для анализа промежуточного представления LLVM и её применение в оценке степени распараллеливания линейных участков кода» опубликована в журнале, входящем в Перечень ВАК. Кроме того, полученные результаты были представлены на международной научной конференции.

А вот несколько примеров выполненных доработок ЦАП.

💻 Сергей Дмитриев по собственной инициативе подключил к ЦАП удобный редактор кода, а также добавил в ЦАП поддержку входа через систему аутентификации РТУ МИРЭА.

🔍 Владислав Кнышов добавил возможность просмотра списка отправленных решений задач ЦАП, а Олег Цветков добавил поддержку просмотра решений, отправленных в ЦАП в режиме зачёта.

📊 Дмитрий Луковников разработал рейтинг студентов по числу открытых способов решения.

🎮 Олег Токарев реализовал панель управления зачётом ЦАП, а Арсений Коротков улучшил постраничную навигацию по спискам решений в кабинетах студента и преподавателя.

📈 Софья Быкова нарисовала логотип ЦАП, а Ярослав Сизиков и Михаил Гальцев улучшили покрытие кода тестами, добавив автоматические тесты для преподавательской и страницы входа.

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

📚 В ЦАП есть автоматическая проверка кода на соответствие стандарту PEP8 и на когнитивную сложность. Остановимся подробнее на последней.

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

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

1. Штраф +1 за каждую конструкцию, которая содержит ветвления (controlflowbreak).
2. Добавляем +1 к штрафу за каждый уровень вложенности конструкций, которые содержат ветвления (nesting).
3. Штраф +1 за переиспользование имени переменной в новом контексте (redefine).

В реальности когнитивная сложность в ЦАП оценивается несколько сложнее. Подробности можно узнать в исходном коде, а также в статье.

🎉 В честь Дня рождения Института информационных технологий 25 апреля на платформе ЦАП будут проводиться соревнования по программированию на языке Python. Для участия в мероприятии необходимо зарегистрироваться, доступно 200 мест:
https://t.me/vika_iit/16/444

🥇 20 победителей смогут посетить экскурсии в офисы «Яндекс» или «ВКонтакте», которые проведут выпускники Института ИТ!

🏅 Кроме того, студенты нашего курса, успешно справившиеся со всеми задачами на соревновании, получат дополнительные баллы активности на семинарах. А каждый из 20 победителей получит до +10 баллов активности.

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

Например, для транспонирования матрицы, заданной в построчной форме, с помощью кортежей, можно воспользоваться функцией zip:

table = tuple(zip(*table))

Функция zip объединяет i-е элементы поданных на вход последовательностей, возвращая генератор. Функция tuple преобразует генератор в кортеж.

Начиная с версии Python 3.6 для удаления дубликатов строк из таблицы можно воспользоваться словарём:

table = tuple(dict.fromkeys(table))

Порядок ключей в словаре соответствует порядку их вставки, а при добавлении дубликата ключа обновляется только соответствующее ему значение. Метод fromkeys создаёт словарь с ключами из поданной на вход последовательности и со значениями None.

Для сортировки строк таблицы можно воспользоваться функцией sorted:

table = sorted(table, key=
    lambda row: row[0])

В качестве ключа в sorted указана анонимная функция, возвращающая значение, по которому следует отсортировать элементы последовательности.

📚 В заключительной 11-й задаче ЦАП предлагается реализовать конечный автомат Мили или Мура в виде класса.

В автомате Мура реакция на входное слово (на вызов метода объекта) зависит только от текущего состояния автомата (значения поля объекта). В автомате Мили реакция на входное слово зависит и от текущего состояния автомата, и от входного слова.

🔄 Для автомата Мура в метках вершин графа указывается "состояние / выходной сигнал". Для автомата Мили в метках дуг указывается "входной сигнал / выходной сигнал".

После реализации конечного автомата в виде класса необходимо написать для него тесты в функции test, при этом требуемая степень покрытия кода тестами (branch coverage) — 100%.

📊 Для выявления непокрытых тестами строк в программе полезно генерировать отчёты о покрытии кода в формате HTML при помощи coverage и pytest:

pip install coverage pytest

Для запуска тестов в program.py и генерации отчёта о покрытии кода тестами достаточно выполнить:

coverage run --branch -m pytest program.py
coverage report
coverage html

✅ В результате будет создана директория htmlcov с файлом index.html, содержащим отчёт о покрытии кода тестами, который можно открыть в веб-браузере (см. видеозапись).

Подробности об инструментах coverage и pytest можно найти в конспекте 5-й лекции нашего курса.

Вопросы и ответы по 11-й задаче

🤔: Что вообще от нас хотят?
🎓: Реализовать конечный автомат по графу: состояния — вершины, переходы — дуги. Подробнее см., например, в книге Автоматное программирование.

🤔: Что за автомат Мура или Мили?
🎓: Мура: выход по состоянию (get_output). Мили: выход по переходу (возвращается методом перехода).

🤔: Как узнать начальное состояние?
🎓: Начальное состояние указано на графе стрелкой без начала.

🤔: Эта стрелка является настоящей входной дугой?
🎓: Нет, не является.

🤔: Начальное состояние является посещенным?
🎓: Да, автомат стартует в начальном состоянии, считая его посещенным.

🤔: А если из состояния есть несколько одинаковых переходов?
🎓: Используется переменная, заданная, например, методом set_var(имя, значение), для выбора перехода.

🤔: Каким должно быть значение этих переменных по умолчанию?
🎓: Выберите любое разумное значение (например, 0).

🤔: Как перехватить обращение к несуществующему методу?
🎓: Придется переопределить __getattr__.

🤔: Как тестировать исключения?
🎓: Перехватывайте их в тестах или напишите аналог pytest.raises.

🤔: Тестировать надо только класс или весь модуль?
🎓: Весь модуль, включая main, см. подробнее здесь.

🚀 Среди тестировщиков 11-й задачи был ваш сверстник. Его зовут Кирилл, он является core-разработчиком проекта CPython — официальной реализации языка, который вы сейчас изучаете.

👨‍💻 Подробнее об опыте работы Кирилла в CPython можно почитать в его статье «Как я стал core-разработчиком Python в 19 лет».

😱 До конца семестра осталось совсем немного времени!

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

🎁 Тем временем, специально для подписчиков нашего канала мы подготовили цикл публикаций шпаргалок по решению задач ЦАП!

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

from math import cos, log


def main(z):
    if z < 46:
        return 89 * z ** 3 - 57 * z ** 4
    if 46 <= z < 82:
        return cos(z) ** 2 - 1 - \
               log(92 * z ** 3, 10) ** 6
    if 82 <= z < 180:
        return 49 * (32 * z ** 3) ** 7 + \
               71 * z ** 4 + z ** 2
    return z ** 3

Другие способы решения включают решение при помощи match или словаря. По способам решения 1-й задачи есть информация в СДО.

⚙️ Обратите внимание, что в коде отсутствует print, а функция называется main — так ЦАП сможет вашу функцию обнаружить и проверить.

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

3 следующих друг за другом символа Σ в формуле соответствуют 3 вложенным циклам, вложенные циклы в Python легко описать при помощи отступов:

from math import sin


def main(b, n, a):
    total = 0
    for c in range(1, a + 1):
        for i in range(1, n + 1):
            for j in range(1, b + 1):
                x = sin(c ** 2)
                y = i ** 3
                z = 33 * j ** 5
                total += x + y + z
    return total

Вычислительная сложность функции main равна O(a*n*b) — тело последнего цикла выполнится a*n*b раз.

Другой способ решения этой задачи — воспользоваться выражениями-генераторами из PEP 289:

from math import sin


def main(b, n, a):
    return sum(
        sin(c**2) + i**3 + 33*j**5
        for c in range(1, a + 1)
        for i in range(1, n + 1)
        for j in range(1, b + 1))

Вычислительная сложность функции main от этого не изменится, но код сократится.

В 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).

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

Основная сложность этой задачи в том, что компоненты вектора принято нумеровать начиная с единицы, а нумерация индексов элементов списка в Python начинается с 0.

Привести списки в соответствие с векторами можно, добавив в начало каждого списка элемент-заглушку. Вот пример такого решения с помощью метода insert:

import math


def main(z, x, y):
    n = len(z)
    z.insert(0, 0)
    x.insert(0, 0)
    y.insert(0, 0)
    s = 0
    for i in range(1, n + 1):
        a = x[n + 1 - math.ceil(i / 4)]
        b = 43 * z[n + 1 - i] ** 3
        c = y[i] ** 2
        s += math.tan(a + b + c)
    return s

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

Вот исправленное решение:

import math


def main(z, x, y):
    n = len(z)
    z = [0] + z
    x = [0] + x
    y = [0] + y
    s = 0
    for i in range(1, n + 1):
        a = x[n + 1 - math.ceil(i / 4)]
        b = 43 * z[n + 1 - i] ** 3
        c = y[i] ** 2
        s += math.tan(a + b + c)
    return s

Этот вариант решения отличается использованием дополнительной памяти для копий списков.

В окончательном варианте решения дополнительная память не используется и пользовательские данные не модифицируются. Вместо этого индексы аккуратно пересчитаны:

import math


def main(z, x, y):
    n = len(z)
    s = 0
    for i in range(0, n):
        a = x[n - math.ceil((i + 1) / 4)]
        b = 43 * z[n - 1 - i] ** 3
        c = y[i] ** 2
        s += math.tan(a + b + c)
    return s

Другие способы решения задачи включают использование низкоуровневого цикла while, выражений-генераторов из PEP 289, списковых включений.

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.