Муниципальное бюджетное образовательное учреждение «Новоаганская общеобразовательная средняя школа №1»
© Коротаева Н.Е.
учитель информатики и ИКТ
МБОУ «Новоаганская ОСШ №1»
Структуры данных: деревья, сети, графы, таблицы
10 класс
Оборудование для педагога:
компьютер с мультимедийным проектором
Оборудование для учащихся:
компьютер, программа тестирования MyTestXPro , рабочие тетради, учебник для 10-11 класса, карточки с дидактическим материалом
Тип урока: комбинированный Вид урока: лекция, беседа, самостоятельная работа с учебником
Форма урока:
классно-урочная форма обучения, фронтальный опрос, индивидуальная работа на компьютерах, коллективная форма организации работы
- ввести классификацию структур информационных моделей;
- сформировать понятия «граф», «деревья», «сети», «таблицы»;
- ознакомить обучающихся с граф-моделями и табличными моделями систем, сформировать умение строить такие модели, использовать их для решения практических задач.
- развивать умение оценивать свою учебную деятельность и деятельность своего партнера;
- развивать умения выделять главное, сравнивать, анализировать, обобщать.
- стимулировать интерес обучающихся к информационным технологиям;
- пробудить интерес к самостоятельному решению задач.
Знать :
- понятия «граф», «дерево», «сеть», «таблица»;
- структуры информационных моделей;
- структуру и типы таблиц.
Уметь :
- ориентироваться в граф-моделях;
- строить граф-модели (деревья, сети, таблицы) по вербальному описанию системы;
- строить различные по типу таблицы.
- Организационный момент – 1 минута.
- Проверка домашнего задания – 5 минут.
- Мотивация и целеполагание – 3 минуты.
- Изучение нового материала – 12 минут.
- Первичная проверка понимания знаний – 4 минуты.
- Физминутка для глаз – 1 минута.
- Закрепление нового материала – 10 минут.
- Рефлексия урока – 2 минуты.
- Подведение итогов – 1 минуты.
- Задание на дом – 1 минута.
Цель: проверить готовность обучающихся к уроку.
- Взаимное приветствие.
- Проверка готовности к уроку.
- Организация внимания.
- Познакомить с критериями оценивания работу на уроке.
Приложение 4 Итоги урока
ЦЕЛЬ :
повторить базовые понятия изучаемой темы
Учитель выявляет затруднения (ошибки), возникшие при сдаче теста, оказывает помощь.
Выполнение теста позволяет проверить знания учащихся, полученные на прошлом уроке, подвести к постановке целей и задач на текущий урок.
Тест. Приложение 1.
3. Приведите примеры материальных моделей, не упомянутые в параграфе.
4. Назовите типы информационных моделей.
Модель - это объект, который используется в качестве «заместителя», представителя другого объекта (оригинала) с определённой целью.
Виды моделей: натурные и информационные
3. Приведите примеры материальных моделей, не упомянутые в параграфе.
Муляж яблока, глобус, манекен.
4. Назовите типы информационных моделей.
Типы информационных моделей: вербальные, графические, табличные, математические.
- Что такое информационная модель?
- Можно ли карту города назвать информационной моделью? Поясните.
- Что такое компьютерная информационная модель?
- Что такое информационная модель?
Информационная модель – это описание в той или иной форме объекта моделирования.
- Можно ли карту города назвать информационной моделью?
Можно.
- Что такое компьютерная информационная модель?
Компьютерная информационная модель – информационные модели, реализованные на компьютере.
Цель:
- подготовить учащихся к самостоятельному формулированию целей и задач урока;
- актуализировать и закрепить опорные знания учащихся, необходимые для создания информационных моделей на основе системного анализа.
Реализация цели осуществляется через составление графа, который через системный анализ объекта моделирования подготавливает обучающихся к самостоятельному определению и формулированию целей и задач урока.
9
- В разговорной речи мы часто используем словесное (вербальное) представление информации. Например, словестное описание некоторой местности: «Наш район состоит из пяти поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между поселков: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино». По такому описанию довольно трудно представить себе эту местность, нелегко и запомнить описание. А представьте себе, что поселков не 5, а 25! Как представить данную информацию, чтобы она стала понятной всем? Это словесное описание – словесная модель. Всё гораздо понятнее становится из схемы (на ней поселки обозначены первыми буквами своих названий).
Д
Б
К
М
Р
Район состоит их пяти поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино.
Сформулировать цели и задачи урока вы сможете сами. Закончите предложение, используя опорные фразы:
- Познакомлюсь с …
- Узнаю о ...
- Смогу поразмышлять …
- Приобрету знания...
- Задумаюсь о …
- Смогу проявить …
- Буду уметь...
ЦЕЛЬ :
- ввести понятия «структура данных», «граф», «сеть», «дерево» «таблица»;
- сформировать навыки построения графов, деревьев, по вербальному описанию системы;
- строить различные по типу таблицы.
Реализация целей этапа осуществляется через показ мультимедийной презентации, сопровождающейся комментариями учителя.
ТАБЛИЦЫ
ГРАФЫ
ИЕРАРХИЧЕСКИЕ СТРУКТУРЫ
Данные, на которых базируется информационная модель, представляют собой систему со всеми характерными признаками – элементным составом, структурой, назначением. Такие структурированные системы данных называют структурами данных.
ГРАФ – это средство для наглядного представления состава и структуры системы.
Сеть – граф, в котором вершины связаны между собой по принципу «многие ко многим».
Для сетей характерно наличие замкнутых путей – циклов .
Ребро графа
Вершина
графа
Вершины графа – это компоненты системы, изображаемые кругами, овалами, прямоугольниками и пр.
Ребро графа – это ненаправленная линия, связывающая компоненты между собой определенным образом.
Пример :
Известно, что существуют четыре группы крови человека. При переливании крови от одного человека к другому не все группы совместимы.
На схеме показаны возможные варианты переливания крови
I
III
II
IV
Дуги
Петля
Петля – линия, выходящая и входящая в одну и ту же вершину. Направленные линии называют дугами (в отличии от ребер неориентированных графов).
Пример :
Район состоит их пяти поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино.
Это словесное описание – словесная модель. По ней можно построить следующую схему – граф.
Д
Б
М
К
Р
Корень (единственная вершина 1-го уровня)
Вершины 2-го уровня (Ветви)
Вершины 3-го уровня (Листья)
Дерево – это граф, предназначенный для отображения вложенности, подчиненности, наследования между объектами. Между любыми двумя его вершинами существует единственный путь. Деревья не содержат циклов и петель.
Административная структура Российской Федерации
Российская Федерация
Центральный округ
Северо-Западный округ
Уральский округ
Приволжский округ
ХМАО-Югра
Курганская обл .
Тюменская обл.
ЯНАО
Нижневартовск
Сургут
Радужный
Династия Рюриковичей
Рюрик
Игорь
Святослав
Ярополк
Олег
Владимир
Святополк
Изяслав
Полоцкий
Борис
Ярослав
Глеб
Мстислав
Тмутараканский
Таблица – универсальное средство представления информации. В таблице может содержаться информация о различных свойствах объектов, об объектах одного класса и разных классов, об отдельных объектах и группах объектов.
Двоичные матрицы отражают качественную связь между объектами: есть связь или нет связи
Таблицы отражают взаимосвязь между различными объектами
Таблица ОС – это таблица, в которой рассматриваются объекты, принадлежащие одному классу.
Таблица 1. Административная структура Российской Федерации
- Объект – город
- Свойства – принадлежность к соответствующим административно-географическим зонам (Регион, Округ).
Таблица 1 – возможное представление иерархической структуры, изображенной на слайде
Таблица 2. Успеваемость
Таблица ОО – это таблица, которая описывает пары объектов и только одно свойство.
В такой таблице строки и столбцы могут поменяться местами:
в строках – информация о предметах, в столбцах – об учениках.
Двоичная матрица называется матрицей смежности: единицы стоят на пересечении строк и столбцов с названием смежных (соединенных дорог) поселков.
Таблица 3. Дорожная сеть
Таблица 3 представляет собой двоичную матрицу, соответствующую структуре сети на слайде
Таблица 4. Переливание крови
У матрицы, отражающей ориентированный граф, симметричности не будет.
Таблица 4 представляет собой матрицу смежности, соответствующую структуре ориентированного графа, изображенного на слайде
Цель:
- установить правильность и осознанность усвоения нового учебного материала;
- выявить пробелы и произвести своевременную коррекцию знаний.
Реализация цели осуществляется через заполнение итоговой таблицы и разгадывание кроссворда.
Система основных понятий
Структуры данных
Графы
Разновидности графа
Деревья
Тип связей в графе
Один ко многим
Элементы дерева
Сети
Корень
Таблицы
Единственность пути между вершинами
Элементы прямоугольной таблицы
Ветви
Строки
Листья
Многие ко многим
Столбцы
Элементы сети
Типы таблиц
Ячейки
Вершины
Ребра
Объект - свойство
Объект – объект
Двоичная матрица
Кроссворд Приложение 2
10
6
в
п
1
р
т
с
е
е
е
е
д
в
о
ь
3
8
г
т
д
у
а
р
2
9
7
ш
к
р
м
л
о
р
ф
м
а
ц
и
о
н
н
а
я
и
н
4
р
ф
н
д
а
е
е
н
л
ь
т
я
с
и
ь
л
5
Галкина И.А. учитель «Водоватовская СОШ» Арзамасского района, Нижегородской области
Цель : обеспечение усвоения новых знаний и способов действий на уровне применения в измененной ситуации.
Реализация цели на данном этапе работы осуществляется через использование вариативных заданий, предоставление обучающемуся возможности выбора при их выполнении, использование наиболее значимых для него способов проработки учебного материала. Дифференцированный подход позволяет обучающимся первой группы выполнять задание на репродуктивном уровне, вторая группа работает на конструктивном уровне, третья группа – на творческом уровне.
Работа выполняется на выбор учащегося в текстовом редакторе MS Word, либо в тетради.
Составление информационной модели подготавливает обучающихся к использованию приобретенных знаний и умений в практической деятельности и повседневной жизни .
Решение задач из учебника
№ 1. (стр. 79 учебника, задание 5)
№ 2. (стр.79 учебника, задание 6)
№ 3 (стр.79 учебника, задание 10). Дополнительное задание творческого уровня
Приложение 3 Задание.
38
Цель : выявление уровня осознания содержания пройденного материала
Продолжите фразу:
- Сегодня я узнал…
- Я приобрел…
- У меня получилось …
- Я смог…
- Меня удивило…
- Урок дал мне для жизни…
- Мне захотелось…
- Было интересно…
- Было трудно…
- Я выполнял задания…
- Самым сложным при выполнении задания для меня было…
- Самым неожиданным при выполнении задания для меня было…
- Самым интересным при выполнении задания для меня было…
Цель : оценить работу каждого обучающегося с обязательным указанием положительных моментов; выставить отметки за работу на уроке
Приложение 4 Итоги урока
Цель : дать полную информацию о домашнем задании; прокомментировать предложенные на выбор задания
Учебник. § 14, стр. 79 - ответить на вопросы 1-5, 8, 9,12-14 (устно), 17 (письменно в тетради или на компьютере)
Обучающиеся
Группа 1
Уровень
Задание
Репродуктивный
Группа 2
Группа 3
Нарисуйте родословное дерево своей семьи (только по мужской или только по женской линии) с наибольшим числом известных вам уровней.
Конструктивный
Творческий
Нарисуйте родословное дерево своей семьи (только по мужской или только по женской линии) с наибольшим числом известных вам уровней. Полученное дерево приведите к табличной форме. В полях, значения которых неизвестны, поставьте прочерки.
Нарисуйте родословное дерево своей семьи (по мужской и по женской линии) с наибольшим числом известных вам уровней. Полученное дерево приведите к табличной форме. В полях, значения которых неизвестны, поставьте прочерки. Работу выполните на компьютере.
Самоанализ урока
42