Регеда В.В., Регеда О.Н. Основы алгоритмизации

Подождите немного. Документ загружается.

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

высшего профессионального образования

«Пензенский государственный университет»

Основы алгоритмизации

Методические указания

по курсу «Информатика»

Пенза

Издательство

Пензенского государственного

университета

2008

УДК 621.3 (075)

О-75

Содержится краткий теоретический материал по основам алго-

ритмизации. Рассмотрены виды алгоритмических процессов, а также

основные правила выполнения схем алгоритмов по ГОСТ 19.701−90.

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

Методические указания подготовлены на кафедре «Электротех-

ника и транспортное электрооборудование» и предназначены для

студентов специальностей 140607 «Электрооборудование автомоби-

лей и тракторов», 190201 «Автомобиле- и тракторостроение», 100101

«Сервис автомобильной электроники», изучающих курс «Информа-

тика».

С о с т а в и т е л и: В. В. Регеда, О. Н. Регеда

Р е ц е н з е н т С. Б. Кутыркин, кандидат технических наук,

директор фирмы «Пензасертинг».

Введение

Многие задачи, предназначенные для решения на ЭВМ, преду-

сматривают разработку алгоритма их реализации.

Алгоритм – это точное предписание, которое определяет процесс,

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

Можно дать и другие определения алгоритма:

1) это описание последовательности действий для решения задачи

или достижения поставленной цели;

2) это правила выполнения основных операций обработки дан-

ных;

3) это описание вычислений по математическим формулам.

Алгоритмами, например, являются правила сложения, умножения,

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

«алгоритм» происходит от algoritmi, являющегося латинской транс-

литерацией арабского имени хорезмийского математика IX века аль-

Хорезми. Благодаря латинскому переводу трактата аль-Хорезми ев-

ропейцы в XII веке познакомились с позиционной системой счисле-

ния, и в средневековой Европе алгоритмом стали называть десятич-

ную позиционную систему счисления и правила счета в ней.

Применительно к ЭВМ алгоритм определяет вычислительный

процесс, начинающийся с обработки некоторой совокупности воз-

можных исходных данных и направленный на получение определен-

ных этими исходными данными результатов. Термин «вычислитель-

ный процесс» распространяется и на обработку других видов инфор-

мации, например, символьной, графической или звуковой.

Если вычислительный процесс заканчивается получением резуль-

татов, то говорят, что соответствующий алгоритм применим к рас-

сматриваемой совокупности исходных данных. В противном случае

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

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

ми свойствами:

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

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

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

Результативность означает возможность получения результата

после выполнения конечного количества операций.

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

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

Массовость заключается в возможности применения алгоритма к

целому классу однотипных задач, различающихся конкретными зна-

чениями исходных данных.

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

менты:

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

ходных данных, промежуточных и конечных результатов;

• правило начала;

• правило непосредственной переработки информации (описа-

ние последовательности действий);

• правило окончания;

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

Алгоритм всегда рассчитан на конкретного исполнителя. В нашем

случае таким исполнителем является ЭВМ. Для обеспечения воз-

можности реализации на ЭВМ алгоритм должен быть описан на язы-

ке, понятном компьютеру, т. е. на языке программирования.

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

программа для ЭВМ представляет собой описание алгоритма и дан-

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

последующего автоматического выполнения.

1. Общие положения

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

На практике наиболее распространены следующие формы пред-

ставления алгоритмов:

• словесно-формульная

(записи на естественном языке);

• графическая, или схемная

(изображения с помощью графичес-

ких символов);

• с помощью псевдокодов

(полуформализованные описания ал-

горитмов на условном алгоритмическом языке, включающие в себя

как элементы языка программирования, так и фразы естественного

языка, общепринятые математические обозначения и др.);

• программная

(тексты на языках программирования).

Перед составлением программ чаще всего используются словес-

но-формульный и схемный способы. Иногда перед составлением

программ на низкоуровневых языках программирования типа языка

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

циями некоторого высокоуровневого языка программирования.

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

