Реферат: работа состоит в выполнении 2-х последовательных заданий: 1) задания по быстрому поиску (деревья поиска различного вида), алгоритмам сортировки;

Задание на курсовую работу

(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

Вариант 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 статистик: использовать линейный алгоритм

Поиск по ключу: использовать АВЛ-деревья

Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»

им. В.И. Ульянова (Ленина)

Кафедра АСОИУ

Отчет

по курсовой работе на тему:

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

Выполнили:

ФИО1

ФИО2

Группа № ХХХХ

Факультет: КТИ

Проверила

Дернова Е.С.

Санкт-Петербург

2010