Алгоритмы и структуры данных
Цели и задачи
- Цель по SMART: к концу урока учащиеся объяснят назначение алгоритма и основных структур данных, определят свойства алгоритмов, распознают линейную и квадратичную сложность, восстановят алгоритм поиска максимума и обоснуют выбор бинарного поиска в задаче с массивом из 1024 элементов.
- Сформировать представление об алгоритме как о конечной последовательности точных действий, предназначенной для решения задачи, и закрепить его основные свойства.
- Научить различать очередь, стек, граф и дерево по способу организации и доступа к данным.
- Научить оценивать простейшую алгоритмическую сложность и применять оценки $O(1)$, $O(n)$ и $O(n^2)$ при анализе проходов по массиву.
- Развивать умение анализировать условие, проверять истинность утверждений, восстанавливать порядок действий и аргументировать выбор алгоритма.
Планируемые результаты
Личностные
- Осознают значение алгоритмического мышления для учебной, профессиональной и повседневной деятельности.
- Проявляют готовность проверять рассуждение, а не принимать ответ без обоснования.
- Развивают ответственное отношение к точности формулировок и результатам совместной работы.
- Проявляют познавательный интерес к способам повышения эффективности программ.
Метапредметные
- Анализируют текст задания, выделяют ключевые условия и сопоставляют их с известными понятиями.
- Строят логическую последовательность действий и проверяют её на корректность.
- Работают с таблицами, схемами, утверждениями и оценками сложности.
- Аргументируют выбор решения, участвуют в обсуждении и осуществляют самопроверку по критериям.
- Используют математическую запись $O(n)$ и $O(n^2)$ для описания поведения алгоритма.
Предметные
- Знать определение алгоритма и его свойства: понятность, определённость, конечность и результативность.
- Уметь соотносить очередь, стек, граф и дерево с характерным способом организации данных.
- Уметь отличать один проход по массиву от двух вложенных проходов и определять их асимптотические оценки.
- Уметь восстанавливать порядок шагов поиска максимума и анализировать один проход пузырьковой сортировки.
- Уметь выбирать бинарный поиск для упорядоченного массива и объяснять его преимущество перед последовательным поиском.
Универсальные учебные действия (УУД)
Личностные УУД
- Определяют личный смысл изучения алгоритмов в связи с программированием, анализом данных и будущей профессией.
- Оценивают собственную уверенность при работе с формальными правилами и сложностью алгоритмов.
- Принимают необходимость точного и проверяемого описания действий.
Регулятивные УУД
- Формулируют цель работы с рабочим листом и планируют последовательность её выполнения.
- Проверяют ответ по условию, находят ошибку в порядке действий или рассуждении.
- Сопоставляют полученный результат с эталоном и корректируют решение.
- Распределяют время между заданиями разного типа.
Познавательные УУД
- Классифицируют структуры данных по способу доступа к элементам.
- Сравнивают алгоритмы по числу операций и моделируют работу поиска или сортировки.
- Устанавливают причинно-следственные связи между вложенностью циклов и сложностью.
- Извлекают существенную информацию из таблицы, набора утверждений и схемы графа.
Коммуникативные УУД
- Формулируют краткое объяснение выбранного ответа и приводят доказательство.
- Работают в паре, распределяя роли аналитика и проверяющего.
- Задают уточняющие вопросы к рассуждению одноклассника.
- Согласуют общий ответ и корректно указывают на логическую ошибку.
Подготовка учителя к уроку
- Распечатать рабочий лист с десятью заданиями по одному экземпляру на каждого ученика и подготовить два резервных экземпляра.
- Подготовить карточки для парной работы с обозначениями «алгоритм», «очередь», «стек», «граф», «дерево», «поиск», «сортировка».
- Вывести на доску или экран памятку: свойства алгоритма, различия $O(1)$, $O(n)$ и $O(n^2)$, принцип бинарного поиска.
- Подготовить схему массива из 1024 элементов, дерево поиска середины и четыре варианта ответа к заданию о пузырьковой сортировке.
- Подготовить карточки «истина» и «ложь» по одной паре на парту для быстрой проверки утверждений.
- Подготовить таймер на 4 минуты для самостоятельной работы и цветные маркеры для выделения ключевых слов.
- Организовать на доске три зоны: «Алгоритм», «Структуры данных», «Эффективность».
- Подготовить эталон рабочего листа для поэтапной самопроверки, не выдавая его до завершения самостоятельной работы.
- Проверить наличие компьютера, проектора или интерактивной доски; при отсутствии техники подготовить плакаты с теми же схемами.
Ход урока
Этап 1. Организационный момент и мотивация (4 мин)
Цель этапа: включить учащихся в исследовательскую работу и показать практическую ценность выбора алгоритма.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель приветствует класс и говорит: "Здравствуйте. Сегодня мы будем не просто вспоминать определения, а проверять, как выбор алгоритма и структуры данных влияет на решение задачи. Откройте рабочие листы и подпишите их. В течение урока вам понадобится не угадывать ответ, а каждый раз находить признак, который его подтверждает." | Готовят тетради и рабочие листы, записывают дату и тему, формулируют готовность к работе. |
3 мин | Учитель показывает на экране два способа поиска числа: последовательный просмотр 1024 ячеек и последовательное деление массива пополам. Спрашивает: "Какой способ вы выберете, если данные уже упорядочены? Что именно делает алгоритм эффективным?" Приём "Подумай — обсуди в паре — поделись": 30 секунд индивидуально, 1 минута в паре, затем ответы класса. | Записывают предварительное мнение, обсуждают его в парах и формулируют ответы: "Нужно делить массив пополам, потому что после каждого шага исключается половина вариантов". |
Завершение этапа: учитель подводит итог: "Сегодня мы проверим, из каких свойств складывается корректный алгоритм, как устроены разные структуры данных и почему один алгоритм может быть существенно быстрее другого. Начнём с понятий, без которых нельзя решить задания рабочего листа."
Этап 2. Актуализация знаний (5 мин)
Цель этапа: актуализировать представления о данных, командах, массивах и последовательности действий.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель показывает четыре карточки: «ввести число», «сравнить с нулём», «вывести результат», «повторять до выполнения условия». Говорит: "Расположите карточки так, чтобы получился осмысленный фрагмент решения. Что произойдёт, если действие сформулировано неоднозначно?" | В парах выстраивают карточки, объясняют последовательность и отвечают: "Исполнитель не поймёт, какое действие выбрать, поэтому результат не гарантирован". |
3 мин | Учитель проводит приём "Верю — не верю" и зачитывает: "Массив хранит набор элементов; алгоритм может состоять из команд; любая случайная последовательность действий является алгоритмом". Просит поднять карточку «истина» или «ложь» и объяснить один выбор. | Поднимают карточки, отмечают: первые два утверждения истинны, последнее ложно, поскольку алгоритм требует точности и гарантированного результата. |
Завершение этапа: учитель подводит итог: "Мы увидели, что последовательность действий сама по себе ещё не является алгоритмом. Теперь выясним, какие обязательные свойства делают описание алгоритмом и где именно возникает затруднение в заданиях рабочего листа."
Этап 3. Постановка проблемы и целеполагание (4 мин)
Цель этапа: обнаружить затруднения при классификации алгоритмов и сформулировать план открытия нового знания.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель предлагает выполнить задания 1 и 3 рабочего листа без подсказки: "Выберите наиболее точное определение алгоритма и отметьте истинные утверждения о его свойствах. Не спешите: подчеркните слова, на которых основывается ваш выбор." После краткой проверки спрашивает: "Какие формулировки оказались похожими, но неверными?" | Индивидуально выполняют задания 1 и 3, подчёркивают слова «конечная», «точных», «понятен», «завершаться». Объясняют, почему бесконечное число команд и неопределённый смысл противоречат свойствам алгоритма. |
2 мин | Учитель фиксирует на доске план: "1) уточнить свойства алгоритма; 2) различить структуры данных; 3) научиться оценивать число действий; 4) применить правила к заданиям 5, 7, 8 и 10. В конце вы должны будете обосновать ответ, а не только выбрать вариант." | Записывают план и формулируют цель: "Научиться распознавать свойства, структуры и эффективность алгоритмов по их описанию". |
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Завершение этапа: учитель подводит итог: "Затруднение возникло не в чтении вариантов, а в отсутствии критериев проверки. Сейчас построим эти критерии и сразу применим их к рабочему листу."
Этап 4. Открытие нового знания (10 мин)
Цель этапа: сформировать систему признаков алгоритма, структур данных и базовых оценок сложности.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель записывает на доске: "Алгоритм — конечная последовательность точных действий, понятных исполнителю и приводящих к результату". Затем говорит: "Проверьте каждое утверждение из задания 3 по четырём вопросам: понятна ли команда, однозначна ли она, конечен ли процесс, получается ли результат?" | Переносят определение в тетрадь, составляют рядом четыре ключевых слова: понятность, определённость, конечность, результативность. |
3 мин | Учитель демонстрирует четыре схемы доступа: очередь людей у кассы, стопка книг, сеть соединений, иерархия папок. Говорит: "Очередь работает по принципу FIFO: первым пришёл — первым обслужен. Стек — LIFO: последним положили, первым сняли. Граф описывает связи, дерево — иерархию без циклов." | Заполняют в тетради мини-таблицу «структура — принцип»: очередь — FIFO, стек — LIFO, граф — связи, дерево — иерархия. Соотносят схемы с названиями. |
4 мин | Учитель показывает три фрагмента: один фиксированный набор операций, один проход по массиву и два вложенных прохода. Объясняет: "Фиксированное число действий не зависит от $n$, это $O(1)$. Один проход делает примерно $n$ действий, это $O(n)$. При вложенных проходах внешняя и внутренняя операции повторяются, поэтому получается порядка $n \cdot n$, то есть $O(n^2)$." Учитель обращает внимание на задание 4 и задачу 10. | Записывают соответствия: $O(1)$ — постоянная сложность, $O(n)$ — линейная, $O(n^2)$ — квадратичная. В задании 4 вписывают $1$ и $n^2$ или соответствующие обозначения в пропуски, объясняют выбор. |
Запись в тетрадях
- Алгоритм — конечная последовательность точных и понятных действий, приводящих к результату.
- Очередь: FIFO; стек: LIFO; граф: вершины и рёбра; дерево: иерархическая структура без циклов.
- Один проход по $n$ элементам — $O(n)$; два вложенных прохода — $O(n^2)$; фиксированное число действий — $O(1)$.
Завершение этапа: учитель подводит итог: "Теперь у нас есть критерии, с которыми можно проверять почти все первые задания листа. Перейдём от определения и классификации к восстановлению конкретного алгоритма и анализу его работы."
Этап 5. Первичное закрепление: поиск и сортировка (8 мин)
Цель этапа: применить критерии к восстановлению алгоритма поиска максимума и анализу одного прохода пузырьковой сортировки.
Время | Действие учителя | Действие учеников |
|---|---|---|
4 мин | Учитель обращается к заданию 5: "Расставьте шаги поиска максимума. Представьте массив 6, 2, 9, 4. Начинаем с первого элемента как с текущего максимума, затем сравниваем каждый следующий с максимумом и заменяем его при необходимости. Какой шаг должен быть последним?" Учитель предлагает одному ученику восстановить порядок у доски. | Расставляют шаги: выбрать первый элемент как максимум; просматривать остальные элементы; сравнивать текущий элемент с максимумом; при большем значении обновлять максимум; вывести максимум. Проверяют порядок на массиве 6, 2, 9, 4 и получают 9. |
4 мин | Учитель разбирает задание 8: "Массив равен [2, 4, 7, 9]. При проходе слева направо сравниваем соседей и меняем местами только тогда, когда левый больше правого. Выполните сравнения: 2 и 4, 4 и 7, 7 и 9. Произойдут ли обмены?" | Поочерёдно проверяют пары, фиксируют отсутствие обменов и выбирают [2, 4, 7, 9]. Объясняют: "Массив уже упорядочен по возрастанию, поэтому ни одна левая величина не больше правой". |
Эталон решения
Для поиска максимума в массиве $[6,2,9,4]$: 1) $max=6$; 2) сравнить $2$ и $6$, максимум не меняется; 3) сравнить $9$ и $6$, получить $max=9$; 4) сравнить $4$ и $9$, максимум не меняется; 5) вывести $9$. Для пузырькового прохода: $2<4$, $4<7$, $7<9$, поэтому обменов нет и результатом остаётся $[2,4,7,9]$.
Завершение этапа: учитель подводит итог: "Мы восстановили алгоритм по его инварианту: после обработки очередного элемента переменная максимум хранит наибольшее значение среди просмотренных. В сортировке мы проверяли не догадку, а каждую соседнюю пару. Теперь вы самостоятельно примените все правила к оставшимся заданиям."
Этап 6. Самостоятельная работа с самопроверкой (10 мин)
Цель этапа: диагностировать индивидуальное понимание структур данных, графов, поиска и сложности алгоритмов.
Время | Действие учителя | Действие учеников |
|---|---|---|
6 мин | Учитель говорит: "Выполните задания 2, 6, 7, 9 и 10. В задании 7 используйте оценки числа сравнений в худшем случае, а в задании 10 обязательно напишите объяснение, а не только название алгоритма. Работайте индивидуально; если сомневаетесь, выпишите признак, который проверяете." Учитель наблюдает, фиксирует типичные затруднения, не сообщает ответы. | Индивидуально решают задания. В задании 2 выбирают очередь; в задании 6 соединяют структуры с принципами; в задании 9 считают степени вершин $A=2$, $C=3$, отмечают связность и число рёбер; в задании 10 выбирают бинарный поиск. |
4 мин | Учитель выводит эталон на экран по частям и говорит: "Сверяйте не только букву или слово, но и обоснование. Для массива из 1024 элементов каждый шаг бинарного поиска оставляет половину: $1024 \to 512 \to 256 \to ... \to 1$. Поэтому требуется не более 10 делений пополам, а с учётом проверки элемента — порядка $\log_2 1024=10$ сравнений, в зависимости от принятой модели подсчёта." | Проверяют ответы цветным маркером, исправляют ошибки одной линией, рядом записывают причину исправления. Формулируют: "Бинарный поиск эффективнее, потому что работает за $O(\log n)$, а последовательный просмотр — за $O(n)$". |
Эталон решения
В задании 9 рёбра $AB$, $AC$, $BC$, $CD$ дают четыре ребра; степени вершин: $A=2$, $B=2$, $C=3$, $D=1$. Граф связен, поскольку из любой вершины можно попасть в любую другую по цепочке рёбер. В задании 10 выбирается бинарный поиск: $1024=2^{10}$, значит после 10 делений массив может быть сведён к одному элементу. Последовательный поиск в худшем случае проверяет 1024 элемента, а бинарный — около 10 сравнений.
Завершение этапа: учитель подводит итог: "Самопроверка показала, что один и тот же навык — выделение ключевого признака — работает и для графа, и для структуры данных, и для оценки поиска. Осталось обобщить материал и проверить, можете ли вы самостоятельно объяснить выбор алгоритма."
Этап 7. Рефлексия и домашнее задание (4 мин)
Цель этапа: обобщить изученные признаки, оценить достижение цели и зафиксировать направление дальнейшей работы.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель проводит приём "Одноминутная формула": "За одну минуту запишите три фразы: алгоритм — это..., очередь отличается от стека тем, что..., бинарный поиск эффективен, потому что..." Затем просит двух учеников прочитать ответы. | Пишут три фразы и зачитывают их: "Алгоритм конечен и точен"; "в очереди первым выходит первый, а в стеке первым выходит последний"; "бинарный поиск каждый раз отбрасывает половину вариантов". |
2 мин | Учитель предлагает поставить знак в листе самооценки: "Отметьте, что вы уже умеете: определить свойства; распознать структуру; найти $O(n)$ или $O(n^2)$; объяснить бинарный поиск. Один вопрос, который остался, запишите внизу листа." | Отмечают освоенные действия, записывают индивидуальный вопрос или затруднение, фиксируют домашнее задание. |
Критерии оценивания практической работы
- «5» — верно выполнены не менее 9 из 10 заданий, в заданиях 7, 9 и 10 приведено содержательное обоснование, а порядок поиска максимума восстановлен без ошибок.
- «4» — верно выполнены 7–8 заданий, допускается одна неточность в подсчёте сравнений или формулировке объяснения, но основные понятия и алгоритмы различены.
- «3» — верно выполнены 5–6 заданий, распознаны определение алгоритма, очередь, базовые свойства и общий принцип бинарного поиска, однако есть ошибки в сложности, графах или порядке действий.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Как по формулировке понять, что перед нами корректный алгоритм? | Выявление понимания свойств понятности, определённости, конечности и результативности. |
Чем очередь отличается от стека и как это проверить на примере? | Проверка осознания принципов FIFO и LIFO. |
Почему два вложенных прохода дают $O(n^2)$? | Выявление понимания связи между структурой циклов и количеством операций. |
Почему для массива из 1024 элементов выбран бинарный поиск? | Проверка умения аргументировать выбор алгоритма через сравнение $O(\log n)$ и $O(n)$. |
Завершающее слово учителя
"Сегодня мы увидели, что алгоритмы отличаются не только записью команд, но и точностью, способом работы с данными и эффективностью. Типичная ошибка — выбрать ответ по знакомому слову, не проверив условие и порядок действий. На следующем уроке мы продолжим анализировать алгоритмы и рассмотрим, как их свойства проявляются в программной реализации. Сохраните рабочий лист: он станет опорой для дальнейшего изучения поиска, сортировки и структур данных."
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Составить таблицу из четырёх строк: алгоритм, очередь, стек, граф или дерево; для каждого указать определение, основной признак и небольшой пример. Дополнительно решить 4 коротких задания на определение $O(1)$, $O(n)$ и $O(n^2)$. | Закрепляет терминологию и умение классифицировать структуры; при проверке обратить внимание на точность определений и различие одного и двух вложенных проходов. |
Средний (повышающий) | Решить 4 задачи в том же ключе, что рабочий лист: восстановить поиск минимума или максимума, определить результат одного прохода пузырьковой сортировки, подсчитать степени вершин заданного графа и выбрать способ поиска в упорядоченном массиве. | Переносит алгоритмы на новые данные; при проверке смотреть на последовательность шагов, подсчёт рёбер и обязательное объяснение выбора поиска. |
Продвинутый (дополнительный) | Разработать и описать собственный пример, в котором последовательный поиск сравнивается с бинарным на массиве из $2^k$ элементов. Указать число шагов в худшем случае для двух методов и объяснить, какие условия необходимы для бинарного поиска. | Развивает исследовательское мышление и умение самостоятельно формулировать аргумент о сложности; при проверке обратить внимание на упорядоченность массива и корректность оценки $O(\log n)$. |
Контрольные вопросы перед выходом: «Какое свойство алгоритма нарушено, если команда допускает два разных толкования? Почему очередь и стек дают разный порядок извлечения элементов? Какую сложность имеет один проход по массиву? Почему бинарный поиск нельзя напрямую применить к неупорядоченным данным?»
