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

Обновлено: 01.07.2024

Цель работы

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

Задачи лабораторной работы

После выполнения работы студент должен знать и уметь:

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

Перечень обеспечивающих средств

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

Общие теоретические сведения

Решение любой задачи на ЭВМ можно разбить на следующие этапы: разработка алгоритма решения задачи, составление программы решения задачи на алгоритмическом языке, ввод программы в ЭВМ, отладка программы (исправление ошибок), выполнение программы на ПК, анализ полученных результатов.

Первый этап решения задачи состоит в разработке алгоритма.

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

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

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

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

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

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

Задание 1. Определить площадь трапеции по введенным значениям оснований (a и b) и высоты (h).

Процесс решения задач на компьютере – это совместная деятельность человека и ЭВМ. На долю человека приходятся этапы, связанные с творческой деятельностью – постановкой, алгоритмизацией, программированием задач и анализом результатов, а на долю персонального компьютера – обработка информации с разработанным алгоритмом.

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

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

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

Третий этап – алгоритмизация задачи.На основе математического описания необходимо разработать алгоритм решения.

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

Задача составления алгоритма не имеет смысла, если не известны или не учитываются возможности его исполнителя (ребёнок может прочесть, но не может решить сложную задачу).

Исполнителем может быть не только человек, но и автомат. Компьютер – лишь частный, но наиболее впечатляющий пример исполнителя, чьё поведение основано на реализации алгоритма. Более того, создание персонального компьютера оказало воздействие на развитие теории алгоритмов, одной из областей дискретной математики.

Эффективный метод построения алгоритма –метод пошаговой детализации(последовательного построения). При этом сложная задача разбивается на ряд более простых. Для каждой подзадачи – свой алгоритм. Универсальный эффективный метод построения алгоритма является основой структурного программирования (языки QBasic, Turbo Pascal и др.).

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

Используются различные способы записи алгоритмов:

– словесный (запись рецептов в кулинарной книге, инструкции по использованию технических устройств и т. п.);

– графический – пример на рисунке;

– структурно-стилизованный (для записи используется язык псевдокода).

Свойства алгоритма.При составлении и записи алгоритма необходимо обеспечить, чтобы он обладал рядом свойств.

Однозначностьалгоритма – единственность толкования исполнителем правил выполнения действий и порядка их выполнения. Чтобы алгоритм обладал этим свойством, он должен быть записан командами из системы команд исполнителя (сложитьАиВ).

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

Результативностьалгоритма – предполагает, что выполнение алгоритма должно завершиться получением определённых результатов. У нас для целыхАиВвсегда будет вычислена сумма.

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

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

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

Пятый этап – ввод программы и исходных данных в ЭВМс клавиатуры с помощью редактора текстов и их запись на гибкий или жёсткий диск для постоянного хранения.

Шестой этап – тестирование и отладка программы. Исполнение алгоритма с помощью ЭВМ, поиск и исключение ошибок. При этом программисту приходится выполнять рутинную работу по проверке работы программы, поиску и исключению ошибок, и поэтому для сложных программ этот этап часто требует гораздо больше времени и сил, чем написание первоначального текста программы.

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

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

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

Седьмой этап – исполнение отлаженной программы и анализ результатов.На этом этапе программист запускает программу и задаёт исходные данные, требуемые по условию задачи.

Полученные результаты анализируются постановщиком задачи, и на основании этого анализа вырабатываются соответствующие решения, рекомендации, выводы. Например, если при решении задачи на ПК результат 2+3=4, то следует изменить алгоритм и программу.

Чтобы персональный компьютер (ПК) выполнил решение какой-либо задачи, ему необходимо получить от человека инструкции, как её решать. Набор таких инструкций для компьютера, направленный на решение конкретной задачи, называется компьютерной программой.

Современные компьютеры не настолько совершенны, чтобы понимать программы, написанные на каком-либо употребляемом человеком языке.

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

В самом общем смыслеязыком программированияназывается фиксированная система обозначений и правил для описания алгоритмов и структур данных.

Язык программирования Турбо- Паскаль. Структура языка Turbo-Pascal, основные понятия. Запись и порядок выполнения операций в арифметическом выражении. Стандартные математические функции и процедуры Turbo-Pascal

