Использование автоматного программирования для реализации визуализаторов


Статья опубликована в журнале «Компьютерные инструменты в образовании». 2004. № 2, с. 19 — 33.

М.А. Казаков, А.А. Шалыто

Статья в формате PDF
Визуализатор (online)
Исходные коды визуализатора

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

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