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

Обновлено: 07.07.2024

Загрузить презентацию (144 кБ)

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

Формируемые умения: самоанализ вопросов теста, слушать, работать по учебнику, по карточкам.

Цели использования ИКТ: проверить теоретические знания с помощью теста, созданного в программе MyTestXPro, объяснить новый материал с использованием презентации MS PowerPoint, закрепить знания с помощью кроссворда, созданного в презентации MS PowerPoint, работа по карточкам в текстовом редакторе MS Word.

Этап урока, на котором использовались ИКТ: актуализация знаний, тестовый контроль, изучение нового материала.

Формы организации работы детей: индивидуальная, групповая, практическая.

Формы организации работы учителя: контроль, объяснение, консультирование.

Технологические особенности: личностно–ориентированная, дифференцированная, объяснительно– иллюстративное обучение, технология учебной дискуссии.

Технические условия

Используемое оборудование: компьютерный класс с установленным ПО (MS Power Point, MS Word, MyTestXPro), проектор, экран.

Разработанные цифровые образовательные ресурсы: подготовка теста в MyTestXPro, презентации нового материала урока, кроссворда.

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

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

Вложение	Размер
struktura_dannyh_derevya_grafy_tablitsy.docx	558.39 КБ

Предварительный просмотр:

Конспект открытого урока информатики на тему:

Класс: 10 (общеобразовательный)

Учитель: Гериханов Шахман Хамзатович

Дата проведения: 12.02.2019 г.

Тип урока: комбинированный

Учебник: Информатика и ИКТ. Базовый уровень: учебник для 10-11 классов/И.Г.Семакин, Е.К.Хеннер

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

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

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

Оборудование: компьютер учителя с мультимедийным проектором.

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

2. Проверка домашнего задания – фронтальный опрос (5 мин)

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

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

5. Подведение итогов (2 мин)

6. Задание на дом (1 мин)

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

2. Проверка домашнего задания – фронтальный опрос.

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

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

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

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

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

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

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

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

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

Рассмотрим другой пример графа рис.2

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

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

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

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

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

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

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

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

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

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

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

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

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

Запишем в словарь урока:

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

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

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

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

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

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

Конспект открытого урока информатики на тему:

Класс: 10 (общеобразовательный)

Учитель: Гериханов Шахман Хамзатович

Дата проведения: 12.02.2019 г.

Тип урока: комбинированный

Учебник: Информатика и ИКТ. Базовый уровень: учебник для 10-11 классов/И.Г.Семакин, Е.К.Хеннер

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

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

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

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

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

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

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

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

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

Оборудование: компьютер учителя с мультимедийным проектором.

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

2. Проверка домашнего задания – фронтальный опрос (5 мин)

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

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

5. Подведение итогов (2 мин)

6. Задание на дом (1 мин)

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

2. Проверка домашнего задания – фронтальный опрос.

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

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

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

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

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

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

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

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

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

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

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

рис.1

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

рис.2

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

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

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

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

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

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

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

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

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

рис.3

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

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

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

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

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

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

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

Внимание Скидка 50% на курсы! Спешите подать
заявку

Профессиональной переподготовки 30 курсов от 6900 руб.

Курсы для всех от 3000 руб. от 1500 руб.

Повышение квалификации 36 курсов от 1500 руб.

Лицензия №037267 от 17.03.2016 г.
выдана департаментом образования г. Москвы

Конспект урока по Информатике "Структуры данных: деревья, сети, графы, таблицы" 10 класс

Учитель: Коротаева Наталья Егоровна

Образовательное учреждение: МБОУ Новоаганская ОСШ №1

Предмет: информатика и ИКТ

Краткая аннотация урока: на уроке используются презентации MS Power Point для актуализации, проверки знаний и объяснения нового материала, для проверки знаний программа тестирования MyTestXPro , для закрепления знаний работа по карточкам (из книги И.Г. Семакина) в текстовом редакторе MS Word .

Класс, профиль: 10 класс

Раздел: Информационные модели

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

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

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

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

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

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

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

