Моделирование процедурной информации. Понятие алгоритма

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

Модель процедурной информации в информатике называют алгоритмом. Слово алгоритм происходит от имени выдающегося средневекового математика IX в. Абу Джафара ибн Мусы аль‑Хорезми, который, в частности, изложил правила выполнения арифметических операций над числами. В трудах европейских ученых, изучавших арабскую (десятичную) систему счисления, с течением времени "аль‑Хорезм" трансформировался в алгорифм, а затем в алгоритм. Термин "алгоритм" использовался ранее для обозначения последовательности операций над числами.

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

· дискретность – представление алгоритма в виде упорядоченного множества шагов (действий, операций);

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

В процессе выполнения алгоритма осуществляется модификация значений атрибутов соответствующей фактографической модели (преобразование данных). Данные в алгоритме делятся на начальные (исходные), которые известны до начала работы алгоритма, и результаты. Кроме этих видов данных, в алгоритме могут использоваться и данные, создаваемые в процессе работы алгоритма как промежуточные результаты (промежуточные данные). Например, в алгоритме сложения N чисел результаты сложения k < N чисел будут промежуточными.

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

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

Блок-схема

При записи алгоритмов в виде блок-схем действия (операции) изображаются графическими символами. Существует разработанная система графических символов для обозначения наиболее общего набора действий (ПРИЛОЖЕНИЕ 1).

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

1) если передача управления идет справа налево или снизу вверх, то конец линии заканчивается стрелкой;

2) если передача управления идет сверху вниз или слева направо, то конец линии может не заканчиваться стрелкой;

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

В блок-схеме структура алгоритма выражается комбинацией трёх базовых структур: следование, развилка, цикл (повторение).

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

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

Структура "Развилка" обеспечивает выбор одной из двух возможных альтернатив передачи управления в алгоритме. В этой структуре вначале проверяется истинность некоторого высказывания, а затем, в зависимости от результата проверки (ложь или истина), управление передается на выполнение одного из двух альтернативных действий (Рис. 6, а)). Для краткости для обозначения результата проверки высказывания вместо слов "ложь" и "истина" могут использоваться обозначения "0", "1" или "-", "+".

Эта структура называется также "ЕСЛИ-ТО-ИНАЧЕ" и может быть прочитана следующим образом: "Если высказывание истинно, то выполнить действие А, иначе (т.е. если высказывание ложно) выполнить действие Б".

а)

б)

Рис. 6. Структура "Развилка"

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

Иногда, при реализации структуры "Развилка", одна из альтернатив может быть пустой, т.е. не требовать каких-либо действий. В этом случае пустая альтернатива может быть опущена (Рис. 6, б)).

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

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

Структура "Повторение" выполняется до тех пор, пока высказывание истинно. Как только высказывание становится ложным, происходит передача управления на выход из структуры. Так как истинность высказывания проверяется перед выполнением действия А, то вполне возможно, что в том случае, когда высказывание будет ложным с самого начала, цикл не выполнится ни одного раза. Блок, в котором записано высказывание, называют заголовком цикла, а действие А – телом цикла. Тело цикла должно содержать действие, влияющее на истинность высказывания. Это необходимо для того, чтобы цикл когда-то мог быть закончен.

а)

б)

Рис. 7. Структура "Повторение"

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

то в наиболее общем виде любой алгоритм может быть представлен как:

Справедливо и обратное: любой блок (модуль) алгоритма может быть развёрнут в виде последовательности базовых структур:

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

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

На Рис. 8 приведен пример блок-схемы упрощенного алгоритма действий пешехода, переходящего улицу на пешеходном переходе, управляемом светофором.

Рис. 8 Блок-схема алгоритма перехода улицы

На Рис. 9 приведен пример блок-схемы алгоритма нахождения действительных корней квадратного уравнения aX² + bX + c = 0. Значения коэффициентов a, b, c вводятся как исходные данные, соответствующие решаемому квадратному уравнению. Известно, что наличие действительных корней зависит от значения дискриминанта D, которое должно быть больше или равно 0. В противном случае корни будут комплексными. Поэтому необходимо вычислить дискриминант и затем проверить выполнение условия не отрицательности дискриминанта. Если условие выполняется, то алгоритм продолжается по ветке, где вычисляются известные формулы нахождения действительных корней квадратного уравнения. В результате будут получены и выведены значения обоих корней X₁ и X₂. В противном случае сообщается, что корни мнимые.

