УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Требования к визуализаторам алгоритмов, выполняемых на базе технологии Vizi. Версия 4.1

Введение

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

Технология Vizi позволяет формально программировать логику визуализатора на базе реализации визуализируемого алгоритма. Для облегчения программирования визуализатора разработана библиотека Vizi (текущая версия 0.4b6). Эта библиотека скрывает многие технические детали реализации визуализаторов при использовании технологии Vizi.

1. Требования к коду визуализатора

1.1. Языки программирования

Визуализатор должен быть написан на языке Java.

При использовании следующих компиляторов не должно выдаваться сообщений об ошибках (error) и предупреждений (warning), в том числе предупреждений об использовании deprecated API:

1. Sun JDK 1.1.4
2. Sun JDK 1.1.8
3. Sun JDK 1.3
4. Sun JDK 1.4

1.2. Среды исполнения

Визуализатор должен работать в следующих средах:

1. AppletViever vv. 1.1.4, 1.1.8, 1.3, 1.4
2. Internet Explorer v. 5.0+
3. Netscape Navigator v. 4.0+
4. Opera v. 5.0+
5. Mozilla v. 1.0+

1.3. Поддержка многоязычности

Визуализатор должен полностью поддерживать многоязычность (internationalization) на уровне XML-описания. При этом не допускается использование явной или неявной конкатенации строк для получения сообщений выводимых пользователю.

1.4. Совместимость

Визуализатор должен быть полностью совместим с последней версией библиотеки Vizi, в том числе по интерфейсу пользователя, параметрам, значениям параметров по умолчанию.

1.5. Интерфейс визуализатора

К интерфейсу визуализатора предъявляются следующие требования.

1. Все действия визуализатора должны быть прокомментированы.
2. Интерфейс должен быть понятен неподготовленному пользователю.
3. Для каждого элемента управления должна отображаться соответствующая подсказка (hint).
4. Нажатие на активную (enabled) кнопку, выбор из активного списка и аналогичные действия пользователя должны сопровождаться видимыми изменениями состояния визуализатора.
5. В интерфейсе не должно быть зависимостей вида «Пользователь не может изменить количество вершин, пока не нажмет кнопку Restart».
6. Визуализатор, должен подстраивать размер своих элементов (в том числе, размер шрифтов) под размер области, отведенной для рисования. При изменении размеров визуализатора должно происходить динамическое изменение размеров отображаемых элементов (в том числе, шрифтов).
7. Визуализатор должен «прилично» выглядеть при ширине 400+ и высоте 300+ пикселей. Для визуализаторов работы с деревьями и графами — соответственно 600+ и 400+ пикселей. При этом шрифт должен быть удобочитаем, в частности, не слишком мелким.

1.6. Требования к визуализаторам алгоритмов на графах

К визуализаторам алгоритмов на графах дополнительно предъявляются следующие требования.

1. Ребра графа,инцедентные одной вершине, не должны пересекаться.
2. Рекомендуется ввести два режима: «Визуализация» и «Редактирование», переключение между которыми осуществляется при нажатии одной из кнопок управления.
3. При визуализации должен отображаться не только граф (при необходимости, с весами), но и его матрица смежности (с возможностью отключения).
4. Если на некотором шаге алгоритм оперирует с вершиной (ребром, дугой), то она должна быть выделена не только на графе, но и в матрице смежности. При этом цвета выделения на рисунке графа и в матрице должны совпадать.
5. Столбцы и строки матрицы смежности должны быть помечены названиями (номерами) вершин.
6. Если в графе не допускаются петли, то в режиме редактирования на диагонали матрицы смежности должны отображаться крестики.

1.7. Параметры визуализатора

1. Все строки, выводимые визуализатором, должны быть заданы в XML-описании визуализатора.
2. Должна быть предусмотрена возможность задания исходного примера, на котором работает визуализатор, в интуитивно понятной форме.
3. Наличие кнопки «Save/Load» должно конфигурироваться.
4. Цвета всех графических элементов визуализатора должны конфигурироваться через XML-описание визуализатора.

1.8. Прочие требования