вать наряду с программным для сложных программных систем.

Словесный способ записи алгоритмов представляет собой после-

довательное описание этапов обработки данных. Алгоритм задается

в произвольном изложении на естественном языке.

Например, словесный алгоритм определения четности числа n

может быть следующим:

1) задать число n;

2) разделить − число n на два;

3) если остаток от деления равен нулю, то число n – четное, в

ином случае число нечетное.

Описанный алгоритм применим к любым натуральным числам и

должен приводить к решению поставленной задачи.

Словесный способ не имеет широкого распространения, так как по-

добные описания строго не формализуемы, страдают многословностью

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

При схемном описании алгоритм изображается отдельными гео-

метрическими фигурами (символами), связанными между собой с

помощью линий потоков с однозначно заданным направлением со

стрелками. Внутри символов записывается выполняемая ими после-

довательность действий.

Данный способ по сравнению с другими способами записи алго-

ритма имеет ряд преимуществ. Он наиболее нагляден: каждая опера-

ция вычислительного процесса изображается отдельной геометриче-

ской фигурой. Кроме того, графическое изображение алгоритма на-

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

сти от различных условий, повторение отдельных этапов вычисли-

тельного процесса и другие детали.

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

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

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

используются некоторые формальные конструкции и математическая

символика, что приближает запись алгоритма к общепринятой матема-

тической записи. В псевдокоде не приняты строгие синтаксические пра-

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

запись алгоритма на стадии его проектирования и дает возможность

использовать более широкий набор команд, рассчитанный на абстракт-

ного исполнителя. Однако в псевдокоде обычно имеются некоторые

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

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

1.2. Основные правила выполнения схем

алгоритма

Схемой алгоритма называют его графическое представление –

последовательность связанных между собой функциональных бло-

ков, каждый из которых соответствует выполнению одного или не-

скольких действий.

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

данных, вычислению значений выражений, проверке условий, управ-

лению повторением действий, окончанию обработки и т. п.) соответ-

ствует геометрическая фигура, представленная в виде символа. Сим-

волы соединяются линиями потоков данных или управления, опре-

деляющими очередность выполнения действий.

Правила выполнения схем алгоритмов устанавливаются в дейст-

вующем ГОСТ 19.701–90 Схемы алгоритмов, программ данных и сис-

тем. Они строятся из имеющих заданное значение символов, краткого

пояснительного текста и соединительных линий. Схемы алгоритмов

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

уровней зависит от размеров и сложности задачи обработки данных.

В ГОСТ 19.701–90 определены символы, предназначенные для

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

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

дующих случаях:

– схемах данных;

– схемах программ;

– схемах работы системы;

– схемах взаимодействия программ;

– схемах ресурсов системы.

В стандарте используются следующие понятия:

1) основной символ – символ, используемый в тех случаях, когда

точный тип (вид) процесса или носителя данных не известен или от-

сутствует необходимость в описании фактического носителя;

2) специфический символ – символ, используемый в тех случаях,

когда известен точный тип (вид) процесса или носителя данных или

когда необходимо описать фактический носитель данных;

3) схема – графическое представление определения, анализа или

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

бражения операций, данных, потока, оборудования и т. д.

Схема данных отображает путь данных при решении задач и оп-

ределяет этапы обработки, а также различные применяемые носите-

ли данных. Она состоит из символов данных; символов процесса,

который следует осуществить над данными; символов линий, ото-

бражающих потоки данных между процессами; (или) носителями

данных и специальных символов, используемых для облегчения на-

писания и чтения схемы.

Схема программы отображает последовательность операций в

программе. Она состоит из символов процесса, указывающих факти-

ческие операции обработки данных; линейных символов, отобра-

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

для облегчения написания и чтения схемы.

Схема работы системы отображает управление операциями и по-

ток данных в системе. Она состоит из символов данных, указывающих

на наличие данных; символов процесса, указывающих операции, ко-

торые следует выполнить над данными; линейных символов, отобра-

жающих потоки данных между процессами и (или) носителями дан-