Система программирования Turbo Pascal предназначена для выполнения этапов решения задачи на алгоритмическом языке Паскаль и включает в себя три главные компоненты: редактор текстов, компилятор, исполнительную систему.

С помощью встроенного в систему текстового редактора можно формировать в памяти любые тексты, не только программы на Паскале. В частности, это могут быть исходные данные решаемой задачи в текстовой форме. Текст программы, созданный редактором, можно сохранить на диске в виде файла с именем следующего формата <имя файла>.раs, где pas — это стандартное расширение имени файла, созданного системным редактором. Имя файла задается пользователем.

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

Turbo Pascal позволяет редактировать, компилировать, компоновать и выполнять Паскаль-программы. При этом пользователю предоставляется высокая скорость компиляции, удобство работы с компьютером и мощная библиотека процедур и функций.

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

Program<имя программы> (заголовок программы);

Uses(раздел объявления модулей);

Label(раздел объявления меток);

Const(раздел объявления констант);

Type(раздел объявления типов);

Var(раздел объявления переменных);

Procedure(function)(раздел объявления подпрограмм: процедурили функций);

Begin

<операторы > (раздел операторов, обязательная часть);

end.

Все указанные разделы отделяются друг от друга точкой с запятой.

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

Заголовок программы состоит из зарезервированного словаprogramи имени программы (со списком параметров, заключенных в круглые скобки). Завершается заголовок точкой с запятой.

В Turbo Pascal имеются особенности в структуре программы. Так, заголовок программы необязателен и игнорируется компилятором. Порядок размещения разделов произвольный, можно создавать несколько одинаковых разделов. Единственное правило, которое необходимо выдерживать, - в любом месте программы можно использовать лишь элементы (метки, типы, константы, переменные, подпрограммы и т. д.), которые были определены ранее по тексту программы или являются предопределенными элементами языка. Исключением из этого правила может быть лишь определение типа-указателя через неопределенный до этого тип. Однако этот тип в дальнейшем должен быть обязательно определен.

Операторы в разделе операторов отделяются друг от друга точкой с запятой. Передendточка с запятой не ставится, однако ее наличие не является ошибкой, а лишь означает присутствие между последним исполняемым оператором и служебным словомendеще одного оператора - пустого оператора. Заканчивается программа словомend, после которого ставится точка.

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

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

- конструкции одного уровня вложенности записываются на одном вертикальном уровне (начинаются с одной позиции в строке);

- вложенная конструкция записывается смещенной по строке на несколько позиций вправо относительно внешней для нее конструкции.

Знаки операций предназначены для обозначения тех или иных арифметических, логических или других действий. Они бывают двух типов: состоящие из небуквенных символов (например, +, -, * и т.д.) и буквенные операции (например, not, mod, div и т. д.), представляющие собой зарезервированные слова. Операции над данными делятся на унарные (применимые к одному операнду) и бинарные (применимые к двум операндам). Приведем примеры бинарных арифметических операций (в таблице буква I обозначает целые типы, R — вещественные типы):

Знак	Выражение	Типы операндов	Тип результата	Операция
+	А+В	R,R I,I I,R; R,I	R I R	Сложение
-	А-В	R,R I,I I,R; R,I	R I R	Вычитание
*	А*В	R,R I,I I,R; R,I	R I R	Умножение
/	А/В	R,R I,I I,R; R,I	R R R	Вещественное деление
Div	A div B	I, I	I	Целое деление
Mod	A mod B	I, I	I	Остаток от деления

Арифметическое выражение задает порядок выполнения действий над числовыми величинами. Арифметические выражения содержат арифметические операции, функции, операнды, круглые скобки. Одна константа или одна переменная — простейшая форма арифметического выражения.

Порядок выполнения операций в арифметическом выражении подчиняется трем правилам:

1. Правилу скобок. Оно гласит, что первыми выполняются операции в скобках. Если имеется несколько пар вложенных скобок, вычисления начинаются с самых внутренних скобок.

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

3. Правилу следования: операции одинакового старшинства (приоритета) выполняются слева направо в порядке их следования.

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

Турбо Паскале не содержит некоторые часто используемые математические функции, поэтому при их вычислении используют эквивалентные математические формулы:

Функция	Эквивалентная математическая формула	Запись в программе
ax		exp(x*ln(a))
tg(x)		sin(x)/cos(x)
arcsin(x)		arctan(x/sqrt(1-x*x))
arccos(x)		arctan(sqrt(1-x*x)/x)
logax		ln(x)/ln(a)

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

Структура процедуры имеет следующий вид:

Procedure <имя процедуры>(формальные параметры : их тип);

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

Процедура вызывается по имени:

<имя процедуры> (фактические параметры);

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

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

Заголовок процедуры может выглядеть так:

PROCEDURE GG(a,b,c:integer); вызыватьсятак: GG(3,n,m)

Здесь a,b,c-формальные параметры, а 3, n, m-фактические параметры

Таким образом в процедуру передаются значения: a=3, b=n, c=m

Переменные описанные в процедуре после слова Var, являются внутренними переменными процедуры или промежуточными, они не являются данными для операций внутри процедуры и не являются результатом её выполнения, а нужны лишь для промежуточных действий. Данные и результаты описываются в круглых скобках после имени процедуры. Перед описанием переменных-результатов пишут служебное слово var.

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

Примеры: правила сложения, умножения, решения алгебраических уравнений и т.п.

1.Универсальность (массовость) - применимость алгоритма к различным наборам исходных данных.

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

3.Конечность - каждое из действий и весь алгоритм в целом обязательно завершаются.

4.Результативность - по завершении выполнения алгоритма обязательно получается конечный результат.

5.Выполнимость (эффективность) - результата алгоритма достигается за конечное число шагов.

6.Детерминированность (определенность) - алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно. Т.е. одно и то же предписание после исполнения должно давать один и тот же результат.

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

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

2. информационные алгоритмы , представляющие собой набор сравнительно простых процедур, работающих с большими объемами информации (алгоритмы баз данных);

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

По типу передачи управления алгоритмы бывают: основные (главные выполняемые программы) и вспомогательные (подпрограммы).

Для задания алгоритма необходимо описать следующие его элементы:

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

3.правило непосредственной переработки информации (описание последовательности действий);

5.правило извлечения результатов.

Способы описания алгоритмов.

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

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

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

Правила создания блок – схем:

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

2.Стрелка в конце линии может не ставиться, если линия направлена слева направо или сверху вниз.

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

4.Из блока (кроме логического) может выходить только одна линия.

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

6.Если на схеме имеет место слияние линий, то место пересечения выделяется точкой. В случае, когда одна линия подходит к другой и слияние их явно выражено, точку можно не ставить.

7.Схему алгоритма следует выполнять как единое целое, однако в случае необходимости допускается обрывать линии, соединяющие блоки.

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

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

1.«да» — условие выполнено.

2.«нет» — условие не выполнено.

Циклические алгоритмы содержат цикл – это многократно повторяемый участок алгоритма.Различают циклы с предусловием и постусловием.Также циклы бывают детерминированные и итерационные.Цикл называется детерминированным, если число повторений тела цикла заранее известно или определено. Цикл называется итерационным, если число повторений тела цикла заранее неизвестно, а зависит от значений параметров (некоторых переменных), участвующих в вычислениях.

Для составления программы, предназначенной для решения на ЭВМ какой-либо задачи, требуется составление алгоритма ее решения.

Алгоритм — это точное предписание, которое определяет процесс, ведущий от исходных данных к требуемому конечному результату. Алгоритмами, например, являются правила сложения, умножения, решения алгебраических уравнений, умножения матриц и т.п. Слово алгоритм происходит от algoritmi, являющегося латинской транслитерацией арабского имени хорезмийского математика IX века аль-Хорезми. Благодаря латинскому переводу трактата аль-Хорезми европейцы в XII веке познакомились с позиционной системой счисления, и в средневековой Европе алгоритмом называлась десятичная позиционная система счисления и правила счета в ней.

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

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

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

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

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

Для задания алгоритма необходимо описать следующие его элементы:

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

правило непосредственной переработки информации (описание последовательности действий);

правило извлечения результатов.

Алгоритм всегда рассчитан на конкретного исполнителя. В нашем случае таким исполнителем является ЭВМ. Для обеспечения возможности реализации на ЭВМ алгоритм должен быть описан на языке, понятном компьютеру, то есть на языке программирования.

