1.7. Обработка информации

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

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

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

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

1) правильность - алгоритм решения задачи должен давать верные результаты, иными словами, результаты, отвечающие постановке задачи и используемым исходным данным;

2) параметризуемость - одним алгоритмом можно решать задачи, отличающиеся различными исходными данными, задаваемыми как параметры;

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

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

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

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

Рис. 1.21. Абстрактная машина

Абстрактная машина должна не только правильно распознать последовательность инструкций в алгоритме по его записи на языке пользователя с помощью интерфейса, но и выполнить их, чтобы получить результат. Другими словами, АМ функционально можно разделить на две части: одна (интерпретатор) должна "понять", что нужно сделать, а другая (исполнитель) - сделать это. При этом язык действий (команд), которые способен выполнить исполнитель, может не совпадать с языком пользователя, а перечень действий отличаться от инструкций, входящих в записи алгоритма на языке пользователя. Поэтому функцией интерпретатора является обеспечение интерфейса с пользователем, прием алгоритма и исходных данных и их перевод с языка пользователя на язык команд исполнителя, а также перевод результата выполнения алгоритма исполнителем на язык пользователя (рис. 1.21). Таким образом, исполнитель, входящий в состав АМ, является, в свою очередь, вложенной в нее абстрактной машиной , а интерпретатор АМ является пользователем. Вложенность абстрактных машин можно продолжить до тех пор, пока язык пользователя абстрактной машины(i=1, 2, 3,+) не совпадет с языком ее исполнителя (рис. 1.22).

Рис. 1.22. Вложенные абстрактные машины

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

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

Рис. 1.23. Взаимодействие пользователя с абстрактной машиной в диалоговом режиме

Каждое такое событие связывается с состоянием (например, состояние 1 на рис. 1.23), в котором находится пользователь в ходе диалога, и выбираемой им командой (на рис. 1.23 это команда 1) на исполнение абстрактной машиной некоторого алгоритма, оперирующего с исходными данными (ИД1), введенными пользователем или хранящимися в АМ. Поскольку диалоговый режим подразумевает возможность выбора пользователем определенной команды (события) из множества возможных в данном состоянии, интерпретация АМ происшедшего начинается с проверки, какое именно событие произошло, т.е. какой алгоритм необходимо исполнить. Для каждого конкретного состояния любое возможное в нем событие интерпретируется абстрактной машиной как выполнение одного из возможных для данного состояния условий (на рис. 1.23 это условие 1), сигнализирующего о том, что произошло именно это событие и необходимо исполнить соответствующий ему алгоритм (алгоритм 1 на рис. 1.23). Результат исполнения алгоритма (результат 1 на рис. 1.23) предъявляется пользователю, при этом изменяется состояние, в котором он находится (состояние 2 на рис. 1.23). Далее происходит новое событие (на рис. 1.23 это выбор пользователем команды 4), которое вновь интерпретируется АМ с исполнением уже другого алгоритма (алгоритма 4 на рис. 1.23). После чего пользователь оказывается в новом состоянии (состояние 3 на рис. 1.23) и так далее.

Для обобщенного описания возможностей, имеющихся при диалоге пользователя с АМ, используются диаграммы перехода состояний (рис. 1.24). На диаграмме располагается конечное число прямоугольников, соответствующих всем возможным состояниям процесса диалога, одно из которых (на рис. 1.24 - это состояние 1) является начальным. Все возможные в данном состоянии команды (условия), по которым осуществляется исполнение того или иного алгоритма, обозначаются на диаграмме стрелками, выходящими из соответствующего прямоугольника и ведущими в прямоугольник, обозначающий состояние, в которое осуществляется переход после исполнения алгоритма. Около стрелки размещают две надписи. Верхняя указывает условие, при выполнении которого должен быть исполнен алгоритм, обозначенный в нижней надписи.

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

Алгоритмы, которые должны быть исполнены АМ, необходимо описать на интерпретируемом ею языке. Для современных персональных компьютеров - это языки визуального программирования, примером которых является Visual Basic ⁴. Однако прежде чем писать программу на алгоритмическом языке рекомендуется представить алгоритм в более привычной для человека форме.

Рис. 1.24. Пример диаграммы перехода состояний

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

1) базовые конструкции структурного программирования (БКСП);

2) конструкции, полученные из БКСП или другой (исходной) ДКСП путем допустимых преобразований.

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

К основным БКСП относят конструкции "следование", "ветвление", "цикл-пока".

К дополнительным БКСП относят "выбор" и "цикл-до".

На рис. 1.25 приведены графическое и вербальное описания конструкции "следование", заключающейся в последовательном выполнении сначала подпроцесса a, а затем подпроцесса b.

Рис. 1.25. Следование Рис. 1.26. Пример использования конструкции "следование"

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

