PyAlgovizualizer — эффективное преподавание алгоритмов (Стас Фомин, OSEDUCONF-2024)

Материал из 0x1.tv

Докладчик
Стас Фомин.jpg
Стас Фомин

Преподавание алгоритмов через книги-слайды — устарело и неэффективно. С другой стороны, путь постижения хакера — реальная отладка на промышленных языках — тяжела и не для всех.

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

PyAlgovizualizer — это как раз такой модуль и подход, как готовить «живые» самовизуализурующиеся, компактные алгоритмы на Python, по которым преподаватель может провести занятие вживую, или записать видеоролик, и которых студенты могут вполне изучать самостоятельно, имея только браузер.

Видео

Презентация

Thesis

По личному опыту — 25 лет преподавания (МФТИ, ИСПРАН), и 35 лет учеником (ВУЗЫ, курсы, MOOCи), преподавание алгоритмов, как у нас, так и по миру, сильно не дотягивает до возможного технологического уровня.

Да, когда-то, в ветхозаветные времена — времён поклонению библиям алгоритмов — трёхтомнику Кнута, «книжке с ослом» («Алгоритмы: построение и анализ»), которых правда обычно держали на полках, а реально читали плохонапечатанные методички ВУЗов, казалось — что так и должно быть, хотя работало это только для тех, кто реально пытался всё это как-то кодить.

Но надо признать очевидные «для 2024» факты: «бумажные книги — всё».

По форме:


  • нельзя искать,
  • неудобно (для 2024) читать,
  • невозможно копировать и как-то взаимодействовать.
  • кирпич! не унести, не скопировать, не …
  • качественная печать — белая бумага, цветные иллюстрации — адски дорого, обычно на бумаге «стандарт Питер-пресс» с

серой «туалетной бумагой».


Любители «запаха бумажных листов», «шелеста страниц», «разрезания упаковки», «читать про алгоритмы в метро» — мною не наблюдались уже давно.

Также бумага неудобна по процессу издания:


  • «вотерфолл»-процесс, с фиксированным дедлайном и невозможностью правок.
  • куча дополнительных печатных ограничений хорошей вёрстки (совпадение строчек на прямой и обратной стороне листа и

т.п.), которой правда уже много кто не заморачивается.


Давайте не тратить кучу сил на вёрстку, впихивание слабовпихуемого в прокрутово ложе «листа бумаги», «чернобелой печати», когда это просто ненужно — читать будут с разных устройств, телефонов, планшетов, портретно и альбомно ориентированных мониторов разного разрешения, где нужна адаптивная вёрстка, нет ограничений на объём, но есть цвета и гиперссылки и возможность интерактивности, которые пропадают в книгах. Не нужны ни бумажные учебники, ни специализированные гибкие-негибкие e-ink устройства — это я говорю, как владелец нескольких десятков «электронных книг».

Так что проехали! Не говоря уж о том, что в РФ полезно бы вообще держатся подальше от издательского бизнеса учебников — там до сих пор мафия, перестрелки, бандиты с золотыми цепями (опыт личных знакомых «в теме»).

Казалось бы — электронные PDF-книги, прекрасно написанные, адаптированные для чтения с планшетов, с правильными экранными шрифтами, мониторной вёрсткой, с цветными картинками и гиперссылками, читаем на компьютерах и планшетах, публикуем-обновляем на сайте сами, используем цвет-поиск… — проблема решена?

Это действительно сильно лучше, но тут по-прежнему активны ограничения статики:


  • страничная вёрстка — с кучей проблем автору по вёрстке с учётом разбиения, переносов, ссылок на изображения и

картинки;

  • проблема как показать работу алгоритма в динамике — серия иллюстраций, логи работы, и надежда, что где-то в голове

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


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

И главное — мир алгоритмов огромен, десятки тысяч статей ежегодно, непонятных, часто с кризисом воспроизводимости[1] — их нельзя засовывать в книгу. Наоборот, пришло время вытаскивать всё из книг, и превращать в некие «интерактивные лаборатории с нелинейной навигацией», как «структуры технологий» в популярных играх.

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

  • «Алгоритм словами» — полный отстой. Может создать иллюзию понимания, но скорее всего ложную.
  • «Псевдокод» — иллюзия понимания, но есть проблема воспроизводимости — при переходе к работающему алгоритму, может

