Иерархия. Деревья. Графы

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

Задачи:

• Образовательные: проверить знания, полученные на предыдущем уроке, познакомить с понятиями иерархия, иерархическая система, дерево, совершенствовать умения строить графы при решении задач в различных учебных предметах.
• Развивающие: развитие творческих способностей, логического мышления учащихся, развитие умений делать анализ, выделяя объекты и обозначая связи между ними.
• Воспитательные: воспитание самостоятельности при выполнении  заданий, умения самостоятельно оценивать результат своей деятельности.
• Здоровьесберегающая: соблюдение правил ТБ, смена деятельности обучающихся во избежание переутомления.

ХОД УРОКА

1. Организационный момент.

Приветствие учащихся, отметка отсутствующих.

2. Проверка домашнего задания.

Проверка теоретического материала.

3. Изучение нового материала

Ответьте на следующие вопросы:

1. Что такое модель?
2. Назовите виды моделей (натурные и информационные)
3. Приведите примеры материальных моделей, не упомянутые в параграфе.
4. Назовите типы информационных моделей (вербальные, графические, табличные, математические)
5. Что такое информационная модель? (и.м. – это описание в той или иной форме объекта моделирования)
6. Можно ли карту города назвать информационной моделью? Ответ поясните.
7. Что такое компьютерная информационная модель? (информационные модели, реализованные на компьютере)
8. В чем преимущество компьютерных информационных моделей перед теоретическими?

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

Мы рассмотрим несколько часто используемых видов описания структур данных: графы, иерархические структуры (деревья) и таблицы.

(Записывают тему урока в тетрадь) 

 Графы

В разговорной речи мы часто используем словесное (вербальное) представление информации. Например, словестное описание некоторой местности: «Наш район состоит из пяти поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино». По такому описанию довольно трудно представить себе эту местность, нелегко и запомнить описание. А представьте себе, что поселков не 5, а 25! Всё гораздо понятнее становится из схемы  (на ней поселки обозначены первыми буквами своих названий)

Это не карта местности. Здесь не выднржаны направления по сторонам света, не соблюден масштаб. На этой схеме отражен лишь факт существования пяти поселков и дорожной связи между ними. Такая схема называется графом.

Глядя на этот граф, легко понять структуру дорожной системы в данной местности. Построенный граф позволяет, апример, ответить на вопрос: через какие поселки надо проехать, чтобы добраться из Репкино в Мышкино. Видно, что есть два возможных пути:

1. Р-К-Б-М
2. Р-К-Д-Б-М

Очевидно, первый путь более выгодный, он короче. Однако, если по какой-то причине дорога между К и Б окажется непроезжей, то единственным остается второй путь. Граф на рисунке 1 еще называют сетью.