В качестве примера рассмотрим запись алгоритма (рис. 1.26), согласно которому переменной x сначала присваивается значение, равное значению переменной y, а затем значение переменной x увеличивается в два раза и к нему прибавляется единица.

Отметим непривычное, но характерное для программирования использование знака "=" не для обозначения равенства левой и правой части выражения, а для обозначения операции присваивания переменной (стоящей в левой части) значения некоторой формулы, стоящей в правой части. Если, например, перед началом выполнения рассматриваемого алгоритма значения переменной y было равно 4, то в ходе выполнения алгоритма значение переменной x станет равным сначала 4, а потом 9.

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

Выполнение конструкции "ветвление" (рис. 1.27) начинается с проверки условия, задаваемого логическим выражением L; если оно истинно (равно 1), то выполняется подпроцесс a, в противном случае, т.е. при L = 0, выполняется подпроцесс b. Существенной чертой конструкции "ветвление" является слияние обеих ветвей, т. е. независимо от того, подпроцесс какой именно из ветвей был выполнен, следующей будет выполняться одна и та же конструкция.

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

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

Рис. 1.27. Ветвление

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

Выполнение повторяющихся (циклических) действий можно организовать с помощью базовой конструкции "цикл-пока" (рис. 1.29). Ее выполнение начинается с проверки логического выражения (условия) L. Если оно истинно (равно 1), то выполняется подпроцесс а. Для того чтобы повторная проверка имела смысл, в ходе выполнения подпроцесса а должны изменяться значения переменных, используемых в логическом выражении L. Начальные значения этим переменным, называемым переменными цикла, должны быть присвоены до выполнения конструкции "цикл-пока". Как только условие L перестает выполняться (т. е., став ложным, примет значение равное 0), осуществляется выход из конструкции. Подпроцесс а называется телом цикла. Так же как и в других БКСП, тело цикла записывается со сдвигом вправо относительно его обрамления.

#S

Рис. 1.28. Пример использования конструкции "ветвление"

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

Рис. 1.29. Конструкция "цикл-пока"

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

Примером допустимого преобразования может служить получение ДКСП, представленной на рис. 30. Она получена из БКСП "следование" (рис. 1.25) подстановкой БКСП "цикл-пока" (рис. 1.29) вместо второго подпроцесса.

Представленный на рис. 30 алгоритм является примером использования конструкции "цикл-пока" для вычисления суммы первых 100 натуральных чисел. Этот алгоритм находит значение переменной

s=1+2+3+4+...+100 .

При первой проверке условия цикла, когда n = 1, оно выполняется: выражение 1<101 истинно. К нулевому значению суммы s прибавляется единица и она становится равной тоже единице. Затем модифицируется переменная цикла n, она увеличивается на единицу и становится равной двум. Условие n<101 снова проверяется и так как оно справедливо, мы вновь выполняем тело цикла: к сумме s прибавляется n, которое равно двум, а n возрастает еще на единицу, становясь равным трем. Циклическое добавление натуральных чисел к сумме будет продолжаться до тех пор, пока мы не добавим к ней n = 100. Сразу после этого, до выхода из тела цикла, n увеличивается еще на единицу и становится равным 101. Перейдя к проверке условия цикла, мы увидим, что оно перестало выполняться, действительно, выражение 101<101 является ложным, т. е. равно 0. Следовательно, мы выходим из цикла, причем значение переменной s равно искомой сумме первых 100 натуральных чисел.

Рис. 1.30. Пример использования конструкции "цикл-пока"

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

ВЫБОР по n

ЕСЛИ n = 1 ТО a

ЕСЛИ n = 2 ТО b

ЕСЛИ n = 3 ТО c

ИНАЧЕ d

ВСЕ-ВЫБОР

Рис. 1.31. Конструкция "выбор"

Второй дополнительной БКСП является конструкция "цикл-до" (рис. 1.32). В отличие от конструкции "цикл-пока" ее выполнение начинается не с проверки условия L, а сразу с выполнения подпроцесса а. Только после его выполнения, а, следовательно, и модификации переменных цикла проверяется значение логического выражения L. Вторым отличием от конструкции "цикл-пока" является то, что циклическое повторение подпроцесса а осуществляется до того, как выполнится условие L, а не пока оно выполняется. Другими словами, выход из "цикл-до" происходит при условии, что логическое выражение L истинно, то есть равно 1. Если же условие L не выполняется (то есть, логическое выражение принимает значение, равное 0) осуществляется повторное выполнение тела цикла. Алгоритм вычисления суммы первых 100 натуральных чисел с использованием конструкции "цикл-до" приведен на рис. 1.33. Отметим, что по сравнению с алгоритмом, изображенным на рис. 1.30, логическое выражение изменилось на противоположное.

Рис. 1.32. Конструкция "цикл-до"

Рис. 1.33. Пример использования конструкции "цикл-до"