Курсовая работа по дисциплине «Алгоритмы и структуры данных» нацелена на создание нескольких реализаций заданного алгоритма и выполнение сравнительного анализа этих реализаций по времени исполнения, затратам памяти, объему исходного кода.
Общий порядок выполнения курсовой работы:
1) Обоснование выбора вариантов реализаций заданного алгоритма.
2) Разработка вариантов реализации
3) Разработка вариантов рабочей нагрузки
4) Разработка механизмов протоколирования и обработки протоколов
5) Разработка структурно-функциональной организации программы экспериментального исследования
6) Разработка алгоритмов, структур данных и исходного кода средств поддержки экспериментирования
7) Проведение экспериментов и обработка результатов
8) Оценка параметров реализации задач курсового проектирования
В качестве параметров варьирования реализаций могут выступать следующие:
· Язык реализации
· Типы дынных
· Множества используемых операций и функций
· Числовые значения и их соотношения, играющие значимую роль в спецификациях данных и алгоритмов.
Примерные варианты типовых заданий на курсовую работу:
| № | Алгоритм | Пример варьирования реализации |
| Сортировка слиянием, сортировка по количеству единиц в двоичном представлении числа | Язык реализации, размерность входных данных (байт,?16 бит?, 32 бит, 64 бит) | |
| Пузырьковая сортировка по количеству единиц в двоичном представлении числа | Язык реализации, размерность входных данных (байт,?16 бит?, 32 бит, 64 бит) | |
| Сортировка вставками,сортировка по количеству единиц в двоичном представлении числа | Язык реализации, размерность входных данных (байт,?16 бит?, 32 бит, 64 бит) | |
| Сортировка перемешиванием (шейкерная сортировка), сортировка по количеству единиц в двоичном представлении числа | Язык реализации, размерность входных данных (байт,?16 бит?, 32 бит, 64 бит) | |
| Сортировка построением двоичного дерева, сортировка по количеству единиц в двоичном представлении числа | Язык реализации, размерность входных данных (байт,?16 бит?, 32 бит, 64 бит) | |
| Сортировка слиянием | Язык реализации, тип входных данных – целые числа, числа с плавающей точкой, строки, структуры | |
| Сортировка вставками | Язык реализации, тип входных данных – целые числа, числа с плавающей точкой, строки, структуры | |
| Сортировка перемешиванием (шейкерная сортировка) | Язык реализации, тип входных данных – целые числа, числа с плавающей точкой, строки, структуры | |
| Сортировка построением двоичного дерева, | Язык реализации, тип входных данных – целые числа, числа с плавающей точкой, строки, структуры | |
| Пузырьковая сортировка | Язык реализации, тип входных данных – целые числа, числа с плавающей точкой, строки, структуры | |
| Пузырьковая сортировка единиц в двоичном числе по возрастанию | Язык реализации, процент единиц в числе | |
| Пузырьковая сортировка единиц в двоичном числе по убыванию | Язык реализации, процент единиц в числе | |
| Проверка корректности скобочной последовательность | Язык реализации, количество вариантов скобок – (), (){}, (){}<>, (){}[]<>, (){}[]<>/\ | |
| Двоичный поиск | Язык реализации, тип входных данных – целые числа, числа с плавающей точкой, строки, структуры | |
| Поиск общей подпоследовательноси | Язык реализации, тип входных данных – массивы - целые числа, числа с плавающей точкой, структуры, строки | |
| Поиск цикла в графе | Язык реализации, отношение количества вершин к количеству ребер графа | |
| Проверка связности графа | Язык реализации, отношение количества вершин к количеству ребер графа | |
| Подсчет количества листьев в двоичном дереве | Язык реализации, отношение количества вершин к количеству ребер графа | |
| Подсчет количества вершин с двумя потомками в двоичном дереве | Язык реализации, отношение количества вершин к количеству ребер графа | |
| Подсчет количества листьев в двоичном дереве | Язык реализации, отношение количества вершин к количеству ребер графа, обход дерева «снизу вверх» | |
| Подсчет количества вершин с двумя потомками в двоичном дереве | Язык реализации, отношение количества вершин к количеству ребер графа, обход дерева «снизу вверх» | |
| Раскраска графа | Язык реализации, отношение количества вершин к количеству ребер графа, способ задания графа – список смежности/матрица смежности | |
| Алгоритм Краскала (минимальное остовное дерево) | Язык реализации, отношение количества вершин к количеству ребер графа, способ задания графа – список смежности/матрица смежности | |
| Волновой алгоритм на лабиринте | Язык реализации, отношение количества свободных клеток к занятым | |
| Алгоритм Дейкстры | Язык реализации, отношение количества вершин к количеству ребер графа, взвешенный/невзвешенный граф | |
| Есть ли в графе цикл | Язык реализации, отношение количества вершин к количеству ребер графа | |
| Наименьший общий предок | Язык реализации, отношение количества вершин к количеству ребер графа | |
| Вычисление постфиксного выражения | Арифметические операции, логические побитовые операции (вариация разрядности операндов),?операции над строками? | |
| Преобразование инфиксного выражения в постфиксное | Арифметические операции, логические побитовые операции (вариация разрядно30сти операндов), количество вариантов арифметических операций,?операции над строками? | |
| Поиск в хеш-таблице | Язык реализации, отношение количества столбцов в таблице к количеству записей | |
| Построение хеш-таблицы | Язык реализации, типы данных (строки, целые числа, структуры) | |
| Поиск в хеш-таблице | Язык реализации, типы данных (строки, целые числа, структуры) | |
| Построение хеш-таблицы | Язык реализации, отношение количества столбцов в таблице к количеству записей | |
| RLE-кодирование | Язык реализации, типы данных – байты, 32-битные int, структуры | |
| RLE-кодирование | Язык реализации, кодирование/декодирование | |
| Заливка многоугольника (входные данные - изображение в виде матрицы MxN, цвет заливки и координаты точки, с которой начинается заливка) | Язык реализации, количество бит на пиксель (2, 8, 24) |
По согласованию с преподавателем могут предлагаться другие параметры варьирования и иные темы. Возможны индивидуальные темы в рамках проектов, осуществляемых в УлГТУ и в ИТ-компаниях города.