Презентация Презентация по информатике "Графические модели"

• 1 слайд

  Тема: Информационные модели
  Решение задания А5 КИМ
  

• 2 слайд

  Пример 1
  Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
  Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам.
  

• 3 слайд

  Решение
  1. поскольку нас интересуют только маршруты, НЕ проходящие через пункт В, столбец и строку, соответствующие этому пункту, можно удалить из таблицы:
  
  

• 4 слайд

  2. дальше действуем так же, как показано при решении следующих далее разобранных задач; причем из всех маршрутов нужно оставить только те, которые проходят через пункт Е
  3. первый шаг от А (в скобках указаны длины маршрутов):
  АС (4), AD (8)
  прямой маршрут AF не рассматриваем, потому что он не проходит через пункт E
  4. второй шаг
  ACD (7), ADC (11), ADE (13)
  маршрут ADF не рассматриваем, потому что он не проходит через пункт E
  

• 5 слайд

  5. третий шаг:
  ACDE (12), ADEF (18)
  маршрут ADEF дошел до пункта назначения;
  маршрут ADC продолжать не имеет смысла, потому что из C можно проехать только в пункты A и D, где мы уже были;
  маршрут ACDF не рассматриваем, потому что он не проходит через пункт E
  6. четвертый шаг:
  ACDEF(17)
  7. этот маршрут тоже дошел до пункта назначения, его длина меньше, чем для предыдущего, его и выбираем
  8. Ответ: 17.
  

• 6 слайд

  Домашнее задание:
  В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.
  
  

• 7 слайд

  Спасибо за внимание!
  
  

• 1 слайд

  Решение заданий А5 КИМ ЕГЭ
  
  Графические информационные модели
  ГКОУ «Бутушская СОШ-сад» Алхасов Р.М.
  

• 2 слайд

  Задание 1. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
  
  Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).
  

• 3 слайд

  Решение:
  1. начнём строить возможные маршруты из пункта A; за 1 шаг можно приехать в B, C или сразу в G (в скобках показаны длины маршрутов):
  AB(5), AD(12), AG(25)
  заметим, что G – это целевая точка (конечный пункт), поэтому мы уже имеем один полный маршрут длиной 25
  2. строим двух шаговые маршруты: из B дальше можно ехать в D (возврат в А неинтересен!)
  ABD (5 + 8 = 13)
  этот маршрут нет смысла продолжать, поскольку в D можно приехать быстрее: длина уже найденного маршрута AD равна 12
  3. из D можно ехать в B и C:
  ADB (12 + 8 = 20)
  ADC (12 + 2 = 14)
  

• 4 слайд

  третий шаг: маршрут ADB продолжать бессмысленно: из B можно вернуться только в A и D
  продолжаем маршрут ADC (14):
  ADCE (14 + 4 = 18)
  ADCF (14 + 5 = 19)
  ADCG (14 + 10 = 24)
  в последнем варианте мы приехали в конечный пункт, причем новый маршрут имеет длину 24 < 25, то есть, он короче найденного ранее
  четвёртый шаг: продолжаем маршрут ADCE:
  ADCEG (18 + 5 = 23)
  и маршрут ADCF:
  ADCFG (19 + 5 = 24)
  других продолжений (без возврата в уже посещённые пункты) нет, поэтому кратчайший маршрут – ADCEG, он имеет длину 23.
  Ответ: 23.
  

• 5 слайд

  Решение с помощью графов
  После первого шага:
  A
  B
  D
  5
  12
  +5
  +12
  G
  25
  +25
  

• 6 слайд

  После второго шага:
  A
  B
  D
  5
  12
  G
  25
  B
  С
  14
  20
  +5
  +12
  +25
  +2
  +8
  

• 7 слайд

  После третьего шага:
  A
  B
  D
  5
  12
  G
  24
  B
  С
  14
  20
  +5
  +12
  +25
  +2
  +8
  F
  E
  G
  +4
  +5
  +10
  25
  18
  19
  

• 8 слайд

  После четвёртого шага:
  A
  B
  D
  5
  12
  G
  24
  B
  С
  14
  20
  +5
  +12
  +25
  +2
  +8
  F
  E
  G
  +4
  +5
  +10
  25
  18
  19
  G
  G
  +5
  +5
  24
  23
  

• 9 слайд

  Задание 2. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
  
  Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
  

• 10 слайд

  A
  B
  C
  2
  4
  A
  B
  C
  E
  2
  4
  7
  1
  построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4):
  
  для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее
  например, из вершины В можно проехать в вершины C и E (длины путей соответственно 1 и 7):
  
  

• 11 слайд

  D
  A
  B
  C
  E
  2
  4
  7
  1
  3
  4
  D
  A
  B
  C
  E
  2
  4
  7
  1
  3
  4
  3
  новые маршруты из С – в D и E (длины путей соответственно 3 и 4):
  
  новый маршрут из D – в E (длина пути 3):
  
  

