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

Анализ алгоритмов

Информатика11 класс68 разделов
Анализ алгоритмов

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

Анализ алгоритмов: оценка эффективности и поиск узких мест

Цели и задачи

  • Цель по SMART: к концу урока научиться анализировать простые алгоритмы, определять их временную сложность по числу выполнений основных операций и обосновывать, какой из двух алгоритмов эффективнее.
  • Сформировать представление о сложности алгоритма как характеристике зависимости количества операций от размера входных данных.
  • Научиться выделять основную операцию алгоритма, подсчитывать число её выполнений для последовательных, условных и циклических конструкций.
  • Развивать умение сравнивать алгоритмы, объяснять результаты анализа и находить узкие места в программном решении.
  • Воспитывать ответственное отношение к качеству программного продукта, самостоятельность при исследовании и готовность аргументированно защищать собственное решение.

Планируемые результаты

Личностные

  • Осознавать связь эффективности алгоритмов с качеством цифровых продуктов и будущей профессиональной деятельностью.
  • Проявлять познавательную мотивацию при исследовании способов ускорения алгоритмов.
  • Понимать ценность точного, проверяемого и аргументированного объяснения результата.
  • Проявлять самостоятельность при выборе способа анализа и оценке собственной работы.

Метапредметные

  • Выделять существенную информацию в тексте алгоритма и представлять её в виде таблицы или математической зависимости.
  • Планировать исследование, фиксировать промежуточные результаты и проверять гипотезы на небольших входных данных.
  • Сравнивать несколько способов решения одной задачи по заданному критерию.
  • Аргументированно формулировать выводы в устной и письменной форме, сотрудничать при решении исследовательской задачи.

Предметные

  • Знать понятия «основная операция», «размер входных данных», «временная сложность» и обозначение порядка роста $O(...)$.
  • Уметь определять порядок роста для последовательных действий и простых циклов.
  • Уметь различать линейную, квадратичную и логарифмическую зависимости на качественном уровне.
  • Уметь сравнивать два алгоритма при малых и больших значениях размера входных данных.
  • Владеть способом пошагового анализа алгоритма и объяснения полученного результата.

Универсальные учебные действия (УУД)

Личностные УУД

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

Регулятивные УУД

  • Формулируют цель исследования алгоритма и планируют последовательность анализа.
  • Выбирают основную операцию и устанавливают критерий сравнения решений.
  • Осуществляют самоконтроль по чек-листу: определён вход, выбрана операция, подсчитаны повторы, сформулирован вывод.
  • Обнаруживают ошибку в подсчёте и корректируют решение после проверки на примере.
  • Оценивают результат по критериям точности, полноты и аргументированности.

Познавательные УУД

  • Выделяют основную операцию и размер входных данных в описании алгоритма.
  • Строят зависимость числа операций от размера входа и распознают характер её роста.
  • Сравнивают последовательный и вложенный циклы по числу повторений.
  • Используют таблицу значений и простой график как модели поведения алгоритма.
  • Формулируют обобщение о влиянии структуры цикла на сложность.

Коммуникативные УУД

  • Распределяют роли в группе: аналитик, проверяющий, оформитель и докладчик.
  • Задают уточняющие вопросы о выбранной основной операции и способе подсчёта.
  • Аргументируют вывод ссылкой на число повторений, а не только на интуитивную оценку.
  • Сопоставляют разные решения и корректно предлагают исправления.
  • Кратко представляют результат исследования классу.

Подготовка учителя к уроку

  • Подготовить презентацию с проблемным вопросом, двумя фрагментами псевдокода, таблицей значений $n$, $n^2$, $\log_2 n$ и схемой алгоритма анализа.
  • Распечатать карточки трёх уровней по одной на каждого ученика: базовые последовательные и линейные циклы, повышенные вложенные циклы, исследовательские задания на сравнение алгоритмов.
  • Распечатать групповую карточку с алгоритмом анализа: определить вход, выбрать основную операцию, посчитать повторы, записать зависимость, обозначить порядок роста, сделать вывод.
  • Подготовить лист самооценки на каждого ученика и мини-лист «Билет на выход» на каждого ученика.
  • Вывести на доску памятку: «последовательные блоки складываются; повторение в цикле умножается; вложенные циклы перемножаются».
  • Подготовить маркеры, стикеры двух цветов и четыре листа формата А3 для групповой работы.
  • Подготовить ноутбук и проектор; при наличии компьютеров открыть среду для выполнения коротких фрагментов псевдокода или Python.
  • Разделить класс на смешанные группы по 4 человека и заранее определить рабочие места групп.
  • Подготовить таймер на 2, 5 и 7 минут для исследовательских этапов.

