Нормальные алгоритмы Маркова: построение, выполнение и анализ
Цели и задачи
- Цель по SMART: к концу урока научиться выполнять не менее двух шагов нормального алгоритма Маркова для заданного слова, составлять простой алгоритм из 3–5 правил и объяснять результат его работы.
- Сформировать представление о нормальном алгоритме Маркова как формальной системе преобразования слов с упорядоченными правилами подстановки.
- Научиться различать заключительные и незаключительные правила, выбирать первое применимое правило и фиксировать последовательность преобразований.
- Развивать алгоритмическое, логическое и критическое мышление через решение практических задач и поиск ошибок в готовом алгоритме.
- Воспитывать аккуратность записи, готовность проверять результат и интерес к теоретическим основам информатики, связанным с программированием.
Планируемые результаты
Личностные
- Осознавать значение формальных алгоритмов для будущей профессиональной деятельности в области программирования и обработки информации.
- Проявлять интерес к исследованию поведения алгоритма и готовность самостоятельно проверять полученный результат.
- Понимать ценность точности, последовательности и ответственности при выполнении формальных преобразований.
- Оценивать собственные затруднения и выбирать способ их преодоления при работе с алгоритмами.
Метапредметные
- Извлекать из условия задачи порядок правил, ограничения их применения и критерий остановки алгоритма.
- Планировать последовательность действий, вести таблицу промежуточных результатов и осуществлять самопроверку.
- Сравнивать разные алгоритмы преобразования слов, находить закономерности и выявлять ошибочные шаги.
- Аргументированно объяснять решение в паре и корректно обсуждать расхождения в результатах.
Предметные
- Знать понятия «слово», «подстановка», «заключительное правило», «нормальный алгоритм Маркова».
- Уметь применять правила к самому левому вхождению образца, соблюдая порядок правил.
- Уметь составлять трассировку выполнения алгоритма в виде цепочки промежуточных слов.
- Уметь определять результат работы алгоритма и устанавливать причину зацикливания или остановки.
Универсальные учебные действия (УУД)
Личностные УУД
- Определять личный смысл изучения формальных моделей алгоритмов для дальнейшего обучения информатике.
- Проявлять познавательную инициативу при проверке гипотез о результате работы алгоритма.
- Формировать ответственное отношение к точности записи каждого шага.
- Осуществлять самооценку готовности применять правила без подсказки.
Регулятивные УУД
- Формулировать цель практической работы и планировать порядок выполнения правил.
- Фиксировать промежуточный результат после каждого шага алгоритма.
- Сопоставлять полученный результат с условием и находить место ошибки.
- Корректировать решение после взаимопроверки по предложенному эталону.
Познавательные УУД
- Выделять в записи правила образец, замену и признак завершения.
- Применять логическое правило выбора: проверять правила сверху вниз и использовать первое применимое.
- Моделировать работу алгоритма таблицей или цепочкой преобразований.
- Анализировать, почему изменение порядка правил может изменить результат или привести к зацикливанию.
Коммуникативные УУД
- Распределять роли в паре: исполнитель выполняет шаги, контролёр проверяет выбор правила.
- Формулировать уточняющие вопросы о месте применения правила и критерии остановки.
- Доказывать правильность результата, ссылаясь на конкретные шаги трассировки.
- Принимать замечания партнёра и согласовывать исправленный вариант решения.
Подготовка учителя к уроку
- Подготовить фрагмент учебника по теме «Нормальные алгоритмы Маркова» для работы с определением и обозначениями.
- Распечатать карточки с тремя практическими заданиями: базовым, повышенным и исследовательским — по одной карточке на пару.
- Подготовить отдельный лист с алгоритмом для проблемного диалога: 1) $a\to b$; 2) $b\to c$; 3) $c\to.$
- Вывести на доску или экран памятку: «Идём по правилам сверху вниз; заменяем первое подходящее вхождение; точка означает остановку».
- Подготовить таблицу трассировки с графами «Шаг», «Применённое правило», «Полученное слово».
- Распечатать лист самооценки и билет на выход — по одному экземпляру на каждого ученика.
- Подготовить маркеры, стикеры двух цветов и таймер для практической работы.
- Организовать рабочие места для пар; предусмотреть возможность записи решения на интерактивной доске.
- Подобрать из учебника короткий теоретический фрагмент и упражнения, соответствующие правилам подстановки без указания номеров страниц.
Ход урока
Этап 1. Организационный момент и мотивация (3 мин)
Цель этапа: включить учащихся в учебную деятельность и создать проблемную ситуацию, показывающую необходимость точного порядка действий.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель приветствует класс и говорит: "Здравствуйте, ребята. Сегодня мы будем работать не с готовой программой, а с очень строгой системой правил. Откройте тетради, запишите дату и тему урока: «Нормальные алгоритмы Маркова». Наша задача — не просто узнать определение, а научиться выполнять такой алгоритм без пропуска ни одного шага." | Открывают тетради, записывают дату и тему урока, готовят учебник и ручку. |
2 мин | Учитель показывает на экране правила: «1. а → б; 2. б → в; 3. в →.» и слово «а». Затем задаёт проблемный вопрос: "Какое слово получится? Можно ли сразу заменить «а» на «в», потому что такая буква появляется после двух действий? Или необходимо строго выполнить правила по порядку? Обсудите ответ с соседом 30 секунд и объясните его." | Обсуждают ответ в парах, предполагают: «Сначала получится б, затем в, а после правила с точкой алгоритм остановится». Объясняют, что пропуск шага нарушит алгоритм. |
Завершение этапа: учитель подводит итог: "Мы увидели, что результат зависит не только от набора правил, но и от порядка их применения. Теперь восстановим необходимые понятия и сформулируем точный алгоритм действий."
Этап 2. Актуализация знаний и выявление затруднения (5 мин)
Цель этапа: актуализировать знания об алгоритме, строках и подстановках, зафиксировать затруднение при выборе правила.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель обращается к классу: "Вспомним признаки алгоритма. Что означает, что алгоритм дискретен? Почему исполнитель должен однозначно понимать каждую команду? Приведите пример преобразования строки, знакомого вам по программированию или работе с текстом." Учитель фиксирует на доске слова «точность», «конечность», «последовательность». | Отвечают: «Алгоритм состоит из отдельных шагов», «каждая команда должна быть понятна исполнителю», «строку можно заменить, удалить или дополнить». Записывают ключевые слова. |
3 мин | Учитель раздаёт парам мини-карточку со строкой «абаба» и двумя действиями: заменить первое «аба» на «в»; если образца нет, прекратить работу. Учитель спрашивает: "Как определить, какое вхождение менять? Что произойдёт, если одна пара заменит первое вхождение, а другая — последнее?" | Выполняют замену, получают «вба», сравнивают варианты и формулируют: «Нужно заранее задать однозначное правило выбора вхождения, иначе результаты могут различаться». |
Завершение этапа: учитель подводит итог: "Мы умеем выполнять отдельную замену, но нам нужно формальное описание всей системы: как расположены правила, какое из них выбирать и когда завершать работу. Именно это сейчас и откроем."
Этап 3. Проблемный диалог и целеполагание (4 мин)
Цель этапа: совместно вывести основные правила выполнения нормального алгоритма Маркова и сформулировать цель практической работы.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель записывает на доске две подстановки: $ab\to X$ и $b\to Y$, исходное слово «abb». Говорит: "Какое правило применяем первым? Если первое правило подходит, можем ли мы сразу перейти ко второму? Найдите первое слева подходящее вхождение и объясните свой выбор." | Находят «ab» в начале слова, получают «Xb», формулируют: «Правила проверяются сверху вниз, поэтому второе правило не используется на этом шаге». |
2 мин | Учитель показывает запись «$c\to d.$» и спрашивает: "Что меняет точка после стрелки? Почему такое правило называют заключительным? Сформулируйте сегодняшую цель одним предложением: чему мы должны научиться после разбора определения?" | Отвечают: «Точка означает остановку после выполнения замены». Формулируют цель: «Научиться выполнять и составлять алгоритмы Маркова, отслеживая каждый шаг и результат». |
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Завершение этапа: учитель подводит итог: "Цель определена: мы должны превратить словесное описание правил в точную трассировку преобразований. Сначала кратко уточним теорию по учебнику, а затем почти всё оставшееся время посвятим практике."
Этап 4. Открытие нового знания по учебнику (7 мин)
Цель этапа: сформировать точное представление о нормальном алгоритме Маркова и алгоритме выбора применимого правила.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель предлагает прочитать в учебнике фрагмент с определением и говорит: "Читайте текст с пометками: отметьте галочкой уже знакомые идеи, плюсом — новое, вопросом — непонятное. Найдите в тексте три обязательных элемента: исходное слово, упорядоченную систему подстановок и условие остановки." | Читают фрагмент с пометками, выделяют три элемента, формулируют вопросы по обозначениям. |
2 мин | Учитель обобщает: "Нормальный алгоритм Маркова — это конечная упорядоченная последовательность правил подстановки. Для текущего слова просматриваем правила сверху вниз, выбираем первое применимое правило и заменяем самое левое вхождение образца. Если применено заключительное правило, работа завершается." | Записывают определение и проговаривают алгоритм по шагам: «прочитать правила сверху вниз — найти образец — заменить первое левое вхождение — проверить остановку». |
2 мин | Учитель разбирает пример на доске: правила $ab\to c$, $c\to d$, $d\to.$, исходное слово «ab». Спрашивает: "Какое правило сработает первым? Что произойдёт на втором шаге? Почему третье правило останавливает алгоритм?" | Записывают цепочку «ab → c → d», называют применённые правила и объясняют: «После заключительной замены дальнейший поиск правил не выполняется». |
Запись в тетрадях
Нормальный алгоритм Маркова — упорядоченная последовательность правил подстановки над словами. Правила проверяются сверху вниз. На каждом шаге применяется первое подходящее правило к самому левому вхождению образца. Запись $u\to v.$ является заключительной и останавливает алгоритм после замены.
Завершение этапа: учитель подводит итог: "Теоретическое правило теперь зафиксировано. Давайте проверим его не на одном коротком примере, а на серии преобразований, где важны точность и взаимная проверка."
Этап 5. Первичное закрепление: работа в парах (8 мин)
Цель этапа: отработать выполнение нормального алгоритма по таблице трассировки и научиться объяснять выбор каждого правила.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель раздаёт карточку 1 и говорит: "Работаем в парах. Один ученик — исполнитель, второй — контролёр; через четыре минуты поменяйтесь ролями. Выполните алгоритм и после каждого шага заполняйте таблицу. Алгоритм: 1) $01\to 10$; 2) $10\to 11$; 3) $11\to.$. Исходное слово — «01». Не перепрыгивайте через правила." | Распределяют роли, записывают исходное слово и начинают трассировку. |
3 мин | Учитель контролирует пары и задаёт вопросы: "Какое правило проверяете первым? Почему нельзя сразу применить правило 2? Что записываете в графе «применённое правило»?" При необходимости показывает на доске первый шаг без сообщения полного ответа. | Выполняют: «01 → 10 → 11», указывают правила 1 и 2, затем отмечают применение правила 3 и остановку. |
3 мин | Учитель организует взаимопроверку: "Обменяйтесь карточками с соседней парой. Проверьте три критерия: порядок правил, левое вхождение, фиксация заключительного шага. Поставьте две звезды за верные элементы и одно пожелание, если найдено исправимое нарушение." | Сверяют решения, отмечают правильные элементы, формулируют замечание, например: «Не указано, что последняя замена является заключительной». |
Эталон решения
Исходное слово: «01». 1. Применяем правило $01\to 10$: получаем «10». 2. Правило $01\to 10$ больше не применимо; применяем $10\to 11$: получаем «11». 3. Применяем заключительное правило $11\to.$: слово преобразуется в «11», после чего алгоритм останавливается. Цепочка: $01\to 10\to 11$.
Завершение этапа: учитель подводит итог: "Мы научились вести трассировку и проверять её по критериям. Теперь каждый самостоятельно решит задачу, чтобы увидеть, какие шаги уже выполняются уверенно, а где нужна коррекция."
Этап 6. Самостоятельная практическая работа (10 мин)
Цель этапа: проверить индивидуальное умение выполнять и анализировать нормальный алгоритм Маркова.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель раздаёт карточки трёх уровней и говорит: "Выберите уровень, который соответствует вашей готовности. Базовый вариант обязателен для всех, повышенный можно выбрать при уверенной работе, исследовательский предназначен для тех, кто готов анализировать поведение системы. Записывайте не только ответ, но и всю цепочку слов." | Выбирают карточку, переписывают правила и исходное слово, уточняют условие остановки. |
5 мин | Учитель напоминает общий алгоритм: "Проверяйте правила строго сверху вниз. Если образец встречается несколько раз, заменяйте самое левое вхождение. После каждого шага ставьте номер правила. Если возникает заключительная подстановка, остановитесь именно на ней." | Индивидуально выполняют выбранное задание и составляют трассировку. |
3 мин | Учитель выводит эталон выбранного базового задания на экран и предлагает самопроверку: "Сверьте каждый переход, а не только последнее слово. Если есть расхождение, обведите место ошибки и исправьте цепочку рядом, не стирая первый вариант." | Проверяют решение по шагам, исправляют ошибки, отмечают в листе самооценки: «могу самостоятельно», «нужна подсказка» или «пока затрудняюсь». |
Эталон решения
Базовое задание: правила $ab\to c$, $c\to ba$, $aa\to.$; исходное слово «aab». Первый шаг: правило 1 неприменимо к началу «aa», но вхождение «ab» есть справа, поэтому получаем «ac». Второй шаг: применяем правило 2, получаем «aba». Третий шаг: правило 1 применяется к «ab», получаем «ca». Четвёртый шаг: правило 2 применяется к «c», получаем «baa». Затем правило 3 неприменимо, правило 1 неприменимо, правило 2 применяется к «c» отсутствующему; алгоритм останавливается из-за отсутствия применимых правил. При проверке важно обсуждать порядок поиска и не считать отсутствие правила заключительной остановкой.
Завершение этапа: учитель подводит итог: "Самостоятельная работа показала, что главный источник ошибок — не сложность замены, а нарушение порядка проверки правил. Осталось обобщить результат и выяснить, чем отличается обычная остановка от остановки по заключительному правилу."
Этап 7. Обобщение, рефлексия и домашнее задание (8 мин)
Цель этапа: обобщить алгоритм действий, выявить типичные ошибки и дать задание для продолжения практики дома.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель предлагает приём «Светофор»: "Покажите зелёную карточку, если можете объяснить порядок применения правил; жёлтую — если выполняете по образцу, но сомневаетесь; красную — если пока не понимаете, когда остановиться. Теперь ответьте: чем отличается заключительное правило от обычной остановки?" | Показывают карточки, отвечают: «Заключительное правило специально сообщает об остановке после замены; при обычной остановке применимых правил больше нет». |
2 мин | Учитель проводит мини-викторину: "Верно ли, что можно выбрать любое подходящее правило? Верно ли, что заменяется самое левое вхождение? Можно ли менять порядок правил без изменения результата?" | Отмечают ответы: «Нет», «Да», «Нет, результат может измениться», кратко обосновывают каждый ответ. |
3 мин | Учитель раздаёт билет на выход и говорит: "За одну минуту запишите: 1) правило выбора подстановки; 2) значение точки в записи правила; 3) одну ошибку, которую вы сегодня научились предупреждать. Сдайте билет при выходе. Домашнее задание выберите по уровню, но базовый уровень обязателен." | Заполняют билет на выход, записывают домашнее задание и формулируют личный результат урока. |
Завершение этапа: учитель подводит итог: "Сегодня мы построили рабочую модель нормального алгоритма Маркова: увидели порядок выбора правил, научились составлять трассировку и отличать два способа остановки. Проверьте дома не только последнее слово, но и каждый переход между словами."
Критерии оценивания практической работы
- «5» — правильно выполнена трассировка выбранного задания, указаны номера применённых правил, соблюдены порядок проверки и правило самого левого вхождения, корректно определён момент остановки.
- «4» — результат в целом верен, но допущена одна неточность в записи промежуточного шага или объяснении причины остановки, исправленная после самопроверки.
- «3» — выполнена основная часть преобразований, но допущены две ошибки в выборе правила, порядке действий или фиксации заключительного правила; после подсказки ученик может продолжить решение.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Какое правило выбора подстановки вы будете применять первым при решении новой задачи? | Проверка понимания ключевого алгоритма выбора правила. |
На каком шаге самостоятельной работы вы почувствовали затруднение? | Выявление точек затруднения в трассировке и определении остановки. |
Чем заключительное правило отличается от обычного правила? | Проверка осознания двух способов завершения алгоритма. |
Что вы сможете объяснить однокласснику после сегодняшнего урока? | Оценка переноса знания и субъективной уверенности ученика. |
Завершающее слово учителя
"Сегодня мы увидели, как из простых подстановок строится строгий формальный алгоритм. Самая частая ошибка — применить удобное правило, нарушив порядок просмотра, или забыть проверить самое левое вхождение. Дома обязательно записывайте всю цепочку преобразований, а не только конечное слово. На следующем уроке мы продолжим практику и исследуем алгоритмы, которые могут приводить к зацикливанию или давать разные результаты при изменении порядка правил."
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Выполнить 3 задачи на применение нормального алгоритма Маркова к заданному слову: для каждой записать правила, все промежуточные слова, номера применённых правил и момент остановки. | Закрепляет базовый алгоритм трассировки; при проверке обратить внимание на порядок правил, самое левое вхождение и различение заключительной и обычной остановки. |
Средний (повышающий) | Составить 2 собственных нормальных алгоритма по 3–5 правил: один должен преобразовывать слово с двоичными символами в другое слово, второй — удалять или заменять заданную последовательность; проверить каждый на двух исходных словах. | Формирует умение конструировать алгоритм и прогнозировать его работу; проверять наличие применимости правил и однозначность результата. |
Продвинутый (дополнительный) | Исследовать алгоритм из 4–6 правил, в котором изменение порядка двух правил меняет результат или приводит к зацикливанию. Привести исходное слово и две трассировки, затем письменно объяснить причину различия. | Развивает анализ и оценку алгоритмов; при проверке смотреть на доказательность трассировки и корректность вывода о влиянии порядка правил. |
Контрольные вопросы перед выходом: «Как выбирается правило в нормальном алгоритме Маркова? Что означает точка после правой части подстановки? Что записывают в трассировке? Чем отличается остановка по заключительному правилу от остановки при отсутствии применимых правил?»
