ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ № 2
(4 семестр)
Цель: реализация алгоритмов сортировки и быстрого поиска, сортировки, алгоритмов на графах и их исследование.
Содержательно курсовая работа состоит в выполнении 2-х последовательных заданий: 1) сортировка и поиск данных;
2) алгоритмы на сетях и графах (реализация и модификация известных алгоритмов, генерация тестовых данных и исследование на них характеристик алгоритмов, визуализация работы алгоритмов на графах).
Примерный перечень тем: исследование методов сортировки включением, исследование методов сортировки выбором, исследование методов сортировки обменом, исследование методов сортировки с помощью деревьев, исследование улучшенных методов сортировки, исследование линейного и бинарного поисков, исследование методов оптимизации поиска, исследование задач поиска по дереву, исследование задач на построение остовного дерева, исследование задач на поиск путей в графе и т.п.
Тематика заданий на курсовую работу №2, приведенных в данных методических указаниях, может быть дополнена, расширена, увязана с решением актуальных практических задач задач, предложенных как преподавателем так и студентом. В этом случае заданием на курсовую работу может быть задача по проектированию единой программы, в которой в обязательном порядке применяются алгоритмы сортировки и быстрого поиска информации.
ЗАДАНИЕ 1. СОРТИРОВКА И ПОИСК ДАННЫХ
|
|
|
Имеется некоторая база данных, которая хранится в текстовом файле. Файл с данными создается самостоятельно. Требуется по ключу (выбирается самостоятельно) произвести сортировку данных (использовать алгоритм сортировки, указанный в варианте задания), Реализовать поиск данных по заданному значению ключа (использовать алгоритм, указанный в варианте задания). При выполнении работы необходимо изучить алгоритмы, необходимые для реализации поставленного задания, проанализировать время их работы в наилучшем, среднем, наихудшем случае (для этого рекомендуется создать несколько файлов с тестовыми входными данными). При выполнении алгоритмов сортировки создать тестовый пример с небольшим объемом входных данных, который наглядно демонстрирует работу алгоритмов. В пояснительной записке представить результаты исследования.
Вариант 1.
Сведения о водителях пассажирского автотранспорта. (ФИО сотрудника, класс, стаж работы, оклад)
Сортировка: использовать простые алгоритмы сортировки: вставками, выбором, обменами.
Поиск по ключу: использовать АВЛ-деревья
Вариант 2.
Сведения об успеваемости в сессию потока студентов (ФИО, индивидуальный номер зачетной книжки, средний балл)
|
|
|
Сортировка: использовать алгоритм быстрой сортировки
Поиск по ключу: использовать случайные бинарные деревья поиска
Вариант 3.
Сведения о кинотеатре (название, район города, где расположен кинотеатр, категория, вместимость)
Сортировка: использовать пирамидальную сортировку
Поиск по ключу: использовать случайные бинарные деревья поиска с рандомизацией
Вариант 4.
Расписание прибытия и отправления самолетов (номер рейса, тип самолета, время отбытия, время прибытия)
Сортировка: использовать сортировку слиянием
Поиск по ключу: использовать рандомизированные пирамиды поиска (TREAP)
Вариант 5.
Анкетная информация отдела кадров завода (ФИО сотрудника, табельный номер, должность, оклад)
Сортировка: использовать простые алгоритмы сортировки- вставками, выбором, обменами.
Поиск по ключу: использовать рандомизированные пирамиды поиска (TREAP)
Вариант 6.
Сведения о вкладах в сберегательном банке. (ФИО владельца вклада, № вклада, величина вклада, длительность вклада)
Сортировка: использовать алгоритм быстрой сортировки
Поиск по ключу: использовать случайные бинарные деревья поиска с рандомизацией
|
|
|
Вариант 7.
Обработка библиотечной информации.(ISBN книги, название книги, ФИО автора, количество страниц в книге)
Сортировка: использовать пирамидальную сортировку
Поиск по ключу: использовать случайные бинарные деревья поиска
Вариант 8.
Сведения о гостиницах города (название, общее количество номеров, количество одноместных, двух- и трех местных номеров, стоимость проживания в сутки)
Сортировка: использовать сортировку слиянием
Поиск по ключу: использовать АВЛ-деревья
Вариант 9.
Сведения о газетах (название газеты, индекс издания, фамилию, ФИО редактора, цену экземпляра газеты).
Сортировка: использовать простые алгоритмы сортировки - вставками, выбором, обменами.
Поиск по ключу: использовать случайные бинарные деревья поиска
Вариант 10.
Информация о куриной ферме (вес , возраст, порода, количество ежемесячно получаемых от курицы яиц, номер курицы) .
Сортировка: использовать алгоритм быстрой сортировки
Поиск по ключу: использовать АВЛ-деревья
ЗАДАНИЕ 2. АЛГОРИТМЫ НА СЕТЯХ И ГРАФАХ
Множество самых разнообразных задач может быть сформулировано в терминах теории графов. Для заданного варианта задания необходимо разработать программу, использующую графовые структуры данных, реализовать или модифицировать известные алгоритмы на сетях и графах, провести на тестовых данных исследование характеристик используемых алгоритмов
|
|
|
Вариант 1.
Надо соединить телефонным кабелем все домики полярной станции. Всего домиков N. Известны координаты домиков (X,Y), являющиеся целыми числами (за единицу измерения взяли 1 метр). Требуется написать программу, определяющую минимальную общую длину кабеля,соединяющего все домики между собой (возможно через другие домики).
Вариант 2.
У предприятия существует большая сеть филиалов в разных городах. Требуется написать программу, определяющую максимальное время, требующееся курьеру для доставки секретного пакета из одного произвольного филиала в другой произвольный филиал. Известны координаты местонахождения филиалов и скорость перемещения курьера.
Вариант 3.
Задано N городов c номерами от 1 до N и сеть из M дорог с односторонним движением между ними. Каждая дорога задается тройкой (i, j, k), где i - номер города, в котором дорога начинается, j - номер города, в котором дорога заканчивается, а k - ее длина (число k - натуральное). Дороги друг с другом могут пересекаться только в концевых городах. Все пути между двумя указанными городами A и B можно упорядочить в список по неубыванию их длин (если есть несколько путей одинаковой длины, то выбираем один из них). Необходимо найти один из путей, который может быть вторым в списке.
Дата добавления: 2018-06-27; просмотров: 376; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!