Всегда выбирайте самый трудный путь, на нем вы не встретите конкурентов! Шарль де Голль. - презентация

1 Всегда выбирайте самый трудный путь, на нем вы не встретите конкурентов! Шарль де Голль

2 ABCDE A B291 C10934 D81311 E16411 В таблице представлено расстояние между населенными пунктами в километрах. Определить кратчайшее расстояние между пунктами A и E.

3 Тема урока: «Информационная модель. Граф. Пути в графах»

4 Актуализация знаний, умений и навыков Что такое информационная модель? Приведите примеры информационных моделей объектов. Какую информационную модель называют описательной? Как применяют информационную модель на практике?

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

6 Ответ прост: Графическая модель

7 История возникновения Графы возникли в восемнадцатом столетии, когда известный математик, Леонард Эйлер, пытался решить теперь уже классическую задачу о Кенигсбергских мостах. В то время в городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголь и друг с другом.

8 Что же такое граф? Граф это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Граф является информационной моделью некоторого объекта или системы объектов.

9 ГРАФЫ ориентированные неориентированные дуги рёбра

10 Взвешенный граф граф, каждому ребру или вершине которого поставлено в соответствие некое значение (вес).

11 Возвращаемся к условию задачи, озвученной в начале урока.

12 ABCDE A B291 C10934 D81311 E16411 В таблице представлено расстояние между населенными пунктами. Определить кратчайшее расстояние между пунктами A и E.

13 Еще раз проанализируем таблицу. Такую таблицу называют весовой матрицей. Какие особенности в таблице вы заметили? ABCDE A B291 C10934 D81311 E16411

14 Части таблицы, разделённые диагональю – симметричны, т.е. содержат одни и те же данные. Можно рассматривать данные любой половины таблицы, разделенной диагональю.

15 Приступим к построению графа ABCDE A B291 C10934 D81311 E16411 A B C E D

16 Определим все пути в графе и расстояние, пройденное на этом пути (вес-расстояние в км.) A B C E D Будем делать обход по графу в алфавитном порядке, т.е. сначала все пути через АВ, АС, AD и т.д. 1. ABCDE – 25 км 2. ABCE – 15 км 3. ABDCE – 10 км 4. ACBDE – 31 км 5. ACDE – 24 км 6. ACE – 14 км 7. ADCE – 15 км 8. ADE – 19 км 9. AE – 16 км

17 Кратчайший путь в данном графе : ABDCE – 10 км Кратчайший путь в данном графе : ABDCE – 10 км ABCDE A B291 C10934 D81311 E16411 A B C E D

18 Задача из демоверсии ГИА по информатике и ИКТ:

19 Решение: A B F D E AF=15 км 2.ABCDF=14 км 3.ACDF=13 км 4. ACEF=14 км 5.ABCEF=15 км C 5 5 2

20 По заданной таблице построить граф средствами, выписать все возможные пути и определить кратчайший из них. По заданной таблице построить граф средствами текстового процессора Open Office. Org. WRITER, выписать все возможные пути и определить кратчайший из них.

21

22 Подведем итоги: Мы вспомнили, что такое информационная модель Узнали, что такое граф Можем классифицировать графы по типам: ориентированный, неориентированный, взвешенный Можем на основе табличной информационной модели построить граф и определить все пути в нем На основе анализа всех путей в графе мы можем делать заключение о том, какой путь самый короткий.

23 Домашнее задание:

24 Всем спасибо! До свидания!