Структуры и алгоритмы обработки данных

8.3 
Содержание курсового проекта 
Целью курсового проекта является разработка и исследование 
эффективного алгоритма реализации различных структур данных, а также 

---

25 
использование различных алгоритмов для решения практических задач. В 
индивидуальных заданиях фиксируются набор реализуемых операций и вид 
управляющей структуры данных для оптимизации доступа к элементам 
множества (цепочки). Алгоритм реализуется в виде программы для ПЭВМ. 
Программа используется для постановки эксперимента по оценке сложности 
разработанного алгоритма. Полученная оценка сравнивается с теоретической. 
Интерфейс программы должен содержать справочную информацию по 
используемой структуре данных и описание используемого алгоритма. 
Этапы выполнения курсового проекта 
1. Получение задания. 
2. Анализ литературы, периодических изданий, Интернет источников на 
предмет изучения опыта используемой структуры данных и предполагаемого 
алгоритма решения поставленной задачи. 
3. Реализация всех операций в виде функций и составление отладочной 
программы, демонстрирующей выполнение каждой операции на наборах 
данных, вводимых с клавиатуры. 
4. Разработка, реализация и отладка алгоритмов генерации случайных 
наборов 
данных 
заданного 
класса 
и 
размерности 
и 
случайной 
последовательности операций над этими данными. 
5. Теоретическая оценка вычислительной сложности комплексного 
алгоритма. 
6. Проведение экспериментов и получение экспериментальных оценок 
сложности. 
7. Обработка результатов и оформление курсового проекта. 
Перечень тем курсовых проектов 
1. Программная реализация и сравнительный анализ различных 
алгоритмов внутренних сортировок, относящихся к методам вставок. 
2. То же для методов обменной сортировки. 
3. То же для методов выборки. 
4. То же для методов группировки. 

---

26 
5. Программная реализация и сравнительный анализ различных методов 
хранения разреженных матриц и операций над ними. 
6. Программная реализация и сравнительный анализ различных методов 
хеширования для определенного набора ключей. 
7. Программная реализация и сравнительный анализ различных методов 
поиска информации в массиве: cканирование, предупорядочение, блочный, 
логарифмический поиски. 
8. Программная реализация процедур поиска, включения, исключения 
звеньев в двусвязном списке, расщепления списка на два по заданному ключу, 
сцепления двух списков. 
9. То же для односвязного списка. 
10. Программная реализация процедуры создания и редактирования 
обычного и прошитого бинарных деревьев и исследования их эффективности. 
11. Программная реализация процедур включения, исключения вершин 
для сбалансированного дерева. 
12. Оценка эффективности применения линейных структур в различных 
языках программирования. 
13. Разреженные матрицы. Метод последовательного распределения для 
разреженных матриц. Операции над разреженными матрицами.