Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

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

Содержание

В таблице представлено расстояние между населенными пунктами в километрах. Определить кратчайшее расстояние между пунктами A и E.
Информационные модели на графах. Пути в графах В таблице представлено расстояние между населенными пунктами в километрах. Определить кратчайшее расстояние Для того, чтобы решить поставленную задачу, необходимо изменить форму представления информации в Что такое граф?Граф это множество точек или вершин и множество линий или Какие виды графов вам известны ?ГРАФЫориентированныенеориентированныедугирёбра Взвешенный граф — граф, каждому ребру или вершине которого поставлено в соответствие некое значение (вес). Возвращаемся к условию задачи В таблице представлено расстояние между населенными пунктами. Определить кратчайшее расстояние между пунктами A и E. Давайте определимся с целями и задачами урока. Как вы их Еще раз проанализируем таблицу. Такую таблицу называют весовой матрицей. Какие Части таблицы, разделённые диагональю – симметричны, т.е. содержат одни и те же Теперь приступим к построению графа. Проверим правильность построенияABCED298101611314 Определим все пути в графе и расстояние, пройденное на этом пути (вес-расстояние Кратчайший путь в данном графе : ABDCE – 10 км ABCED298101611314 Задача из демоверсии ГИА по информатике и ИКТ 2013 года: Решение: Задача из демоверсии ЕГЭ по информатике и ИКТ 2013 года: Решение: Подведем итоги:Мы вспомнили, что такое графМожем классифицировать графы по типам: ориентированный, неориентированный, Домашнее задание: Решите задачу из демоверсии ГИА-9 2013 года:
Слайды презентации

Слайд 2 В таблице представлено расстояние между населенными пунктами в

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

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

Слайд 3 Для того, чтобы решить поставленную задачу, необходимо изменить

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

форму представления информации в более удобную. Какая форма будет наиболее

оптимальна в данной ситуации?

Слайд 4 Что такое граф?
Граф это множество точек или вершин

Что такое граф?Граф это множество точек или вершин и множество линий

и множество линий или ребер, соединяющих между собой все

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

Слайд 5 Какие виды графов вам известны ?
ГРАФЫ
ориентированные
неориентированные
дуги
рёбра

Какие виды графов вам известны ?ГРАФЫориентированныенеориентированныедугирёбра

Слайд 6 Взвешенный граф — граф, каждому ребру или вершине

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

которого поставлено в соответствие некое значение (вес).

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

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

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

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

кратчайшее расстояние между пунктами A и E.

Слайд 9 Давайте определимся с целями и задачами урока. Как

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

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

в граф
Как определить все пути в графе
Определить кратчайший путь

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

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

матрицей. Какие особенности в таблице вы заметили?

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

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

одни и те же данные. Следовательно, можно рассматривать данные

любой половины таблицы, разделенной диагональю.

Слайд 12 Теперь приступим к построению графа.

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

Слайд 13 Проверим правильность построения
A
B
C
E
D
2
9
8
10
16
11
3
1
4

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

Слайд 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 –

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

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

Слайд 16 Задача из демоверсии ГИА по информатике и ИКТ

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

2013 года:

Слайд 17 Решение:

Решение:

Слайд 18 Задача из демоверсии ЕГЭ по информатике и ИКТ

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

2013 года:

Слайд 19 Решение:

Решение:

Слайд 20 Подведем итоги:
Мы вспомнили, что такое граф
Можем классифицировать графы

Подведем итоги:Мы вспомнили, что такое графМожем классифицировать графы по типам: ориентированный,


по типам: ориентированный, неориентированный, взвешенный
Можем на основе табличной информационной

модели построить граф и определить все пути в нем
На основе анализа всех путей в графе мы можем делать заключение о том, какой путь самый короткий.
  • Имя файла: informatsionnye-modeli-na-grafah-puti-v-grafah.pptx
  • Количество просмотров: 114
  • Количество скачиваний: 0
- Предыдущая Подарок маме к 8 марту
Следующая - Компьютерные вирусы и антивирусные программы

Похожие презентации

В чём суть изменений урока с введением ФГОС НОО опыты и эксперименты В чём суть изменений урока с введением ФГОС НОО опыты и эксперименты 127
Проект познавательно исследовательской деятельности Удивительная планета Земля проект по окружающему миру (подготовительная группа) по теме Проект познавательно исследовательской деятельности Удивительная планета Земля проект по окружающему миру (подготовительная группа) по теме 75
Острое аномальное маточное кровотечение Острое аномальное маточное кровотечение 80
Презентация Магазины бывают разные презентация к уроку (подготовительная группа) Презентация Магазины бывают разные презентация к уроку (подготовительная группа) 153
Влияние речи взрослого на развитие речи дошкольника материал Влияние речи взрослого на развитие речи дошкольника материал 105
Быстрая сортировка.quicksort Быстрая сортировка.quicksort 92
Презентация Портрет младшего дошкольника презентация Презентация Портрет младшего дошкольника презентация 86
3 3 87
Презентация Независимость судебной системы - миф или реальность Презентация Независимость судебной системы - миф или реальность 102
Кадастровая оценка с-х угодий Кадастровая оценка с-х угодий 118
Презентация по теме Классный уголок Презентация по теме Классный уголок 96
Презентация Инклюзивное образование материал Презентация Инклюзивное образование материал 99
Презентация Наш любимый детский сад презентация к уроку Презентация Наш любимый детский сад презентация к уроку 92
Специфика стандартизации в таможенной сфере Специфика стандартизации в таможенной сфере 102
Методическая разработка: Организация работы бассейна презентация к уроку по теме Методическая разработка: Организация работы бассейна презентация к уроку по теме 93
Методическая разработка Формы работы с родителями имеющих детей с интеллектуальной недостаточностью. методическая разработка ( группа) Методическая разработка Формы работы с родителями имеющих детей с интеллектуальной недостаточностью. методическая разработка ( группа) 107
Презентация к внеклассному мероприятию Денежная валюта стран мира Презентация к внеклассному мероприятию Денежная валюта стран мира 65
Отгадай загадки Отгадай загадки 85
Туристский офис Туристский офис 160
Взаимосвязь методики ознакомления дошкольников с социальной действительностью с другими науками презентация по теме Взаимосвязь методики ознакомления дошкольников с социальной действительностью с другими науками презентация по теме 103
Устройство Эндоскопов Устройство Эндоскопов 165
Основныемакроэкономическиепоказатели Основныемакроэкономическиепоказатели 80
ГАМЕТОГЕНЕЗ ГАМЕТОГЕНЕЗ 71
Строгановский дворец Строгановский дворец 98
Weird animal Weird animal 93
Развитие и коррекция речи детей посредством Лего-технологий презентация к уроку (старшая, подготовительная группа) Развитие и коррекция речи детей посредством Лего-технологий презентация к уроку (старшая, подготовительная группа) 78
Проект проект (старшая группа) по теме Проект проект (старшая группа) по теме 34
практикум для родителей Речевое дыхание материал (старшая группа) практикум для родителей Речевое дыхание материал (старшая группа) 78
Транзгенні та химерні організми Транзгенні та химерні організми 134
Поход в Эрмитаж презентация к уроку (младшая группа) Поход в Эрмитаж презентация к уроку (младшая группа) 96