Ключевые слова: информатика, навигаторы, алгоритм Дейкстры, моделирование, оптимизация, линейное программирование.
Цели:
- Развитие познавательных интересов;
- Формирование интереса к современным информационным устройствам, изучение принципа работы GPS-навигатора;
- Изучение нового материала, расширение знаний в области MS Excel; развитие практических навыков решения задач с помощью компьютера;
- Построение и решение задачи о кратчайшем пути в графе методом линейного программирования;
- Воспитание информационной культуры учащихся, расширение знаний в области информационных технологий;
- Расширение знаний по теме, использование материала ЕГЭ.
Тип урока: комбинированный: лекция, беседа по новому материалу с группой, выполнение практической работы индивидуально.
Целевая аудитория: 10-11 классы.
Методы:
- информационный (словесный);
- наглядно-иллюстративный;
- практический.
Формы организации учебной деятельности:
- изучение нового материала через беседу;
- практическая работа с раздаточным материалом;
- творческая домашняя работа;
Оборудование: проектор, экран, ноутбук, компьютеры
Материалы урока: конспект учителя (Приложение 1), раздаточный материал (Приложение 2).
Программное обеспечение: MS Office: PowerPoint, Excel.
Этапы урока:
- Организационный момент(3 мин.)
- Теоретическая часть (20 мин.)
- Постановка цели урока и мотивация, актуализация знаний по теме.
- Освоение нового материала, демонстрация презентации.
- Практическая часть (10 мин.)
- Практическая работа на компьютере. Анализ результатов.
- Проверка усвоения знаний учащимися, вопросы учителя, учащихся (5 мин.)
- Подведение итогов урока, домашнее задание (2 мин.)
Ход урока
I. Приветствие, проверка отсутствующих. Объявление темы урока, цели, задач.
(Слайды 1-2)
II. Теоретическая часть урока.
Слайд 3. Ответьте на вопросы.
Учитель предлагает учащимся ответить и поразмыслить над вопросами, ответы на которые мы получим в течение урока. Учащиеся отвечают – учитель направляет их мысли.
Учитель: «С древнейших времен, человечество старается найти ответы на два вопроса: «Где Я?» и «Куда мы идем?». Для того, что бы ответить на эти вопросы мы, люди, придумали массу способов ориентирования: (по солнцу, по звездам, по мху на деревьях, по елочным лапкам. Изобрели такой замечательный прибор как компас и нарисовали карты местности. А потом, когда стали ходить по морю, сама по себе появилась целая наука называемая Навигацией. Когда же люди поняли, что земля не плоская, а круглая смастерили глобус «обрисовали» его параллелями и меридианами. Теперь, где находятся север, юг, запад и восток знает любой школьник.
Слайд 4. Карта урока.
По карте учитель может в любой момент урока переключить внимание учащихся на наиболее важные моменты, пояснить материал, задать домашнее задание.
Слайд 5. Спутниковые системы.
Учитель: «Но и этого оказалось мало и тогда, Американские военные, запустили на орбиту несколько спутников и научили их связи, по средствам радиопередачи на особой частоте, с особыми приборчиками называемыми GPS-навигаторами. Этот прекрасный навигационный прибор в руках военных показывает свое место расположения на земле с погрешностью до нескольких сантиметров.
Со временем, Военные США запустили на спутниках еще несколько радиоканалов и поделились ими с гражданскими лицами. Если в руках военных погрешность составляет сантиметры, то гражданское оборудование может ошибаться в пределах 100 метров. Однако, гражданские лица, отказываться от навигаторов все равно не стали, а как раз наоборот, внедрили куда можно. Сначала навигаторы получили моряки и авиаторы потом работники скорой помощи, сейчас же мы дошли до того, что чудо прибор встраивается в некоторые гражданские автомобили на стадии производства. И становится GPS-навигатор в автомобиле привычным и необходимым».
Слайд 6. Российские системы навигации
Учитель предлагает посмотреть видеоролик о российской системе навигации ГЛОНАСС. Учащиеся смотрят, изучают принцип передачи и обработки информации.
Слайд 7. Компоненты системы мониторинга
Учитель: «В целом работает следующим образом:
Вокруг земли, с одной скоростью летает куча спутников, если точнее 24. Размещены они таким образом, что где бы Вы не находились, несколько из них находятся в небе над Вами. Искать спутники глазами – бесполезно т.к. они высоко (17 000 км) и маленькие (около 5 метров вместе с солнечными батареями). Для того, что бы определить Ваше положение на плоскости достаточно быть в зоне видимости 2-х спутников, но чем больше из них видя вас, тем лучше и точнее оно будет определено.
Люди, придумавшие GPS достойны всяческих похвал за саму идею, которая заключается в том, что спутник имеет внутренние, сверхточные часы и всегда знает, сколько времени там, где он пролетает. Устройство (Навигатор) получает сигнал от спутника, в котором сообщается его (спутника) время и местонахождения. Устройство сравнивает разницу во времени отправки сообщения и свое собственное время и понимает, насколько далеко оно от спутника. Два таких удаления и мы уже знаем точку на плоскости, а если три, то можно добавить и высоту или глубину»
Слайд 8. Принцип работы
Учитель предлагает задуматься над принципом работы устройств навигации. Опрашивает учащихся, может кто-то знает?
Учитель: «В наше время нас окружает огромное количество разнообразных приспособлений, призванных упростить нашу жизнь. Но используя их, мы не задумываемся над принципом их работы, не говоря уже о технических деталях. Одним из таких устройств является спутниковый навигатор. Несмотря на большую популярность GPS, алгоритмы, которые они используют в своей работе, не столь хорошо известны.
Слайд 9. Образцы портативных и специальных навигаторов.
Учитель: «Изучим самых ярких представителей – портативные, авиационные и морские навигаторы».
Учитель «На уроке мы должны разобраться с принципом взаимодействия и смоделировать работу устройства навигации».
Учитель: «Вспомним что такое модель, моделирование и какие основные этапы моделирования мы знаем?»
Учащиеся: «Формулировка задачи, информационная модель, математическая модель, решение – написание программы, получение результата, анализ результата, корректировка модели».
Слайд 10. Определения теории графов.
Учитель: «Чтобы решить задачу нам необходимо вспомнить определения. Что такое граф? Вершины, дуги графа? Ориентированный граф?»
Учащиеся читают, вспоминают определения, по кнопке Демонстрация на экране появляется наглядная иллюстрация.
Слайды 11-12. Алгоритм Дейкстры.
Учитель: «В навигаторах используется Алгоритм Дейкстры (1959г) для определения оптимального пути между двумя графами на карте. Навигатор, при введении начальной и конечной точки маршрута изучает расположение и длины граф, реорганизует все графы воедино и пытается определить все объекты, которые наиболее приближены к точке назначения. Единственный минус такого алгоритма состоит в том, что он не учитывает важности того или иного объекта, он считает, что все точки интереса одинаково важны, а ведь на самом деле, чем ближе объект к цели, тем он важнее или то, что по грунтовой дороге ехать труднее, чем по асфальтной трассе».
III. Практическая часть урока.
Слайд 13. Постановка задачи
Учитель формулирует задачу: «Для олимпийской столицы характерна транспортная напряженность? Постараемся решить эту проблему.
Дана сеть автомобильных дорог центрального района города Сочи. Необходимо найти кратчайшие пути от въезда в город (со стороны Туапсе) до выезда (на Адлер), чтобы быстрее добраться до Красной поляны.»
Учитель раздает учащимся материал для практической работы на карточках – то же самое будет отображаться на экране проектора, чтобы пошагово проконтролировать и направить учащихся.
Совместно учащиеся за компьютерами и учитель указывая на иллюстрации презентации проводят этапы нахождения кратчайшего пути графа, представленного на слайде 14.
Слайд 14. Информационная модель
Учитель предлагает дома рассмотреть с помощью GoogleMaps, Яндекс Карт различные карты города Сочи (съемка – Схема, Спутник, Гибрид).
Для решения задачи мы используем карту Сочи из материалов Яндекс’а:
Рисунок 1. Схематическое изображение автомобильных дорог Сочи. (оригиналы рисунков в большем размере в Приложении 3)
Путем линейной интерполяции – замены частей дорог отрезками на карте – можно приближенно рассчитать длину каждой улицы.
Допущения задачи:
- пренебрегаем наличием мостов;
- пренебрегаем погрешностью карты;
- используем линейную интерполяцию.
Построим граф.
Слайды 15-16. Математическая модель.
Рисунок 2
Учитель: «На графе вершины – пересечения дорог, длины дуг – длины дорог, км»
Рисунок 3
Слайд 17. Компьютерная модель
Так как по условию С1,2= 3, С1,3=5, С2,3=1, С2,4=1, С2,8=7, С3,5=2, С2,6=2, С3,8=3, С4,5=1, С4,7=4, С5,6=1, С6,7=1, С7,8=1 тогда
Рисунок 4
Слайд 18. Расчет с помощью Excel.
Занесем исходные данные, ограничения в электронную таблицу
Рисунок 5
Слайд 19. Надстройка «Поиск решения»
Рисунок 6
Рисунок 7
Рисунок 8
Сохраняем результаты и переходим к анализу полученного решения
Слайд 20. Результат работы программы
Учитель проверяет у всех ли учащихся получилось такое решение. Компьютер мог выдать альтернативный вариант решения, который тоже может быть верным.
Слайд 21. Анализ результатов.
Учитель: «Кратчайший путь включает ребра: (V1-V2); (V2-V3);(V3-V8). Длина пути составляет 8 км Турист должен проехать по улицам: Донская, Гагарина, Орджоникидзе, чтобы быстрее выехать из центра города».
IV. Проверка усвоения знаний учащимися, вопросы учителя, учащихся
Слайд 22. Рефлексия.
Учитель узнает, что нового учащиеся узнали на уроке. Какой принцип работы устройств навигации, в чем заключается алгоритм их работы и как найти кратчайший путь?
V. Подведение итогов урока, домашнее задание
Слайд 23. Домашнее задание
Учащимся предлагается изучить еще раз дома конспект урока и решить подобную задачу на закрепление материала. Для талантливых детей можно задать составление алгоритма Дейкстры на языке программирования.
Слайд 24. Дополнительный материал
Учитель может напомнить задачу из КИМ ГИА на тему графы и предложить решить ее для актуализации знаний по теме (Приложение 1). Задать дополнительно домашнее задание по вариантам КИМов.
Учитель благодарит всех за работу на уроке, прощается с учащимися.
Использованная литература:
- УМК Н.Д. Угриновича. Информатика и информационные технологии 10-11 класс.
- Исследование информационных моделей, элективный курс, Н. Угринович.
- В.В. Плаксин. Лекции по дискретной математике. ЮРГТУ (НПИ), Новочеркасск.
- Г.Л. Бродецкий, Д.А. Гусев. Экономико-математические методы и модели в логистике, М: Изд-во «Академия», 2012.
- А.К. Лопатин. Моделирование работы навигатор, Коломна.
Интернет-источники:
- ru.wikipedia.org/wiki/GPS – Википедия. Материал о GPS.
- review.1k.by/phone/GPS_navigatoryi_CHto_k_chemy_i_kak_eto_rabotaet-223.html – GPS-навигаторы. Что к чему и как это работает.
- autotracker.ua/ – Система мониторинга на транспорте.
- www.kub.ru/maps/sochi/ – Карты Сочи.