YourLib.net
Твоя библиотека
Главная arrow Информатика (Под общ. ред. А.Н. Данчула) arrow 1.7. Обработка информации. Алгоритмы. Объекты
1.7. Обработка информации. Алгоритмы. Объекты

1.7. Обработка информации. Алгоритмы. Объекты

   Процессы обработки информации могут быть выполнены как человеком, так и компьютером. Человек может обрабатывать как закодированную информацию, представленную в виде текста на естественном или каком-то другом специализированном языке (левополушарное мышление), так и незакодированную неформализованную информацию в виде некоторых образов (правополушарное мышление). Моделирование правополушарного мышления на компьютере является весьма сложной проблемой, относящейся к направлению искусственного интеллекта.
   Смоделировать на компьютере левополушарное мышление человека легче, так как его суть состоит в способности обрабатывать информацию, представленную в текстовом виде в соответствии со сформулированной на определенном языке и однозначно понимаемой последовательностью инструкций, называемой алгоритмом. Понятие алгоритма интуитивно ясное, но теоретически достаточно сложное. Оно сформировалось в математике лишь в 20-х годах прошлого века, а начало построения теории алгоритмов на основе различных формальных определений относят ко второй трети XX века. Дадим содержательное пояснение сути таких определений.
   Под алгоритмом будем понимать сформулированное на определенном языке точное предписание, которое задает исполнимый за конечное время процесс, начинающийся с произвольных исходных данных определенной структуры и направленный на получение полностью определенного этими исходными данными результата.
   Уточнить понятие алгоритма можно, например, задав обязательные свойства алгоритмов, т. е. требования, которым должны удовлетворять предписания, задающие интересующий нас процесс. К свойствам алгоритмов, обеспечивающим возможность их эффективного использования в практической деятельности,в том числе и при разработке реализующих их компьютерных программ, можно отнести:
   правильность — алгоритм решения задачи должен давать верные результаты, иными словами, результаты, отвечающие постановке задачи и используемым исходным данным;
   параметризуемость — одним алгоритмом можно решать задачи, отличающиеся различными исходными данными, задаваемыми как параметры;
   однозначность интерпретации — интерпретация (последовательность действий при выполнении) алгоритма при любом конкретном варианте исходных данных является вполне определенной и не зависящей от интерпретатора (программы или человека, выполняющего алгоритм);
   конечность — алгоритм решения задачи не может заключаться в выполнении сколь угодно большого числа шагов; число шагов (а следовательно, и время выполнения алгоритма) должно быть конечным.
   Для лучшего понимания сущности алгоритма введем понятие абстрактной машины как объекта, способного выполнить обработку информации в соответствии с некоторым алгоритмом. С помощью абстрактной машины (AM) можно моделировать обработку информации человеком, техническим устройством, компьютером, информационной системой. AM взаимодействует с находящимся во внешней среде пользователем AM, получая от него исходные данные (ИД) и алгоритм их обработки и выдавая ему результат обработки ИД (рис. 1.21).
   Алгоритм, исходные данные и результат обработки записываются на языке, однозначно понимаемом как пользователем AM, так и самой абстрактной машиной. Назовем этот язык языком пользователя AM. Языковые и другие средства, предоставляемые абстрактной машиной пользователю для взаимодействия с нею с целью приема от него алгоритмов и исходных данных и передачи ему результатов, назовем интерфейсом AM.
   Абстрактная машина должна не только правильно распознать последовательность инструкций в алгоритме по его записи на языке пользователя с помощью интерфейса, но и выполнить их, чтобы получить результат. Другими словами, AM функционально можно разделить на две части: одна (интерпретатор) должна «понять», что нужно сделать, а другая (исполнитель) — сделать это. При этом язык действий (команд), которые способен выполнить исполнитель, может не совпадать с языком пользователя,

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

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

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

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

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

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

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

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

(на рис. 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) является начальным. Все возможные в данном состоянии команды (условия), по которым осуществляется исполнение того или иного алгоритма, обозначаются на диаграмме стрелками, выходящими из соответствующего прямоугольника и ведущими в прямоугольник, обозначающий состояние, в которое осуществляется переход после исполнения алгоритма. Около стрелки размещают две надписи. Верхняя указывает условие, при выполнении которого должен быть исполнен алгоритм, обозначенный в нижней надписи.
   Диаграммы перехода состояний, таким образом, описывают все возможные варианты совместной обработки информации человеком (пользователем), выбирающим то или иное Условие, и компьютером, выполняющим тот или иной Алгоритм. Эти диаграммы можно строить в виде иерархически упорядоченного множества диаграмм различного уровня подробности. Любую стрелку диаграммы верхнего уровня, соединяющую какие-то два состояния, можно более подробно описать с помощью диаграммы нижнего уровня, в которой эти состояния являются начальным и конечным. При таком иерархическом описании Алгоритм на диаграмме верхнего уровня исполняется не исключительно АМ, а попеременно АМ и пользователем в режиме диалога. Алгоритм диаграмм переходов состояний нижнего уровня, исполняемый только АМ, будем называть алгоритмической процедурой или просто процедурой этой АМ.
   Пользователь, работая на ПК с каким-либо приложением (программой), снабженным современным графическим интерфейсом,

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

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

обладает большими возможностями ведения диалога. Любое его допустимое действие над тем или иным элементом управления (элементом интерфейса), предоставляемым приложением, рассматривается как событие — выполнение некоторого условия, вызывающего выполнение соответствующей алгоритмической процедуры над имеющимися данными.
   Исходными данными для написания таких программ являются диаграммы перехода состояний, описывающие диалоговые возможности, которые должны быть предоставлены пользователю этой программы, а также описания алгоритмов (процедур), выполняемых программой, и исходных данных для них.
   В настоящее время наиболее популярны объектно-ориентированные методы создания программ, являющиеся развитием традиционного алгоритмического программирования. Идея объектно-ориентированного подхода заключается в том, что программа представляется не в виде алгоритмической процедуры — последовательности инструкций (команд), а в виде иерархически упорядоченной совокупности взаимодействующих объектов. Программный объект можно рассматривать как симбиоз структурированных данных, описывающих свойства некоторого объекта предметной области или элемента интерфейса, и методов — действий над этими данными, описываемых как алгоритмические процедуры. Обработка информации с помощью программы представляет собой конъюнкцию (соединение) событий, инициируемых действиями пользователя с объектами — элементами интерфейса, и вызываемых этими действиями методов (событийных процедур). Эти процедуры изменяют состояние (значениясвойств) объектов. Изменение свойств объектов возможно лишь посредством присущих этому объекту методов.
   Алгоритмы, которые должны быть исполнены АМ, необходимо описать на интерпретируемом ею языке. Для современных персональных компьютеров это языки систем визуального программирования, примером которых является Visual Basic (см. гл. 4). Однако, прежде чем писать программу на алгоритмическом языке, рекомендуется представить алгоритм в более привычной для человека форме.
   В настоящее время при описании алгоритмов и составлении программ наиболее удобно и распространено использование так называемых допустимых конструкций структурного программирования (ДКСП), которые бывают двух видов:
   —  базовые конструкции структурного программирования (БКСП);
   —  конструкции, полученные из БКСП или другой (исходной) ДКСП путем допустимых преобразований.
   Базовые конструкции структурного программирования делятся на три основные конструкции и две дополнительные. С помощью основных базисных конструкций можно представить любой алгоритм, втом числе и дополнительные БКСП. Дополнительные БКСП вводятся для удобства ввиду их частого использования. БКСП легко реализуются соответствующими последовательностями операторов языков программирования.
   К основным БКСП относят конструкции «следование», «ветвление», «цикл-пока».
   К дополнительным БКСП относят «выбор» и «цикл-до».
   На рис. 1.25 приведено графическое и вербальное описание конструкции «следование», заключающейся в последовательном выполнении сначала подпроцесса а, а затем подпроцесса b.

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

   Мы видим, что и в графической, и в вербальной форме представления подпроцессы выполняются в порядке их следования сверху вниз. При необходимости отразить в графическом представлении алгоритма другой порядок следования можно использовать направленные стрелки.
   В качестве примера рассмотрим запись алгоритма (рис. 1.26), согласно которому переменной х сначала присваивается значение, равное значению переменной у, а затем значение переменной х увеличивается в 2 раза и к нему прибавляется единица.
   Отметим непривычное, но характерное для программирования использование знака «=» не для обозначения равенства левой и правой части выражения, а для обозначения операции присваивания переменной (стоящей в левой части) значения некоторой формулы, стоящей в правой части. Если, например, перед началом выполнения рассматриваемого алгоритма значение переменной у было равно 4, то в ходе выполнения алгоритма значение переменной х станет равным сначала 4, а потом 9.
   Большинство практических задач нельзя решить с помощью линейных алгоритмов, в которых используется только конструкция «следование», поскольку часто бывает нужно перейти к исполнению разных подпроцессов в зависимости от результата проверки выполнения того или иного условия. Большое число таких переходов может усложнить разработку, программирование и изучение логики выполнения алгоритма. Использование ДКСП помогает преодолеть этот недостаток.
   Выполнение конструкции «ветвление» (рис. 1.27) начинается с проверки условия, задаваемого логическим выражением L; если оно истинно (равно 1), то выполняется подпроцесс а, в противном случае, т. е. при L = 0, выполняется подпроцесс b. Существенной чертой конструкции «ветвление» является слияние обеих ветвей, т. е. независимо от того, подпроцесс какой именно из ветвей был выполнен, следующей будет выполняться одна и та же конструкция.
   Наличие единственного входа и единственного выхода характерно для всех конструкций структурного программирования и обеспечивает ясность логики выполнения алгоритма.
   Отметим, что в вербальном представлении конструкции «ветвление» подпроцесс, который выполняется при справедливости условия L, записывается между ключевыми словами «ТО» и «ИНАЧЕ», располагаемыми в разных строках. Подпроцесс, который выполняется, если это условие не справедливо, записывается

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

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

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

 Рисунок

   Выполнение повторяющихся (циклических) действий можно организовать с помощью базовой конструкции «цикл-пока» (рис. 1.29). Ее выполнение начинается с проверки логического выражения (условия) L. Если оно истинно (равно 1),

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 
< Пред.   След. >