Как на основе автоматного подхода был создан метод построения логики визуализаторов для алгоритмов дискретной математики

Шалыто А.А.

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

Нельзя сказать, что этот разговор меня сильно обрадовал, но и не сильно расстроил, так как я слышал подобные высказывания весьма часто и привык к ним. Тем более, что систем управления на мою и не только мою жизнь хватит. Однако, некоторую радость от этого разговора я всё-таки испытал: по сравнению с ситуацией, описанной в статье «Об автоматизации стиральных машин», я за пару лет кое-чего добился – в указанный список добавились визуализаторы алгоритмов.

Даже, если бы я ничего больше в жизни не сделал – инициатива создания методов и технологий построения логики визуализаторов с применением автоматов, по моему мнению, весьма значительное достижение, так как такие визуализаторы в процессе изучения алгоритмов дискретной математики и программирования применялись не только в нашем университете. Однако,    везде, и в нашем университете, в частности, где такие визуализаторы строились, сильные студенты эвристически строили такие визуализаторы вместо того, чтобы, по крайней мере, один из них создал формальный метод построения их логики.

На кафедре «Компьютерные технологии» (КТ) университета ИТМО каждый студент в качестве курсовой работы по «Дискретной математике» разрабатывал и реализовывал проект визуализатора одного из алгоритмов дискретной математики. Таким образом, студент должен продемонстрировать не только знания по дискретной математике и программированию, но и на одном из языков программирования (в основном Java) реализовать визуализатор, который бы наглядно показывал, как работает алгоритм. При этом визуализатор должен был формировать не только графические образы, но и текстовые комментарии. Это также позволяет приобрести знания в области создания пользовательских интерфейсов.

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

Идея создания указанных методов, как выяснилось в дальнейшем, была инициировано мною. Я начал преподавать на кафедре КТ с 1998 году. Тогда в университете я работал по совместительству и занятия проводил по вечерам, начиная с 18:30, читая лекции по автоматному программированию.

Вместо практических занятий я давал домашние задания, одно из которых состояло в преобразовании того или иного алгоритма дискретной математики в конечный автомат. Для этого я предлагал использовать метод, предложенный в статье Туккель Н.И., Шалыто А.А. Реализация вычислительных алгоритмов на основе автоматного подхода // Телекоммуникации и информатизация образования. 2001. № 6, с. 35-53. В дальнейшем мы написали ещё одну статью на эту тему: Туккель Н.И., Шалыто А.А., Шамгунов Н.Н. Реализация рекурсивных алгоритмов на основе автоматного подхода // Телекоммуникации и информатизация образования. 2002. № 5, с. 72-99.

Как сейчас помню, как мне в 2001 году поздно вечером сдавал домашнее задание студент пятого курса Матвей Казаков, команда которого в 1999 году на чемпионате мира ACM ICPC заняла третье место. Выполненное задание занимало две страницы. На первой была написана маленькая и изящная программа, содержащая четыре вложенных цикла (какой алгоритм она реализовала не помню), а на второй – её эквивалентная автоматная реализация, состоящая из ужаснейшего оператора switch, содержащего девять или десять меток case. Я посмотрел на получившееся безобразие и грустно сказал: «Ну, что Матвей, не подходит автоматный подход для реализации вычислительных алгоритмов?»

После некоторого молчания студент ответил: «Да, похоже не подходит», но после небольшой паузы добавил: «А зато, как мне кажется, очень подходит для формирования логики визуализаторов алгоритмов дискретной математики, так как в программах с циклами, в которых как бы всё движется и поэтому не понятно что и как визуализировать, а в эквивалентных автоматах есть состояния, в которых можно считать, что автомат останавливается. Это позволяет показывать в них все что захочется». Я несколько опешил, а потом обрадовался, Поставил Матвею зачёт, и на этом, как оказалось временно, всё закончилось.   

Продолжение эта история получила в июне 2002 года. На предварительной защите магистерской диссертации Матвей Казаков в начале своего выступления среди других благодарностей поблагодарил и меня «за идею автоматного подхода к построению визуализаторов». Я, как бы наивно, спросил выступающего: «А, что мне делать с этой благодарностью?» Ответа, естественно, не получил и предложил Матвею разработать на основе этого подхода визуализатор и сдать Гоше Корнееву (призёру указанного выше чемпионата мира 2000 и 2001 годов, причём в 2001 году Казаков был тренером их команды). Георгий слышал наш разговор, так как в этот день предзащитил свою бакалаврскую работу.

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

Все произошло, как я и просил. После того, как они защитились, мы собрались вместе, и Матвей показал мне и Георгию, как он по-новому построил визуализатор. Видно было, что Корнеев удивился и сказал, что подумает об услышанном. Произведённое впечатление понравилось Матвею, и он бодро поступил ко мне в аспирантуру, но летом, естественно, ничего не делал.