Ход урока

Этап 1. Организационный момент и мотивационный крючок (3 мин)

Цель этапа: включить учащихся в исследовательскую деятельность и показать практическую значимость анализа алгоритмов.
Время
Действие учителя
Действие учеников
1 мин
Учитель приветствует класс и показывает на экране два сообщения: «Алгоритм А обрабатывает 1 000 записей за секунду» и «Алгоритм Б обрабатывает 1 000 000 записей за секунду». «Представьте, что оба алгоритма дают правильный ответ. Почему разница в скорости может стать критичной для поисковой системы, банка или сервиса рекомендаций? Сегодня мы будем не просто запускать алгоритмы, а исследовать их поведение при росте объёма данных».
Фиксируют в тетради тему, приводят примеры: «пользователь ждёт ответа», «растёт число записей», «сервер тратит больше ресурсов». Формулируют предположение: «важно знать, как меняется число операций».
2 мин
Учитель объявляет приём «Проблемный вопрос»: «Как по виду алгоритма заранее понять, будет ли он работать приемлемо на больших данных, даже если мы ещё не запускали программу на реальном сервере? Запишите индивидуальную гипотезу, затем обсудите её с соседом».
За 30 секунд записывают гипотезу, одну минуту обсуждают её в парах и предлагают варианты: «посчитать операции», «посмотреть на циклы», «сравнить время работы».
Завершение этапа: учитель подводит итог: "Мы увидели, что правильность алгоритма ещё не гарантирует его практическую пригодность. Сейчас вспомним, какие конструкции программы влияют на число выполняемых действий, и подготовим инструменты для анализа."

Этап 2. Актуализация знаний и фиксация затруднения (6 мин)

Цель этапа: актуализировать знания о переменных, циклах и структуре алгоритма, выявить затруднение в оценке количества операций.
Время
Действие учителя
Действие учеников
2 мин
Учитель демонстрирует псевдокод: «Для $i$ от 1 до $n$ выполнить: вывести $i$». «Сколько раз сработает команда вывода при $n=5$, $n=100$ и $n=1000$? Что здесь можно считать основной операцией?»
Записывают значения в таблицу: 5, 100 и 1000. Отвечают: «основная операция — вывод или действие внутри цикла».
2 мин
Учитель показывает второй фрагмент: «Для $i$ от 1 до $n$ выполнить: для $j$ от 1 до $n$ выполнить: сравнить $i$ и $j$». «Попробуйте без полного выполнения программы определить число сравнений при $n=3$ и $n=10».
Сначала считают для $n=3$: 9 сравнений, затем для $n=10$: 100. Обсуждают, что вложенный цикл даёт $n\cdot n$ повторений.
2 мин
Учитель организует «Светофор»: «Зелёная карточка — можете объяснить, почему получились такие числа; жёлтая — понимаете пример, но затрудняетесь обобщить; красная — пока не видите способ анализа». После сигналов уточняет: «Что именно вызывает трудность: выбор операции, подсчёт повторений или запись общего результата?»
Поднимают карточки, называют затруднение. Формулируют: «нужно научиться переходить от конкретных значений к зависимости от $n$».
Завершение этапа: учитель подводит итог: "Мы умеем считать отдельные примеры, но нам нужен общий способ описать поведение алгоритма при любом размере входа. Сформулируем цель и порядок исследования."

Этап 3. Постановка проблемы и целеполагание (4 мин)

Цель этапа: сформулировать учебную задачу и критерии успешного анализа алгоритма.
Время
Действие учителя
Действие учеников
2 мин
Учитель проводит «Сократовский диалог»: «Если вход содержит $n$ элементов, что должно измениться при переходе от $n=10$ к $n=1000$? Достаточно ли сообщить одно время запуска? Почему два алгоритма могут различаться при больших $n$, хотя на маленьких данных работают почти одинаково?»
Отвечают: «увеличится число операций», «одного измерения недостаточно», «важен характер роста». Формулируют понятие размера входных данных как числа элементов или другого параметра, определяющего объём работы.
2 мин
Учитель фиксирует на доске план: «1. Найти размер входа. 2. Выбрать основную операцию. 3. Посчитать число её выполнений. 4. Описать зависимость от $n$. 5. Сравнить алгоритмы и сделать вывод». «Какой результат покажет, что цель достигнута?»
Записывают план, предлагают критерии: «выделена операция», «получена формула или порядок роста», «вывод подтверждён расчётом».