1. По визуализатору (без дополнительной информации) подготовленному пользователю должно быть понятно, как работает алгоритм (при этом разрешаются ссылки на другие алгоритмы, как шаги визуализатора).
2. При иерархической структуре алгоритма должны быть предусмотрены шаги различных размеров.
3. Визуализатор должен обеспечивать сохранение своего состояния в и восстановление его из human-operable формата.

1.9. Стиль кода

1. Отступ — 4 символа.
2. Все переменные и методы должны быть документированы (JavaDoc).
3. Ширина исходного кода не более 80 символов.
4. Отсутствие неиспользуемых переменных, методов, присваиваний, приведений типов.
5. Классы визуализатора должны быть в отдельном пакете (package) — наследнике ru.ifmo.ips.vizi.

2. Требования к документации

2.1. Структура проектной документации

Проектная документация должна состоять из следующих документов (допустимые форматы документов указаны в скобках).

1. Пояснительная записка (MS Word или TeX).
2. Страница с визуализатором на русском и английском языках (HTML).
3. XML-описание визуализатора (XML).
4. Описание алгоритма на русском языке (HTML).
5. Описание интерфейса визуализатора на русском языке (HTML).
6. Исходные тексты визуализатора (Java).
7. Описание нестандартных параметров визуализатора (HTML).

2.2. Структура пояснительной записки к проекту

Пояснительная записка к визуализатору должна иметь следующую структуру.

Аннотация

Введение

Раздел 1. Анализ литературы

Раздел 2. Описание алгоритма

Раздел 3. Реализация визуализируемого алгоритма

Раздел 4. Описание модели данных

Раздел 5. Преобразование программы к виду удобному для преобразования в автомат

Раздел 6. Описание интерфейса визуализатора

Раздел 7. Описание конфигурации визуализатора

Заключение

Список источников

Приложения

2.3. Оформление проектной документации

Проектная документация должна быть оформлена следующим образом.

1. Размер основного шрифта — 12-й кегль.
2. Размеры полей: верхние и нижние — 2 см, левое — 3 см, правое — 1 см.
3. Межстрочный интервал — полуторный.
4. Основной текст — шрифт с засечками (Times New Roman).
5. Заголовки (в том числе, подписи к рисункам) — шрифт без засечек (Arial).
6. Исходные тексты программ и XML-файлов, а так же их фрагменты — моноширинной шрифт (Courier New).

2.4. Форматы предоставляемых документов

Все документы должны быть представлены в удобочитаемом (human-readable) виде (не автоматически сгенерированные Word, Frontpage, DreamWeaver и т.д.)

1. Java: Code Conventions for the Java(TM) Programming Language
2. HTML: HTML 4.01 Specification, XHTMLT 1.0 The Extensible HyperText Markup Language (Second Edition) compatibility mode.
3. XML: Extensible Markup Language (XML) 1.0 (Second Edition)
4. XSL: Extensible Stylesheet Language (XSL) Version 1.0
5. MS Word: Microsoft Word XP (2000).
6. TeX: Совместимость с MikTeX

3. Порядок выполнения визуализатора

1. Анализ литературы по визуализируемому алгоритму.
2. Реализация алгоритма на языке Java.
3. Формирование модели данных по реализации.
4. Модификация программы с использованием модели данных.
5. Преобразование программы к виду, удобному для преобразования в автомат (преобразование циклов).
6. Разбиение программы на шаги визуализации.
7. Запись модели данных и программы с разбиением на шаги в XML-формате.
8. Отладка XML-описания программы, полученной в предыдущем пункте (с автоматической генерацией автоматов по XML-описанию программы).
9. Разработка интерфейса визуализатора:
   • представление объектов визуализации;
   • комментарии к состояниям;
   • элементы управления;
   • надписи.
10. Стыковка интерфейса и описания программы, полученного в пункте 8, в частности, путем добавления составляющих ответственных за визуализацию к XML-описанию.
11. Совместная отладка интерфейса и логики визуализатора.
12. Добавление конфигурации визуализатора к XML-описанию.
13. Оформление проектной документации.
14. Создание итоговой версии визуализатора, включая набор документов.

4. Примечания

1. Библиотека Vizi доступна по адресу http://ctddev.ifmo.ru/vizi/.
2. Краткая документация доступна по адресу http://ctddev.ifmo.ru/vizi/readme.html (также входит в архив Vizi, в каталоге docs).