Файл: Практическая работа по теме 2 Знакомство с современными российскими программными решениями на уроках информатики и во внеурочной деятельности.pdf

Практическая работа по теме 2.2 «Знакомство с современными российскими программными решениями на уроках информатики и во внеурочной деятельности»
Название работы:
Разработка серии учебных заданий для решения задачи поиска кратчайшего пути в графе на материале геоинформационных систем (навигаторов).
1.
Целью планируемой образовательной активности является подвести учащихся к пониманию того, что направленный граф является моделью дорожной сети, а работа навигационных сервисов основывается на применении модифицированного алгоритма Дейкстры на модели дорожной сети, где в качестве весовых значений ребер используются расчетные показатели времени проезда по ребру в указанном направлении. В связи с этим первым действием при планировании активности является выбор подходящего участка дорожной сети. Если учащиеся живут в населенном пункте, в котором актуальна ситуация периодических дорожных пробок, то лучше использовать фрагмент карты знакомой учащимся местности.
2.
Для выбранного фрагмента карты следует определить начальную и конечную точки маршрута. Обязательно, чтобы между точками существовало несколько альтернативных маршрутов. Желательно, чтобы таких альтернативных маршрутов было больше трех.
3.
Сделайте в геоинформационной системе расчет оптимального маршрута во время минимальной загрузки дорожной сети. Сделайте скриншот карты этого маршрута.
4.
Сделайте серию скриншотов ситуаций, когда на каких-то участках оптимального маршрута возникают пробки. Покажите, как изменяются маршруты в данном случае.
5.
На этом этапе занятия необходимо создать модель дорожной сети в виде направленного графа. Возможно, часть улиц имеет одностороннее движение.
Вершинами графа будут перекрестки, где возможно изменение маршрута.
Следует по возможности разнообразить карту маршрутов, поэтому стоит исходить из предположения, что пробка может возникнуть на любом ребре графа, чтобы определить возможные дополнительные вершины.
Обозначьте вершины непосредственно на карте.
6.
Постройте граф, соответствующий выбранному и размеченному фрагменту дорожной сети. Для этого графа создайте таблицу расстояний идеального маршрута (используйте расчеты навигатора, расстояние измеряется в минутах).
7.
Для каждого альтернативного маршрута, из числа предложенных навигатором или определенного искусственно, определите таблицу расстояний, при котором

он становится кратчайшим путем в графе.
Сохраните эти таблицы.
8.
Подготовьте серию таблиц с другими значениями расстояний на ребрах.
Задачей школьников будет, используя алгоритм Дейкстры, определить кратчайший путь в графе. Далее они могут проложить его на карте, чтобы визуализировать.
9.
Спланируйте этап рефлексии на занятии. Какие выводы сделали
школьники, что они поняли, чему научились?