Глоссарий. Тема № 1. Основные понятия алгоритмизации

Тема № 1. Основные понятия алгоритмизации. Алгоритмы и способы их описания.

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

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

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

Любой алгоритм обладает следующими основными свойствами:

- дискретностью;

- определенностью;

- результативностью;

- массовостью.

Дискретность – последовательное выполнение простых или ранее определённых (подпрограммы) шагов.

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

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

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

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

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

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

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

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

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

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

Наименование	Обозначение	Функции
Процесс		Выполнение операции или группы операции, в результате которых изменяется значение, форма представления или расположение данных.
Ввод-вывод		Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод).
Решение		Выбор направления выполнения алгоритма в зависимости от некоторых переменных условии.
Предопределенный процесс		Использование ранее созданных и отдельно написанных программ (подпрограмм).
Документ		Вывод данных на бумажный носитель.
Магнитный диск		Ввод-вывод данных, носителем которых служит магнитный диск.
Пуск-останов		Начало, конец, прерывание процесса обработки данных.
Соединитель		Указание связи между прерванными линиями, соединяющими блоки.
Межстраничный соединитель		Указание связи между прерванными линиями, соединяющими блоки, расположенные на разных листах.
Комментарий		Связь между элементом схемы и пояснением.

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

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

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

алгоритм <имя>

Пример: Вычислить

Записать алгоритм на алгоритмическом языке и графическим способом.

алг Вычисление Y

исх x

рез y

Начало

Ввести x

если x>0

то y=ln (x)

иначеесли x<0 и x>-5

то y=x

иначе y=cos(x)

вывод y

Конец

Блок - схема

К основным структурам алгоритмов относятся: линейные, разветвляющиеся, циклические.

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

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

Циклическим называется алгоритм, в котором некоторая часть операций выполняется многократно. Однако это не значит «до бесконечности» (иначе нарушается требование его результативности – получение результата).

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

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

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

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

Исполнитель алгоритма – объект или субъект, выполняющий некоторые команды. Для каждого исполнителя существует система команд, т.е. совокупность всех команд, которую умеет делать исполнитель.

Подходы к созданию алгоритмов и требования к ним существенно изменились в ходе эволюции ПК. В эпоху ЭВМ I и II поколения основными требованиями к алгоритму были:

- min требования к алгоритму в отношении ОЗУ ПК

- min времени использования.

Подход, ориентированный на непосредственное выполнение ПК операций, называется операционным.

Программа состоит из команд, непосредственно использующихся в процессорах:

- операция присваивания

- простые арифметические операции

- операции сравнения чисел

- использование операторов условного и безусловного перехода

- операторов вызова подпрограмм

Операции присвоения.

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

Арифметические операции.

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

Операции сравнения.

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

Условный и безусловный переходы.

Безусловным - называется переход, для которого применение порядка выполнения команд определяет назначение и не всегда, и не зависит от условий.

Условным – называется переход, порядок выполнения команд для которого определяется некоторым условием (чаще по условию сравнения величин).

Операции вызова подпрограмм.

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

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

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

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

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

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

3. конструкция принятия двоичного решения. Применяется для представления разветвляющихся алгоритмов. Описывается языком графических символов следующим образом:

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

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

Структурный подход позволяет сделать большой запас ПО, который постоянно пополняется. Появилось много языков программирования, которые являются как процедурно ориентированными, так и объектно-ориентированными (Pascal, QB, Fortran – процедурные языки).

В объектно-ориентированном подходе исходная задача представлена как совокупность взаимодействующих объектов. Объекты в перпендикулярном приближении похожи на процедуры внутри программы. Каждый объект ведет себя независимо. К объектно-ориентированным языкам относятся Visual C++, VB. Существуют так же логические языки LISP и PROLOG.

Глоссарий

Дискретность – последовательное выполнение простых или ранее определённых (подпрограммы) шагов.

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

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

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

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

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

Вопросы для самопроверки:

1. Что такое алгоритм? Перечислите основные свойства алгоритма.

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

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

4. Охарактеризуйте структурный подход к созданию алгоритмов.

5. Перечислите основные структуры алгоритмов.

6. Что такое система команд исполнителя?

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями: