Тема: Моделирование. Неориентированный и ориентированный графы. Задачи
презентация к уроку по информатике и икт (9 класс) на тему
Презентации с разбором задач и подборкой для самостоятельного решения.
Скачать:
Предварительный просмотр:
Подписи к слайдам:
Графы I. два варианта значения слова “граф”: 1) удобная форма описания структур типа дорожной сети или сети передачи данных; 2) математический объект G := (V, E), где V — это непустое множество вершин, а E — множество ребер (пар вершин). Для описания графа часто используют квадратную таблицу, которая описывает все возможные связи между узлами (без учета дублирования). Если, например, на пересечении строки A и столбца B записано число 1, это означает, что есть ребро, соединяющее вершины A и B; число 0 в этой ячейке означает, что такого ребра нет. Такую таблицу называют матрицей смежности .
А2 и А13 на графы Единица на главной диагонали (выделенной зеленым цветом) показывает, что в графе есть петля — ребро, которое начинается и заканчивается в одной и той же вершине. Неориентированный граф — ребра не имеют направления и каждое из них учтено в матрице смежности дважды. “ Длину” связей между вершинами называют “весом”. Весовая матрица
А2 и А13 на графы
Задача на «кратчайшее расстояние» ДЕМО 2013
Способ 1. Построение графа. А2. Задача на «кратчайшее расстояние» способы решения 1. Анализ весовой матрицы и количества ребер. AB=3, BC=7, BD=4, BE=7, CE=5, DE=2, EF=3 2. Построение графа. A B 3 C 7 E 7 D 4 5 2 F 3 3. Перебор путей из A в F. ABCEF=3+7+5+3=18 ABDEF=3+4+2+3=12 ABEF=3+7+3=13 ( лексикографический порядок)
Способ 2. Построение дерева возможных путей А2. Задача на «кратчайшее расстояние» способы решения 1. Определение вершины. 2. Построение графа. 3. Ответ ABDEF=12 E ,2 A B ,3 3 C ,7 7 E ,5 7 D ,4 4 5 2 F ,13 3 3 F ,18 E ,7 F ,12 3
А2. Задача на «кратчайшее расстояние» способы решения Способ 3. Перебор возможных путей без построения дерева 1. Все ребра от вершины A . AB=3 2. Все ребра из B (3 ребра). ABC=3+7=10 ABD=3+4=7 ABE=3+7=10 3. Все ребра из вершин С, D, E (3 ребра) . ABCD=10+2=12 ABDE=7+2=9 ABEF=10+3=13 – цель достигнута 4. Все ребра из вершин D,E ( 4 ребра). ABCDE=12+2=14 ABDEF=9+3=12 – цель достигнута 5. Ребра из вершины E (5 ребер) ABCDEF=14+3=17 – цель д-а Можно было не рассматривать, см. п.4. очевидно.
А2. Задача на «кратчайшее расстояние» способы решения Способ 4. Использование алгоритма Дейкстры. Описание в статье К.Полякова на сайте http://kpolyakov.narod.ru/download/inf-2012-03b.pdf
Способ 1. Построение графа. Демо 2015, №5. Задача на «кратчайшее расстояние» Анализ весовой матрицы и количества ребер. AB= 5 , А D=12, AG=25, BD=8, CD=2, CE=4, CF=5, CG=10, EG=5, FG=5 2. Построение графа. 3. Перебор путей
Способ 1. Построение графа. Демо 2015, №5. Задача на «кратчайшее расстояние» 1. Анализ весовой матрицы и количества ребер. AB= 5 , А D=12, AG=25, BD=8, CD=2, CE=4, CF=5, CG=10, EG=5, FG=5 3. Перебор путей: 3.1 ABD=5+8=13 AD=12 AG=25 3.2 DCEG=2+4+5=11 DCG=2+10=12 DCFG=2+5+5=12 2. Построение графа. А G B F E D C 5 5 5 4 5 10 25 2 12 8 3.3 AD+DCEG=12+11=23 ADCEG
Способ 2 . Построение дерева Возможных путей Демо 2015, №5. Задача на «кратчайшее расстояние» 1. Определение вершины 2. Построение графа. 3. Перебор путей : AD 12 C 2 E 4 G 5 =12+2+4+5=23 AD 12 C 2 F 5 G 5 =12+2+5+5=24 AD 12 C 2 G 10 =12+2+10=24 AG 25 =25 A B,5 D,8 D,12 B,8 C,2 E,4 G,5 F,5 G,5 G,10 G,25
Задача на «кратчайшее расстояние» тренировочные задачи
Задача на «кратчайшее расстояние»
Задача на «кратчайшее расстояние» тренировочные задачи
Задача на «кратчайшее расстояние» тренировочные задачи Открытый банк заданий ГИА: http://opengia.ru/subjects/informatics-11/topics/1 Задание №12 f4c6 Задание №085029 Задание №049386 Задание №02 f448 Задание №14 F165 Задание №202015 Задание №2 D7F6D Задание №42 bfcc …
Предварительный просмотр:
Подписи к слайдам:
В9. Задача на «количество различных путей из одной вершины в другую» Компьютерное ЕГЭ 2012-13 ДЕМО 2013 Ориентированный граф. Разрешимость задачи требует отсутствия циклов.
ДЕМО 2015
Задача на «количество различных путей из одной вершины в другую» Способ 1. Перебор всех возможных путей «методом наблюдения» Все пути с АБ: АБДИЛ, АБДЖЛ, АБВДИЛ, АБВДЖЛ, АБВЖЛ 2. Все пути с АВ: АВДИЛ, АВДЖЛ, АВЖЛ 3. Все пути с АГ: АГВДИЛ, АГВДЖЛ, АГВЖЛ, АГЕЖЛ, АГЕКЛ 13 ПУТЕЙ
ДЕМО 2015
Все пути с АБ: АБДЛ, АБДИЛ, АБВДИЛ, АБВДЛ, АБВЖЛ 2. Все пути с АВ: АВЖЛ, АВДИЛ, АВДЛ 3. Все пути с АГ: АГВДИЛ, АГВДЛ, АГВЖЛ, АГЕЖЛ, АГЕКЛ 13 ПУТЕЙ
2013-В9. Задача на «количество различных путей из одной вершины в другую» Способ 2. Пошаговое построение всех возможных путей Все вершины из А: АБ, АВ, АГ 2. Все вершины, содержащие 2 ребра: АБД, АБВ, АВД, АВЖ, АГВ, АГЕ 3. Все вершины, содержащие 3 ребра: АБДИ, АБДЖ, АБВД, АБВЖ, АВДИ, АВДЖ, АВЖЛ , АГВД, АГВЖ, АГЕЖ, АГЕК 4. Все вершины, содержащие 4 ребра: АБДИЛ , АБДЖЛ , АБВДИ, АБВДЖ, АБВЖЛ , АВДИЛ , АВДЖЛ , АГВДИ, АГВДЖ, АГВЖЛ , АГЕЖЛ , АГЕКЛ 5. Все вершины, содержащие 5 ребер: АБВДИЛ, АБВДЖЛ, АГВДИЛ, АГВДЖЛ 13 ПУТЕЙ
Задача на «количество различных путей из одной вершины в другую» Способ 3. Подстановка 1. 13 ПУТЕЙ 1. Вершины, в которые можно прибыть только из А: N Б = N Г =1 2. N Л = N И +N Ж +N К = = N Д +( N Д + N В + N Е )+ N Е = =2 N Д +2 N Е + N В = 2( N Б + N В )+2 N Г + N В = =2 N Б +2 N Г +3( N Б + N А + N Г )=2+2+9=13 ДЕМО 2015
Задача на «количество различных путей из одной вершины в другую» Способ 4. Подстановка 2. 13 ПУТЕЙ вершина предыдущая N Б А 1 В АБГ 3 Г А 1 Д БВ 1+3=4 Е Г 1 Ж ДВЕ 4+3+1=8 И Д 4 К Е 1 Л ИЖК 4+8+1=13 ДЕМО 2015
Задача на «количество различных путей из одной вершины в другую» Задачи для тренировки
Задача на «количество различных путей из одной вершины в другую» Задачи для тренировки Задание №00 b853 http://opengia.ru/items/00b853739e1be3119859001fc68344c9 На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
По теме: методические разработки, презентации и конспекты
Презентация к уроку информатики 3класс по теме "Ориентированный граф"
Урок проходит в игровой форме , учащиеся помогают Бабе яге выполнить задания , тем самым знакомятся с новыми понятиями....
Практико-ориентированный проект по теме: «Моделирование современного урока литературы в условиях перехода в ФГОС второго поколения»
• Отличительной особенностью ФГОС является его деятельностный характер, ставящий главной целью развитие личности учащегося....
Обобщение опыта по теме "Моделирование при решении задач на движение на уроках математики".
Моделирование в обучении математике служит тем методическим приемом, который формирует у учащихся математические понятия и прививает им навыки математических действий. В то же время использовани...
презентация "Моделирование. Введение в теорию графов"
Презентация предназначена для проведения урока информатики в 11 классе (профильный уровень) по теме "Табличные и иерархические модели" . Содердит наглядно представленый теоретический материал и пример...
Открытый урок по геометрии 8 класс «Метод математического моделирования при решении мотивационно - прикладных задач по теме « Подобие треугольников»»
урок математического моделирования по теме " Подобие треугольников"...
презентация к уроку «Метод математического моделирования при решении мотивационно - прикладных задач по теме « Подобие треугольников»»
Презентация к открытому уроку " Метод математического моделирования при решении мотивационно - прикладных задач по теме " Подобие треугольников""...
Сценарий урока для 7 класса по теме "Ориентированный граф"
Планируемые результаты:Предметные:Знать: понятие ориентированный граф, чем он отличается от неориентированного графа.Уметь: составлять и различать ориентированный и неориентированный граф по заданному...