Задание на курсовую работу
(2 семестр 2 курса)
Цель: реализация алгоритмов быстрого поиска, сортировки, алгоритмов на графах и их машинное исследование.
Содержательно курсовая работа состоит в выполнении 2-х последовательных заданий: 1) задания по быстрому поиску (деревья поиска различного вида), алгоритмам сортировки; 2) задание по алгоритмам на графах (реализация и модификация известных алгоритмов, генерация тестовых данных и исследование на них характеристик алгоритмов, визуализация работы алгоритмов на графах).
Часть I
Имеется некоторая база данных, которая хранится в текстовом файле. Файл с данными создается самостоятельно. Требуется по ключу (выбирается самостоятельно) произвести сортировку данных (использовать алгоритм сортировки, указанный в варианте задания), найти медиану или i-ую статистику (использовать алгоритм, указанный в варианте задания). Реализовать поиск данных по ключу (использовать алгоритм, указанный в варианте задания).
При выполнении работы необходимо изучить алгоритмы, необходимые для реализации поставленного задания, проанализировать время их работы в наилучшем, наихудшем случае (для этого рекомендуется создать несколько файлов с тестовыми входными данными). При выполнении алгоритмов сортировки создать тестовый пример с небольшим объемом входных данных, который наглядно демонстрирует работу алгоритмов. Результаты исследования должны быть представлены в отчете.
В отчете должно быть отражено 1) цель работы, 2) задание, 3) описание алгоритма (схема или код на псевдоязыке), 4) результаты исследования алгоритма (оценки в наилучшем наихудшем случае, численные примеры), 5) выводы. Отчет должен быть оформлен в соответсвии со следующими требованиями:
Печатается через 1.3 интервала шрифтом «Times New Roman» 14 pt., Абзацный отступ 10 мм. Слова разделяются одним пробелом. В обозначениях физических и математических величин буквы латинского алфавита набираются курсивным шрифтом (это не относится к сокращениям слов, например max, opt, cos и т. п.), а буквы греческого и русского алфавитов – прямым шрифтом. То же правило распространяется на буквы, находящиеся в индексах. Обозначения химических элементов также набирают прямым шрифтом, векторные величины – жирным (прямым или курсивным). Для обозначения матриц допускается как курсивный (светлый или жирный), так и прямой жирный шрифт. Для записи формул рекомендуется пользоваться редактором формул Microsoft Equation 3.0 либо MathType 5.0. Все надписи на рисунках выполняются шрифтом «Times New Roman» в векторном начертании. Они должны начинаться с прописной буквы, сокращения слов не допускаются. Размер шрифта: основной текст – 12 pt, индексы – 9 pt. Полная подрисуночная подпись размещается по центру поля рисунка. Она содержит сокращенное обозначение «Рис. » и номер рисунка (через пробел). Текст в таблицах печатается через 1 интервал, шрифт «Times New Roman», основной текст 12 pt, индексы 10 pt. Пример оформления таблицы представлен ниже
Таблица 5.2
| Основные размеры, мм | Масса образца, кг | |||
| Образец | Диаметр | Длина | до | после обработки |
| Стандартный | 14.0 | 250.0 | 2.50 | 2.37 |
| Обработанный | 14.0 | 255.0 | 2.55 | 2.53 |
Вариант 1
Сведения о водителях пассажирского автотранспорта. (ФИО сотрудника, класс, стаж работы, оклад)
Сортировка: использовать простые алгоритмы сортировки- вставками, выбором, обменами.
Нахождение медиан и i-x статистик: использовать алгоритм Хоара
Поиск по ключу: использовать АВЛ-деревья
Вариант 2
Сведения об успеваемости в сессию потока студентов (ФИО, индивидуальный номер зачетной книжки, средний балл)
Сортировка: использовать алгоритм быстрой сортировки
Нахождение медиан и i-x статистик: использовать линейный алгоритм
Поиск по ключу: использовать случайные бинарные деревья поиска
Вариант 3.
Сведения о кинотеатре (название, район города, где расположен кинотеатр, категория, вместимость)
Сортировка: использовать пирамидальную сортировку
Нахождение медиан и i-x статистик: использовать алгоритм Хоара
Поиск по ключу: использовать случайные бинарные деревья поиска с рандомизацией
Вариант 4
Расписание прибытия и отправления самолетов (номер рейса, тип самолета, время отбытия, время прибытия)
Сортировка: использовать сортировку слиянием
Нахождение медиан и i-x статистик: использовать линейный алгоритм
Поиск по ключу: использовать рандомизированные пирамиды поиска (TREAP)
Вариант 5
Анкетная информация отдела кадров завода (ФИО сотрудника, табельный номер, должность, оклад)
Сортировка: использовать простые алгоритмы сортировки- вставками, выбором, обменами.
Нахождение медиан и i-x статистик: использовать алгоритм Хоара
Поиск по ключу: использовать рандомизированные пирамиды поиска (TREAP)
Вариант 6
Сведения о вкладах в сберегательном банке. (ФИО владельца вклада, № вклада, величина вклада, длительность вклада)
Сортировка: использовать алгоритм быстрой сортировки
Нахождение медиан и i-x статистик: использовать линейный алгоритм
Поиск по ключу: использовать случайные бинарные деревья поиска с рандомизацией
Вариант 7
Обработка библиотечной информации.(ISBN книги, название книги, ФИО автора, количество страниц в книге)
Сортировка: использовать пирамидальную сортировку
Нахождение медиан и i-x статистик: использовать алгоритм Хоара
Поиск по ключу: использовать случайные бинарные деревья поиска
Вариант 8
Сведения о гостиницах города (название, общее количество номеров, количество одноместных, двух- и трех местных номеров, стоимость проживания в сутки)
Сортировка: использовать сортировку слиянием
Нахождение медиан и i-x статистик: использовать линейный алгоритм
Поиск по ключу: использовать АВЛ-деревья
Вариант 9
Сведения о газетах (название газеты, индекс издания, фамилию, ФИО редактора, цену экземпляра газеты).
Сортировка: использовать простые алгоритмы сортировки - вставками, выбором, обменами.
Нахождение медиан и i-x статистик: использовать алгоритм Хоара
Поиск по ключу: использовать случайные бинарные деревья поиска
Вариант 10
Информация о куриной ферме (вес , возраст, порода, количество ежемесячно получаемых от курицы яиц, номер курицы) .
Сортировка: использовать алгоритм быстрой сортировки
Нахождение медиан и i-x статистик: использовать линейный алгоритм
Поиск по ключу: использовать АВЛ-деревья
Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»
им. В.И. Ульянова (Ленина)
по курсовой работе на тему:
«Структуры и алгоритмы обработки данных»
Выполнили:
ФИО2
Группа № ХХХХ
Факультет: КТИ
Проверила
Дернова Е.С.
Санкт-Петербург
2010