Рис. 9. Блок-схема алгоритма решения квадратного уравнения

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

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

Псевдокод

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

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

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

1. Вместо графического обозначения процесса (действия, операции) используют текстовую конструкцию вида <Фраза естественного языка, обозначающая действие>. Например, <Ввод исходных данных>, <Ждать зеленый свет светофора>, <Вычислить S=S+X> и т.п.

2. Структура "Следование" в псевдокоде выражается последовательностью фраз, записанных в отдельной строке. Например:

<Ввести данные а, в, с>

<Вычислить дискриминант D=b²-4ac>

3. Структура "Развилка" реализуется на псевдокоде с помощью ключевых слов в виде:

ЕСЛИ <Высказывание> ТО

<Выполнить А>

ИНАЧЕ

<Выполнить Б>

ВСЕ_ЕСЛИ

Действие А будет выполнено в случае истинности высказывания, записанного между ключевыми словами ЕСЛИ и ТО, а действие Б в этом случае будет пропущено. И наоборот, если высказывание ложно, то пропускается действие А и выполняется действие Б. Ключевое слово ВСЕ_ЕСЛИ обозначает конец структуры "Развилка". После выполнения этой структуры управление передается на запись, непосредственно следующую за ключевым словом ВСЕ_ЕСЛИ. В псевдокоде допускается запись структуры развилки и с одной альтернативой:

ЕСЛИ <Высказывание> ТО

<Выполнить А>

ВСЕ_ЕСЛИ

4. Структура "Повторение" (цикл) организуется в виде:

ЦИКЛ <Высказывание>

<Выполнить А>

ВСЕ_ ЦИКЛ

При входе в цикл проверяется истинность высказывания. Действие А выполняется тогда и повторяется до тех пор, пока высказывание истинно. Если высказывание оказывается ложным, цикл сразу завершается, а управление передается на запись, непосредственно следующую за ключевым словом ВСЕ_ЦИКЛ. Запись <Выполнить А> называют телом цикла. Если в тело цикла входит запись, также являющаяся в свою очередь циклом, то допускается для большей наглядности алгоритма помечать ключевые слова этих структур своими индексами. Например:

ЦИКЛ1 <Для всех i от 1 до М с шагом 1>

<S=0>

ЦИКЛ2 <Для всех j от 1 до N с шагом 1>

<S= S+X_i,j>

ВСЕ_ ЦИКЛ2

<Печать S>

ВСЕ_ ЦИКЛ1

Индексация ключевых слов допускается и для структуры "Развилка", если одна развилка входит в состав другой развилки.

5. Для обозначения операции ввода данных используется ключевое слово ВВЕСТИ, а для операции вывода - ВЫВЕСТИ. За этими ключевыми словами в круглых скобках записываются списки имен атрибутов, получающих вводимые значения или значения которых выводятся в качестве результатов. В списке вывода, кроме того, могут указываться выражения, значения которых необходимо вывести в качестве результатов.

6. Каждому алгоритму присваивается имя, которое записывается в начале псевдокода алгоритма (в заголовке) после ключевого слова АЛГОРИТМ. В конце, завершая псевдокод алгоритма, ставится ключевое слово ВСЕ_АЛГОРИТМ. Например:

АЛГОРИТМ Нахождение_корней_квадратного_уравнения

…

ВСЕ_АЛГОРИТМ

7. Алгоритм может быть оформлен в виде вызываемой процедуры (подалгоритма). В этом случае после имени алгоритма в круглых скобках записывается список имен формальных параметров алгоритма. Например, АЛГОРИТМ Функция1(А, В, С). При вызове такого алгоритма для выполнения указывается его имя, а в скобках имена формальных параметров заменяются именами соответствующих фактических атрибутов, значения которых используются при выполнении как исходные данные, или которым будут присвоены результаты работы алгоритма. Между формальными и фактическими атрибутами должно обеспечиваться взаимно однозначное соответствие.

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

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

1) Пример алгоритма перехода улицы:

АЛГОРИТМ Переход_улицы

