• Ход урока 1. Сообщить учащимся тему урока. 2. Проверка домашнего задания
  • 3. Объяснение нового материала .
  • (Слайд 1) Графы
  • (слайд 4) Граф [graph
  • Петля
  • Следующий тип структур – это иерархические структуры (деревья)
  • (слайд 6) Дерево
  • «один ко многим»
  • (Слайд 7)
  • «объект – свойство».
  • Ученик Предмет Русский язык Алгебра
  • Начальная вершина Конечная вершина I II
  • 4. Закрепление нового материала
  • Ольга Мария Светлана Екатерина
  • 5. Подведение итогов 6. Задание на дом

  • Скачать 108.94 Kb.


    Дата18.10.2017
    Размер108.94 Kb.
    ТипУрок

    Скачать 108.94 Kb.

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



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

    Цели урока:

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

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

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

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

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

    • Создать условия для развития умения выделять главное, сравнивать, анализировать, обобщать.

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

    • Воспитывать внимательность, стремление довести дело до намеченного результата;

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

    План урока

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

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

    3. Объяснение нового материала

    4. Закрепление нового материала

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

    6. Задание на дом

    Ход урока

    1. Сообщить учащимся тему урока.

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

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



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

    • Назовите виды моделей (натурные и информационные)

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

    • Назовите типы информационных моделей (вербальные, графические, табличные, математические)

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

    • Можно ли карту города назвать информационной моделью? Ответ поясните.

    • Что такое компьютерная информационная модель? (информационные модели, реализованные на компьютере)

    • В чем преимущество компьютерных информационных моделей перед теоретическими?

    3. Объяснение нового материала.

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

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

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



    Графы

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



    1рис.1

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

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


    1. Р-К-Б-М

    2. Р-К-Д-Б-М

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

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

    Для сетей также характерно наличие замкнутых путей, которые называют циклами. На рис.1 имеется цикл К-Д-Б-К. Кстати, термин «дорожная сеть» используется и в разговорной речи.

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

    Рассмотрим другой пример графа (Слайд 3)



    3рис.2

    Граф на рис.2 показывает возможные варианты переливания крови. Группы крови обозначены вершинами графа. А стрелки указывают на возможность переливания одной группы крови человеку с другой группой крови.

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

    Итак, запишем словарь урока: (слайд 4)

    Граф [graph - от греч. - пишу, изображаю] – это средство для наглядного представления состава и структуры системы.

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

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

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

    Петля – это ребро, соединяющее вершину с нею самой.

    Вершины, которым не соответствует ни одно ребро, называются "изолированными".



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

    Число ребер, соединяющих две фиксированные вершины, может быть произвольным, поскольку оно определяется количеством и характером связей между соответствующими этим вершинам объектами, В то же время каждому ребру соответствует не более двух вершин.



    Следующий тип структур – это иерархические структуры (деревья)

    Иерархическую структуру имеют, например, системы административного управления, между элементами которых установлены отношения подчиненности. На рис.3 (слайд 5) изображен граф, отражающий иерархическую административную структуру нашего государства.



    2рис.3

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



    Запишем в словарь урока: (слайд 6)

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

    Обычно у дерева, отображающего иерархическую систему, выделяется одна главная вершина, которая называется корнем дерева. От нее идут ветви дерева. От корня начинается отсчет уровней дерева. Каждая вершина дерева (кроме корня) имеет одну исходную вершину на предыдущем уровне и может иметь множество порожденных вершин на следующем уровне. Такой принцип связи называется «один ко многим», в отличие от сети – там связь «многие ко многим». Вершины, которые не имеют порожденных вершин, называются листьями. На рис.3 листьями являются вершины, обозначающие города.

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

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

    Еще одним примером иерархической структуры является система доменных адресов в Интернете.

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



    (Слайд 7) Домашняя библиотека

    Автор

    Название

    Год издания

    Жанр

    А. Беляев

    «Человек – амфибия»

    2000 г.

    Фантастика

    А. Пушкин

    «Сказка о царе Салтане»

    2003 г.

    Поэтическая сказка

    Л. Толстой

    «Война и мир»

    1972 г.

    Трагедия

    А. Конан-Дойль

    «Голубой карбункул»

    1980 г.

    Детектив

    Данная таблица является примером таблицы типа «объект – свойство». Каждая строка такой таблицы относится к конкретному объекту. В нашем примере объект – это автор книги.

    Другой тип таблиц называется «объект – объект». Такие таблицы отражают взаимосвязь между различными объектами. Примером является таблица успеваемости учеников по разным предметам. Эта таблица отражает связь между объектами двух типов: учениками и изучаемыми дисциплинами. Оценка (расположена в ячейке) является характеристикой такой связи.



    (Слайд 8) Успеваемость

    Ученик

    Предмет

    Русский язык

    Алгебра

    Химия

    Физика

    История

    Музыка

    Иванов Петр

    4

    5

    5

    4

    4

    5

    Ботов Иван

    3

    3

    3

    3

    3

    4

    Волков Илья

    5

    5

    5

    5

    5

    5

    Галкина Нина

    4

    4

    5

    2

    4

    4

    Важной разновидностью таблиц типа «объект-объект» являются двоичные матрицы. Двоичные матрицы отражают качественную связь между объектами: есть связь или нет связи.

    (Слайд 9) Переливание крови

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

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

    I

    II

    III

    IV

    I

    1

    1

    1

    1

    II

    0

    1

    0

    1

    III

    0

    0

    1

    1

    IV

    0

    0

    0

    1

    Может возникнуть вопрос: зачем мы переводим графы в табличную форму? Ведь граф, с точки зрения человека, гораздо нагляднее и понятнее представляет структуру системы, чем таблица. Для человека это действительно так. Однако для компьютерной обработки табличная форма подходит лучше. Многие компьютерные технологии работают с таблицами (базы данных, электронные таблицы); обработку таблиц удобно описывать на универсальных языках программирования. Поэтому представление системы в форме графа обычно используется в теоретических моделях, а в компьютерном моделировании чаще работают с табличным представлением.

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

    Рассмотрим логическую задачу (Задание 16 (1) к §14)





    Иван

    Петр

    Семен

    Николай

    Иванов

    0

    1

    0

    0

    Петров

    0

    0

    1

    0

    Семенов

    1

    0

    0

    0

    Николаев

    0

    0

    0

    1

    Иванов Петр

    Петров Семен

    Семенов Иван

    Николаев Николай

    Европа

    Франция


    Париж

    4. Закрепление нового материала

    Учебник стр.79 Задание 5

    Ученик

    Школа


    Брат

    Сестра
    включает

    родственник посещает
    включает

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

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

    Третий граф ориентированный. Здесь обозначена связь «включает». Заметим, что можно нарисовать еще одну дугу такого же типа между вершинами «Европа» и «Париж». Однако она будет нести избыточную информацию, так как из факта, что Франция включает Париж, а Европа включает Францию, следует, что Европа включает Париж.


    В ячейки лучше вносить не единицы и нули, а + - и названия городов.




    Ольга

    Мария

    Светлана

    Екатерина

    Антон

    -

    -

    -



    Борис



    -

    -

    -

    Давид

    -

    -



    -

    Григорий

    -



    -

    -

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

    6. Задание на дом §14; вопросы и задания на стр.79


    Коьрта
    Контакты

        Главная страница


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

    Скачать 108.94 Kb.