ных, а также поток управления между процессами; специальных сим-

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

Схема взаимодействия программ отображает путь активаций про-

грамм и взаимодействий с соответствующими данными. Каждая про-

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

раз (в схеме работы системы программа может изображаться более

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

указывающих на наличие данных; символов процесса, указывающих

на операции, которые следует выполнить над данными; линейных

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

также инициации процессов; специальных символов, используемых

для облегчения написания и чтения схемы.

Схема ресурсов системы отображает конфигурацию блоков дан-

ных и обрабатывающих блоков, которая требуется для решения зада-

чи или набора задач. Она состоит из символов данных, отображаю-

щих входные, выходные и запоминающие устройства вычислитель-

ной машины; символов процесса, отображающих процессоры; ли-

нейных символов, отображающих передачу данных между устройст-

вами ввода-вывода и процессорами, а также передачу управления

между процессорами; специальных символов, используемых для об-

легчения написания и чтения схемы.

1.3. Основные символы, применяемые в схемах

алгоритмов

Операции обработки данных и носители информации изобража-

ются на схеме соответствующими символами.

В ГОСТ 19.701–90 даются рекомендуемые формы символов и

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

влияющие на соответствующую форму символов. Символы должны

быть, по возможности, одного размера.

В старом ГОСТ 19002 дополнительно устанавливались габариты

символов. Большая часть символов по построению условно вписана в

прямоугольник со сторонами а и b. Минимальное значение а = 10 мм,

увеличение а производится на число, кратное 5 мм. Размер b = 1,5a. Для

отдельных блоков допускается соотношение между а и b, равное 1 : 2.

В табл. 1.1 приведены основные символы данных, используемые

на схемах алгоритма.

Таблица 1.1

Название

символа

Обозначение Пояснение

Данные

Символ отображает данные; носитель дан-

ных не определен

Запоминаемые

данные

Символ отображает хранимые данные в

виде, пригодном для обработки; носитель

данных не определен

Оперативное

запоминающее

устройство

Символ отображает данные, хранящиеся в

оперативном запоминающем устройстве

Запоминающее

устройство с

прямым досту-

пом

Символ отображает данные, хранящиеся в

запоминающем устройстве с прямым дос-

тупом (магнитный диск, гибкий магнит-

ный диск и т. п.)

Документ

Символ отображает данные, представлен-

ные на носителе в удобочитаемой форме

(распечатка принтера, документ для опти-

ческого или магнитного считывания и т. п.)

Ручной ввод

Символ отображает данные, вводимые

вручную во время обработки с устройств

любого типа (клавиатура, переключатели,

кнопки, световое перо и т. п.)

Дисплей

Символ отображает данные, представлен-

ные в удобочитаемой форме на носителе в

виде отображающего устройства (экран

для визуального наблюдения, индикаторы

ввода информации и т. п.)

В табл. 1.2 приведены символы процессов, используемые на схе-

мах алгоритма.

Таблица 1.2

Название сим-

вола

Обозначение Пояснение

Процесс

Символ отображает функцию обработки данных

любого вида (выполнение определенной опера-

ции или группы операций, приводящее к изме-

нению значения, формы или размещения ин-

формации)

Предопреде-

ленный

процесс

Символ отображает предопределенный процесс,

состоящий из одной или нескольких операций

(шагов) программы, которые определены в под-

программе, модуле и т. п.

Ручная

операция

Символ отображает любой процесс, выполняе-

мый человеком

Подготовка

Символ отображает модификацию команды

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

щую функцию (установка переключателя, моди-

фикация индексного регистра или инициализа-

ция программы)

Решение

Символ отображает решение или функцию пере-

ключательного типа, имеющую один вход и ряд

альтернативных выходов, один и только один из

которых может быть активизирован после вы-

числения условий, определенных внутри этого

символа

Параллельные

действия

_____________

Символ отображает синхронизацию двух или

более параллельных операций

Граница

цикла

Символ, состоящий из двух частей, отображает

начало и конец цикла. Обе части символа имеют

один и тот же идентификатор