Таким образом, можно дать следующее определение программы.

Программа для ЭВМ представляет собой описание алгоритма и данных на некотором языке программирования, предназначенное для последующего автоматического выполнения.

Способы описания алгоритмов

К основным способам описания алгоритмов можно отнести следующие:

структурный или блок-схемный;

с помощью граф-схем;

с помощью сетей Петри.

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

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

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

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

1. Ввести значения а их.

2. Сложить х и 6.

3. Умножить aна 2.

4. Вычесть из 2а сумму (х+6).

5. Вывести у как результат вычисления выражения.

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

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

Оформление программ должно соответствовать определенным требованиям. В настоящее время действует единая система программной документации (ЕСПД), которая устанавливает правила разработки, оформления программ и программной документации. В ЕСПД определены и правила оформления блок-схем алгоритмов (ГОСТ 10.002-80 ЕСПД, ГОСТ 10.003-80 ЕСПД).

Операции обработки данных и носители информации изображаются на схеме соответствующими блоками. Большая часть блоков по построению условно вписана в прямоугольник со сторонами а и b. Минимальное значение а = 10 мм, увеличение а производится на число, кратное5 мм. Размер b=1,5a. Для от дельных блоков допускается соотношение между а и b, равное 1:2. В пределах одной схемы рекомендуется изображать блоки одинаковых размеров. Все блоки нумеруются. Виды и назначение основных блоков приведены в табл. 1.

Таблица 1. Условные обозначения блоков схем алгоритмов

Наименование

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

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

Выбор направления выполнения алгоритма в зависимости от некоторых переменных условий.

Использование ранее созданных и отдельно написанных программ (подпрограмм).

Вывод данных на бумажный носитель.

Ввод-вывод данных, носителем которых служит магнитный диск.

Начало, конец, прерывание процесса обработки данных.

Указание связи между прерванными линиями, соединяющими блоки.

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

Связь между элементом схемы и пояснением.

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

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

Если при обрыве линии продолжение схемы находится на этом же листе, то на одном и другом конце линии изображается специальный символ соединитель — окружность диаметром 0,5 а. Внутри парных окружностей указывается один и тот же идентификатор. В качестве идентификатора, как правило, используется порядковый номер блока, к которому направлена соединительная линия.

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

Блок-схема должна содержать все разветвления, циклы и обращения к подпрограммам, содержащиеся в программе.

Алгоритмы появились вместе с математикой, а первые упоминания о них встречаются в книге математика Мухаммеда бен Мусы аль-Хорезми из города Хорезма. Он описал методы выполнения различных действий с многозначными числами еще в 825 году. Само слово «алгоритм» появилось после того, как книгу ученого перевели на латинский язык в Египте.

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

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

Свойства и виды

Для изучения понятия нужно разобраться в свойствах алгоритма в информатике. Их существует несколько:

дискретность;
детерминированность или определенность;
понятность;
завершаемость или конечность;
массовость или универсальность;
результативность.

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

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

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

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

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

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

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

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

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

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

Способы записи

Алгоритмы записываются несколькими методами. В информатике используется всего три:

словесно-формульный;
графический;
программный.

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

Графическое описание состоит из связанных между собой географических фигур. Основные элементы блок-схем:

прямоугольники;
эллипсы;
ромбы;
шестиугольники;
стрелки;
пунктирные линии;
соединительные фигуры.

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

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

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

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

Правила создания

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

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

Разобраться с действиями помогут простые примеры алгоритмов по информатике. Когда есть ряд чисел от 1 до 100 и необходимо найти из них простые, то выбираются те, что делятся на единицу и себя. В этом случае используется циклическая структура:

сначала нужно взять число 1;
проверить, меньше ли оно, чем 100;
если да, то узнать, простое ли оно;
при выполнении условия записать;
перейти к числу 2;
повторить операцию.

Такие действия проводят со всеми числами. При этом первые четыре шага будут постоянно повторяться. Если попадается число, не являющееся простым (4, 6, 8 и т. д. ), то его нужно просто пропустить. Алгоритм в этом случае обладает предусловиями, то есть проверки происходят в начале цикла.

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

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

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

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

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

Читайте также: