Учитель информатики

Линейный алгоритм. Понятие и особенности. Блок-схема

Каждый человек на протяжении своей жизни решает множество задач разной сложности. Но даже самые простые из задач выполняются последовательно, то есть за несколько шагов. Эту последовательность можно назвать алгоритмом. Последовательности бывают разные, но начинать их изучение лучше всего с линейных.

Прежде чем приступить к рассмотрению основной темы статьи, следует сделать краткое отступление и сказать несколько слов про алгоритмический язык.

Этапы решения задачи на компьютере

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

Решение задачи с использованием компьютера включает в себя этапы, показанные на рис. 2.1.

На первом этапе обычно осуществляется постановка задачи, происходит осознание её условия. При этом должно быть чётко определено, что дано (какие исходные данные известны, какие данные допустимы) и что требуется найти в решаемой задаче. Также должны быть чётко выделены существенные свойства рассматриваемого объекта, указаны связи между исходными данными и результатами.

На втором этапе описательная информационная модель формализуется, т. е. записывается с помощью некоторого формального языка.

Для этого требуется:

• понять, к какому классу принадлежит рассматриваемая задача;
• записать известные связи между исходными данными и результатами с помощью математических соотношений;
• выбрать наиболее подходящий способ для решения задачи.

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

На четвёртом этапе алгоритм записывается на одном из языков программирования. Вы учитесь записывать программы на языке Паскаль.

На пятом этапе осуществляется отладка и тестирование программы. Этап отладки и тестирования также называют компьютерным экспериментом.

Отладка программы — это процесс проверки работоспособности программы и исправления обнаруженных при этом ошибок. Ошибки могут быть связаны с нарушением правил записи программы на конкретном языке программирования. Их программисту помогает найти используемая система программирования; она выдаёт на экран сообщения о выявленных ошибках.

Проверка правильности разработанной программы осуществляется с помощью тестов. Тест — это конкретный вариант значений исходных данных, для которого известен ожидаемый результат.

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

Основные понятия

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

Изучение свойств алгоритма в информатике в 9 классе является важным этапом. Это ключевые понятия. Их должны усвоить ученики, прежде чем составлять схемы и программы:

1. Целенаправленность. Любой составленный перечень команд должен иметь конечную цель, ради которой выполняются действия. Чаще всего алгоритм составляется для решения определенной команды.
2. Понятность. Запись всех команд и описаний внутри алгоритма должно быть четким, сформулированным и понятным. Важно, чтобы исполнитель мог их выполнить.
3. Дискретность. Все действия по решению поставленной задачи должны быть разбиты на элементарные команды.
4. Однозначность. При выполнении команды исполнитель должен точно знать, что делать.
5. Массовость. Последовательность команд составляют так, чтобы ее можно было использовать для решения той же задачи, но при других исходных данных.

Каждый алгоритм имеет определенную структуру, которой придерживаются все. Любая программа для исполнения должна выглядеть следующим образом:

• название;
• описание используемых данных;
• начало тела;
• перечень команд;
• конец.

Для отображения составленного алгоритма используют различные способы и методики. Среди самых распространенных выделяют:

• словесно-формульное отображение;
• блок-схема (графический вариант);
• операторные схемы;
• алгоритмические языки;
• псевдокод.

Наиболее распространен графический способ (составление блок-схемы).

Графический способ

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

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

Это неполный список геометрических фигур, которые могут использоваться. Но при составлении программ в графическом виде на уроках информатики в 9 классе знания этих элементов достаточно.

Соединение отдельных элементов выполняют с помощью стрелок, которые и определяют последовательность действий вычислительной машины. Существует множество программных продуктов, в которых можно начертить блок-схемы. При ее создании руководствуются специальным документом ГОСТ 19 .701−90 ЕСПД, в котором прописаны все правила построения и используемые обозначения.

Другие способы отображения

Формульно-словесное описание представляет собой последовательность команд, предложенных исполнителю в виде слов и формул. Все действия записываются на понятном языке, свойственном предметной области. Описание команд составляется в произвольной форме.

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

Близок к алгоритмическим языкам псевдокод. Это специальная система команд для абстрактной машины.

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

Аннотация к презентации

Посмотреть и скачать презентацию по теме «Алгоритм и его формальное исполнение» по информатике, включающую в себя 17 слайдов. Скачать файл презентации 1.08 Мб. Средняя оценка: 3.3 балла из 5. Для учеников 9 класса. Большой выбор учебных powerpoint презентаций по информатике

Алгоритм и его формальное исполнение

Слайд 2

Алгоритм

Алгоритм – это предназначенное для конкретного исполнителя точное описание последовательности действий, направленных на решение поставленной задачи.

Слайд 3

