733.87K
Категория: ИнформатикаИнформатика

Проектирование диагностических материалов по оценке качества знаний, достижения образовательных результатов

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.

1
3
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/
English     Русский Правила