Добро пожаловать на канал курса Программирования на языке Python! github.com/true-grue/kispython 🎉

Наш курс завершается зачетом, на котором, в зависимости от успеваемости студента, будет предложено решить 2, 1 или 0 задач, сгенерированных с помощью ЦАП.

1. Допуском на зачет является успешное решение всех домашних задач от ЦАП. Это касается всех студентов без исключения.

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

3. Сократить число решаемых задач на зачете можно, выполнив творческий проект. В начале апреля производится контроль выполнения творческих проектов. Если прогресс оказался неудовлетворителен, то студент выбранный проект теряет. Успешно выполненный проект позволяет решить 0 задач на зачете.

На каждом семинарском занятии студент может решить до 2 задач, произвольной сложности.

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

Система начисления баллов зависит от преподавателя и будет рассматриваться на семинарских занятиях.

В нашем курсе предусмотрены задачи на дом. Их автоматически генерирует и проверяет Цифровой Ассистент Преподавателя (ЦАП), расположенный на странице http://kispython.ru

Студентам необходимо зарегистрироваться на http://kispython.ru/register, следуя подсказкам интерфейса: авторизоваться через ЕСИА РТУ МИРЭА или зарегистрироваться с помощью почты (студенты отправляют сообщения на почту со своей почты @edu.mirea.ru, а робот ее время от времени проверяет и подтверждает учетные записи) и выбрать свою группу.

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

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

Для задач разных типов алгоритмом кластеризации были выявлены наиболее распространённые в прошлом году подходы к решению. На полученных данных была обучена искусственная нейронная сеть. В этом году решение задачи ЦАП одного и того же типа известными нейронной сети способами позволяет зарабатывать учебные достижения, изучая Python!

На картинке показан один из способов решения 2-й задачи ЦАП при помощи словаря dict[bool, float], в котором ключом является True или False, а значением — вычисленное по одной из формул число. В следующих задачах ЦАП необходимо будет достигать бóльшего разнообразия в синтаксической структуре решений.

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

Первый блок из 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. В других способах решения деревья описываются вложенными словарями, списками, иерархиями объектов.