Похожие презентации:
Проектирование диагностических материалов по оценке качества знаний, достижения образовательных результатов
1.
Проектирование диагностических материалов по оценкекачества знаний, достижения образовательных результатов
Подготовка к ОГЭ
«Формальные описания реальных
объектов и процессов»
Витько Наталья Петровна
Учитель информатики ГБОУ СОШ № 310
г. Санкт-Петербург
2.
Содержание• Теория
• Разбор решений задач
• Задачи для самостоятельного решения
• Источники
3.
Определение кратчайшего путимежду пунктами
• Иногда очень трудно структурировать информацию описанными
структурами из-за сложных «взаимоотношений» между
объектами.
• В заданиях ОГЭ этой темы чаще всего используются две
информационные модели — таблицы и схемы (графы).
• Информация в таблице строится по следующим правилам: на
пересечении строки и столбца находится информация,
характеризующая комбинацию этой строки и столбца.
• На схеме (графе) информация строится по следующему правилу:
если между объектами схемы имеется связь, то она отображается
линией, соединяющей названия этих объектов на схеме.
4.
Граф – это набор вершин и связей междуними, называющихся рёбрами:
5.
Дерево – это связный граф без циклов(замкнутых участков)
6.
Взвешенный графУ взвешенных графов указан «вес ребра»:
7.
Весовая матрицаИз взвешенных
графов получается
весовая матрица,
обратное
преобразование
тоже возможно.
8.
ПОИСК КРАТЧАЙШЕГО ПУТИ(ПЕРЕБОР)
9.
Разбор задания 3.1.В таблице приведена стоимость перевозок между соседними
железнодорожными станциями, укажите схему, соответствующую таблице:
A
A
B
2
C
7
D
E
B
C
2
7
D
4
3
3
4
5
E
5
3
3
10.
Решение: Необходимо рассмотреть каждую схему иподсчитать количество ребер, выходящих из каждой
вершины. В скобках будем указывать соответствующую
данному «ребру» стоимость:
1 схема:
A: B(2), C(7), E(4)
B: A(2), C(4)
Здесь уже можно остановиться, т.к. для вершины B по
схеме два ребра,
а по таблице одно значение (B->A=2 )
11.
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
12.
Разбор задания 3.2.На схеме приведена стоимость перевозок между соседними
железнодорожными станциями, укажите таблицу,
соответствующую схеме:
13.
13
A
A
B
C
D
E
F
A
B
C
D
E
F
B
3
3
C
3
3
2
2
5
4
A
B
3
3
3
3
5
C
5
4
E
2
5
5
2
F
2
4
2
2
D
3
3
2
D
2
E
2
5
5
2
5
3
A
B
C
D
E
F
4
A
B
C
D
E
F
B
3
3
C
2
5
4
B
3
3
E
2
5
5
3
2
5
3
C
D
E
2
5
3
5
3
3
2
D
3
3
A
F
2
4
3
A
5
4
2
3
5
F
2
4
F
2
4
14.
A: B(3), E(2), F(2)Решение:
Необходимо рассмотреть каждую таблицу и подсчитать количество пересечений
для каждой строки, т.е. для каждой ж.д. станции. В скобках будем указывать
соответствующую данной станции стоимость:
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
15.
Разбор задания 3.3.• В таблице приведена стоимость перевозок между
соседними железнодорожными станциями. Укажите
таблицу, для которой минимальное расстояние от
точки A до точки F больше 8
1
3
A
A
B
C
D
E
F
C
3
2
3
D
5
4
5
5
A
A
B
C
D
E
F
B
2
B
E
2
3
2
3
D
3
4
E
5
1
3
5
F
2
2
4
2
1
2
2
5
4
C
F
4
4
4
A
A
B
C
D
E
F
3
4
C
3
4
D
4
2
4
2
E
4
2
2
B
2
2
F
2
4
A
A
B
C
D
E
F
B
2
C
D
3
5
E
F
5
5
3
3
3
5
3
3
2
2
16.
Решение:По дереву 1-й таблицы
видно, что каждая из
ветвей в результате
возвращает
сумму большую 8. То
есть таблица 1 соответс
твует искомому
результату.
Ответ: 1
17.
Задачи для самостоятельногорешения:
1.
Между населёнными пунктами А, В, С, D, Е, F построены дороги,
протяжённость которых (в километрах) приведена в таблице:
Определите
длину кратчайшего
пути между
пунктами А и F. Передвигать
ся можно только по дорогам,
протяжённость которых
указана в таблице.
1)
2)
3)
4)
5
6
7
8
A
A
B
5
C
5
B
C
D
5
5
4
2
1
1
E
5
2
F
2
D
F
E
4
1
1
3
3
1
1
18.
2.Водитель автомобиля должен добраться из пункта А в пункт D за 5 часов. Из
представленных таблиц выберите такую, согласно которой водитель сможет
доехать из пункта А в пункт D за это время.
В ячейках таблицы указано время (в часах), которое занимает дорога из
одного пункта в другой. Передвигаться можно только по дорогам, указанным в
таблицах.
1)
2)
3)
4)
1
2
3
4
19.
3. Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённостькоторых (в километрах) приведе. Определите длину кратчайшего пути между
пунктами А и E, проходящего через пункт C. Передвигаться можно только по
дорогам, протяжённость которых указана в таблице:
A
A
B
C
D
E
1
4
3
7
2
5
B
1
C
4
2
D
3
5
E
7
3
3
2
2
20.
4. Между населёнными пунктами А, В, С, D, Е, F построены дороги,протяжённость которых приведена в таблице:
Определите длину кратчайшего пути между пунктами А и F (при
условии, что передвигаться можно только по построенным дорогам).
21.
5. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённостькоторых приведена в таблице. Отсутствие числа в таблице означает, что прямой
дороги между пунктами нет. Определите длину кратчайшего пути между
пунктами A и F, не проходящего через пункт E. Передвигаться можно только по
указанным дорогам.
22.
6. Учитель Иван Петрович живёт на станции Антоновка, а работает настанции Дружба. Чтобы успеть с утра на уроки, он должен ехать по самой
короткой дороге. Проанализируйте таблицу и укажите длину кратчайшего
пути от станции Антоновка до станции Дружба:
23.
7. Между населёнными пунктами A, B, C, D, E, F построены дороги,протяжённость которых приведена в таблице. Отсутствие числа в таблице
означает, что прямой дороги между пунктами нет. Определите длину
кратчайшего пути между пунктами A и E, проходящего через пункт D.
Передвигаться можно только по указанным дорогам.
24.
8. На схеме нарисованы дороги между четырьмя населёнными пунктами A,B, C, D и указаны протяжённости данных дорог.
Определите, какие два пункта наиболее удалены друг от друга (при
условии, что передвигаться можно только по указанным на схеме дорогам).
В ответе укажите кратчайшее расстояние между этими пунктами.
25.
9. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённостькоторых (в километрах) приведена в таблице. Определите длину кратчайшего
пути между пунктами A и D, проходящего через пункт E. Передвигаться можно
только по дорогам, протяжённость которых указана в таблице.
26.
10. Между населёнными пунктами A, B, C, D, E построены дороги,протяжённость которых (в километрах) приведена в таблице. Определите
длину кратчайшего пути между пунктами B и E, не проходящего через
пункт А. Передвигаться можно только по дорогам, протяжённость которых
указана в таблице.
27.
Ответы:№
Верный ответ
задания
№
Верный ответ
задания
1
2
6
4
2
2
7
9
3
8
8
13
4
4
9
10
5
15
10
10
28.
Источники• https://labs-org.ru/oge
• https://inf-oge.sdamgia.ru
• https://www.kpolyakov.spb.ru/