Свойства алгоритма

Дискретность — разделение алгоритма на последовательность шагов.

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

Результативность — получение из исходных данных результата за конечное число шагов.

Пример: Алгоритм всегда приводит к результату, алгоритм покраски забора.

Слайд 4

Массовость — возможность применения алгоритма к большому количеству различных исходных данных.

Пример: Алгоритмы сложения, вычитания, умножения и деления.

Детерминированность (определённость) — исполнитель должен выполнять команды алгоритма в строго определенной последовательности.

Пример: алгоритм управления самолётом.

Слайд 5

Выполнимость и понятность — алгоритм должен содержать команды, входящие в систему команд исполнителя и записанные на понятном исполнителю языке.

Пример: алгоритм включения компьютера.

Слайд 6

Блок-схемы

Прямоугольник с закругленными углами, применяется для обозначения начала или конца алгоритма

Параллелограмм, предназначен для описания ввода или вывода данных, имеет один вход вверху и один выход внизу

Прямоугольник, применяется для описания линей­ной последовательности команд, имеет один вход вверху и один выход внизу

Слайд 7

Ромб, служит для обозначения условий в алгоритми­ческих структурах «ветвление» и «выбор», имеет один вход верху и два выхода (налево, если условие вы­полняется, и направо, если условие не выполняется)

Прямоугольник со срезанным углом, применяется для объявления переменных или ввода комментариев

Слайд 8

Программа

Программа — алгоритм, записанный на «понятном» компьютеру языке программирования

Слайд 9

Машинный язык

Слайд 10

Ассемблер

Слайд 11

Языки программирования высокого уровня

Слайд 12

QBasic

Слайд 13

Pascal

Программа Pascal, названная в честь

Слайд 14

Delphi

Слайд 15

Операционные системы

Слайд 16

Программы-трансляторы

Слайд 17

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

§ 4.1, стр.105-112, составить блок-схему решения квадратного уравнения №4.1, стр.108.

Циклические конструкции

Базовая структура цикл (или повторение) обеспечивает многократное выполнение одних и тех же команд. Существует несколько разновидностей циклических структур. Любая из них содержит тело цикла (набор повторяющихся команд) и заголовок цикла, который определяет количество повторений тела цикла.

ЦИКЛ С ПРЕДУСЛОВИЕМ (ИЛИ ЦИКЛ «ПОКА»)

Заголовок этой структуры содержит условие, которое называется предусловием. Эта структура предписывает повторять тело цикла до тех пор, пока выполняется условие в его заголовке (т. е. пока оно остается истинным).

Работа цикла с предусловием начинается с проверки условия в его заголовке. Если условие истинно — выполняются команды тела цикла и происходит возврат к заголовку цикла. Снова проверяется условие заголовка (поскольку оно могло измениться в результате работы команд цикла) — если оно истинно, опять выполняется тело цикла. Так происходит до тех пор, пока проверка условия в заголовке не выдаст результат «нет». Тогда управление будет передано команде, следующей непосредственно за циклом.

Возможна ситуация, когда команды тела цикла не будут выполнены ни разу — если условие в заголовке сразу же выдает результат проверки «нет». Также возможна ситуация, когда условие заголовка всегда выдает положительный результат проверки — это приведет к бесконечному выполнению цикла, так называемому «зацикливанию» алгоритма. Таким образом, при создании цикла «пока» следует обращать особое внимание на формулировку условия в его заголовке.

■ Пример 6. Записать на алгоритмическом языке алгоритм получения остатка от деления целого числа а на целое число b с помощью вычитания.

Решение. Если число а меньше b, то остатком от деления служит само число а. В ином случае необходимо вычитать b из числа а до тех пор, пока результат не станет меньше b — он и будет остатком от деления.

ЦИКЛ С ПОСТУСЛОВИЕМ (ИЛИ ЦИКЛ «ДО»)

Постусловие формулируется противоположным образом по отношению к предусловию. Цикл «до» предписывает повторять команды тела цикла до тех пор, пока не выполнится условие в его заголовке (т. е. пока оно остается ложным).

Работа цикла с постусловием начинается с выполнения команд тела цикла. Затем проверяется условие цикла. Если условие ложно (проверка условия дает результат «нет») — происходит возврат к выполнению команд тела цикла. Затем снова проверяется условие (поскольку оно могло измениться в результате работы команд цикла). Так происходит до тех пор, пока проверка условия не выдаст результат «да». Тогда происходит выход из цикла и управление будет передано команде, следующей непосредственно за циклом.

В отличие от цикла с предусловием, тело цикла «до» всегда выполняется хотя бы один раз (до первой проверки). Тело цикла «пока» может не выполниться ни разу, если условие при первой же проверке выдаст «нет». Поэтому цикл с постусловием можно заменить циклом с предусловием, а наоборот — нет.

