Что такое 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
  • Количество просмотров: 129
  • Количество скачиваний: 0
- Предыдущая Подарок маме к 8 марту
Следующая - Компьютерные вирусы и антивирусные программы

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

Урок по теме Организм человека 3 класс Урок по теме Организм человека 3 класс 103
Сонный Треугольник и Доступ к Сонным Артериям Сонный Треугольник и Доступ к Сонным Артериям 111
Прагматические аспекты перевода Прагматические аспекты перевода 112
1000 мелочей 1000 мелочей 78
Презентация :В гостях у сказки презентация Презентация :В гостях у сказки презентация 121
Міжнародні стандарти аудиту Міжнародні стандарти аудиту 80
мастер -класс Сюрприз для деда и бабы презентация к уроку (средняя группа) мастер -класс Сюрприз для деда и бабы презентация к уроку (средняя группа) 102
Голубые фишки Голубые фишки 106
НЕОПРЕДЕЛЕННЫЙ ИНТЕГРАЛ НЕОПРЕДЕЛЕННЫЙ ИНТЕГРАЛ 136
85
Презентация по краеведению Своя игра по теме Герои Мантуровцы (к дню Героев России) Презентация по краеведению Своя игра по теме Герои Мантуровцы (к дню Героев России) 135
Среднесрочный проект Театр для всех проект (средняя группа) Среднесрочный проект Театр для всех проект (средняя группа) 116
Презентация по казахскому языку на тему Абай- дана, Абай -дара (6 класс) Презентация по казахскому языку на тему Абай- дана, Абай -дара (6 класс) 125
Presentation Presentation 94
Презентация Презентация 122
Отчёт о работе по внеурочной деятельности. презентация к уроку (1 класс) Отчёт о работе по внеурочной деятельности. презентация к уроку (1 класс) 137
Животные пустынь Животные пустынь 86
Презентация по краеведению.Интерактивная игра-викторина Литературная карта г.Гусева9-11классы Презентация по краеведению.Интерактивная игра-викторина Литературная карта г.Гусева9-11классы 129
Дидактическая игра Домашние и дикие животные тренажёр по развитию речи (средняя группа) Дидактическая игра Домашние и дикие животные тренажёр по развитию речи (средняя группа) 33
Педагогический проект Развитие речи детей младшего дошкольного возраста. проект (младшая группа) Педагогический проект Развитие речи детей младшего дошкольного возраста. проект (младшая группа) 101
Ультразвук.Защита от ультразвука Ультразвук.Защита от ультразвука 110
Физиологические особенностипитания и пищеварительной системы собак и кошек.  Физиологические особенностипитания и пищеварительной системы собак и кошек.  97
Свадебный каравай Свадебный каравай 144
Цель в жизни Цель в жизни 119
Консультация для родителей. Тема Развитие мелкой моторики у детей через нетрадиционные виды аппликации. презентация к уроку (подготовительная группа) по теме Консультация для родителей. Тема Развитие мелкой моторики у детей через нетрадиционные виды аппликации. презентация к уроку (подготовительная группа) по теме 108
Технология колбасных изделий Технология колбасных изделий 97
Дневник Kent pre-task Дневник Kent pre-task 83
Мастер-класс по лэпбуку для педагогов Зимние виды спорта методическая разработка Мастер-класс по лэпбуку для педагогов Зимние виды спорта методическая разработка 194
Презентация выступления на педсовете: Выбор сказкотерапии как всестороннее развитие дошкольников Презентация выступления на педсовете: Выбор сказкотерапии как всестороннее развитие дошкольников 128
Твои поступки презентация к уроку (1, 2, 3, 4 класс) Твои поступки презентация к уроку (1, 2, 3, 4 класс) 131