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

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

Анатомо-физиологические особенности кожи новорожденных Анатомо-физиологические особенности кожи новорожденных 112
Проект Наш любимый с ребенком уголок Москвы (в рамках стажировочной площадки) материал (подготовительная группа) по теме Проект Наш любимый с ребенком уголок Москвы (в рамках стажировочной площадки) материал (подготовительная группа) по теме 112
Пластилинография, как средство развития мелкой моторики рук детей раннего и младшего дошкольного возраста презентация к уроку (младшая группа) Пластилинография, как средство развития мелкой моторики рук детей раннего и младшего дошкольного возраста презентация к уроку (младшая группа) 107
Презентация к проекту По следам сказок (часть 3) презентация к уроку (младшая группа) Презентация к проекту По следам сказок (часть 3) презентация к уроку (младшая группа) 107
Исследование фракталов в искусстве Исследование фракталов в искусстве 120
Первопечатник Иван Фёдоров Первопечатник Иван Фёдоров 110
Урок по Основам Светской этике 4 класс- Нравственные идеалы. Леди и джентльмены. презентация к уроку (4 класс) по теме Урок по Основам Светской этике 4 класс- Нравственные идеалы. Леди и джентльмены. презентация к уроку (4 класс) по теме 135
Презентация для педагогической гостиной По историческим залам Гуманной Педагогики Презентация для педагогической гостиной По историческим залам Гуманной Педагогики 119
Поставки стеновых материалов Кирпич Импортный и Отечественный, Газобетонные и стеновые блоки Поставки стеновых материалов Кирпич Импортный и Отечественный, Газобетонные и стеновые блоки 99
3d studio max 3d studio max 113
Эксплуатация скважин, оборудованных ШСНУ на Родниковом месторождении Эксплуатация скважин, оборудованных ШСНУ на Родниковом месторождении 115
Занимательные игры В.В. Воскобовича презентация к уроку (младшая, средняя, старшая, подготовительная группа) Занимательные игры В.В. Воскобовича презентация к уроку (младшая, средняя, старшая, подготовительная группа) 95
Консультация для родителей детей 6-7 лет Речевая готовность ребёнка к школе консультация (подготовительная группа) Консультация для родителей детей 6-7 лет Речевая готовность ребёнка к школе консультация (подготовительная группа) 104
Саратов Саратов 91
Трансформационная теория перевода Трансформационная теория перевода 153
Современное состояние рекламного рынка РФ Современное состояние рекламного рынка РФ 122
kzh btilre hm bure 1 kzh btilre hm bure 1 140
Портфолио студента педагогического колледжа Портфолио студента педагогического колледжа 337
Компьютерные технологии в проектировании среды Компьютерные технологии в проектировании среды 119
Нормы оценок в начальной школе презентация к уроку Нормы оценок в начальной школе презентация к уроку 60
История Ижевского оружейного производства История Ижевского оружейного производства 150
Индивидуализация образовательного процесса с учётом образовательных потребностей ребёнка материал Индивидуализация образовательного процесса с учётом образовательных потребностей ребёнка материал 138
Тканевая теория канцерогенеза Тканевая теория канцерогенеза 120
АНАЛИЗ ФИНАНСОВОЙ ОТЧЕТНОСТИ ПАО Нижнекамскшина АНАЛИЗ ФИНАНСОВОЙ ОТЧЕТНОСТИ ПАО Нижнекамскшина 92
Коммерческая тайна Коммерческая тайна 137
презентация презентация для интерактивной доски презентация презентация для интерактивной доски 100
Презентация Системы программирования. Объектно-ориентированное программирование Презентация Системы программирования. Объектно-ориентированное программирование 307
Эрмитаж (Виртуальная экскурсия) презентация к уроку (старшая группа) Эрмитаж (Виртуальная экскурсия) презентация к уроку (старшая группа) 64
ДИОКСИД СЕРЫ ДИОКСИД СЕРЫ 153
Презентация к открытому уроку Введение в образовательную программу Презентация к открытому уроку Введение в образовательную программу 116