■ Пример 7. Записать алгоритм примера 6 с помощью цикла «до».

Решение.

ЦИКЛ С ПАРАМЕТРОМ (ЦИКЛ СО СЧЕТЧИКОМ, ИЛИ ЦИКЛ «ДЛЯ»)

Эта структура предписывает повторять команды тела цикла для всех значений некоторой переменной (параметра, или счетчика цикла).

Имя параметра цикла (счетчика) указывают в заголовке после служебного слова для. Затем с помощью служебных слов от и до задают начальное и конечное значение этого параметра.

Работа цикла «для» начинается с присвоения параметру начального значения. Если оно не превышает конечного значения, выполняются команды тела цикла. Затем значение параметра цикла увеличивается на единицу. Если оно снова не превышает конечного значения, опять происходит выполнение тела цикла. Если же полученное значение параметра превысит конечное, цикл будет завершен и управление передано следующей за циклом команде.

Цикл со счетчиком всегда выполняется i₁ – i₂ + 1 раз.

■ Пример 8. Записать алгоритм вычисления факториала числа N.

Решение. Факториал числа вычисляется по формуле N! = 1 × 2 × … × N. Следовательно, для расчета факториала надо организовать цикл со счетчиком, в котором перемножить последовательные целые числа от 2 до N. Значение 1!, равное 1, можно присвоить результирующей переменной до цикла.

Обмен информацией и обсуждение (10 мин)

Представитель каждой группы демонстрирует работу на листах или на интерактивной доске. (Скачать флипчарт для доски) Проводится обмен информацией. Учитель во время выступлений может задавать вопросы наводящие вопросы. Целесообразно ли при составлении алгоритмов с повторяющимся числом шагов записывать все эти шаги много раз? Какое слово мы используем, чтобы показать, что шаги алгоритма повторяются несколько раз? А какое слово мы используем, если количество повторений неизвестно?

Обобщение и выводы (7 мин)

Учитель возвращается к вопросу для исследования и обобщает ответы учащихся.

Алгоритм, последовательность шагов которого повторяется многократно называется циклическим и для его записи вводится специальная алгоритмическая структура-цикл. Для того чтобы показать цикл в алгоритмах, используют команду «ПОВТОРИ n РАЗ». Для того чтобы выделить команды, относящиеся к циклу «ПОВТОРИ …», их записывают со сдвигом вправо.

Если в рассмотренном в начале урока алгоритме будет 100 кубиков, то запись алгоритма будет выглядеть так:

Начало

1. Повтори 100 раз
2. Поднять кубик
3. Перенести к машине
4. Опустить на машину
5. Вернуться
6. Остановиться

Конец

Часто количество повторений зависит от условия, тогда после слова повтори можно записать условие цикла.

Циклические алгоритмы тоже можно представить при помощи блок-схем.

Что такое основы алгоритмизации

Для успешного решения задач на компьютере полезно знать основы алгоритмизации и программирования.

Алгоритмизацией называют раздел информатики, изучающий методы и приёмы построения алгоритмов.

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

Геометрические фигуры, используемые для представления шагов алгоритма, отличаются по функциональному назначению. Для обозначения действия или процесса используется прямоугольник. Для задания условия используется ромб, для ввода-вывода применяют параллелограмм, гексаэдр обозначает цикл с заданным числом повторов. Начало и конец алгоритма оформляют в виде овалов.

Все блоки соединяют друг с другом в порядке выполнения этапов алгоритма с помощью стрелок, указывающих направление следования по элементам блок-схемы.

Блок-схемы следует чертить по определенным правилам, собранным в ГОСТ 19.701-90 ЕСПД. «Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения». Блок-схему можно начертить в специальных программах для черчения, которые имеют библиотеки готовых стандартизированных графических элементов.

Анализ работы

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

Гипотеза Ричарда Мейса утверждает, что избежать ошибок легче, чем их устранить. Благодаря доказательству корректности программ можно выявить их свойства, применяемые ко всем видам входных данных. Само понятие делится на две разновидности — частичную и полную. При первом типе корректности алгоритм дает правильный результат только для тех случаев, когда он завершается. Во втором случае программа завершает работу корректно для всего диапазона данных.

Исполнители во время проверки сравнивают выдаваемые данные со спецификой требуемого результата. Для доказательства корректности используются предусловия и постусловия. Первые должны выполняться перед включением программы, вторые — после завершения ее работы. Формальные методы успешно применяются для многих задач: верификации программ и микропроцессоров, разработки искусственного интеллекта, электронных схем и автоматических систем для железной дороги, спецификации стандартов.

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