выяснится, даже при правильной реализации, что алгоритм вовсе не работал. Дилемма «Точность против Понятности» конечно очевидна, но псевдокод, каким бы понятным он был, за пределами правильного решения.

  • Проблемы подачи контента — как говорилось выше, статика типа книг-статей-слайдов не передают динамики алгоритма —

что-то можно делать с автогенерацией слайдов или картинок, но это очень мучительно и ограничено.

Это решения с более интересны, но тоже имеют свои недостатки:

  • Процедурная видеоанимация (пакет manim) — красиво, но непонятно, что выполняется, сложно

исследовать, нет синхронизации между роликами и выполняемым кодом.

  • «Literate programming» — что-то подобное я делал ранее в книге и слайдах — генерация из питон кода, компактного описания алгоритма картинок и слайдов, но явно вижу пределы, и это сильно мучительно.
Osseduconf-2024-stas-stas-stas-00.png
Osseduconf-2024-stas-stas-stas-01.png
  • Jupyter-ноутбуки. Хороши для представления однонаправленных процессов (пайплайнов ML), постановок ЦЛП/SAT-задач,

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

Osseduconf-2024-stas-stas-stas-02.png


В идеале ожидается «живой» алгоритм, с которым можно играться, изучать=эспериментировать, анализировать каждый шаг, но при этом чтобы было понятно и быстро. «Talks is cheap, show me the code»© — казалось бы надо просто написать очень понятный код, в видеоролике разбирать его работу, и дать возможность легко обучающемуся повторить всё это, поэкспериментировать с каждой строчкой, покачать разные «что-если». Так в общем, уже и делает «весь интернетный мир», при эффективном изучении всего связанного с IT и это хорошо.

Но есть проблемы такого подхода, по отношению к преподаванию сложных алгоритмов:


  • Алгоритмы на индустриальных языках (С/C++/Java/Rust…) — чудовищная перегрузка ненужными подробностями.
  • проблема с визуализацией изменения состояния — просто тыкать в отладочные описания структур — неэффективно —

чуть помогает расширение VSCode «Debug Visualizer» — но там долго перерисовывается, очень нетривиально описывать визуализацию (JSON-программирование).


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

Решение — разработанный питон-модуль pyalgovisualizer, использующий

  • скрытый код визуализации структур данных на питоне (код не сложный, и его пишет преподаватель-публикатор) —

таблицы значений структур, графы и графики — рисуются на специальной «визуализирующей картинке».

  • максимально компактный код алгоритма на Python, работа которого показывается прямо обычной отладкой;
  • получается алгоритм, очищенный от всего лишнего, который можно обычным образом отлаживать, даже в броузерной

версии VSCode, а некая скрытая магия будет при этом визуализировать происходящее понятным образом.


Таким образом, обучающийся, используя коллаборативную среду в браузере, ни секунды не тратя на отладку (см. [2]), может играться с алгоритмом и вместе с преподавателем на удалённом созвоне или в одной комнате («что будет если мы здесь сделаем так?»), и самостоятельно — просмотрев короткий сопровождающий каждый такой «живой квест-пример», ролик.

Как пример, можно посмотреть [3], или заходите на сайт: алгоритм.эвристика.рф, сейчас там пароль ArthurFomin1729, открывайте readme.md и попробуйте поотлаживать любой из алгоритмов, открыв в отдельной панели редактора картинку .visualization.png, и просматривая объясняющие ролики в начале описания каждого алгоритма.


PyAlgovizualizer — эффективное преподавание алгоритмов (Стас Фомин, OSEDUCONF-2024)!.jpg

Примечания и ссылки

  1. «Transparency and reproducibility in artificial intelligence», Nature, [1]
  2. Фомин С. А. Современные «интерактивные среды» и «живые лаборатории» — эффективное дистанционное образование по алгоритмам и математическим дисциплинам / С. А. Фомин // Восемнадцатая конференция. Свободное программное обеспечение в высшей школе: Тезисы докладов материалов конференции, Переславль-Залесский, 27—29 января 2023 года / Отв. редактор В. Л. Чёрный. — Москва: ООО «МАКС Пресс», 2023. — c. 63—64. — EDN GIZTTL., https://0x1.tv/20230128F
    • Видеоразборы решений задач с собеседований с применением PyAlgovisualizer [2]
    • Изложение темы про алгоритм Кристофидеса с использованием PyAlgovisualizer, https://discopal.ispras.ru/Crystofides