• 12 слайд

  новый маршрут из E – в F (длина пути 2):
  
  D
  F
  A
  B
  C
  E
  2
  4
  7
  1
  3
  4
  3
  2
  нужно проехать из А в F, по схеме видим, что в любой из таких маршрутов входит ребро EF длиной 2; таким образом, остается найти оптимальный маршрут из A в E
  

• 13 слайд

  попробуем перечислить возможные маршруты из А в Е:
  А – В – Едлина 9
  А – В – С – Е длина 7
  А – В – C – D – Е длина 9
  А –C – Е длина 8
  А –C – B – Е длина 12
  А –C – D – Е длина 10
  из перечисленных маршрутов кратчайший – A-B-C-E – имеет длину 7, таким образом общая длина кратчайшего маршрута A-B-C-E-F равна 7 + 2 = 9
  таким образом, правильный ответ – 9.
  

• 14 слайд

  Задание 3. Между четырьмя местными аэропортами: ОКТЯБРЬ, БЕРЕГ, КРАСНЫЙ и СОСНОВО, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:
  Аэропорт вылета Аэропорт прилета Время вылета Время прилета
  СОСНОВО КРАСНЫЙ 06:20 08:35
  КРАСНЫЙ ОКТЯБРЬ 10:25 12:35
  ОКТЯБРЬ КРАСНЫЙ 11:45 13:30
  БЕРЕГ СОСНОВО 12:15 14:25
  СОСНОВО ОКТЯБРЬ 12:45 16:35
  КРАСНЫЙ СОСНОВО 13:15 15:40
  ОКТЯБРЬ СОСНОВО 13:40 17:25
  ОКТЯБРЬ БЕРЕГ 15:30 17:15
  СОСНОВО БЕРЕГ 17:35 19:30
  БЕРЕГ ОКТЯБРЬ 19:40 21:55
  Путешественник оказался в аэропорту ОКТЯБРЬ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт СОСНОВО.
  

• 15 слайд

  Решение (граф):
  для решения можно построить граф, показывающий, куда может попасть путешественник из аэропорта ОКТЯБРЬ
  из аэропорта ОКТЯБРЬ есть три рейса:
  ОКТЯБРЬ СОСНОВО 13:40 17:25
  ОКТЯБРЬ КРАСНЫЙ 11:45 13:30
  ОКТЯБРЬ БЕРЕГ 15:30 17:15
  построим граф, около каждого пункта запишем время прибытия
  17:25
  ОКТЯБРЬ
  СОСНОВОО
  БЕРЕГ
  КРАСНЫЙ
  13:30
  17:15
  

• 16 слайд

  3. проверим, не будет ли быстрее лететь с пересадкой: рейс «КРАСНЫЙ-СОСНОВО» вылетает в 13:15, то есть, путешественник на него не успевает; он не успеет также и на рейс «БЕРЕГ-СОСНОВО», вылетающий в 12:15
  4. таким образом, правильный ответ – 4 (прямой рейс).
  

• 17 слайд

  Дамашнее задание:
  Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.
  

• 1 слайд

  Решение заданий А5 КИМ ЕГЭ
  
  Графические информационные модели
  ГКОУ «Бутушская СОШ-сад» Алхасов Р.М.
  

• 2 слайд

  Задание 1. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
  
  Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).
  

• 3 слайд

  Решение:
  1. начнём строить возможные маршруты из пункта A; за 1 шаг можно приехать в B, C или сразу в G (в скобках показаны длины маршрутов):
  AB(5), AD(12), AG(25)
  заметим, что G – это целевая точка (конечный пункт), поэтому мы уже имеем один полный маршрут длиной 25
  2. строим двух шаговые маршруты: из B дальше можно ехать в D (возврат в А неинтересен!)
  ABD (5 + 8 = 13)
  этот маршрут нет смысла продолжать, поскольку в D можно приехать быстрее: длина уже найденного маршрута AD равна 12
  3. из D можно ехать в B и C:
  ADB (12 + 8 = 20)
  ADC (12 + 2 = 14)
  

• 4 слайд

  третий шаг: маршрут ADB продолжать бессмысленно: из B можно вернуться только в A и D
  продолжаем маршрут ADC (14):
  ADCE (14 + 4 = 18)
  ADCF (14 + 5 = 19)
  ADCG (14 + 10 = 24)
  в последнем варианте мы приехали в конечный пункт, причем новый маршрут имеет длину 24 < 25, то есть, он короче найденного ранее
  четвёртый шаг: продолжаем маршрут ADCE:
  ADCEG (18 + 5 = 23)
  и маршрут ADCF:
  ADCFG (19 + 5 = 24)
  других продолжений (без возврата в уже посещённые пункты) нет, поэтому кратчайший маршрут – ADCEG, он имеет длину 23.
  Ответ: 23.
  

