Содержание
-
Подготовка к ОГЭ
«Формальные описания реальных объектов и процессов» Проектирование диагностических материалов по оценке качества знаний, достижения образовательных результатов
-
Содержание
Теория Разбор решений задач Задачи для самостоятельного решения Источники
-
Определение кратчайшего пути между пунктами
Иногда очень трудно структурировать информацию описанными структурами из-за сложных «взаимоотношений» между объектами. В заданиях ОГЭ этой темы чаще всего используются две информационные модели — таблицы и схемы (графы). Информация в таблице строится по следующим правилам: на пересечении строки и столбца находится информация, характеризующая комбинацию этой строки и столбца. На схеме (графе) информация строится по следующему правилу: если между объектами схемы имеется связь, то она отображается линией, соединяющей названия этих объектов на схеме.
-
Граф – это набор вершин и связей между ними, называющихся рёбрами:
-
Дерево – это связный граф без циклов (замкнутых участков)
-
Взвешенный граф
У взвешенных графов указан «вес ребра»:
-
Весовая матрица
Из взвешенных графов получается весовая матрица, обратное преобразование тоже возможно.
-
ПОИСК КРАТЧАЙШЕГО ПУТИ (ПЕРЕБОР)
-
Разбор задания 3.1.
В таблице приведена стоимость перевозок между соседними железнодорожными станциями, укажите схему, соответствующую таблице:
-
Решение: Необходимо рассмотреть каждую схему и подсчитать количество ребер, выходящих из каждой вершины. В скобках будем указывать соответствующую данному «ребру» стоимость: 1 схема: A: B(2), C(7), E(4) B: A(2), C(4) Здесь уже можно остановиться, т.к. для вершины B по схеме два ребра, а по таблице одно значение (B->A=2 )
-
2 схема: A: B(2), C(7), E(4) B: A(2) C: A(7), D(5), E(3) Здесь уже можно остановиться, т.к. для вершины C стоимость по схеме и по таблице различается: по схеме C->D = 5, а по таблице на пересечении C и D цифра 3. 3 схема: A: B(2), C(7), E(4) B: A(2) C: A(7), D(3), E(5) D: C(3), E(3) E: A(4), C(5), D(3) Схема 3 полностью соответствует таблице. Ответ: 3
-
Разбор задания 3.2.
На схеме приведена стоимость перевозок между соседними железнодорожными станциями, укажите таблицу, соответствующую схеме:
-
1 2 3 4
-
Решение: Необходимо рассмотреть каждую таблицу и подсчитать количество пересечений для каждой строки, т.е. для каждой ж.д. станции. В скобках будем указывать соответствующую данной станции стоимость: 1 таблица: A: B(3), E(2), F(2) -3 Здесь уже можно остановиться, т.к. для станции A по схеме два ребра у вершины А, а по таблице уже три значения 2 таблица: A: B(3), F(2) B: A(3), C(3), E(5), F(4) C: B(3), D(2), E(5) D: C(2), E(3) F: A(2), B(4) Таблица 2 полностью соответствует схеме. Ответ: 2 A: B(3), E(2), F(2)
-
Разбор задания 3.3.
В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите таблицу, для которой минимальное расстояние от точки A до точки F больше 8 1 2 3 4
-
Решение:
По дереву 1-й таблицы видно, что каждая из ветвей в результате возвращает сумму большую 8. То есть таблица 1 соответствует искомому результату. Ответ: 1
-
Задачи для самостоятельного решения:
1. Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых (в километрах) приведена в таблице: Определите длину кратчайшего пути между пунктами А и F. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. 1) 52) 63) 74) 8
-
2. Водитель автомобиля должен добраться из пункта А в пункт D за 5 часов. Из представленных таблиц выберите такую, согласно которой водитель сможет доехать из пункта А в пункт D за это время.В ячейках таблицы указано время (в часах), которое занимает дорога из одного пункта в другой. Передвигаться можно только по дорогам, указанным в таблицах. 1) 12) 23) 34) 4
-
3.Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведе. Определите длину кратчайшего пути между пунктами А и E, проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице:
-
4.Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена в таблице:
Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам).
-
5.Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами A и F, непроходящего через пункт E. Передвигаться можно только по указанным дорогам.
-
6. Учитель Иван Петрович живёт на станции Антоновка, а работает на станции Дружба. Чтобы успеть с утра на уроки, он должен ехать по самой короткой дороге. Проанализируйте таблицу и укажите длину кратчайшего пути от станции Антоновка до станции Дружба:
-
7. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт D. Передвигаться можно только по указанным дорогам.
-
8.На схеме нарисованы дороги между четырьмя населёнными пунктами A, B, C, D и указаны протяжённости данных дорог.Определите, какие два пункта наиболее удалены друг от друга (при условии, что передвигаться можно только по указанным на схеме дорогам). В ответе укажите кратчайшее расстояние между этими пунктами.
-
9. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшегопути между пунктами A и Е, проходящего через пункт C. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
-
10. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами B и E, не проходящего через пункт А. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.
-
Ответы:
-
Источники
https://labs-org.ru/oge https://inf-oge.sdamgia.ru https://www.kpolyakov.spb.ru/
Нет комментариев для данной презентации
Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.