Разработка урока по информатике в 9 классе "Деревья и остов графа".

9 класс

Модуль: моделирование и формализация.

Тема: Деревья и остов графа.

Цели:

образовательная – Сформировать представление у учащихся об иерархической системе и дереве. Рассмотреть понятия дерево, иерархическая система, остов графа.

воспитательная – воспитание интереса к изучаемому предмету;

развивающая – развитие познавательного интереса, умение работать самостоятельно.

Тип урока: урок с применением современных информационных технологий.

Форма урока: комбинированный.

Методы обучения: объяснительно-демонстрационные, практические.

Комплексно-методическое обеспечение: мультимедийный проектор, экран, программное обеспечение, компьютеры.

План урока:

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

2.Систематизация теоретических знаний.

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

4.Практическое задание.

5.Подведение итогов урока.

Ход урока ( в ходе всего урока демонстрируется презентация):

I.Организация урока       

В начале урока объявляется тема урока, цели урока и его план.

На прошлом уроке мы подробно рассмотрели графическую информационную модель – граф. Давайте вспомним основные понятия.                     

II.Опрос учащихся       

Опрос происходит по следующим вопросам:

1. Какие вы можете назвать примеры различных форм информационных моделей?

2. Приведите различные примеры графических информационных моделей.

3.Что такое граф?

4.Назовите элементы, из которых состоит граф?

5.Чем отличается дуга от ребра?

6.Что такое взвешенный граф?

7. Что на данном рисунке является весом?

                              26 км.

 

 9,4 км                    126,3 км.           11,2км.

 

                     41,8 км.                          56 км.

8. Какой из графов является ориентированным?

А) связи между населёнными пунктами

Б) родственные связи

 

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

Иерархия – расположение частей ил элементов целого порядка от высшего к низшему.

Иерархические системы – системы, элементы которых находятся в отношениях подчинённости (директор – начальник цеха – начальник участка – бригадир – рабочий), «Входит в состав» (федерация, республика, область, город, район), «Является разновидностью»,  и т.п.

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

            Графы   G1   и  G2 на рис. являются деревьями, а граф G3 – не дерево.

Корень дерева – «главная» вершина, которая не зависит ни от одной другой вершины и является единственной вершиной первого уровня.

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

 

Корень данного «географического дерева» - вершина «Планета Землая», листья – города. Вершины разделены на 5 уровней.

Опишите дерево:

 

       

 

Граф, все компоненты связности которого являются деревьями, называется лесом.

Граф на рис. является лесом, состоящим из двух деревьев.

Любой связный граф имеет остов.  Остовным деревом (остовом или каркасом) связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

 Остовное дерево графа не единственно.

На рис. изображен граф G и два его остовных дерева G1 и G2.

IV.Выполнение практического задания

Задача 1.

Сколькими способами можно рассадить в ряд на три стула трёх учеников? Выписать все возможные случаи.

Решение:

За корневую вершину возьмём произвольную точку плоскости О.

На первый стул можно посадить любого из трёх учеников – X, Y,Z.

                                   О

 

X                            Y                           Z      

Посадив на первый стул ученика Х, на второй стул можно посадить ученика Y или Z. Если же на первый стул сядет ученик  Y, то на второй можно посадить Х  или   Z. А если на первый стул сядет     Z, то на второй можно будет посадить Х или   Y. Это соответствует  на схеме двум ветвям, исходящим из каждой вершины первого уровня:    

                                                          О

             X                                      Y                                       Z

Y                                                                                                                 Y

      Z                                     X                          Z                            X

Третий стул в каждом случае займёт оставшийся ученик. Это соответствует одной ветви дерева, которая «вырастает» на каждой из предыдущих ветвей.

                                                       О

              X                                     Y                                      Z

 Y                                                                                                   Y

      Z                          X                               Z                        X

Z                                                                                                            X

       Y                              Z                           X                        Y

Выпишем все пути от вершин первого уровня к вершинам третьего уровня: X-Y-Z, X-Z-Y, Y-X-Z, Y-Z-X, Z-X-Y, Z-Y-X. Каждый из выписанных путей определяет один из вариантов рассаживания учеников на стулья. Т.к. других путей нет, то искомое число способов – 6. Дерево можно не строить, если не требуется выписывать все возможные варианты, а нужно просто указать их число. Рассуждаем так: на первый стул можно усадить одного из трёх человек, на второй – одного из двух оставшихся, на третий – одного оставшегося: 3*2*1=6.

Задача 2.

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

1.               Иди сейчас по правой тропинке;

2.               На следующей развилке не выбирай правую тропинку;

3.               На третьей развилке не ходи по левой тропинке.

Пролетевший мимо голубь шепнул Ивану – царевичу, что только один совет ворона верный и что обязательно надо пройти по тропинкам разных направлений. Наш герой выполнил задание и попал в волшебный сад. Каким маршрутом он воспользовался?

Решение: Обозначим тропинки Л- левую, П- правую, С- среднюю. Возможные маршруты в виде графа. При этом подсказки ворона отметим более «жирными» рёбрами. Т.к. только один совет ворона верен, то на графе ему будет соответствовать маршрут, имеющий одно «жирное» ребро. Этот маршрут обозначен пунктирной линией:

                П              С      П                Л            С             Л

 

                    С             П    Л              П         Л                С

                         Л                             С                           П      

                                               

Задача 3.                                    О

Какой вид будет иметь дерево для формулы 5*(3+7)*(8-2) ?

Решение: Последовательность выполнения операций определяется при прохождении дерева от листьев к корню (снизу – вверх).  Последней выполняется операция, отмеченная в корне.

 

Домашнее задание:

·                 составить 4 уровня генеалогического древа своей семьи;

·                 построить дерево для арифметического выражения: 6*4+7*(9-1)

V. Подведение итогов урока. Выставление оценок.