Компетентностно-ориентированные задания в системе высшего образования. Шехонин А.А - 62 стр.

UptoLike

ВУЗ: 

Университет ИТМО | Санкт-Петербург

Составители: 

Рубрика: 

62
Джеймс А. Андерсон Дискретная математика и комбинаторика. :
Пер. с англ. — М. : Издательский дом «Вильямс», 2004. — 960 с. : ил. —
Парал. тит. англ. — ISBN 5-8459-0498-6 (рус.). — С. 611–623.
Интернет-ресурсы на тему «Взвешенные графы и алгоритмы поиска
кратчайшего пути».
Электронные карты: http://maps.yandex.ru, http://maps.google.ru и др.
Формулировка задания
Необходимо разработать программу, находящую кратчайший путь
между двумя точками на карте с определением длины пути и выделением
маршрута следования по дорогам.
Для реализации задания студент должен решить следующие задачи:
– выбрать реализуемый алгоритм поиска кратчайшего пути,
основываясь на критерии времени выполнения;
– определить способ описания ключевых точек карты (пересечения
дорог и особые точки — вершины графа, дороги — ребра), их хранения в
файле и программе, определить способ описания двустороннего и
одностороннего движения;
– определить способ ввода пользователем начальной и конечной
точек маршрута. Описать возможность выбора пользователем в качестве
начальной и конечной точки пути не перекрестков, а точек на дорогах или
вблизи них;
– выбрать для примера часть карты, соответствующий площади на
местности не менее 10 км
2
. В качестве центра карты можно выбрать место
своего жительства, работы, учебы и т.д.;
– для студентов, способных выполнить более сложное задание,
предлагается разработать оптимальный по критерию кратчайшего
суммарного пути алгоритм следования из начальной точки в конечную с
прохождением промежуточных точек с заданием и без задания приоритета
их посещения, а также с учетом перепадов высот местности.
Бланк выполнения задания
Задание сдается в виде отчета с результатами выполнения задач,
описанных выше:
– описание цели и актуальности;
– обоснование выбора языка программирования;
– составление сравнительной таблицы времен выполнения
алгоритмов поиска кратчайшего пути на нескольких наборах входных
данных;
– обоснование описания ключевых точек карты (пересечения дорог и
особые точки — вершины графа, дороги — ребра), их хранения в файле и
программе, обоснование способа описания двустороннего и
одностороннего движения;

Страницы