Структуры данных: деревья, сети, графы, таблицы.

МБОУ «Елизаветинская СОШ»

Структуры данных: деревья, сети, графы, таблицы

10 класс

Оборудование и программное обеспечение

компьютер с мультимедийным проектором

Рабочее место ученика

Windows 7

MS OFFICE 2010

Тип урока: комбинированный Вид урока: лекция, беседа, самостоятельная работа на ПК

Форма урока:

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

ЦЕЛИ УРОКА

Образовательная :

• ввести классификацию структур информационных моделей;
• сформировать понятия «граф», «деревья», «сети», «таблицы»;
• ознакомить обучающихся с граф-моделями и табличными моделями систем, сформировать умение строить такие модели, использовать их для решения практических задач.

Развивающая :

• развивать умение оценивать свою учебную деятельность и деятельность своего партнера;
• развивать умения выделять главное, сравнивать, анализировать, обобщать.

Воспитательная :

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

ЗАДАЧИ ДЛЯ УЧАЩИХСЯ

Знать :

понятия «граф», «дерево», «сеть», «таблица»;

структуры информационных моделей;

структуру и типы таблиц.

Уметь :

ориентироваться в граф-моделях;

строить граф-модели (деревья, сети, таблицы) по вербальному описанию системы;

строить различные по типу таблицы.

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

Что такое модель?

Модель - это объект, который используется в качестве «заместителя», представителя другого объекта (оригинала) с определённой целью.

Назовите виды моделей.

Виды моделей: натурные и информационные

Приведите примеры материальных моделей, не упомянутые в параграфе.

Муляж яблока, глобус, манекен.

Назовите типы информационных моделей.

Типы информационных моделей: вербальные, графические, табличные, математические.

Что такое информационная модель?

Информационная модель – это описание в той или иной форме объекта моделирования.

Можно ли карту города назвать информационной моделью?

Можно.

Что такое компьютерная информационная модель?

Компьютерная информационная модель – информационные модели, реализованные на компьютере.

Целеполагание

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

Д

Б

К

М

Р

Район состоит их пяти поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино.

Сформулировать цели и задачи урока вы сможете сами. Закончите предложение, используя опорные фразы:

Буду уметь…

Узнаю о...

Приобрету знания…

Смогу решить…

Смогу проявить…

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

ЦЕЛЬ :

• ввести понятия «структура данных», «граф», «сеть», «дерево» «таблица»;
• сформировать навыки построения графов, деревьев, по вербальному описанию системы;
• строить различные по типу таблицы.

Реализация целей этапа осуществляется через:

• Построение графа с использованием PowerPoint 2010.
• Построение таблиц с помощью EXCEL 2010

СТРУКТУРЫ ДАННЫХ

ТАБЛИЦЫ

ГРАФЫ

ИЕРАРХИЧЕСКИЕ СТРУКТУРЫ

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

Графы

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

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

Для сети также характерно наличие замкнутых путей, которые называются циклами .

Сеть – граф, в котором вершины связаны между собой по принципу «многие ко многим».

Для сетей характерно наличие замкнутых путей – циклов .

Ребро графа

Вершина

графа

Вершины графа – это компоненты системы, изображаемые кругами, овалами, прямоугольниками и пр.

Ребро графа – это ненаправленная линия, связывающая компоненты между собой определенным образом.

Ориентированный граф или несимметричная связь

I

Пример :

Известно, что существуют четыре группы крови человека. При переливании крови от одного человека к другому не все группы совместимы.

На схеме показаны возможные варианты переливания крови

III

II

IV

Дуги

Петля

Петля – линия, выходящая и входящая в одну и ту же вершину. Направленные линии называют дугами (в отличии от ребер неориентированных графов).

Неориентированный граф или симметричная связь

Пример :

Район состоит их пяти поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино.

Это словесное описание – словесная модель. По ней можно построить следующую схему – граф.

Б

Д

К

М

Р

Иерархические структуры - деревья

Корень (единственная вершина 1-го уровня)