Когда в первых числах сентября я пришёл в университет, меня встретил наш декан Владимир Глебович Парфенов и, то ли в шутку, то ли всерьёз, сказал, что я внёс раздрай между тренером и учеником, чего у них никогда не было. Оказалось, что Матвей и Георгий «выясняют отношения» по поводу авторства метода и технологии создания визуализаторов на основе автоматного подхода, что мне, в некотором смысле, было весьма лестно.

Я подошёл к ним и узнал, что пока Матвей в диссертации только собирался автоматизировать метод и технологию построения визуализаторов на основе автоматного подхода, Георгий за лето это сделал. Я быстро «разрулил» ситуацию, объяснив им, что в этой тематике хватит «места» обоим, и предложил совместно написать статью, что мы и сделали [1]. Потом были и другие статьи, в которых метод и технология модифицировались [2-8].  Матвею и Гоше действительно «хватило места», и они защитили кандидатские диссертации.

В 2006 году Георгий Корнеев под моим руководством защитил кандидатскую диссертацию на тему «Автоматизация построения визуализаторов алгоритмов дискретной математики на основе автоматного подхода». Вот ещё два материала на эту тему: «Требования к визуализаторам алгоритмов, выполняемых на базе технологии Vizi»  и «Пример построения логики визуализатора».

В 2010 году кандидатскую диссертацию под руководством В.Г. Парфенова на тему «Методы построения визуализаторов алгоритмов дискретной математики на основе автоматного подхода» защитил Матвей Казаков. Его презентация приведена здесь: https://is.ifmo.ru/disser/kazakov_present.pdf.

Из большого числа визуализаторов, созданных 2004-2005 годах по предложенной Корнеевым технологии Vizi, 14 проектов визуализаторов были опубликованы в сети «Интернет». Среди них наиболее интересна работа: Бедный Ю.Д. Построение визуализаторов нахождения максимального потока в сети методами Диница  и Малхотры – Кумара – Махешвари  на базе технологии Vizi. Университет ИТМО. 2005. При использовании первого метода визуализатор управляется восемью автоматами с общим числом состояний, равным 68, а для второго метода – восемнадцатью автоматами, в которых 89 состояний  Визуализатор для «2-3 деревьев», построенный Николаем Красильниковым, содержит 14 автоматов, в которых 195 состояний. Числа автоматов и состояний в каждом указанных визуализаторов приведены здесь: http://is.ifmo.ru/disser/korn_auto.pdf.

Основные публикации по рассмотренной теме

1. Казаков М.А., Корнеев Г.А., Шалыто А.А. Метод построения логики работы визуализаторов алгоритмов на основе конечных автоматов // Телекоммуникации и информатизация образования. 2003. № 6, с. 27-58. http://is.ifmo.ru/works/vis/.

2. Казаков М.А., Шалыто А.А. Использование автоматного программирования для реализации визуализаторов // Компьютерные инструменты в образовании. \2004. № 2, с. 19-33. http://is.ifmo.ru/works/art_vis.pdf.

3. Корнеев Г.А., Шалыто А.А. Построение визуализаторов алгоритмов дискретной математики // Научно-технический вестник СПбГУ ИТМО. Высокие технологии в оптических и информационных системах. 2005. № 7 (23), с. 118-129. https://ntv.ifmo.ru/file/journal/115.pdf.

4. Корнеев Г.А., Шалыто А.А. VIZI – язык описания визуализаторов алгоритмов //Научно-технический вестник СПбГУ ИТМО. Высокие технологии в оптических и информационных системах. 2005. № 7 (23), с. 130-137.  https://ntv.ifmo.ru/file/journal/115.pdf.

5. Корнеев Г.А. Метод преобразования программ в систему взаимодействующих автоматов / Вестник II межвузовской конференции молодых ученых. Сборник научных трудов. Т. 1. СПб.: ИТМО. 2005, с. 65-72.  http://is.ifmo.ru/works/_a_formalization.pdf.

6. Корнеев Г.А.  Технология разработки визуализаторов алгоритмов / Вестник II межвузовской конференции молодых ученых. Сборник научных трудов. Т. 1. Сб.: ИТМО. 2005, с. 18-23. http://is.ifmo.ru/works/2005/korneev-tech-kmu-2005.pdf.

7. Казаков М.А., Шалыто А.А. Реализация анимации при построении визуализаторов алгоритмов на основе автоматного подхода // Информационно-управляющие системы. 2005. № 4, с. 51-60. http://i-us.ru/index.php/ius/article/view/14543.

8. Казаков М.А., Шалыто А.А. Методы построения логики визуализаторов алгоритмов // Открытое образование. 2005. № 4, с. 53-58. http://is.ifmo.ru/works/bubblevisio/.

Об авторе: Анатолий Шалыто - докт. техн. наук, профессор, Университет ИТМО
Помещена в музей с разрешения автора 28 августа 2025