План урока на тему:

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

Информатика11 класс62 раздела
Способы представления структур данных

Информатика · 11 · Открытие нового · 45 мин

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

Цели и задачи

  • Цель по 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 рёбер построить рисунок, список смежности и матрицу смежности; определить, есть ли в нём цикл и является ли он деревом.
Формирует навык преобразования представлений и анализа графа; проверить симметрию матрицы и обоснование вывода о дереве.
Продвинутый (дополнительный)
Разработать собственный пример из жизни, который естественно описывается деревом, и пример, который описывается графом с циклом; изобразить обе модели и письменно объяснить выбор.
Развивает создание информационной модели и аргументацию; при проверке смотреть на соответствие схемы описанной ситуации, наличие подписей и доказательность объяснения.
Контрольные вопросы перед выходом из класса: «Что хранит список? Что обозначают вершины и рёбра? В чём отличие ориентированного графа от неориентированного? Какие два свойства обязательны для дерева? Почему в матрице неориентированного графа значения симметричны относительно главной диагонали?»

Создайте уникальный план урока по своей теме

  • Любая тема, любой уровень
  • Структура по ФГОС
  • 100% уникальный план урока
  • Цели, ход урока, рефлексия
  • Экспорт в PDF и Word
  • Готово за 1 минуту

Другие темы по информатике для 11 класса

Единственность представления чисел в q-ичных системах счисления. Алфавиты позиционных систем счисленияВизуализация данных и интерпретация результатовАнализ правильности скобочного выраженияДискретные игры двух игроков с полной информацией; Графы. Основные понятия. Виды графов; Построение оптимального пути между вершинами графа; Количество различных путей в ориентированном ациклическомСловари (ассоциативные массивы, отображения). Хэш-таблицыДискретные игры двух игроков с полной информациейСервисы машинного перевода и распознавания устной речи; Идентификация и поиск изображений, распознавание лиц; Самообучающиеся системы; Искусственный интеллект в компьютерных играх и обучающихАдресация в сети Интернет. Система доменных имён; Веб-сайт и веб-страница. Взаимодействие браузера с веб-сервером; Сетевое хранение данныхСетевые протоколы. Сеть Интернет; Веб-сайт и веб-страница. Взаимодействие браузера с веб-сервером; Сетевое хранение данных; Принципы построения и аппаратные компоненты компьютерных сетейБазы данныхКомпьютерные сети и ИнтернетРабота в QGIS

Чем удобны планы уроков Нейрум

  • Готовый план, не набросокЦели, ход урока, планируемые результаты, рефлексия — всё по структуре ФГОС, открыли и пошли вести.
  • План урока или техкартаОдин материал — два формата экспорта в PDF. Скачали то, что нужно завучу.
  • Свой план урока за минутуНе нашли нужный? ИИ-конструктор напишет план урока по вашей теме, классу и типу урока.

Вопросы и ответы

Как скачать план урока «Списки, графы, деревья»?

Зарегистрируйтесь бесплатно — материал сохранится в личном кабинете, откуда его можно скачать как план урока или технологическую карту.

Соответствует ли план урока ФГОС?

Да, структура урока — цели, ход урока, планируемые результаты — построена по ФГОС для 11 класса (информатике).

Можно ли изменить план под свой класс?

Да. После регистрации план урока открывается в конструкторе: этапы и содержание можно отредактировать или перегенерировать.