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

Требования к защите

До конца семестра необходимо подготовить:

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

Защита курсовой работы происходит при показе презентации. Оценка за курсовую работу объявляется и выставляется непосредственно после защиты.

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

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

• Техническое задание (общее)

• Индивидуальное задание (уникальное для каждого из авторов, распределяется в соотношении 50/50)

• Техническое проектирование (архитектура приложения, классы, взаимодействие)
• Алгоритмические обеспечение (используемые алгоритмы, их назначение)

• Теоретическое обоснование сложности (O-оценка на время работы, её причины)
• Эмпирическое обоснование сложности (опытное доказательство соответствующего роста времени)

Представление об ожидаемом теоретическом и эмпирическом обосновании сложности можно получить отсюда, отсюда и отсюда

• Тестирование (описание набора тестов для проверки кода соавтора)
• Выводы (в ходе выполнения курсовой работы рассмотрел... получил знания... освоил...)
• Приложение 1. Руководство пользователя (описание интерфейса и работы с приложением)
• Приложение 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), и позволяет выделять прямоугольные области, подсвечивая все попавшие в них точки.

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 (АП: Гусев, Файзуллов; ВМ: Ежов, Лазарев)

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

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

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

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

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

• Видеолекция о структурах данных для задач RSQ и RMQ
• Статья «Дерево отрезков»
• Визуализатор дерева отрезков

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

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

Shortest Paths (АП: Линьков, Меньшова; ВМ: Захарычев, Киски, Филифоров)

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

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

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

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

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

• Алгоритм Дейкстры поиска кратчайшего пути на взвешенном графе.