Способы записи алгоритмов
Один алгоритм можно записать по-разному: словами, пронумерованными строками, блок-схемой или на языке программирования. Разбираем, чем эти способы отличаются, где какой удобен, какие фигуры и линии используются в блок-схемах, что такое алфавит, синтаксис и семантика языка программирования, и записываем алгоритмы Евклида и переливаний в каждой из форм.
Способы записи алгоритмов: блок-схемы, псевдокод, языки программирования | Информатика 8 класс20:01- Словами: описание и построчная запись
- Рисунком: блок-схемы
- Для компьютера: языки программирования и псевдокод
Полный сосуд на 12 литров, два пустых — на 8 и на 5. Надо отлить ровно половину. Ты, скорее всего, решишь это за пару минут перебором — а как записать решение так, чтобы его без единой ошибки выполнил тот, кто головой не думает вовсе: робот-исполнитель? И почему одну и ту же последовательность действий информатика умеет записывать четырьмя разными способами?
Различать четыре способа записи алгоритма (словесное описание, построчная запись, блок-схема, язык программирования) и объяснять сильные и слабые стороны каждого.
Читать и составлять блок-схемы: знать назначение блоков начала/конца, данных, обработки, принятия решения и правило стрелок на линиях связи.
Объяснять, что такое алфавит, синтаксис и семантика языка программирования, и записывать простой алгоритм на псевдокоде с служебными словами алг, нач, кон.
Словами: описание и построчная запись
Способов записать алгоритм несколько. Основные: словесные (на естественных языках), графические и на языках программирования. Почему их так много? Потому что у алгоритма разные читатели: человеку удобно одно, компьютеру — совсем другое.
Теоретические исследования нашего соотечественника Андрея Андреевича Маркова (младшего) (1903—1979), выполненные в середине прошлого века, показали: в общем случае алгоритм состоит из предписаний двух видов.
Функциональные операторы — предписания, направленные на непосредственное преобразование информации.
Логические операторы — предписания, определяющие дальнейшее направление действий.
Именно эти операторы положены в основу большинства способов записи алгоритмов.
Представь дорогу с работами. Функциональный оператор — рабочий, который что-то делает: копает, кладёт асфальт, меняет данные. Логический оператор — светофор на развилке: сам ничего не делает, только решает, куда ехать дальше. Любой алгоритм собирается из «рабочих» и «светофоров».
Зацепки: ФУНКЦИОНАЛЬНЫЕ — выполняют функцию: непосредственно преобразуют информацию. ЛОГИЧЕСКИЕ — логика решает, куда направить дальнейшие действия.
Словесное описание — запись алгоритма в виде набора предписаний на обычном разговорном языке.
У него минимум ограничений, и он наименее формализован. Но все разговорные языки обладают неоднозначностью: чтобы избежать двусмысленности, текст приходится делать очень подробным — и он становится объёмным и трудным для восприятия.
Словесное описание — как объяснить дорогу прохожему: «дойдёшь до магазина, потом налево, там увидишь». Тебя поймёт человек, который сам додумает, какой магазин и насколько «налево», — а робот на первом же слове остановится. Свобода речи оборачивается двусмысленностью, и чтобы её убрать, приходится расписывать каждую мелочь.
Способ запомнить — правило самопроверки: словесное = свободное: минимум правил, максимум слов; если один и тот же текст можно понять двумя способами — это словесное описание, и его пора переводить в построчную запись.
«Чтобы найти НОД двух чисел, составьте таблицу из двух столбцов и назовите столбцы и . Запишите первое из заданных чисел в столбец , а второе — в столбец .»
«Если данные числа не равны, замените большее из них на результат вычитания из большего числа меньшего.»
«Повторяйте такие замены до тех пор, пока числа не окажутся равными, после чего число из столбца считайте искомым результатом.»
Проверим на и : , НОД . Работает — но попробуй по этому тексту понять, что делать, если числа равны с самого начала: придётся перечитывать.
Построчная запись — запись алгоритма на естественном языке, при которой каждое предписание записывается с новой строки, шаги нумеруются, а исполнение происходит в порядке возрастания номеров шагов.
Предписания могут содержать математические выражения и формулы. Такая запись позволяет избежать ряда неопределённостей и не требует дополнительных знаний — но требует от человека большого внимания.
Это рецепт, разрезанный на пронумерованные карточки: одна карточка — одно действие, и ты идёшь по номерам. Заблудиться труднее, чем в сплошном тексте, а «перейти к п. 8» — как закладка: прыгнул на нужную карточку.
Зацепка: ПО СТРОЧКАМ: каждое предписание с новой строки, шаги пронумерованы и выполняются по возрастанию номеров.
- Обозначить первое из заданных чисел , второе обозначить . 2. Если , то перейти к п. 8. 3. Если , то перейти к п. 4, иначе перейти к п. 6. 4. Заменить на . 5. Перейти к п. 2. 6. Заменить на . 7. Перейти к п. 2. 8. Считать искомым результатом.
Исполняем: , . П. 2: не равны. П. 3: ? Нет — идём к п. 6: . П. 7 → п. 2.
, : не равны; — п. 4: . П. 5 → п. 2.
, : равны — п. 8. Результат . Каждый шаг однозначен: не надо думать, «что имелось в виду», надо только внимательно следить за номерами.
Построчная запись — это просто словесное описание, разбитое на абзацы.
Три правила делают её другим способом: каждое предписание с новой строки, шаги пронумерованы, исполнение идёт по возрастанию номеров (если нет специальных указаний вроде «перейти к п. 8»). Именно нумерация и переходы убирают неоднозначность.
В построчной записи Евклида для , какой пункт выполнится после п. 2?
показать
В построчной записи Евклида для , какой пункт выполнится после п. 2?
П. 8 — числа равны, результат . В словесном описании этот случай пришлось бы додумывать.
Какое определение соответствует понятию «функциональные операторы»?
Рисунком: блок-схемы
Наилучшей наглядностью обладают графические способы записи, и самый распространённый из них — блок-схема. Вместо «перейти к п. 6» — просто линия, по которой скользит взгляд.
Блок-схема — графическое изображение порядка выполнения алгоритма, где предписания изображаются геометрическими фигурами (блоками), а последовательность шагов — соединяющими их линиями связи.
Линии связи слева направо и сверху вниз — стандартные, их изображают без стрелок. Линии справа налево и снизу вверх изображаются со стрелками.
Блок-схема — схема метро для алгоритма: станции-блоки и линии между ними. Едешь «по умолчанию» вниз и вправо, как читаешь страницу, — стрелки не нужны. Поворот назад или вверх — это возврат, и его помечают стрелкой, чтобы не проехать.
Зацепка: БЛОК-схема: предписания помещены в геометрические блоки, а линии связывают порядок шагов.
| Блок | Что внутри | Линии связи |
|---|---|---|
Начало / конец (а) | выполнение всегда начинается с блока начала и заканчивается переходом на блок конца | из начала выходит одна линия; в конец входит одна |
Данные (б) | величины, которые вводятся (исходные данные) или выводятся (результаты) в этом месте | одна входит, одна выходит |
Обработка данных (в) | действия, меняющие значение, форму или размещение информации | одна входит, одна выходит |
Принятие решения (г) | проверяемое условие | одна входит, две выходят — у каждой подписан результат проверки |
Комментарий (д) | пояснительные записи, делающие схему понятнее | — |
Заметь связь с первой частью: блок обработки данных — это функциональный оператор («рабочий»), блок принятия решения — логический («светофор»). Из «светофора» выходят две линии, потому что у условия два исхода.
Блок начала → блок данных: вводим , .
Ромб «?»: нет → идём по линии «нет» к ромбу «?»: нет → блок обработки «», получаем . Линия возвращается вверх к первой проверке — она со стрелкой, потому что идёт снизу вверх.
Второй круг: ? нет; ? да → «», . Снова вверх.
Третий круг: ? да → блок данных выводит → блок конца. Тот же результат, что в построчной записи, но путь виден глазами.
Из ромба (блока принятия решения) выходит одна линия, как из всех остальных блоков.
Две — по одной на каждый результат проверки условия, и около каждой подписано «да»/«нет». Одна выходящая линия — у блоков данных и обработки.
Где блок-схема проигрывает. Создание детальной блок-схемы сложного алгоритма — трудоёмкая задача, а схема, не умещающаяся на одном стандартном листе, теряет своё главное преимущество — наглядность. Поэтому для сложных алгоритмов блок-схемы используют как средство представить решение задачи в общем виде, а не расписать каждый шаг.
Линия на блок-схеме идёт снизу вверх. Нужна ли ей стрелка?
показать
Линия на блок-схеме идёт снизу вверх. Нужна ли ей стрелка?
Да: стандартные направления — слева направо и сверху вниз, они без стрелок; справа налево и снизу вверх — со стрелками.
Какое свойство алгоритма подразумевает его разбиение на последовательность отдельных законченных шагов?
Для компьютера: языки программирования и псевдокод
Человеку хватит слов и картинок. Компьютер не понимает ни того, ни другого — ему нужен язык без единой двусмысленности.
Язык программирования — формальный язык, предназначенный для записи компьютерных программ (алгоритмов, исполнителем которых является компьютер).
Каждый язык характеризуется:
- алфавитом — набором используемых в языке символов;
- синтаксисом — системой правил, по которым из символов алфавита образуются правильные конструкции языка;
- семантикой — системой правил, строго определяющей смысл и способ употребления конструкций языка.
Это три уровня любого языка, и русского тоже. Алфавит — буквы, из которых всё складывается. Синтаксис — грамматика: «мама мыла раму» построено правильно, «раму мыла мама мыла» — нет. Семантика — смысл: фраза «зелёные идеи яростно спят» грамматически правильна, но ничего не значит. Компьютер проверяет сначала синтаксис (собрана ли конструкция по правилам), потом выполняет по семантике (что она значит).
Зацепки: СИНТАКСИС — порядок символов: из алфавита складываются правильные конструкции. СЕМАНТИКА — это смысл: она строго определяет смысл и употребление конструкций.
Языков программирования очень много. В 8–9 классах мы будем изучать Паскаль (Pascal), а желающие смогут попробовать силы на школьном (учебном) алгоритмическом языке — его также называют русским алгоритмическим языком или языком КуМир.
Школьный алгоритмический язык — учебный язык программирования, введённый академиком А. П. Ершовым в 1985 году для записи алгоритмов с использованием ограниченного набора служебных слов.
Служебные слова — слова, смысл и способ употребления которых заданы раз и навсегда: алг (алгоритм), нач (начало), кон (конец) и другие. В книгах их выделяют жирным шрифтом, в тетради и на доске — подчёркиванием.
Псевдокод — способ записи алгоритмов, представляющий собой смесь естественного разговорного языка и школьного алгоритмического языка.
алг <название алгоритма>
нач
<последовательность команд>
кон
Заголовок — что делаем; между нач и кон — команды по одной в строке.
Псевдокод — черновик программы, написанный «почти как для компьютера»: каркас строгий (алг — нач — кон, по команде в строке), а сами команды пока русскими словами. Так ты стандартизируешь запись: все алгоритмы выглядят одинаково, и потом их легко переписать на настоящий язык.
Способ запомнить — по служебным словам: алг — назвал, нач — начал, кон — закончил; между ними по одной команде в строке.
алг переливания · нач · наполнить сосуд ёмкостью л из сосуда ёмкостью л · наполнить сосуд ёмкостью л из сосуда ёмкостью л · вылить всё из сосуда ёмкостью л в сосуд ёмкостью л · вылить всё из сосуда ёмкостью л в сосуд ёмкостью л · наполнить сосуд ёмкостью л из сосуда ёмкостью л · долить из сосуда ёмкостью л в сосуд ёмкостью л · вылить всё из сосуда ёмкостью л в сосуд ёмкостью л · кон
Проследим состояние (сосуды / / ): старт → наполнить : → наполнить из : → вылить в : .
→ вылить в : → наполнить из : → долить из в (входит л): → вылить в : .
В -литровом сосуде ровно л — половина. Семь команд, каждая однозначна: такой алгоритм выполнит и исполнитель Водолей в КуМире.
| Способ | Кому удобен | Плюс | Минус |
|---|---|---|---|
Словесное описание | человеку, впервые узнающему идею | минимум ограничений | неоднозначность, объёмность |
Построчная запись | человеку-исполнителю | нумерация убирает неопределённости | требует большого внимания |
Блок-схема | человеку, которому нужно увидеть структуру | наилучшая наглядность | трудоёмко; большая схема теряет наглядность |
Язык программирования / псевдокод | компьютеру (псевдокод — человеку) | строгость, единая форма записи | нужно знать алфавит, синтаксис и семантику |
Псевдокод — это и есть язык программирования, его можно сразу выполнить на компьютере.
Псевдокод — смесь русского языка и школьного алгоритмического; он ориентирован на исполнителя-человека и помогает понять или изложить суть алгоритма. Чтобы выполнил компьютер, алгоритм нужно записать на настоящем языке программирования.
Программа не запустилась: «в строке 3 пропущена точка с запятой». Какой уровень языка нарушен — алфавит, синтаксис или семантика?
показать
Программа не запустилась: «в строке 3 пропущена точка с запятой». Какой уровень языка нарушен — алфавит, синтаксис или семантика?
Синтаксис: конструкция собрана не по правилам. Смысл (семантика) даже не проверялся.
Что в языке программирования понимается под термином «семантика»?
Роботу нужна запись без единой двусмысленности — и информатика даёт для этого целую лестницу форм. Словесное описание проще всего для человека, но разговорный язык неоднозначен. Построчная запись убирает часть неопределённостей нумерацией шагов и переходами. Блок-схема показывает структуру глазами — блоки-действия, ромбы-условия, линии. А для исполнителя вроде Водолея или компьютера алгоритм записывают на языке программирования или на псевдокоде — с жёстким каркасом алг — нач — кон и по одной однозначной команде в строке. Так и записан алгоритм переливаний из примера 4: семь команд, состояние сосудов , и в большом сосуде ровно половина. Способов записи много, потому что у алгоритма разные читатели — от первоклассника до процессора, — и у каждой формы свои достоинства и недостатки.
Основные способы записи алгоритмов: словесные (словесное описание и построчная запись), графические (блок-схема) и языки программирования; у каждого — свои плюсы и минусы.
Алгоритм состоит из функциональных операторов (преобразуют информацию) и логических (определяют направление действий) — А. А. Марков.
Построчная запись: каждое предписание с новой строки, шаги нумеруются, исполнение по возрастанию номеров.
Блок-схема: начало/конец, данные, обработка (одна входящая и одна выходящая линия), принятие решения (две выходящие); линии вниз и вправо без стрелок, вверх и влево — со стрелками.
Язык программирования = алфавит + синтаксис + семантика; школьный алгоритмический язык (А. П. Ершов, 1985) со служебными словами алг, нач, кон; псевдокод — смесь русского и алгоритмического языка.
Запись алгоритма в виде набора предписаний на обычном разговорном языке.
Запись алгоритма на естественном языке, при которой каждое предписание записывается с новой строки, шаги нумеруются, а исполнение происходит в порядке возрастания номеров шагов.
Графическое изображение порядка выполнения алгоритма: предписания — геометрические фигуры (блоки), последовательность шагов — соединяющие их линии связи.
Формальный язык для записи компьютерных программ; характеризуется алфавитом, синтаксисом и семантикой.
Способ записи алгоритмов — смесь естественного разговорного языка и школьного алгоритмического языка.
Способы записи: словесное описание (просто, но неоднозначно) → построчная запись (строки пронумерованы, исполнение по номерам) → блок-схема (наглядно, но громоздко) → язык программирования / псевдокод (строго, для компьютера).
Операторы (Марков): функциональные — преобразуют информацию; логические — направляют.
Блок-схема: начало/конец; данные (ввод/вывод); обработка (действие); принятие решения (ромб, условие, 2 выхода); комментарий. Линии вниз/вправо — без стрелок, вверх/влево — со стрелками.
Язык программирования: алфавит (символы) + синтаксис (правила построения) + семантика (смысл).
Школьный алгоритмический язык (Ершов, 1985): служебные слова алг, нач, кон. Псевдокод — смесь русского и алгоритмического языка.
Переливания : .
Идея делить все команды алгоритма на «действия» и «развилки» принадлежит советскому математику А. А. Маркову (младшему): его исследования середины XX века показали, что двух видов предписаний хватает для любого алгоритма.
Школьный алгоритмический язык — с русскими словами алг, нач, кон — придумал академик А. П. Ершов в 1985 году; он же добился, чтобы информатика появилась в школах нашей страны.
Что такое функциональный оператор в записи алгоритма?
Предписание, направленное на непосредственное преобразование информации.
Как называется предписание, направленное на непосредственное преобразование информации?