Списки, графы, деревья: способы представления структур данных
Цели и задачи
- Цель по SMART: к концу урока научиться распознавать списки, графы и деревья, выбирать подходящий способ представления данных и строить для заданной ситуации список смежности, матрицу смежности или иерархическую схему.
- Сформировать представление о графе как о множестве вершин и рёбер, о дереве как о связном графе без циклов, а также о списке как об упорядоченной последовательности элементов.
- Научиться анализировать условие задачи и определять, какая структура данных наиболее точно отражает связи между объектами.
- Развивать умение строить информационные модели, сравнивать способы хранения данных и аргументировать выбор модели.
- Воспитывать ответственное отношение к точности данных, интерес к алгоритмам и понимание связи школьной информатики с программированием, сетевыми технологиями и будущей профессиональной деятельностью.
Планируемые результаты
Личностные
- Осознавать практическую значимость структур данных для представления компьютерных сетей, файловых систем, маршрутов и организационных схем.
- Проявлять познавательную мотивацию к исследованию способов хранения и обработки информации.
- Понимать ценность точности, последовательности и проверки модели перед её использованием.
- Осознавать связь изучаемой темы с дальнейшим обучением программированию, анализу данных и информационным технологиям.
Метапредметные
- Уметь выделять объекты и связи между ними в текстовом описании ситуации.
- Уметь сравнивать модели по заданным критериям: наглядность, полнота, компактность и удобство поиска.
- Уметь работать с таблицами, схемами и условными обозначениями.
- Уметь планировать решение, фиксировать промежуточные результаты и проверять модель на соответствие условию.
- Уметь аргументированно представлять результат индивидуальной и парной работы.
Предметные
- Знать понятия «список», «граф», «вершина», «ребро», «степень вершины», «путь», «цикл», «дерево».
- Уметь представлять неориентированный граф рисунком, списком смежности и матрицей смежности.
- Уметь отличать ориентированный граф от неориентированного по направлению рёбер.
- Уметь определять, является ли заданный граф деревом, используя признаки связности и отсутствия циклов.
- Уметь выбирать структуру данных для описания последовательности, сети связей или иерархии.
Универсальные учебные действия (УУД)
Личностные УУД
- Определяют личный познавательный интерес к моделированию данных и связывают тему с возможной профессиональной областью.
- Осознают необходимость точного соблюдения правил построения информационных моделей.
- Оценивают собственную готовность применять изученные структуры при решении новых задач.
- Проявляют самостоятельность при выборе способа представления данных.
Регулятивные УУД
- Формулируют учебную цель на основе проблемной ситуации.
- Планируют последовательность действий при построении модели графа или дерева.
- Сверяют полученную модель с исходным условием и находят несоответствия.
- Осуществляют самооценку по критериям правильности, полноты и обоснованности.
- Корректируют построение после обсуждения с партнёром и проверки по эталону.
Познавательные УУД
- Выделяют существенные объекты и отношения между ними.
- Классифицируют структуры по признакам последовательности, связности и иерархии.
- Строят знаково-символические модели: схемы, списки и матрицы.
- Анализируют граф, находят вершины, рёбра, пути и циклы.
- Преобразуют одну форму представления графа в другую.
Коммуникативные УУД
- Формулируют вопросы к условию и уточняют значения используемых обозначений.
- Обсуждают в паре выбор структуры данных и приводят аргументы.
- Распределяют роли при совместном построении модели.
- Слушают возражения партнёра и корректно уточняют или изменяют решение.
- Представляют результат классу в краткой и доказательной форме.
Подготовка учителя к уроку
- Подготовить презентацию с изображениями списка покупок, схемы социальных связей, карты дорог и иерархии папок.
- Подготовить карточки трёх уровней: распознавание структуры, построение представления графа, анализ дерева; распечатать по одной карточке на каждого ученика.
- Подготовить один комплект крупной карточки на парту с графом из пяти вершин и семи рёбер.
- Подготовить листы в клетку, маркеры трёх цветов и стикеры для групповой фиксации вершин и рёбер.
- Вывести на доску памятку: «граф = вершины + рёбра», «дерево = связный граф без циклов», а также условные обозначения ориентированного и неориентированного ребра.
- Подготовить эталон матрицы смежности для графа из пяти вершин и отдельный эталон списка смежности.
- Проверить работу проектора или интерактивной доски; подготовить таймер на 2, 4 и 6 минут.
- Распечатать лист самооценки по трём критериям: распознаю структуру, строю модель, объясняю выбор.
- Подготовить цветные карточки для приёма «Светофор»: зелёная, жёлтая и красная на каждого ученика.
Ход урока
Этап 1. Организационный момент и мотивация (3 мин)
Цель этапа: включить учащихся в исследовательскую деятельность и показать практическую значимость структур данных.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель приветствует класс и выводит на экран три изображения: список дел, схему дорог между городами и дерево папок на компьютере. «Здравствуйте, ребята. Сегодня мы начнём урок не с определения, а с наблюдения. Посмотрите на экран и найдите общее у этих трёх изображений. Подумайте, какие объекты здесь представлены и как они связаны между собой». | Рассматривают три изображения, индивидуально выделяют объекты и связи, формулируют предположения: «Везде есть элементы», «между объектами можно установить отношения», «в одном случае важен порядок, в другом — связи». |
2 мин | Учитель организует приём «Подумай — обсуди в паре — поделись». «Сначала 30 секунд сформулируйте ответ самостоятельно, затем обсудите его с соседом. Важно не назвать термин, а объяснить, какую информацию нужно хранить в каждом случае. Какие данные достаточно записать последовательно, а где нужно показать связи или подчинение?» После обсуждения фиксирует на доске слова «порядок», «связи», «иерархия». | В течение 30 секунд записывают идею, одну минуту обсуждают её в парах, затем сообщают классу формулировки: «Список хранит порядок», «граф показывает связи между объектами», «дерево показывает уровни и подчинение». |
Завершение этапа: учитель подводит итог: «Мы увидели три разных способа описать данные. Сегодня выясним, чем список отличается от графа, почему дерево является особым графом и как одну и ту же сеть представить рисунком, таблицей или списком».
Этап 2. Актуализация знаний (5 мин)
Цель этапа: актуализировать понятия объекта, отношения, последовательности и информационной модели.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель проводит краткий опрос с приёмом «Верю — не верю». «Поднимите зелёную карточку, если согласны, красную — если не согласны. Первое утверждение: в списке порядок элементов может иметь значение. Второе: граф обязательно изображают только в виде рисунка. Третье: в дереве между двумя вершинами может существовать несколько разных путей». После каждого ответа просит одного ученика объяснить позицию. | Поднимают карточки и поясняют: «Порядок в списке важен», «граф можно представить таблицей или списком», «в дереве между двумя вершинами существует единственный путь, поэтому несколько путей быть не должно». |
3 мин | Учитель записывает на доске небольшой граф: вершины А, Б, В, Г, Д; рёбра А—Б, А—В, Б—Г, В—Г, Г—Д. «Назовите вершины, рёбра и степень вершины А. Есть ли в графе путь А—Б—Г—Д? Есть ли цикл А—Б—Г—В—А? Что изменится, если направление ребра А—Б будет задано от А к Б?» | Называют пять вершин и пять рёбер, определяют степень вершины А как 2, подтверждают наличие пути и цикла, объясняют: «При направленном ребре можно двигаться только из А в Б». |
Завершение этапа: учитель подводит итог: «Мы вспомнили, что модель должна отражать не только объекты, но и отношения между ними. Теперь проверим, как выбрать форму записи так, чтобы не потерять ни один маршрут и ни одну связь».
Этап 3. Постановка проблемы и целеполагание (4 мин)
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Цель этапа: обнаружить затруднение при выборе способа представления одной и той же системы связей.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель предлагает реальный контекст. «Представьте транспортную сеть из пяти пунктов: А, Б, В, Г и Д. Дороги проходят между А и Б, А и В, Б и Г, В и Г, Г и Д. Если я запишу только последовательность А, Б, В, Г, Д, поймём ли мы, какие дороги существуют? А если нарисуем схему, сможем ли быстро проверить наличие каждой связи?» | Анализируют условие и отвечают: «Одна последовательность не показывает все связи», «схема показывает отношения наглядно», «для компьютерной обработки нужна точная запись». |
2 мин | Учитель формулирует проблемный вопрос: «Как представить одну сеть тремя способами: рисунком, списком смежности и матрицей? Как понять, является ли сеть деревом?» Затем предлагает ученикам завершить цель урока: «Сегодня мы научимся…». | Формулируют цель: «Научиться строить разные представления графа», «определять наличие циклов», «отличать дерево от произвольного графа». Записывают цель в тетрадь краткой фразой. |
Завершение этапа: учитель подводит итог: «Затруднение определено: рисунок удобен для человека, а таблица и список удобны для обработки данных. Сейчас мы сами выведем правила перехода от одной модели к другой».
Этап 4. Открытие нового знания (12 мин)
Цель этапа: открыть признаки списка, графа и дерева и освоить три формы представления неориентированного графа.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель показывает на доске три схемы. «Первая запись — последовательность: понедельник, вторник, среда, четверг. Здесь важны порядок и соседство элементов. Вторая схема состоит из точек и соединяющих их линий. Точки назовём вершинами, линии — рёбрами. Ребро показывает отношение между двумя вершинами. Третья схема имеет корневой элемент и ветви. Она отражает иерархию. Запишите: список — упорядоченная последовательность, граф — вершины и рёбра, дерево — связный граф без циклов». | Записывают определения, подписывают на рисунке вершины и рёбра, сравнивают три модели и формулируют различия: «В списке важен порядок», «в графе важны связи», «в дереве есть уровни и нет циклов». |
4 мин | Учитель раздаёт карточки с графом: А—Б, А—В, Б—Г, В—Г, Г—Д. «Построим список смежности. Для каждой вершины перечислите все вершины, соединённые с ней. Не пропустите обратную запись: в неориентированном графе если А соединена с Б, то Б соединена с А». Учитель заполняет первую строку вместе с классом: «Для А получаем Б, В». | В парах заполняют список: А: Б, В; Б: А, Г; В: А, Г; Г: Б, В, Д; Д: Г. Проверяют, что каждая связь указана с обеих сторон. |
5 мин | Учитель выводит пустую таблицу 5 на 5. «Теперь построим матрицу смежности. В строках и столбцах расположим вершины А, Б, В, Г, Д. Если между двумя вершинами есть ребро, ставим 1, если нет — 0. На главной диагонали для простого графа стоят нули: вершина не соединена сама с собой. Обратите внимание: матрица неориентированного графа симметрична относительно главной диагонали». | Заполняют матрицу по списку смежности, объясняют отдельные клетки: «В строке А и столбце Б стоит 1, потому что есть ребро А—Б», «в клетках А—Д и Д—А стоят нули». Формулируют признак симметрии матрицы неориентированного графа. |
Запись в тетрадях
- Список — упорядоченная последовательность элементов.
- Граф — множество вершин и рёбер, задающих связи между вершинами.
- Список смежности для каждой вершины перечисляет все соседние вершины.
- Матрица смежности содержит 1 при наличии ребра и 0 при его отсутствии.
- Дерево — связный граф без циклов; между любыми двумя его вершинами существует единственный путь.
Завершение этапа: учитель подводит итог: «Мы построили одну и ту же сеть рисунком, списком и матрицей. Осталось научиться отличать дерево от графа с циклом и применять это различие к реальным иерархиям».
Этап 5. Первичное закрепление (7 мин)
Цель этапа: закрепить алгоритм распознавания структур и проверить понимание признаков дерева.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель предлагает приём «Сортировка моделей». «На карточках описаны четыре ситуации: список пассажиров в порядке посадки; сеть дружеских связей; структура папок компьютера; карта маршрутов с возможностью вернуться в исходный пункт. Разложите карточки на три группы: список, граф, дерево. Если ситуация допускает несколько моделей, объясните, какая модель будет основной и почему». | В парах распределяют карточки: пассажиры — список; дружеские связи — граф; папки — дерево; карта маршрутов — граф. Формулируют аргументы: «В папках есть подчинение и нет циклического перехода к родительской папке», «в дружбе важны взаимные связи». |
4 мин | Учитель показывает три схемы: первая связна и не содержит циклов; вторая содержит цикл из четырёх вершин; третья состоит из двух несвязанных частей. «Какая схема является деревом? Назовите два обязательных признака дерева. Почему связность сама по себе недостаточна?» | Определяют первую схему как дерево, называют признаки «связность» и «отсутствие циклов», объясняют: «Вторая связна, но содержит цикл, а третья не является деревом, потому что её части не соединены». |
Эталон решения
Алгоритм проверки: 1) убедиться, что из каждой вершины можно попасть в любую другую, то есть граф связен; 2) проверить отсутствие замкнутого маршрута, возвращающегося в исходную вершину; 3) для графа с $n$ вершинами можно дополнительно проверить, что в дереве ровно $n-1$ ребро. Для графа из пяти вершин дерево должно иметь четыре ребра и не содержать циклов.
Завершение этапа: учитель подводит итог: «Теперь мы умеем распознавать структуру и проверять дерево по двум главным признакам. Далее каждый самостоятельно построит модель и покажет, что может контролировать точность записи без подсказки партнёра».
Этап 6. Самостоятельная работа с самопроверкой (8 мин)
Цель этапа: применить новый алгоритм при построении и анализе структур данных.
Время | Действие учителя | Действие учеников |
|---|---|---|
5 мин | Учитель раздаёт карточки трёх уровней. «Выберите уровень, который позволит вам работать продуктивно. Минимальный уровень: определить тип структуры в трёх ситуациях. Базовый уровень: по рёбрам А—Б, А—В, Б—Г, В—Г, Г—Д построить список смежности и матрицу. Повышенный уровень: предложить изменение одного ребра, после которого граф станет деревом, и обосновать ответ. Работайте индивидуально, все обозначения записывайте явно». | Индивидуально выполняют выбранный вариант. На минимальном уровне классифицируют ситуации; на базовом строят список и матрицу; на повышенном анализируют цикл А—Б—Г—В—А и предлагают удалить одно ребро из цикла, например Б—Г или В—Г. |
3 мин | Учитель выводит эталон на доску и организует самопроверку. «Сверьте не только итог, но и каждый шаг. В списке должна быть отражена каждая связь дважды, матрица неориентированного графа должна быть симметричной, а в дереве не должно остаться цикла. Отметьте зелёным правильные элементы, жёлтым — требующие исправления». | Проверяют работу по эталону, исправляют ошибки, подсчитывают результат и отмечают в листе самооценки: «Я распознаю структуру», «Я строю представление графа», «Я могу объяснить, почему граф является или не является деревом». |
Завершение этапа: учитель подводит итог: «Самостоятельная проверка показала, что одна ошибка в исходном списке меняет всю матрицу. Поэтому в информатике важно проверять модель по исходному условию, а не только получать красивую схему».
Этап 7. Рефлексия и домашнее задание (6 мин)
Цель этапа: осознать освоенные способы представления данных, выявить затруднения и определить направление дальнейшей работы.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель проводит рефлексию «Одноминутка». «За одну минуту завершите три фразы: “Сегодня я понял…”, “При построении матрицы мне важно не забыть…”, “Мне нужно ещё потренироваться…”. Затем поднимите карточку: зелёная — могу объяснить тему другому, жёлтая — понимаю основу, но ошибаюсь в деталях, красная — нужна дополнительная помощь». | Записывают три фразы, поднимают карточку самооценки, формулируют конкретное затруднение: «Иногда путаю строку и столбец матрицы», «нужно ещё потренироваться находить циклы». |
3 мин | Учитель задаёт контрольные вопросы перед выходом: «Что является вершинами графа? Чем список смежности отличается от матрицы? Назовите два признака дерева. Почему матрица неориентированного графа симметрична?» После ответов сообщает домашнее задание и благодарит за исследовательскую работу. | Отвечают: «Вершины — объекты, рёбра — связи», «список перечисляет соседей, матрица кодирует наличие связи нулём или единицей», «дерево связно и не имеет циклов», «связь записывается в обе стороны». Записывают домашнее задание выбранного уровня. |
Критерии оценивания практической работы
- «5» — правильно классифицированы структуры, без ошибок построены список смежности и матрица, указаны оба признака дерева, а выбор модели обоснован связным объяснением.
- «4» — выполнена основная часть задания, допущена не более одной содержательной ошибки в списке или матрице, признаки дерева названы верно.
- «3» — распознаны основные структуры и выполнено не менее половины построения, но есть ошибки в фиксации связей или недостаточно обоснован выбор модели.
- Ниже базового уровня — работа требует доработки: не различены граф и дерево либо пропущены существенные связи при построении представления.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Что нового вы узнали о различиях списка, графа и дерева? | Выявление осознания ключевых понятий и способов представления данных. |
Какая проверка помогает понять, является ли граф деревом? | Проверка понимания признаков связности и отсутствия циклов. |
На каком шаге построения матрицы или списка вы испытывали затруднение? | Выявление точек затруднения в алгоритме преобразования модели. |
Где в реальной информационной системе можно применить граф или дерево? | Связь учебного содержания с функциональной грамотностью и будущей профессиональной деятельностью. |
Завершающее слово учителя
«Сегодня мы научились видеть за реальными объектами структуру данных: последовательность, сеть связей или иерархию. Мы построили граф тремя способами и убедились, что точность модели зависит от каждой отдельной связи. Частая ошибка — считать любой связный граф деревом, не проверив наличие циклов. На следующем уроке мы продолжим работу с графами и рассмотрим алгоритмы поиска пути и обхода вершин. Подумайте дома, где в используемых вами приложениях можно встретить графы и деревья».
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Выполнить 4 задания на распознавание списка, графа и дерева; для двух заданных графов перечислить вершины, рёбра и степени вершин. | Закрепляет терминологию и умение выделять основные элементы графа; при проверке обратить внимание на полноту перечисления рёбер и правильность степеней. |
Средний (повышающий) | Для графа из 6 вершин и 7–8 рёбер построить рисунок, список смежности и матрицу смежности; определить, есть ли в нём цикл и является ли он деревом. | Формирует навык преобразования представлений и анализа графа; проверить симметрию матрицы и обоснование вывода о дереве. |
Продвинутый (дополнительный) | Разработать собственный пример из жизни, который естественно описывается деревом, и пример, который описывается графом с циклом; изобразить обе модели и письменно объяснить выбор. | Развивает создание информационной модели и аргументацию; при проверке смотреть на соответствие схемы описанной ситуации, наличие подписей и доказательность объяснения. |
Контрольные вопросы перед выходом из класса: «Что хранит список? Что обозначают вершины и рёбра? В чём отличие ориентированного графа от неориентированного? Какие два свойства обязательны для дерева? Почему в матрице неориентированного графа значения симметричны относительно главной диагонали?»