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