ЦИКЛ <Горит не зеленый свет светофора>

<Стоять>

ВСЕ_ ЦИКЛ

<Перейти улицу>

ВСЕ_АЛГОРИТМ

2) Пример алгоритма (процедуры) решения квадратного уравнения:

АЛГОРИТМ Решение_квадратного_уравнения(а, b, с, D, Х1, Х2)

<D=b²-4ac>

ЕСЛИ < D³0> ТО

<Х1= (-b+ÖD)/2a>

<Х2= (-b-ÖD)/2a>

ИНАЧЕ

ВЫВЕСТИ("Корни мнимые")

ВСЕ_ЕСЛИ

ВСЕ_АЛГОРИТМ

Чтобы получить значения корней конкретного квадратного уравнения (5х²-4х+8=0) необходимо оформить алгоритм вызова процедуры решения квадратного уравнения, задав фактические значения атрибутов уравнения:

АЛГОРИТМ Решение_ уравнения

Решение_квадратного_уравнения(5, 4, 8, D, Х1, Х2)

ЕСЛИ < D³0> ТО

ВЫВЕСТИ(Х1, Х2)

ВСЕ_ЕСЛИ

ВСЕ_АЛГОРИТМ

Алгоритмический язык

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

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

Для иллюстрации приведем пример алгоритма на языке Паскаль, определяющего максимальное по абсолютному значению число из заданных 3-х чисел. Блок-схема алгоритма приведена на ….

Рис. 10 Алгоритм определения наибольшего по модулю числа

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

Program Maximum;

Var A1, A2, A3, AMAX: real;

Begin

Readln(A1, A2, A3);

A1:=Abs(A1);

A2:=Abs(A2);

A3:=Abs(A3);

If A1>=A2 Then AMAX:=A1

Else AMAX:=A2;

If A3>AMAX Then AMAX:=A3;

Writeln(‘AMAX=’,AMAX);

End.

Контрольные вопросы

1. Чем обусловлена необходимость моделирования информации?

2. Перечислите изученные средства моделирования фактографической информации.

3. Перечислите изученные средства моделирования процедурной информации.

4. Перечислите и охарактеризуйте конструктивные элементы ER‑модели.

5. Типы бинарных связей, используемых в ER‑модели.

6. Перечислите и охарактеризуйте конструктивные элементы реляционной модели.

7. В чем заключаются достоинства ER‑модели и реляционной модели?

8. В чем принципиальное отличие моделирования процедурной информации от моделирования фактографической информации?

9. Как называют модель процедурной информации и происхождение этого названия?

10. Что в широком смысле понимается под алгоритмом и его основные свойства?

11. Перечислите изученные средства разработки алгоритмов.

12. Представление базовых структур алгоритма в блок-схеме.

13. Охарактеризуйте технологию разработки алгоритма по принципу "сверху-вниз".

14. Охарактеризуйте псевдокод как средство разработки алгоритма.

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

16. Охарактеризуйте понятие процедуры (подалгоритма).

17. Отличие алгоритмического языка от псевдокода.

Кодирование информации

Данные, поступающие непосредственно от источника информации, могут быть зарегистрированы (выражены) с использованием различных знаковых систем и методов регистрации. Вид данных зависит от способа восприятия информации. Это может быть регистрация механического перемещения, формы или параметров качества поверхности, измерение электрических, магнитных, оптических характеристик, анализ химического состава или химических связей и многое другое. Например, одни данные могут характеризовать яркость свечения, другие - цвет, третьи - температуру, четвёртые - имена и т.п. В соответствии с методом регистрации данные хранятся и транспортируются на носителях различных видов. При выборе знаковой системы для представления данных учитываются свойства носителя информации, используемого для переноса информации от источника к приемнику. Различные носители информации имеют различные возможности по восприятию данных в том или ином виде. Например, бумага не может запечатлеть на себе живой звук, но она может фиксировать звуки в виде нот. А вот электрический ток может отобразить в себе звуковую информацию и даже перенести её на огромное расстояние за короткое время. Для этого необходимо только построить информационную модель звука, используя в качестве носителя электрический ток. Естественно возникает необходимость преобразования информации из формы колебания газовой среды в форму колебания электрического тока.

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

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

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

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