Разрабатываемый курсовой проект включает в себя разработку визуализатора заданного алгоритма или структуры данных. Визуализатор алгоритма – программа, наглядно демонстрирующая работу алгоритма в пошаговом режиме над заданным набором данных. Примеры визуализаторов приложены, другие примеры см. по адресу https://rain.ifmo.ru/cat.
Визуализатор разрабатывается как приложение с графическим интерфейсом или как web-приложение, можно использовать любой язык программирования.
Разработанный визуализатор должен обеспечивать:
1. наглядную графическую иллюстрацию всех особенностей работы алгоритма
2. вывод пояснения к каждому шагу алгоритма
3. работу в пошаговом и автоматическом режиме,
4. регулировку скорости автоматического выполнения
5. возможность отката на любое количество шагов назад,
6. работу с предварительно заданными, со случайными и с введёнными пользователем данными,
7. корректную обработку частных и вырожденных случаев
Пример интерфейса визуализатора представлен на рисунке.
Рис. 1. Пример внешнего вида визуализатора алгоритма
Примечание: в случае затруднений с разработкой графического приложения возможна разработка консольной программы без поддержки функций отката и регулировки скорости, которая будет просто выводить результаты работы в консоль после каждого шага (например, по нажатию клавиши «Enter»). Однако, такая работа не может быть оценена на высокий балл.
Использование возможностей среды разработки для построения графического пользовательского интерфейса можно найти в документации, учебниках и приложенных методических указаниях (для языка C++).
Некоторые сложности в реализации может вызывать пошаговое выполнение алгоритма и откат в обратную сторону. Простейший способ реализации этих функций состоит в том, чтобы предварительно полностью выполнить реализуемый алгоритм и сохранить все его переменные на каждом шаге. Например, если визуализируемый алгоритм использует одномерный массив x, то можно создать двумерный массив xStates, каждая i -я строчка которого будет содержать одномерный массив x на i -м шаге алгоритма. Тогда выполнение шага вперед или назад не будет представлять большой сложности.
2. Примерный план пояснительной записки
1. Описание заданной структуры данных или алгоритма
1.1 Историческая справка
1.2 Описание работы алгоритма.
1.3 Обоснование корректности алгоритма
1.4 Класс входных данных, для которых применим алгоритм или структура
1.5 Анализ временной и пространственной сложности алгоритма
1.6 Сравнение с аналогами
1.7 Примеры практических задач, где может использоваться данный алгоритм.
2. Разработка визуализатора
2.1 Выбор средств разработки
2.2 Определение отображаемых элементов, проектирование интерфейса
2.3 Разработка алгоритмов прямого пошагового выполнения визуализации и выполнения отката
2.4 Особенности программной реализации
2.5 Методика и результаты тестирования ПО
При описании алгоритмов используются блок-схемы в соответствии с ГОСТ.
Примерный объём пояснительной записки – от 15 страниц (без учета листингов).
3. Варианты заданий (вариант выбирается по номеру зачетки)
| № | Алгоритм или структура данных для заданий курсового проекта | ФИО |
| Полный двоичный перебор и его ускорение путем отсечения заведомо неподходящих вариантов. Для визуализации можно взять следующую задачу: дано N камней разных весов. Нужно разбить их на две кучи так, чтобы веса каждой кучи отличались как можно меньше. | ||
| Двоичное дерево поиска. Предусмотреть возможность вставки и удаления произвольных (задаваемых пользователем) элементов | ||
| Перебор с возвратом (backtracking) и отсечениями. Для визуализации можно рассмотреть задачу коммивояжера (или предложить свою). | ||
| Быстрая сортировка Хоара. В визуализаторе показать схематически в виде дерева, как выполнялись рекурсивные вызовы. | ||
| Сортировка Шелла. Рассмотреть различные последовательности приращений. | ||
| Сортировка двоичной кучей (пирамидой). В визуализаторе показать как графическое представление пирамиды, так и её хранение в массиве. | ||
| Обход дерева в ширину (поиск в ширину). | ||
| Обход дерева в глубину (поиск в глубину). | ||
| Хеширование с цепочками переполнения | ||
| Распределяющая сортировка натуральных чисел от младших разрядов к старшим | ||
| Простые методы сортировки (пузырьковая, простым выбором, простыми вставками) | ||
| Двоичный поиск в массиве. Показать особенности поиска: самого левого вхождения; самого правого вхождения; верхней границы (самый маленький элемент, больший или равный искомому) | ||
| Сортировка слиянием. В визуализаторе показать схематически в виде дерева, как выполнялись рекурсивные вызовы. | ||
| Односвязный список. | ||
| Двусвязный список. | ||
| Очередь на основе циклического массива. | ||
| Очередь с приоритетами на основе пирамиды (двоичной кучи) | ||
| Хеширование без цепочек переполнения | ||
| Множество целых чисел на основе битового массива |