Курсовые работы по дисциплине «Алгоритмы и структуры данных» ИВТ УлГТУ на оценку «отлично»

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

Общие замечания

Курсовая работа выполняется в парах.

Техническое задание следует распределить так, чтобы у обоих авторов была индивидуальная алгоритмическая часть. Если один автор реализовывал всё алгоритмическое обеспечение, а второй «делал интерфейс»/«писал тесты»/«искал в интернете», то последний получает оценку не выше «удовлетворительно».

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

Для защиты необходимо подготовить:

  1. Работающее приложение
  2. Пояснительную записку
  3. Презентацию

Выполнение работы не гарантирует автоматического получения оценки «отлично»; оценка зависит от качества и полноты выполнения задания.

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

  • Техническое задание (общее) (1-2 листа; что надо было сделать? как это работает? какие алгоритмы для этого нужно было знать?)
  • Индивидуальное задание (уникальное для каждого из авторов, распределяется в соотношении 50/50, должно содержать алгоритмическую часть) (1 лист; какую часть работы выполнял лично я?)
  • Техническое проектирование
  • UML-диаграмма классов с комментариями (2-4 листа; для каждого класса: как он называется? за что отвечает? какие поля и методы содержит?)
  • Описание взаимодействия классов (можно использовать UML-диаграммы) (3-6 листов; какой класс является главным? к кому он обращается? какие классы участвуют в работе и как? кто кому какие сообщения отправляет?)
  • Javadoc-справка по основной части приложения (рекомендуется использовать Doxygen) (от 2 листов; сгенерировать rtf и скопировать содержимое, подправив стили для удобочитаемости)
  • Алгоритмическое обеспечение
  • Описание используемых алгоритмов и их назначения (2-5 листов; какие алгоритмы и структуры данных понадобились в этой работе? какую роль они здесь играют? где они ещё могут использоваться?)
  • Теоретическое обоснование сложности (O-оценка на время работы, её причины) (2-4 листа; вот тут у нас три вложенных цикла, поэтому O(N3))
  • Эмпирическое обоснование сложности (опытное доказательство соответствующего роста времени) (2-4 листа; вот график, действительно кубическая функция — вот и таблица погрешностей, посмотрите, они малы)
Представление об ожидаемом теоретическом и эмпирическом обосновании сложности можно получить отсюда, отсюда и отсюда
  • Тестирование (описание набора тестов для проверки кода соавтора) (3-5 листов; я тестировал такие-то методы, вот тестовые данные, вот функции библиотеки Catch, вот результаты тестирования)
  • Выводы (1-2 листа; в ходе выполнения работы рассмотрел..., получил навыки..., освоил...)
  • Приложение 1. Руководство пользователя (2-4 листа; описание интерфейса и порядка работы с приложением)
  • Приложение 2. Исходный код (весь, кегль 6)

Библиотеки Принстонского университета

Если ваш вариант основан на лабораторной работе Принстонского университета, вы можете использовать дополнительные файлы для тестирования.

Предложенные программы используют классы из библиотек stdlib.jar и algs4.jar. Скачайте их и добавьте в свой Java-проект.

Варианты курсовой работы

A* Search

Требуется создать приложение, выводящее решение игры «Пятнашки» при помощи алгоритма A*.

Реализовать:

  • Класс Board, представляющий состояние игры;
  • Класс Solver, отыскивающий и выводящий кратчайший путь до финального состояния;
  • Класс(ы) графического интерфейса приложения (можно использовать только консольный интерфейс, но это снижает оценку).

Основные алгоритмы в этой работе:

  • Эвристический поиск кратчайших путей в графе — A*.

Вспомогательные материалы:

Распакуйте архив и подключите папку 8puzzle в ваш проект как Source Folder. Если вы реализуете классы Board и Solver в соответствии со спецификацией, то сможете использовать программу для тестирования:
  • Вызов "PuzzleChecker puzzle10.txt" выводит количество ходов для решения головоломки, переданной в качестве параметра (в данном случае puzzle10.txt).

Burrows-Wheeler

Требуется создать приложение, позволяющее производить сжатие и распаковку данных при помощи преобразований Move-to-front и Барроуза-Уилера, а также кодирования Хаффмана.

Реализовать:

  • Класс MoveToFront, осуществляющий MTF-преобразование;
  • Класс BurrowsWheeler, осуществляющий преобразование Барроуза-Уилера;
  • Класс, осуществляющий кодирование по Хаффману;
  • Класс(ы) графического интерфейса приложения (можно использовать только консольный интерфейс, но это снижает оценку).

Основные алгоритмы в этой работе:

  • Преобразование Move-to-front;
  • Преобразование Барроуза-Уиллера;
  • Кодирование Хаффмана.

Вспомогательные материалы:

Архив содержит набор исходных и сжатых файлов различного типа для тестирования сжатия и распаковки.

Kd-Trees

Требуется создать приложение, отображающее точки на плоскости и позволяющее производить поиск точек в прямоугольнике и поиск ближайшего соседа для точки.

Реализовать:

  • Классы, представляющие геометрические примитивы (точку, прямоугольник);
  • Класс PointSET, представляющий множество точек и выполняющий указанные выше операции за O(N);
  • Класс KdTree, представляющий построенную на множестве точек структуру «Kd-дерево», позволяющую выполнять указанные выше операции с меньшей ожидаемой асимптотикой;
  • Класс(ы) графического интерфейса приложения (можно использовать только консольный интерфейс, но это снижает оценку).

Основные алгоритмы в этой работе:

  • Представление геометрических объектов;
  • Структура данных «Kd-дерево».

Вспомогательные материалы:

Распакуйте архив и подключите папку kdtree в ваш проект как Source Folder. Если вы реализуете классы PointSET и KdTree в соответствии со спецификацией, то сможете использовать программы для тестирования:
  • Вызов "KdTreeVisualizer" выводит графическое окно, в котором можно выделять точки, из которых строится Kd-дерево.
  • Вызов "RangeSearchVisualizer circle10.txt" выводит в графическом окне множество точек из файла, заданного параметром (в данном случае circle10.txt), и позволяет выделять прямоугольные области, подсвечивая все попавшие в них точки.

Molecular Dynamics Simulation

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

Реализовать:

  • (В этой работе детали архитектуры полностью определяются студентами-авторами).

Основные алгоритмы в этой работе:

  • Алгоритмы и операции линейной алгебры и математической физики;
  • Очередь с приоритетами;
  • Event-Driven Simulation.

Вспомогательные материалы:

RSA Cryptosystem

Требуется реализовать набор приложений, позволяющих генерировать открытый и закрытый ключ и производить шифрование и дешифрование сообщений согласно методу RSA. Для поиска простых чисел требуется использовать вероятностные тесты Миллера-Рабина или Лемана.

В качестве опорного текста задания можно использовать этот.

Реализовать:

  • Класс, представляющий многоразрядные целые числа (по согласованию можно использовать стандартную реализацию длинной арифметики в C# или Java);
  • Класс, осуществляющий шифрование и дешифрование;
  • Класс(ы) графического интерфейса приложения (можно использовать только консольный интерфейс, но это снижает оценку);
  • Класс(ы), инкапсулирующие функции сетевого взаимодействия (необязательно, но повышает оценку).

Основные алгоритмы в этой работе:

  • Вероятностные тесты простоты;
  • Поиск обратного элемента в кольце по модулю, расширенный алгоритм Евклида;
  • Быстрое возведение в степень;
  • Длинная арифметика.

Seam Carving

Требуется создать приложение, позволяющее загружать изображения и производить их масштабирование с сохранением контента.

Реализовать:

  • Класс, представляющий изображение в виде матрицы пикселей (можно использовать готовый класс Picture из stdlib.jar, но это снижает оценку);
  • Класс SeamCarver, осуществляющий поиск и удаление путей минимального веса в изображении;
  • Класс(ы) графического интерфейса приложения (можно использовать только консольный интерфейс, но это снижает оценку).

Основные алгоритмы в этой работе:

  • Поиск кратчайших путей в ориентированном ациклическом графе;
  • Динамическое программирование на графе.

Вспомогательные материалы:

Распакуйте архив и подключите папку seamCarving в ваш проект как Source Folder. Если вы реализуете класс SeamCarver в соответствии со спецификацией, то сможете использовать программы для тестирования:
  • Вызов "ShowEnergy HJocean.png" отображает в оттенках серого энергию пикселей переданного в качестве аргумента изображения (в данном случае HJocean.png).
  • Вызов "ShowSeams HJocean.png" отображает минимальные вертикальный и горизонтальный разрез изображения HJocean.png.
  • Вызов "ResizeDemo HJocean.png 50 100" уменьшает изображение HJocean.png на 50 пикселей по горизонтали и 100 пикселей по вертикали с сохранением контента.

Segment Tree Visualizer

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

Приветствуется также демонстрация выполнения операций модификации на отрезке.

Реализовать:

  • (В этой работе детали архитектуры полностью определяются студентами-авторами).

Вспомогательные материалы:

Основные алгоритмы в этой работе:

  • Структура данных «Дерево отрезков».

Shortest Paths

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

Приветствуется реализация возможностей редактирования карты, указания точек не только на дорогах, различных метрик назначения весов рёбрам дорожного графа.

Реализовать:

  • Класс, представляющий карту и дорожный граф;
  • Класс, выполняющий поиск кратчайшего пути;
  • Класс(ы) графического интерфейса приложения.

Основные алгоритмы в этой работе:

  • Алгоритм Дейкстры поиска кратчайшего пути на взвешенном графе.
Источник — https://acm.khpnets.info/w39/index.php?title=Курсовые_работы_по_дисциплине_«Алгоритмы_и_структуры_данных»_ИВТ_УлГТУ_на_оценку_«отлично»&oldid=2258