Визуализатор алгоритма программа, наглядно демонстрирующая работу алгоритма в пошаговом режиме над заданным набором данных. Примеры визуализаторов см по адресу.
| Вид материала | Программа |
СодержаниеЗадание №2. Основные требования Требования к пояснительной записке Варианты заданий |
- Д. С. Осипенко Понятие алгоритма. Примеры алгоритмов. Свойства алгоритмов. Способы, 96.46kb.
- Урок Тема: Понятие алгоритма. Исполнитель алгоритма, 204.38kb.
- План урока Организационный момент(1 мин) Проверка материала прошлого урока(10 мин.), 53.54kb.
- Об одном методе уточнения оценки сложности алгоритма (на примере алгоритма умножения, 32.27kb.
- Применение модифицированного волнового алгоритма для сжатия потокового видеосигнала, 33.24kb.
- Удк 004. 056. 53 Некоторые особенности реализации алгоритма защиты программного обеспечения, 54.51kb.
- Рабочая программа дисциплины: Теория алгоритмов для специальности 050202 «Информатика», 196.64kb.
- Теоретические вопросы, 25.48kb.
- План урока Организационный момент (2 минуты). Актуализация знаний (5 минут). Изучение, 36.57kb.
- Контрольная работа «алгоритмы и исполнители» вариант 1 Закончите предложение: «Алгоритмом, 27.49kb.
ЗАДАНИЕ №1.
Разработка визуализатора алгоритма или структуры данных
Визуализатор алгоритма – программа, наглядно демонстрирующая работу алгоритма в пошаговом режиме над заданным набором данных. Примеры визуализаторов см. по адресу ссылка скрыта. Теоретический материал по разработке визуализаторов с использованием автоматного программирования находится по адресу ссылка скрыта.
Реализация визуализатора должна быть выполнена таким образом, чтобы он мог выполняться непосредственно в браузере пользователя без необходимости ручной загрузки, установки и настройки. Для этого визуализатор алгоритма должен быть разработан языке программирования, например, С++ Builder 6.0.
Разработанный визуализатор должен обеспечивать:
1. наглядную графическую иллюстрацию всех особенностей работы алгоритма
2. вывод пояснения к каждому шагу алгоритма
3. работу в пошаговом и автоматическом режиме,
4. регулировку скорости автоматического выполнения
5. возможность отката на любое количество шагов назад,
6. работу как с предварительно заданными, так и со случайными и введёнными пользователем данными
7. корректную обработку частных и вырожденных случаев
Пример интерфейса представлен на следующем рисунке.
Рис.1. Пример типичного интерфейса визуализатора
(взято с u/vis/tree23/tree23_ru.php)
ЗАДАНИЕ №2.
Разработка задачи, системы тестов и проверяющей программы
Вторым заданием курсового проекта является разработка задачи с набором тестов и проверяющей программой для системы дистанционного практикума по программированию, используемой на кафедре АВТ.
Основные требования:
1. формулировка задачи по возможности должна быть привязана к практике,
2. условие задачи должно быть сформулировано четко и ясно, без каких-либо возможных предположений или разночтений,
3. решение задачи другим методом или с использованием другой структуры данных должно быть затруднительным или невозможным,
4. система тестов должна охватывать все возможные категории возможных входных данных и составлена так, чтобы отсекать подавляющую часть «лобовых» и эвристических решений
5. тесты должны учитывать частные и вырожденные случаи,
6. все неэффективные решения должны отсекаться ограничениями по времени или по памяти,
7. проверяющая программа должна распознавать типовые причины неверных ответов и выдавать соответствующие подсказки,
8. каждый тест должен быть прокомментирован, к наиболее интересным выполнен поясняющий рисунок (не менее чем к пяти тестам)
Для отладки задачи перед размещением её в системе необходимо использовать программу локального тестирования решений. Её можно взять по адресу ссылка скрыта.
ТРЕБОВАНИЯ К ПОЯСНИТЕЛЬНОЙ ЗАПИСКЕ
Пояснительная записка должна содержать следующее:
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 Особенности программной реализации
2.6 Методика и результаты тестирования ПО
2.7 Расчёт объектно-ориентированных показателей разработки
3. Разработка задачи, системы тестов и проверяющей программы
3.1 Формулировка задачи
3.2 Собственное решение задачи
3.3 Доказательство корректности собственного решения
3.4 Анализ эффективности собственного решения
3.5 Обоснование неэффективности или сложности в реализации решений, не использующих предложенную структуру данных / алгоритм
3.6 Описание предложенной системы тестов
3.7 Доказательство, что предложенная система тестов охватывает все (или хотя бы большую часть) категории входных данных
3.8 Исследование сложности «лобовых» решений, обоснование их отсечения системой тестов. Реализация «лобовых» решений (не менее двух), экспериментальные результаты
3.9 Наиболее вероятные эвристические решения, обоснование их отсечения системой тестов. Реализация эвристических решений (не менее двух), экспериментальные результаты
3.10 Классификация типовых ошибок, могущих возникнуть при анализе задачи
3.11 Разработка проверяющей программы. Учет типовых ошибок в формировании подсказок проверяющей программой
3.12 Тестирование корректности системы тестов и проверяющей программы
При описании алгоритмов (как заданного, так и алгоритма визуализации) в обязательном порядке используются блок-схемы в соответствии с ГОСТ 19.701-90 (ИСО 5807-85).
При описании иерархии классов (при разработке визуализатора) обязательно использования стандарта UML.
Объём пояснительной записки – 25-30 страниц, 12 шрифт, интервал 1.3
ВАРИАНТЫ ЗАДАНИЙ
| № варианта | Алгоритм или структура данных для заданий №1-визуализатор и №2-задача в ПС |
| 1 | Полный двоичный перебор и его ускорение путем отсечения заведомо неподходящих вариантов (на примере задачи разделения камней на две кучи) |
| 2 | AVL-деревья |
| 3 | Перебор с возвратом (backtracking) и отсечением заведомо неподходящих вариантов на примере решения задачи коммивояжера. |
| 4 | Алгоритм Краскала |
| 5 | Алгоритм Прима |
| 6 | Получение перестановки по её номеру и номера по заданной перестановке |
| 7 | Алгоритм Эдмондса-Карпа поиска максимального потока в графе |
| 8 | Поиск эйлерова пути или цикла в графе |
| 9 | Метод динамического программирования на примере задачи о рюкзаке |
| 10 | Алгоритм Дейкстры |
| 11 | Динамическое программирование: задача об оптимальной триангуляции выпуклого N-угольника |
| 12 | Сортировка Шелла |
| 13 | Быстрая сортировка Хоара |
| 14 | Пирамидальная сортировка |
| 15 | Поиск сильно связных компонент в графе |
| 16 | Динамическое программирование: перемножение цепочки матриц |
| 17 | Линейное хеширование |
| 18 | Быстрая сортировка Хоара |
| 19 | Пирамидальная сортировка |
| 20 | Распределяющая сортировка |
| 21 | Биномиальные пирамиды |
| 22 | Сортировка слиянием |
| 23 | Построение выпуклой оболочки точек |
| 24 | Алгоритм Ахо-Корасика |
| 25 | Алгоритм Кнута-Морриса-Пратта |
| 26 | Алгоритм Бойера-Мура |
| 27 | B+ - деревья |
| 28 | Поиск максимального парасочетания с помощью чередующихся цепочек |
| 29 | Кодирование текста по методу Хаффмана |
ЛИТЕРАТУРА
Цифровая библиотека вам в помощь:)