• 5 слайд

  Решение с помощью графов
  После первого шага:
  A
  B
  D
  5
  12
  +5
  +12
  G
  25
  +25
  

• 6 слайд

  После второго шага:
  A
  B
  D
  5
  12
  G
  25
  B
  С
  14
  20
  +5
  +12
  +25
  +2
  +8
  

• 7 слайд

  После третьего шага:
  A
  B
  D
  5
  12
  G
  24
  B
  С
  14
  20
  +5
  +12
  +25
  +2
  +8
  F
  E
  G
  +4
  +5
  +10
  25
  18
  19
  

• 8 слайд

  После четвёртого шага:
  A
  B
  D
  5
  12
  G
  24
  B
  С
  14
  20
  +5
  +12
  +25
  +2
  +8
  F
  E
  G
  +4
  +5
  +10
  25
  18
  19
  G
  G
  +5
  +5
  24
  23
  

• 9 слайд

  Задание 2. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
  
  Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
  

• 10 слайд

  A
  B
  C
  2
  4
  A
  B
  C
  E
  2
  4
  7
  1
  построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4):
  
  для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее
  например, из вершины В можно проехать в вершины C и E (длины путей соответственно 1 и 7):
  
  

• 11 слайд

  D
  A
  B
  C
  E
  2
  4
  7
  1
  3
  4
  D
  A
  B
  C
  E
  2
  4
  7
  1
  3
  4
  3
  новые маршруты из С – в D и E (длины путей соответственно 3 и 4):
  
  новый маршрут из D – в E (длина пути 3):
  
  

• 12 слайд

  новый маршрут из E – в F (длина пути 2):
  
  D
  F
  A
  B
  C
  E
  2
  4
  7
  1
  3
  4
  3
  2
  нужно проехать из А в F, по схеме видим, что в любой из таких маршрутов входит ребро EF длиной 2; таким образом, остается найти оптимальный маршрут из A в E
  

• 13 слайд

  попробуем перечислить возможные маршруты из А в Е:
  А – В – Едлина 9
  А – В – С – Е длина 7
  А – В – C – D – Е длина 9
  А –C – Е длина 8
  А –C – B – Е длина 12
  А –C – D – Е длина 10
  из перечисленных маршрутов кратчайший – A-B-C-E – имеет длину 7, таким образом общая длина кратчайшего маршрута A-B-C-E-F равна 7 + 2 = 9
  таким образом, правильный ответ – 9.
  

• 14 слайд

  Задание 3. Между четырьмя местными аэропортами: ОКТЯБРЬ, БЕРЕГ, КРАСНЫЙ и СОСНОВО, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:
  Аэропорт вылета Аэропорт прилета Время вылета Время прилета
  СОСНОВО КРАСНЫЙ 06:20 08:35
  КРАСНЫЙ ОКТЯБРЬ 10:25 12:35
  ОКТЯБРЬ КРАСНЫЙ 11:45 13:30
  БЕРЕГ СОСНОВО 12:15 14:25
  СОСНОВО ОКТЯБРЬ 12:45 16:35
  КРАСНЫЙ СОСНОВО 13:15 15:40
  ОКТЯБРЬ СОСНОВО 13:40 17:25
  ОКТЯБРЬ БЕРЕГ 15:30 17:15
  СОСНОВО БЕРЕГ 17:35 19:30
  БЕРЕГ ОКТЯБРЬ 19:40 21:55
  Путешественник оказался в аэропорту ОКТЯБРЬ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт СОСНОВО.
  

• 15 слайд

  Решение (граф):
  для решения можно построить граф, показывающий, куда может попасть путешественник из аэропорта ОКТЯБРЬ
  из аэропорта ОКТЯБРЬ есть три рейса:
  ОКТЯБРЬ СОСНОВО 13:40 17:25
  ОКТЯБРЬ КРАСНЫЙ 11:45 13:30
  ОКТЯБРЬ БЕРЕГ 15:30 17:15
  построим граф, около каждого пункта запишем время прибытия
  17:25
  ОКТЯБРЬ
  СОСНОВОО
  БЕРЕГ
  КРАСНЫЙ
  13:30
  17:15
  

• 16 слайд

  3. проверим, не будет ли быстрее лететь с пересадкой: рейс «КРАСНЫЙ-СОСНОВО» вылетает в 13:15, то есть, путешественник на него не успевает; он не успеет также и на рейс «БЕРЕГ-СОСНОВО», вылетающий в 12:15
  4. таким образом, правильный ответ – 4 (прямой рейс).
  

• 17 слайд

  Дамашнее задание:
  Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.