пробудить интерес к самостоятельному решению задач.

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

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

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

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

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

Формируемые умения: самоанализ вопросов теста, слушать, работать по учебнику, по карточкам .

Цели использования ИКТ: проверить теоретические знания с помощью теста, созданного в программе MyTestXPro , объяснить новый материал с использованием презентации MS PowerPoint , закрепить знания с помощью кроссворда, созданного в презентации MS PowerPoint , работа по карточкам в текстовом редакторе MS Word .

Формы организации работы детей: индивидуальная, групповая, практическая.

Формы организации работы учителя: контроль, объяснение , консультирование .

Технологические особенности: личностно-ориентированная, дифференцированная, объяснительно- иллюстративное обучение, технология учебной дискуссии.

Используемое оборудование: компьютерный класс с установленным ПО ( MS Power Point , MS Word , MyTestXPro ), проектор, экран .

Разработанные цифровые образовательные ресурсы: подготовка теста в MyTestXPro , презентации нового материала урока, кроссворда.

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

Наиболее часто используемые структуры:

иерархические структуры (деревья);

Граф - это схема, которая наглядно отражает элементарный состав системы и структуру связей объектов системы.

Район состоит из 5 поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино.

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

Через какие поселки надо проехать, чтобы добраться из Репкино в Мышкино.

Граф состоит из вершин, связанных линиями.

Направленная линия (со стрелкой) называется дугой.

Линия ненаправленная (без стрелки) называется ребром.

Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей.

Содержимое разработки

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

к урокам информатики в 10 классе

упорядоченные данные, используемые в информационной модели.

Наиболее часто используемые структуры:

графы;
иерархические структуры (деревья);
таблицы.

это схема, которая наглядно отражает элементарный состав системы и структуру связей объектов системы.

Схема местности

Описание местности

Район состоит из 5 поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино.

Через какие поселки надо проехать, чтобы добраться из Репкино в Мышкино.

Граф состоит из вершин , связанных линиями.

Направленная линия (со стрелкой) называется дугой .

Линия ненаправленная (без стрелки) называется ребром .

Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей .

Неориентированный – граф, вершины которого соединены ребрами.
Ориентированный – граф, вершины которого соединены дугами.
Взвешенный – граф, у которого вершины или рёбра ( дуги ) несут дополнительную информацию ( вес ).
Сеть – граф, в котором возможно несколько различных путей перемещения по ребрам между некоторыми парами вершин. Характерно наличие замкнутых путей ( циклов ).
Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель.

Корень – главная вершина дерева.

Предок – объект верхнего уровня.

Потомок – объект нижнего уровня.

Листья – вершины, не имеющие потомков.

Участники ½ финала

Участники ¼ финала

Первоначальные игроки

Олимпийская система спортивных соревнований

Иерархическая система хранения файлов

Иерархическая структура доменных адресов в Интернет

домены 1 уровня

Доменные адреса:

домены 2 уровня

Использование графов при решении задач

по материалам ГИА (9класс)

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

Представим решение в виде графа:

1 стул

Представим решение в виде графа:

1 стул

2 стул

Представим решение в виде графа:

1 стул

2 стул

3 стул

Представим решение в виде графа:

1 стул

2 стул

3 стул

Выпишем все решения:

A-B-C, A-C-B, B-A-C, B-C-A, C-A-B, C-B-A.

Сколько трехзначных чисел можно записать с помощью цифр 1, 3, 5 и 7 при условии, что в записи числа не должно быть одинаковых цифр?

1 цифра

2 цифра

3 цифра

Для составления цепочек используются бусины, помеченные буквами: A, B, C, D, E . На первом месте в цепочке стоит одна из бусин A, C, E . На втором – любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На третьем месте – одна из бусин C, D, E , не стоящая в цепочке на первом месте. Сколько цепочек можно создать по этому правилу?

1 бусина

2 бусина

3 бусина

Ответ: 19 цепочек .

Задача 4. Отыскание пути

На рисунке изображена схема местности. Передвигаться из пункта в пункт можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? У какого из путей наименьшая длина? У какого наибольшая длина?