Презентация на тему "Информационные модели на графах. Пути в графах"

Содержание

• 
  Слайд 1

  Информационные модели на графах. Пути в графах

• 
  Слайд 2
  

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

• 
  Слайд 3
  

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

• 
  Слайд 4

  Что такое граф?

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

• 
  Слайд 5

  Какие виды графов вам известны ?

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

• 
  Слайд 6
  

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

• 
  Слайд 7

  Возвращаемся к условию задачи

• 
  Слайд 8
  

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

• 
  Слайд 9
  

  Давайте определимся с целями и задачами урока. Как вы их сформулируете?

  Цели… Как преобразовать информацию, представленную в табличной форме в граф Как определить все пути в графе Определить кратчайший путь

• 
  Слайд 10
  

  Еще раз проанализируем таблицу. Такую таблицу называют весовой матрицей. Какие особенности в таблице вы заметили?

• 
  Слайд 11
  

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

• 
  Слайд 12

  Теперь приступим к построению графа.

• 
  Слайд 13

  Проверим правильность построения

  A B C E D 2 9 8 10 16 11 3 1 4

• 
  Слайд 14
  

  Определим все пути в графе и расстояние, пройденное на этом пути (вес-расстояние в км.)

  A B C E D 2 9 8 10 16 11 3 1 4 Будем делать обход по графу в алфавитном порядке, т.е. сначала все пути через АВ, АС, 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 км

• 
  Слайд 15

  Кратчайший путь в данном графе : ABDCE – 10 км

  A B C E D 2 9 8 10 16 11 3 1 4

• 
  Слайд 16

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

• 
  Слайд 17

  Решение:

• 
  Слайд 18

  Задача из демоверсии ЕГЭ по информатике и ИКТ 2013 года:

• 
  Слайд 19

  Решение:

• 
  Слайд 20

  Подведем итоги:

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

• 
  Слайд 21

  Домашнее задание:Решите задачу из демоверсии ГИА-9 2013 года: