Сопоставление графа и таблицы

ИП Ширмамедов А.Э. Учебный центр “Центриум”
РАЗРАБОТКА ЗАНЯТИЯ по теме: «Сопоставление графа и таблицы» по дисциплине Информатика
Разработал:	Матвеев Дмитрий Николаевич, преподаватель информационных дисциплин
Москва, 2020

ЭТАПЫ УЧЕБНОГО ЗАНЯТИЯ

№ п/п	Наименование этапа занятия, вида деятельности	План. время
1.	Организационный момент	5
2.	Актуализация знаний и умений / проверка домашней работы	15
3.	Изучение нового материала	25
4.	Первичное закрепление новых знаний	35
5.	Проверка знаний	35
6.	Выводы, обобщения/рефлексия	4
7.	Домашнее задание	1

Лекционный материал

Соединение малых частей в единое целое

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

Пришло время собрать все полученные знания в единое целое! Сегодня нам предстоит сопоставить граф и таблицу. Казалось бы, а что сложного, мы же уже на прошлых занятиях строили граф по таблице, что новое нас ждет сегодня?

Дело в том, что в прототипе заданий, который мы сейчас разберем, есть некая изюминка. Граф все так же будет построен по таблице (нам уже это делать не придется), но названия пунктов на графе и названия пунктов в таблице совершенно разные! То есть чисто теоретически мы вообще не будем понимать какому пункту графа соответствует тот или иной пункт таблицы.

Рассмотрим конкретный пример:

            На рисунке схема дорог изображена в виде графа, а в таблице содержатся сведения о длине этих дорог в километрах. Так как таблицу и схему рисовали независимо друг от друга, то нумерация населенных пунктов никак не связана с буквенными обозначениями на графе. И помните, что длины ребер на графе никак не отражают длины дорог! Определите кратчайшее расстояние от пункта В до пункта Д

Тактика, которую я предлагаю применять, заключается в следующем: если мы ничего не знаем, то получается, что единственное, на что можно ориентироваться, это количество дорог, исходящих из каждого пункта.

Расставим это количество как на графе, так и в таблице.

Можно обратить внимание, что у нас имеются уникальные пункты Д и А. Чем они уникальны? А это единственные пункты, с которыми связаны 6 дорог и 4 дороги соответственно. Делаем вывод, что П2 – это пункт Д, а П4 – это пункт А. Остались только двойки и тройки в большом количестве. Но какие-то из них так же являются уникальными. Обратим внимание на пункт А. Он ведет в Д (его мы определили), а также в две двойки и одну тройку. Эта тройка – уникальная, т.к. это единственная тройка, в которую ведет дорога из пункта А. Сопоставляем это с таблицей и видим, что П7 – это та самая тройка, то есть П7 – это пункт Б. Тогда В – единственная общая двойка для А и Б. Тогда П5 – это В. Г – единственный неизвестный пункт, в который ведет пункт А. Тогда П6 – это Г.

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

А дальше расставляем все известные длины (то есть нагружаем наш граф). Получаем следующую картинку:

          Теперь решаем задачу, которую мы решали на прошлых занятиях. Ищем кратчайшее расстояние от пункта В до Д. Очевидно, что в нашем случае это 6.

          Ответ: 6

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

Определите длину дороги GF, если известно, что длина дороги DE меньше, чем длина дороги AB.

Расставляем количество дорог и понимаем, что однозначно можно найти только Е, т.к. это единственная двойка, ведущая в две тройки. Делаем вывод, что П4 – это Е.

Все, дальше ничего точно сказать нельзя, остается только предполагать. Предполагать нужно тоже с умом. Очевидно, что здесь проще предположить, какая из оставшихся двоек А, а какая В.

Предположим, что П5 – это А, а П7 – это В. Тогда П3 – это G, А П2 – это С. Тогда можно найти D – это П6, и остается только F, то есть П1.

Получаем такую картину

Давайте проверим условие, что длина дороги DE меньше, чем длина дороги AB, Длина дороги DE – 17, длина дороги AB – 18.

Нам повезло, условие выполнилось, значит мы сделали верное предположение. Остается ответить на вопрос о длине дороги GF. Она равна 20.

Ответ: 20

Практическая работа №4

Тема: Сопоставление графа и таблицы

Цель работы: Отработка полученных на уроке навыков

Задания к работе:

1)      Сопоставьте названия пунктов и их нумерацией. Галочка обозначает, что дорога между двумя пунктами имеется, но ее длина не указана. Допустим, что П1 – Б, П2 – А, П3 – В, то ответ надо записать в виде БАВ.

 

2)      Определите длину дороги из Г в Д

 

3)      Найдите кратчайшее расстояние между пунктами E и G

 

4)      Определите, какие номера пунктов могут соответствовать пунктам Б и В. Ответ запишите номера пунктов в порядке возрастания и без пробелов.

 

5)      Определите пункт, с которым связано наименьшее количество дорог. Если у нескольких пунктов число дорог одинаково, то выберите тот, который имеет стоит ближе к концу латинского алфавита.

 

Самостоятельная работа №4

Тема: Сопоставление графа и таблицы

Цель работы: Оценивание приобретенных на уроке навыков

Задания к работе:

1)      Найдите длину самого длинного по количеству ребер маршрута от пункта А до пункта П1 (учитывая то, что по одной дороге можно пройти только один раз)

 

2)      Перед вами созвездие дельфина. Определите номера пунктов, образующих его хвост. В ответ запишите только номера пунктов без пробелов и разделителей, причем первое число – пункт соединения хвоста и тела, а второе число – конец хвоста.

 

3)      Перед вами созвездие медведя. Определите номера пунктов, которые могут соответствовать пунктам В и Г. В ответ запишите два числа друг за другом без разделителей в порядке убывания.

 

4)      Определите номер пункта G, если известно, что длина дороги CF меньше, чем длина дороги СG.

 

5)      Определите кратчайшее расстояние между пунктами Г и Д.

Краткое описание документа:

Это разработка занятия для учебных центров (или комплекса занятий для школы) по теме: "Динамическое программирование в решении задач на количество программ".

Материал, разработанный мной, позволит провести занятие по подготовке к ЕГЭ (ЕГЭ 2021 №23).

Материал включает в себя практическую и самостоятельную работу.