Одним из важнейших понятий информатики является понятие алгоритма. Существует множество его определений, данных известными учеными в разные времена. Термин «алгоритм» происходит от имени средневекового математика Аль Хорезми, который ещё в 825 году описал правила выполнения четырех арифметических действий в десятичной системе счисления. Впоследствии это слово стало собирательным названием для отдельных правил (последовательности действий) определенного вида, причем не только арифметических. В течение длительного времени его употребляли только математики, обозначая словом «алгоритм» пошаговые правила решения различных задач.
Под алгоритмом понимается точное предписание, задающее преобразование исходных данных в искомый результат.
Процесс создания алгоритма называется алгоритмизацией.
Алгоритм обладает следующими основными свойствами:
Дискретность – представление процесса в виде отдельных элементарных шагов, логическая взаимосвязь выполнения которых не вызывает сомнения;
Определенность (детерминированность) – каждая команда алгоритма должна быть точно и однозначно определена, также должно быть однозначно определено, какая команда будет выполняться на следующем шаге. Результат выполнения команды не должен зависеть от какой-либо дополнительной информации.
Результативность (конечность) – алгоритм всегда должен заканчиваться после выполнения конечного числа шагов, при этом должен быть получен результат или указано, что его получить невозможно.
Массовость – алгоритм решения задачи разрабатывается в общем виде так, чтобы его можно было применить для классов задач, различающихся лишь исходными данными.
Наиболее популярным способом описания алгоритмов программ являются блок-схемы.
Блок-схема – это набор простейших геометрических фигур, соединённых в определённой логической последовательности.
Блок-схемы отличаются наглядностью, они унифицированы и имеют соответствующий стандарт доступный широкому кругу специалистов, занимающихся переработкой данных. При составлении схем следует придерживаться правил, установленных ГОСТ 19.701-90 «Схемы алгоритмов, программ данных и систем. Условные обозначения и правила выполнения».
Схемы программ состоят из:
1) символов данных, отображающих неопределённые данные;
2) символов процесса, указывающих фактические операции обработки данных;
3) линейных символов, указывающих поток управления;
4) специальных символов, используемых для облегчения написания и чтения схемы.
Таблица 3.1 – Условные обозначения символов, используемых при составлении схем программ
| Наименование | Обозначение | Функция | |
| Символы данных: | |||
| Данные | Символ отображает данные, носитель данных не определён | ||
| Символы процесса: | |||
| Процесс | Отображает функцию обработки данных любого вида (выполнение определённой операции или группы операций, приводящее к изменению значения, формы или размещения информации или к определению, по какому из нескольких направлений потока следует двигаться) | ||
Продолжение таблицы 3.1
| Решение | Отображает решение или функцию переключательного типа, имеющую один вход и ряд альтернативных выходов, один и только один из которых может быть активизирован после вычисления условий, определённых внутри этого символа. Соответствующие результаты вычисления могут быть записаны по соседству с линиями, отображающими эти пути | ||
| Символы линий: | |||
| Линия | Отображает поток данных или управления. При необходимости или для повышения удобочитаемости могут быть добавлены стрелки-указатели | ||
| Пунктирная линия | Символ отображает альтернативную связь между двумя или более символами. Кроме того, символ используют для обведения аннотированного участка | ||
| Специальные символы: | |||
| Соединитель | Отображает выход в часть схемы и выход из другой части этой схемы и используется для обрыва линии и продолжении её в другом месте. Соответствующие символы-соединители должны содержать одно и то же уникальное обозначение | ||
| Терминатор | Отображает вход во внешнюю среду и выход из внешней среды (начало или конец схемы программы, внешнее использование и источник или пункт назначения данных) | ||
| Комментарий | Используется для добавления описательных комментариев или пояснительных записей в целях объяснения или примечаний | ||
При графическом представлении алгоритма с помощью схемы каждый пункт алгоритма отображается на схеме некоторой геометрической фигурой (блоком) и дополняется элементом словесного описания. Блоки в схемах соединяются между собой линиями потока. Основное направление (стандартное) потока информации идёт сверху вниз и слева направо. В случаях, когда нужно внести большую ясность в схему, на линиях указывают стрелки. Если поток имеет направление отличное от стандартного, стрелки должны указывать это направление.
В схемах следует избегать пересечения линий, и они должны быть направлены к центру символа. При необходимости линии потока в схемах следует прерывать для избежания пересечений или втех случаях, когда схема представлена на нескольких страницах.
Базовые типы вычислительных процессов.
Под вычислительным процессом следует понимать конечную последовательность действий, выполняемых в строго определённом порядке над его компонентами с целью получения некоторого результата. Любой вычислительный процесс имеет начало (точку входа) и хотя бы одну точку выхода (конец), а также, в общем случае, должен содержать действия, обеспечивающие продвижение (шаг процесса).
По характеру выполнения вычислений выделяют три основных типа вычислительных процессов:
− линейные,
− разветвляющиеся,
− циклические.
1 Линейный вычислительный процесс (следование) – процесс, где действия выполняются последовательно друг за другом.
| начало |
| Ввод данных |
| Присвоение |
| Вычисление |
| Вывод результатов |
| Останов |
2 Разветвление (разветвление вычислительных процессов) – это вычислительный процесс, в результате реализации которого в зависимости от истинности (ложности) условия, необходимо выполнить вполне определенные последовательности действия (ветви условия).
Разветвление Обход
| Усл. |
| начало |
| Ввод данных |
| Вычисл. |
| Вычисл. |
| Вывод результата |
| Останов |
| Усл. |
| начало |
| Ввод данных |
| Вычисл. |
| Вывод результата |
| Останов |
| Нет |
| Да |
Обход – частный случай разветвления, когда в вычислительном процессе одна из ветвей условия не содержит никаких действий.
3 Циклический вычислительный процесс - это процесс, в котором необходимо многократно повторить какие-либо действия (действие).
В циклическом вычислительном процессе выделяют следующие составные части:
− действие или группа действий, задающих начальное значение для выполнения цикла;
− действия или группа действий, которые необходимо многократно повторять (тело цикла);
− действия или группа действий, осуществляющая процесс управления циклом или определяющая, нужно ли повторять цикл ещё раз или необходимо закончить его (счётчик цикла).
В базовой структуре циклического типа выделяют два вида:
В цикле «ДО» проверка условия выхода из цикла выполняется после того, как выполнено тело цикла, то есть цикл «До» выполняется хотя бы 1раз.
В цикле «ПОКА» проверка условия выхода из цикла осуществляется до того, как выполнено тело цикла, то есть если при первой проверке условие выхода из цикла выполняется, то тело цикла не выполняется ни разу.
Взаимодействие базовых структур вычислительных процессов
В практике решения задач используются различные сочетания базовых структур вычислительных процессов, а также их возможные комбинации. Выбор последовательности использования тех или иных структур вычислительных процессов обусловлен характером решаемой задачи, степенью её сложности, профессиональной подготовленностью специалиста и т. д.
Цикл «ДО» Цикл «ПОКА»
| Начало |
| Ввод данных |
| Усл. |
| Вывод рез. |
| Останов |
| Да |
| Нет |
| Да |
| Нет |
| Начало |
| Ввод данных |
| Вывод рез. |
| Останов |
| Нет |
| Да |
| Да |
| Нет |
| Усл. |