Посмотрите план целиком

Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.

Запись в тетрадях

Тема урока. Анализ алгоритма — определение количества основных операций и характера его роста при увеличении размера входных данных. План анализа: размер входа → основная операция → число повторений → зависимость → порядок роста → вывод.
Завершение этапа: учитель подводит итог: "У нас появился общий алгоритм самого анализа. Теперь проверим его на простых конструкциях и увидим, как структура программы превращается в математическую зависимость."

Этап 4. Открытие нового знания: порядок роста (10 мин)

Цель этапа: вывести правила анализа последовательных действий, одиночного и вложенного циклов и ввести обозначение $O(...)$.
Время
Действие учителя
Действие учеников
3 мин
Учитель показывает на экране псевдокод: «прочитать $n$ чисел; для каждого числа выполнить одно сравнение; вывести результат». «Выберем сравнением основную операцию. Сколько раз она выполнится? Как изменится число сравнений при удвоении $n$?»
Определяют $n$ сравнений, записывают зависимость $T(n)=n$. Формулируют: «при удвоении входа число операций примерно удваивается».
3 мин
Учитель записывает рядом два последовательных фрагмента: «один цикл на $n$ повторений» и «два последовательных цикла на $n$ повторений». «Получаем $n+n=2n$. Для оценки порядка роста постоянный множитель не меняет тип зависимости, поэтому оба случая относят к $O(n)$.»
Сверяют рассуждение, записывают: $n+n=2n$, порядок роста $O(n)$. Объясняют, что последовательные участки анализируются сложением.
2 мин
Учитель возвращается к вложенному циклу: «Для $i$ от 1 до $n$, для $j$ от 1 до $n$ выполнить сравнение». «Внешний цикл запускает внутренний $n$ раз, а внутренний каждый раз выполняется $n$ раз. Значит, всего $n\cdot n=n^2$, порядок роста $O(n^2)$.»
Строят короткую схему из $n$ строк по $n$ действий, записывают $T(n)=n^2$ и $O(n^2)$. Отвечают: «при удвоении $n$ число операций возрастает примерно в четыре раза».
2 мин
Учитель показывает фрагмент: «пока $n>1$: заменить $n$ на $n/2$». «После каждого шага размер уменьшается в два раза. Сколько шагов потребуется, чтобы дойти до единицы? Это логарифмическая зависимость: $O(\log n)$. На уроке нам важно распознавать её по последовательному делению размера задачи.»
Записывают признак логарифмического роста: размер задачи на каждом шаге уменьшается в постоянное число раз. Сравнивают три типа: $O(\log n)$, $O(n)$, $O(n^2)$.

Запись в тетрадях

  • Последовательные участки: число операций складывается; при оценке порядка роста выбирают наиболее быстро растущий член.
  • Один цикл с $n$ повторениями обычно даёт $O(n)$.
  • Два вложенных цикла по $n$ повторений обычно дают $O(n^2)$.
  • Последовательное уменьшение размера задачи в несколько раз обычно даёт $O(\log n)$.
  • Чем медленнее растёт функция сложности, тем лучше алгоритм масштабируется при больших входных данных.
Завершение этапа: учитель подводит итог: "Мы получили не набор отдельных формул, а язык для сравнения алгоритмов. Теперь применим его в группах: каждой группе предстоит доказать свой вывод подсчётом операций и объяснить его классу."

Этап 5. Исследовательская работа в группах (9 мин)

Цель этапа: применить алгоритм анализа к фрагментам разной структуры и сформулировать аргументированный вывод.
Время
Действие учителя
Действие учеников
1 мин
Учитель распределяет роли и раздаёт карточки: «В каждой группе есть аналитик, проверяющий, оформитель и докладчик. На листе А3 запишите размер входа, основную операцию, число повторений, порядок роста и вывод. Не ограничивайтесь ответом $O(n)$ или $O(n^2)$ — объясните, откуда он получен».
Распределяют роли, читают условие карточки и фиксируют порядок действий.
5 мин
Учитель предлагает задания. Группа 1 анализирует один цикл по $n$ элементов. Группа 2 анализирует два последовательных цикла по $n$ элементов. Группа 3 анализирует два вложенных цикла: внешний — от 1 до $n$, внутренний — от 1 до $n$. Группа 4 анализирует цикл, в котором на каждом шаге $n$ заменяется на $n/2$. Учитель перемещается между группами и задаёт вопросы: «Что именно вы считаете основной операцией? Сколько раз выполняется внутренний цикл при каждом значении внешнего? Как проверить ваш вывод на $n=4$?»
В группах считают операции, заполняют лист А3, проверяют результат на $n=4$ или $n=8$, отмечают возможную ошибку стикером и исправляют её. Получают соответственно $O(n)$, $O(n)$, $O(n^2)$ и $O(\log n)$.
3 мин
Учитель проводит краткую защиту: «Докладчику каждой группы — одна минута. Назовите алгоритм, основную операцию, подсчёт и практический вывод. Остальные группы задают по одному уточняющему вопросу».
Докладчики представляют решения. Одноклассники задают вопросы: «Почему два последовательных цикла не дают $O(n^2)$?», «Почему вложенность приводит к умножению?», «Как проверили логарифмический случай?»
Завершение этапа: учитель подводит итог: "Группы показали, что одинаковый внешний размер входа может приводить к разному росту затрат. Теперь каждый индивидуально проверит, умеет ли он применять этот способ без поддержки группы."

Этап 6. Первичное закрепление и самостоятельная работа с самопроверкой (8 мин)

Цель этапа: закрепить умение определять порядок роста и выявлять ошибочные рассуждения.
Время
Действие учителя
Действие учеников
5 мин
Учитель раздаёт индивидуальные карточки трёх уровней. «Базовый уровень: определите порядок роста для одного цикла по $n$ элементам и последовательности из трёх таких циклов. Повышенный уровень: определите порядок роста вложенных циклов, где внутренний цикл выполняется от 1 до $i$. Продвинутый уровень: сравните алгоритмы $A$ с $T_A(n)=3n+5$ и $B$ с $T_B(n)=n^2$. Обоснуйте, какой выгоднее при больших $n$. Запишите не только ответ, но и два шага рассуждения».
Индивидуально решают выбранный уровень. Для вложенного случая получают сумму $1+2+...+n=\frac{n(n+1)}{2}$ и делают вывод $O(n^2)$. Для сравнения объясняют, что при больших $n$ линейный алгоритм растёт медленнее квадратичного.
3 мин
Учитель выводит эталон на экран и проводит «Самопроверку по чек-листу»: «Поставьте плюс, если указали размер входа, выделили основную операцию, обосновали число повторений, записали порядок роста и сформулировали вывод. Если есть ошибка, подчеркните место, а рядом запишите исправление».
Сверяют решение с эталоном, отмечают пункты чек-листа, исправляют одну обнаруженную ошибку. Показывают светофор: зелёный — могу объяснить, жёлтый — нужна ещё тренировка, красный — нужна помощь.

Эталон решения

Для вложенных циклов, где внешний индекс $i$ принимает значения от 1 до $n$, а внутренний выполняется $i$ раз, общее число операций равно $T(n)=1+2+...+n=\frac{n(n+1)}{2}$. Раскрываем выражение: $T(n)=\frac{n^2+n}{2}$. При больших $n$ главным является член $n^2$, поэтому порядок роста — $O(n^2)$. Для сравнения $T_A(n)=3n+5$ имеет линейный рост $O(n)$, а $T_B(n)=n^2$ — квадратичный рост $O(n^2)$; при достаточно больших $n$ алгоритм A эффективнее, несмотря на постоянный множитель 3.
Завершение этапа: учитель подводит итог: "Самостоятельная проверка показала, что важен не только итоговый символ $O(...)$, но и путь к нему. На заключительном этапе применим этот способ к ситуации, близкой к реальной разработке, и оценим собственное понимание."

Этап 7. Включение в систему знаний и рефлексия (5 мин)

Цель этапа: связать анализ сложности с выбором алгоритма в практической ситуации и осмыслить результат урока.
Время
Действие учителя
Действие учеников
3 мин
Учитель предлагает кейс: «Сервис должен обработать список из 10 000 записей. Алгоритм A выполняет примерно $5n$ операций, алгоритм B — $n^2$ операций. Какой вариант вы предложите команде разработчиков? Можно ли выбрать B только потому, что его код короче? Обоснуйте ответ по формуле и характеру роста».
В парах вычисляют порядок величин: для A около 50 000 операций, для B около 100 000 000. Формулируют: «выбираем A, потому что линейный рост существенно лучше квадратичного на больших данных». Объясняют, что краткость кода не равна эффективности.
2 мин
Учитель организует «Одноминутку»: «Закончите три фразы: сегодня я научился; теперь я могу; мне ещё нужно потренироваться в…». Затем просит двух учеников озвучить разные варианты.
Заполняют три фразы, называют собственный результат и трудность: «выбор основной операции», «анализ вложенных циклов», «сравнение роста функций».
Завершение этапа: учитель подводит итог: "Сегодня вы научились смотреть на алгоритм как на объект исследования: выделять операцию, считать повторы и предсказывать поведение на больших данных. Осталось зафиксировать результат и выбрать уровень домашней практики."

Этап 8. Итог урока и домашнее задание (0 мин)

Цель этапа: оформить итог урока и дать дифференцированное задание для закрепления.
Время
Действие учителя
Действие учеников
0 мин
Учитель заранее объявляет домашнее задание после рефлексии: «Выберите обязательный уровень или добавьте повышенный и продвинутый. Перед сдачей проверьте каждое решение по пяти шагам анализа».
Записывают выбранный уровень и критерии проверки в дневник.

Критерии оценивания практической работы

  • «5» — верно выполнены все пункты выбранной карточки, указаны размер входа и основная операция, корректно подсчитано число повторений, порядок роста обоснован, вывод сформулирован точно.
  • «4» — решение в основном верное, но допущена одна неточность в записи формулы, обозначении порядка роста или объяснении; ход рассуждения понятен.
  • «3» — определены размер входа и хотя бы одна существенная часть подсчёта, но есть ошибки в анализе вложенности или отсутствует развёрнутое обоснование.
  • Ниже базового уровня — не выделена основная операция или вывод не связан с числом повторений; работа требует повторного анализа по памятке.

Рефлексия

Вопрос для ученика
Цель вопроса
Какой шаг анализа алгоритма теперь выполняется у вас уверенно?
Выявление освоенного действия и осознание личного результата.
Почему два последовательных цикла по $n$ элементов обычно относят к $O(n)$, а два вложенных — к $O(n^2)$?
Проверка понимания различия между сложением и умножением числа повторений.
Какую ошибку вы обнаружили при самопроверке и как её исправили?
Диагностика регулятивных действий: контроль и коррекция.
Какой вопрос по анализу алгоритмов вы хотели бы исследовать дальше?
Поддержка познавательной инициативы и связь с дальнейшим изучением алгоритмов.

Завершающее слово учителя

"Сегодня мы увидели, что анализ алгоритма позволяет заранее оценить его поведение на больших объёмах данных. Главная ошибка — называть сложность только по внешнему виду кода, не выделив основную операцию и не посчитав повторения. Используйте пятишаговый алгоритм анализа при решении задач и чтении программ. На следующем уроке мы продолжим сравнивать алгоритмы и рассмотрим, как выбирать эффективный способ решения конкретной задачи."

Домашнее задание

Уровень
Что задать
Зачем
Базовый (обязательный)
Проанализировать 4 простых фрагмента псевдокода: один последовательный блок, один цикл по $n$ элементам, два последовательных цикла и два вложенных цикла. Для каждого указать размер входа, основную операцию, число повторений и порядок роста.
Закрепляет базовый алгоритм анализа; при проверке смотреть на различие между сложением и умножением повторений.
Средний (повышающий)
Решить 3 задания на сравнение алгоритмов: определить порядок роста для цикла с внутренним числом повторений $i$, цикла с делением размера входа пополам и пары функций $4n+7$ и $n^2$. Для каждого написать краткое обоснование.
Развивает умение переходить от псевдокода к формуле и сравнивать алгоритмы при больших значениях входа.
Продвинутый (дополнительный)
Исследовать два способа поиска элемента в упорядоченном списке: последовательный просмотр и деление диапазона пополам. Составить таблицу числа шагов для нескольких значений $n$, определить порядок роста и написать вывод о применимости методов.
Формирует исследовательское мышление и связывает линейную и логарифмическую сложность с практической задачей поиска.
Контрольные вопросы перед выходом из класса: «Что называют размером входных данных? Как выбрать основную операцию? Почему вложенные циклы часто дают произведение числа повторений? Какой порядок роста медленнее: $O(n)$ или $O(n^2)$? Назовите два шага, которые вы выполните перед тем, как сравнивать алгоритмы».

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

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

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

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

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

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

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

Как скачать план урока «Анализ алгоритмов»?

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

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

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

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

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