Вершины 2-го уровня (Ветви)

Вершины 3-го уровня (Листья)

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

Примеры иерархических структур - деревьев

Административная структура Российской Федерации

Российская Федерация

Северо-Западный округ

Центральный округ

Сибирский округ

Приволжский округ

Омская

Томская обл .

обл.

Кемеровская обл.

Бийская обл.

Тарский

Черлакский

Саргатский

Примеры иерархических структур - деревьев

Династия Рюриковичей

Рюрик

Игорь

Святослав

Ярополк

Олег

Владимир

Святополк

Изяслав

Полоцкий

Борис

Ярослав

Глеб

Мстислав

Тмутараканский

ТАБЛИЦЫ

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

Элементы прямоугольной таблицы

Строки

Типы таблиц

Столбцы

Ячейки

Объект-свойство

Объект-объект

Двоичная матрица

Ученик

Ученик

Дата

15.03

Ботова

Иванов

Танцы

осадки

русский

Петров

1

Легкая атлетика

Иванова

алгебра

16.03

4

снег

Темпе ратура

4

- 15

0

5

дождь

0

3

- 20

1

Двоичные матрицы отражают качественную связь между объектами: есть связь или нет связи

Таблицы отражают взаимосвязь между различными объектами

Каждая строка относится к конкретному объекту

Пример таблицы «объект-свойство»

Таблица 1. Административная структура Российской Федерации

Город

Регион

Омск

Тюмень

Округ

Омская обл.

Тюменская обл.

Сибирский

Сургут

Уральский

Ханты-Мансийский АО

Нижневартовск

Ханты-Мансийский АО

Уральский

Сергиев Посад

Уральский

Московская обл.

Центральный

• Объект – гор

Пример таблицы «объект-объект»

Таблица 2. Успеваемость

Ученик

Предмет

Русский

Аликин Петр

Алгебра

Ботов Иван

4

Химия

3

Волков Илья

5

Физика

5

Галкина Нина

5

3

4

3

История

4

4

3

4

5

5

3

5

5

5

3

4

Таблица ОО – это таблица, которая описывает пары объектов и только одно свойство.

В такой таблице строки и столбцы могут поменяться местами:

в строках – информация о предметах, в столбцах – об учениках.

Пример таблицы «двоичная матрица» ( матрица смежности )

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

Таблица 3. Дорожная сеть

Поселок

Поселок

Бабкино

Бабкино

0

Дедкино

Дедкино

Кошкино

1

Кошкино

1

Репкино

Репкино

1

1

0

1

Мышкино

0

Мышкино

1

0

0

1

0

1

0

0

1

0

1

0

0

0

0

0

0

Таблица 3 представляет собой двоичную матрицу, соответствующую структуре сети на слайде

Пример таблицы «двоичная матрица»

Таблица 4. Переливание крови

Начальная вершина

Конечная вершина

I

I

1

II

II

1

0

III

III

1

0

IV

1

IV

1

0

0

0

1

1

0

0

1

1

У матрицы, отражающей ориентированный граф, симметричности не будет.

Таблица 4 представляет собой матрицу смежности, соответствующую структуре ориентированного графа, изображенного на слайде

Подведем итоги

Система основных понятий

Структуры данных

Графы

Разновидности графа

Деревья

Тип связей в графе

Один ко многим

Элементы дерева

Сети

Таблицы

Корень

Элементы прямоугольной таблицы

Единственность пути между вершинами

Ветви

Листья

Строки

Многие ко многим

Типы таблиц

Элементы сети

Столбцы

Ячейки

Вершины

Ребра

Объект - свойство

Объект – объект

Двоичная матрица

Рефлексия

Цель : выявление уровня осознания содержания пройденного материала

Продолжите фразу:

Сегодня я узнал…

Мне захотелось…

Было интересно…

Было трудно…

Я выполнял задания…

Самым сложным при выполнении задания для меня было…

Самым интересным при выполнении задания для меня было…

Подведение итогов

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

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

Нарисовать граф «Моё место в нашей галактике»