§ 22. Основы теории алгоритмов
§ 23. Формы представления алгоритмов
§ 24. Информация и управление. Управляющие алгоритмы
ЛЕКЦИЯ 6
§ 22. ОСНОВЫ ТЕОРИИ АЛГОРИТМОВ
Алгоритм является фундаментальным понятием информатики. А раз так, необходима дисциплина, занимающаяся его изучением. Такой дисциплиной является теория алгоритмов. Первые алгоритмы появились вместе с математикой, а теория алгоритмов возникла лишь в 30-х гг. нашего века. Математики, решая задачи, строя алгоритмы, позволяющие находить их решения, не уточняли само понятие алгоритма. В этом просто не было необходимости. Под алгоритмом всегда понималась процедура, которая позволяла путем выполнения последовательности элементарных шагов получать однозначный результат (не зависящий от того, кто именно выполнял эти шаги) или за конечное число шагов прийти к выводу о том, что решения не существует.
Долгое время речь шла лишь об алгоритмах, производящих вычисления, и набор элементарных шагов был ясен. В него входили все арифметические операции, а также проверки равенств, неравенств или других отношений подобного типа. Часто алгоритмы задавались в виде формул, в которых с помощью скобок определялся порядок выполнения элементарных шагов в процессе вычислений.
Но к началу 20-го в. стали усложняться объекты, с которыми оперировали алгоритмы. Появилась необходимость выполнять операции над векторами, матрицами, множествами, функциями и т. п. Возникла масса вопросов. Одни из них были связаны с трактовкой элементарности тех или иных шагов (например: можно ли считать взятие интеграла таким шагом?), другие - с оценкой конечности и однозначности алгоритма.
У математиков стала возникать мысль, что не для всяких математических задач вообще можно найти процедуру решения, которая явилась бы алгоритмом, т. е. появилась идея, что существуют алгоритмически неразрешимые проблемы. Но для того чтобы такая идея получила право на жизнь, надо было научиться доказывать факт отсутствия алгоритма. А для этого необходимо было дать точное определение алгоритма, без которого разговоры о существовании или несуществовании его теряли всякий смысл. Так возникла необходимость в точном понятии «любой алгоритм», т. е. максимально общем понятии алгоритма, под которое подходили бы любые мыслимые виды алгоритмов. Попытки сформулировать такое понятие привели в 30-х гг. 20-го в. к возникновению теории алгоритмов. Итак, теория алгоритмов – это наука, объектом изучения которой является любой алгоритм и его свойства. Теория алгоритмов оказалась тесно связанной с математической логикой. А вместе они образовали новую науку - метаматематику, которая изучает основные средства математики (методы доказательств, способы построения аксиоматических теорий, свойства математических процедур) математическими методами. Когда же началось бурное развитие вычислительной техники и наук, связанных с ее использованием, то выяснилось, что в основе этих наук также должна лежать теория алгоритмов, поскольку ЭВМ может реализовать только такие процедуры, которые представлены в виде алгоритмов.
В теории алгоритмов используется идея построения конкретных алгоритмических моделей, каждая из которых содержит конкретный набор элементарных шагов, способов определения следующего шага и т. д. С теоретической точки зрения наибольший интерес представляют модели, которые были бы одновременно универсальными (т. е. позволяющими описать любой алгоритм) и простыми, содержащими минимум необходимых средств. Требование простоты важно для того, чтобы выделить действительно необходимые элементы и свойства алгоритма и облегчить доказательства общих утверждений об этих свойствах. (В прикладных моделях гораздо важнее удобство программирования и эффективность вычислений, поэтому их средства: набор элементарных шагов и т. д. - намного богаче.) Поиск теоретических моделей алгоритмов происходил в трех направлениях, которые и определили три основных класса таких моделей.
Первое направление основано на арифметизации алгоритмов. Как вы уже знаете, любые данные можно закодировать числами, и тогда всякое их преобразование станет арифметическим вычислением. Всякий алгоритм в таких моделях вычисляет значения некоторой числовой функции, а его элементарные шаги - это известные всем арифметические операции. Последовательности шагов определяются с помощью двух основных способов.
Первый способ - суперпозиция, т. е. подстановка функций в функции, порождающая математические формулы, в которых порядок действий определяется расстановкой скобок. Например, формула а × b + c/d получается подстановкой в функцию х + у функций а × b вместо х и c/d вместо у.
Другой способ – рекурсия, т. е. определение очередного значения функции через ранее вычисленные значения этой же функции. Классическим примером рекурсии служит функция «факториал»:
n! = 1 × 2× 3 × … n.
С помощью суперпозиции факториал через арифметические операции определить нельзя: дело в том, что «обычные» суперпозиционные формулы содержат фиксированное число операций для любых значений переменных, а при вычислении факториала число умножений растет с ростом n. Рекурсивное же определение факториала выглядит так:
0! = 1;
(n +1)! = n! (n+1).
Структура такого определения функций (называемого примитивно-рекурсивным) состоит из двух частей: определения значения функции f для начального значения аргумента (в нашем примере - для 0) и определения f (n + 1) через f (n) и другую функцию, которая считается определенной ранее (в примере роль этой функции играет умножение). Т. е. для вычисления f (n + 1) надо вычислить f в предыдущих точках: 1, 2 ... n.
Существуют и другие виды рекурсии, в которых понятие предыдущих точек определяется более сложно. Функции, которые можно построить из целых чисел и арифметических операций с помощью суперпозиций и рекурсивных определений, называются рекурсивными функциями. Они являются исторически первым уточнением понятия алгоритма, т.е. первой универсальной алгоритмической моделью.
Второе направление поиска теоретических моделей алгоритмов основано на простой идее: для того чтобы алгоритм понимался однозначно, а каждый его шаг можно было считать элементарным и выполнимым, он должен быть представлен так, чтобы его могла выполнять машина. Чем проще структура машины и ее действия, тем убедительнее выглядит утверждение, что ее работа и есть выполнение некоторого алгоритма. При этом структура машины должна быть универсальной, такой, чтобы на ней можно было выполнить любой алгоритм. Эта идея привела к концепциям абстрактной машины как универсальной алгоритмической модели. Она была выдвинута А. Тьюрингом и Э. Постом практически одновременно (в 1936 — 1937 гг.). Действия абстрактной машины сводятся к тому, что она обозревает символы, записанные в памяти, и в зависимости от своего состояния и того, каков обозреваемый символ, она стирает его или заменяет другим символом или какой-то последовательностью символов, после чего переходит в новое состояние и читает следующий символ. Наибольшую известность среди моделей такого типа получила модель Тьюринга, за которой закрепилось название «машина Тьюринга».
Третье направление, связанное с уточнением понятия «алгоритм», близко ко второму, но отвлекается от конкретных машинных механизмов. Если рассматривать «механические», формальные преобразования данных, не употребляя машинной терминологии («память», «состояние машины», «считывание» и т.д.), то описание действий машины превращается в систему подстановок, которые указывают, какие замены символов надо производить и в каком порядке использовать сами подстановки.
Наиболее известная алгоритмическая модель этого типа – так называемые нормальные алгоритмы Маркова (название происходит от имени советского математика А. А. Маркова).
В теории алгоритмов установлен важный факт: в универсальной алгоритмической модели всегда существует универсальный алгоритм, т. е. алгоритм, который способен моделировать работу любого другого алгоритма, описанного в этой модели. Универсальный алгоритм устроен следующим образом. Имеется метод кодирования S для любого алгоритма А в данной модели. Если на вход универсального алгоритма U подать код S(A) алгоритма A и исходные данные х, то результат работы U будет равен результату работы А над х: U(S(A),x) = А(х). По существу, метод кодирования алгоритмов - это язык программирования, а код S(A) - это программа алгоритма А в языке S. Поэтому концепция универсального алгоритма, существование которого было доказано в 30-х гг. нашего века (раньше, чем появились универсальные ЭВМ), свидетельствует о том, что в основе работы ЭВМ лежат не только физические, но и математические идеи (успехи электроники влияют лишь на быстродействие и размеры ЭВМ).
С гордостью отметим, что значительный вклад в развитие теории алгоритмов внесли советские ученые А. А. Марков, А. И. Мальцев, В. М. Глушков, А. Н. Колмогоров, А. П. Ершов, Ю. Л. Ершов, А. А. Ляпунов, П. С. Новиков, С. В. Яблонский и многие другие.
В настоящее время теорию алгоритмов разделяют на классическую и прикладную.
Характерная особенность классической теории алгоритмов состоит в выборе минимальных средств для представления и преобразования информации, продиктованном соображениями удобства формализации понятия алгоритма. Процедуры конкретных вычислений, записанные при помощи подобных минимальных средств, сводятся к сложной кодировке и моделированию преобразования информации и обычно настолько громоздки и затруднительны для понимания, что не могут быть использованы в реальной практике. Но вместе с тем результаты классической теории являются методологической основой прикладной теории алгоритмов.
Возникновение прикладного направления в теории алгоритмов заставило по-новому взглянуть на понятие алгоритма и привело к постановке нового круга нетрадиционных проблем, связанных со средствами выразимости эффективности и адекватности алгоритмов. Прикладная теория алгоритмов направлена на исследование моделей алгоритмов, способных учитывать многообразие факторов, возникающих в реальных процессах обработки информации. На практике под алгоритмом понимают любое преобразование вычислительной информации, выразимое в используемом алгоритмическом языке. Поэтому, в отличие от традиционных классических определений, реальные алгоритмы могут в явном виде учитывать сложную структурную организацию информации и способов ее обработки, а также обладать широкими вычислительными возможностями.
Однако многообразие средств вычислительной техники, областей применения, методов вычислений и направлений в алгоритмических языках приводит к огромному количеству моделей вычислений, отражающих тот или иной аспект обработки информации. (Существуют десятки направлений и методологий программирования и сотни реальных, активно используемых алгоритмических языков). А это в свою очередь влечет за собой трудности в понимании логических основ обработки вычислительной информации, порождает различные частные методы для решения задач одного и того же типа и иногда приводит к неэффективному использованию вычислительной техники и человеческих ресурсов. Таким образом, прикладное направление в теории алгоритмов, с одной стороны, существенно обогащает понятие алгоритма, с другой — перегружает его описаниями алгоритмических языков или реализующих систем.
Разделение теории алгоритмов на классическую и прикладную условно и отражает два подхода к понятию алгоритма — математический и прагматический. Уже сейчас наблюдается тенденция к взаимному обогащению и слиянию этих двух подходов, выражающаяся в многочисленных общих результатах, а также в стремлении логиков и программистов к взаимному пониманию. Как видим, взаимоотношение между классической и прикладной теориями алгоритмов соответствует диалектическому принципу «единства и борьбы противоположностей», что в конечном итоге приводит к становлению единой теории алгоритмов.
Существует еще одно условное деление теории алгоритмов – на качественную и количественную (метрическую). Качественная теория алгоритмов исследует алгоритмы с позиций устанавливаемого ими соответствия между исходными данными и результатами. Количественная теория алгоритмов исследует алгоритмы с позиций сложности, как самих алгоритмов, так и задаваемых ими вычислений.
С понятием алгоритма тесно связано понятие алгоритмического анализа как нового методологического приема для изучения сложных процессов и систем, основанного на алгоритмическом моделировании изучаемых явлений. Старый прием – «научиться чему-либо можно, когда можешь научить этому кого-нибудь другого» - приобрел в настоящее время новое звучание: «познать явление можно, когда можешь составить алгоритм его функционирования». Алгоритмическое представление «сложное = составные части + взаимодействие» позволяет выявить определенные закономерности в поведении сложной системы, взаимосвязь составляющих частей, изучить ее динамические характеристики.
Сейчас трудно найти область знания, где бы ни использовались алгоритмы. Это почти все разделы математики, математическая логика, теория моделей. В последние десятилетия алгоритмы вошли в практику лингвистов, психологов, экономистов. Без теории алгоритмов не обходятся при решении задач управления, искусственного интеллекта, машинного перевода.
В заключение отметим, что основы алгоритмической теории очень сложны. Нам достаточно тех общих сведений, которые даны в этой лекции.
§ 23. Формы представления алгоритмов
Для наглядного представления алгоритмов в информатике весьма широко используются блок-схемы, которые вам уже достаточно хорошо знакомы.
Блок-схемы позволяют представить алгоритмы в обозримом виде, что дает возможность анализировать их работу, искать логические ошибки в процедуре их реализации и т. п.
Блок-схема представляется в виде графа специального вида. Вершины графа соответствуют определенным частям алгоритмов (в предельном случае отдельным шагам алгоритма или командам вычислительной машины), а дуги показывают возможные переходы между этими вершинами в процессе выполнения алгоритма.
Безусловные шаги принято изображать прямоугольниками, условные шаги – ромбами. Из ромба всегда выходят две стрелки: одна имеет пометку «да» (условие выполнено), другая - пометку «нет» (условие не выполнено). Граф, изображенный на рисунке 8, соответствует процессу отыскания максимального числа в последовательности, который был описан ранее.
Рис.8. Блок-схема алгоритма Процесс выполнения алгоритма представляется в графе как путь из начальной вершины в конечную. Если все шаги алгоритма безусловные, то этот путь при любых данных одинаков, хотя результаты, разумеется, могут быть различными. Если же в алгоритме есть условные шаги (а чаще всего так и бывает), то путь зависит от выполнения содержащихся в них условий. Как правило, алгоритм содержит циклы, т. е. замкнутые пути, возвращающиеся в пройденную ранее вершину. Алгоритм на нашем рисунке содержит цикл между шагами 6 и 10, который разветвляется в шаге 7. Поэтому возможны два варианта прохождения цикла 6, 7, 8, 9, 10, 6 и 6, 7, 10, 6. Цикл обязательно содержит условную вершину, в которой можно выйти из цикла. В данном примере такой вершиной является шаг 10. Выход из цикла происходит, когда все числа последовательности просмотрены. Если условия выхода из цикла сформулированы неправильно, то может оказаться, что они никогда не выполняются, и процесс исполнения алгоритма становится бесконечным (зацикливается).
Рис. 9. Укрупненная блок-схема алгоритма Для компактного описания циклов в языках программирования имеются специальные операторы циклов. Основную часть нашего примера (шаги 2 - 10) с помощью такого оператора можно записать гораздо короче. Правда, оператор цикла нельзя считать элементарным шагом, в частности, потому, что время его выполнения зависит от исходных данных и может быть сколь угодно большим. Элементарность шагов входит в число необходимых требований к алгоритмам. Однако уже на нашем простом примере видно, что строгое соблюдение этого требования весьма обременительно - описание алгоритма разрастается и становится плохо обозримым. Выход заключается в том, что шаги надо укрупнять, но при условии, что они в дальнейшем будут доведены до элементарных. Крупный шаг - это фактически алгоритм, являющийся частью (подалгоритмом) более сложного алгоритма. Такие подалгоритмы называются блоками. Блок обычно не элементарен (его размеры неограниченны и выбираются произвольно). Однако правильно сформулированный блок обладает всеми другими признаками алгоритмического шага. В частности, он имеет точно выделенное начало (точку входа) и может быть условным или безусловным. У безусловного блока — всегда одна точка выхода. Условный блок имеет несколько точек выхода (их может быть больше двух, если блок содержит несколько условий). Другие блоки алгоритма связаны с данным блоком только через точки входа и выхода. Поэтому если блок правильно решает свою задачу, т. е. всегда дает нужный результат, то его внутренняя структура несущественна для остальной части алгоритма. Из этого следуют два важных вывода. Во-первых, описание алгоритма можно представлять в укрупненном блочном виде (рис. 9). Отсутствие детального описания внутренней структуры блоков не мешает пониманию того, как работает алгоритм в целом; важно лишь, чтобы было четко определено, какие блоки запускают данный блок в работу, где лежит его исходная информация, где будет записан результат, и куда переходить после окончания его работы. Такое блочное представление особенно удобно на первых этапах разработки алгоритмов (детализация блоков происходит позднее). Во-вторых, детализацией разных блоков (т. е. программированием - доведением их до настоящих алгоритмов и программ) могут заниматься разные люди независимо друг от друга. Это важно при организации работ по созданию сложных программ. Блок-схемы являются частным случаем наглядных форм представления алгоритмов. Существуют и другие способы представления: операторные алгоритмы, диаграммы смены состояний и т. п. Развивается и теория таких представлений. Программы, написанные на языке программирования, можно также рассматривать в качестве форм представления алгоритмов. Современное программирование в отличие от классической теории алгоритмов стремится предоставить разработчику реальных алгоритмов богатый арсенал мощных и разнообразных средств, как для представления информации, так и для выражения процессов ее обработки. Стремление избавить пользователя от излишней детализации и кодировки при составлении программ привело к появлению целого семейства алгоритмических языков высокого уровня. Этот процесс продолжает бурно развиваться и является определяющим фактором современного программирования. Понятие алгоритмического языка является одним из основополагающих понятий любого направления информатики, а программирования особенно. Алгоритмический язык - это язык, используемый для формальной записи алгоритмов. Языки такого типа изучаются и используются в математической логике и в программировании. В математической логике исследуются универсальные алгоритмические языки, на которых можно описать любую процедуру, относимую к интуитивно понимаемому множеству алгоритмов. Примером такого языка может служить язык, на котором функционирует машина Тьюринга. В программировании используется несколько типов алгоритмических языков, что определяется особенностями тех универсальных логических алгоритмических языков, которые были использованы при создании конкретного языка программирования. Например, язык ЛИСП опирается на идею реализации алгоритмов как последовательностей вычислений рекурсивных функций. Другой язык программирования - РЕФАЛ использует «универсальный» алгоритмический язык в виде схем нормальных алгоритмов Маркова, а в основе языка ПРОЛОГ лежит модель, заимствованная из логики предикатов первого порядка. В самом общем случае языком программирования можно назвать фиксированную систему обозначений для описания алгоритмов и структур данных. Такой язык имеет два «лица». Одно из них обращено к человеку, использующему язык для записи своих программ, а другое адресовано ЭВМ, которая должна понимать эти программы. Язык большинства современных ЭВМ достаточно беден и состоит из команд типа «выделить память определенного размера»; «выбрать из определенного места в памяти информацию»; «запомнить информацию в определенном месте памяти»; «сложить два числа»; «перейти к выполнению очередной команды, выбрав ее из определенного места в памяти» и т. п. Как правило, команд - несколько сотен. Все они настолько просты, что могут быть эффективно реализованы аппаратурой. Набор команд функционально полон, и, в принципе, используя команды из этого набора (в программировании говорят, пользуясь заданной системой команд), можно описать любой алгоритм. Правда, такая запись для сложных задач будет настолько громоздкой, что у человека очень мало шансов сделать ее безошибочной. Существует лишь два выхода из этого положения. Первый из них связан с созданием более сложных ЭВМ и, вследствие этого, с аппаратурой поддержки более мощных языков. Второй путь - программное моделирование более мощного входного языка. Такой прием в программировании называют созданием виртуальной вычислительной машины, состоящей частично из аппаратуры, а частично из программного обеспечения. На практике обычно создается иерархия виртуальных ЭВМ, где каждый следующий уровень позволяет программисту использовать все более и более мощный входной язык. При этом конечно, требуются специальные программы-переводчики (трансляторы), функция которых - преобразование программ на входном языке виртуальной машины в эквивалентные программы, понимаемые аппаратурой ЭВМ. Такая трансляция может быть одношаговой или многошаговой, в зависимости от числа уровней в иерархии виртуальных ЭВМ. Уже разработаны тысячи языков программирования, но лишь сотни из них реализованы хотя бы для одной ЭВМ. Однако даже среди этих сотен языков активно используются лишь несколько десятков. Алгоритмический язык ПАСКАЛЬ назван в честь английского ученого Б. Паскаля. По своей идее это алголоподобный (от названия АЛГОЛ) язык, вобравший в себя все лучшие проектные решения предшественника. Но вместе с тем это качественно новый шаг, связанный, прежде всего, с тем, что здесь впервые была воплощена концепция абстрактных типов данных. Если раньше все данные, преобразования которых описывались в программе, относились к одному из заранее определенных типов (целые, действительные и т.п.), то в ПАСКАЛе были введены средства конструирования новых типов данных. Были в языке и другие важные нововведения, среди которых следует отметить интервальные типы данных, средства работы с множествами и некоторые другие. Благодаря этим свойствам ПАСКАЛЬ стал не только интересным и мощным средством программирования широкого круга прикладных задач, но и языком, пригодным для обучения программированию как систематической дисциплине, основанной на фундаментальных понятиях, ясно и естественно отраженных в самом языке ПАСКАЛЬ. Почти одновременно с ПАСКАЛем, в начале 70-х гг., был разработан и язык программирования СИ. Но если ПАСКАЛЬ шел больше от теории программирования, то язык СИ - типичный пример влияния практических потребностей системного программирования на разработку новых языков. Изначально он создавался как инструментальное средство для реализации операционной системы UNIX на ЭВМ фирмы DEC, но популярность его быстро переросла рамки конкретной машины, операционной системы и задач системного программирования. И сейчас язык СИ можно по праву назвать одним из универсальных языков программирования. С одной стороны, в нем имеются средства определения новых типов данных, широкий набор операторов, характерных для языков высокого уровня, модульность и структурность, а с другой - в язык СИ включены средства программирования почти на уровне ассемблера (например, побитовые операции и работа с указателями). СИ-программы компактны и эффективны, но практическое использование языка требует от программиста осторожности, аккуратности и знания преимуществ и недостатков тех или иных конструкций. Практически каждый из языков программирования фиксировал достижения самой дисциплины программирования и открывал в ней новые пути развития. Так, ФОРТРАН показал возможность «отрыва» от конкретной ЭВМ с ее фиксированной системой команд; АЛГОЛ - использование строгого и элегантного математического стиля для реализации сложных алгоритмов; ПАСКАЛЬ - конструирование новых типов данных, а СИ - интеграцию языка программирования с операционной обстановкой, в которой этот язык функционирует. Если же говорить о языках обработки символьной информации, то следует отметить уже упоминавшиеся нами ЛИСП (List Processing Language), ПРОЛОГ (Programming in Logic) и РЕФАЛ (Алгоритмический язык рекурсивных функций). Языки символьной обработки сыграли важную роль в программировании. С одной стороны, они позволили осуществить разработку и реализацию ряда практически важных систем аналитических преобразований, интеллектуальных программ и т. д., а с другой стороны, именно эти языки породили целый спектр исследований, результатом которых стала разработка и реализация языков представления знаний. Современные пользователи наиболее часто используют язык объектно-ориентированного программирования Visual Basic. Это связано с широким распространением пакета программ Microsoft Office под Windows и предоставляемыми возможностями создания собственных приложений. Активно входят в практику программирования языки для создания приложений, работающих в сетях. Отметим, что существует также «прикладная» классификация языков программирования, согласно которой все они делятся на группы по областям применения. § 24. ИНФОРМАЦИЯ И УПРАВЛЕНИЕ. УПРАВЛЯЮЩИЕ АЛГОРИТМЫ В повседневной жизни мы всюду сталкиваемся с управлением и в самом общем виде понимаем под ним совокупность действий, осуществляемых человеком, группой людей или автоматическим устройством. Эти действия в идеальном случае представляют собой алгоритмы управления. Они направлены на поддержание или улучшение работы управляемого объекта в соответствии с имеющейся программой (алгоритмом функционирования) или целью управления. Управлять – значит влиять на ход какого-либо процесса или состояние некоторого объекта и его положения в пространстве. Управление является всегда целенаправленным действием, и цель его задается наперед. С точки зрения кибернетики, управляющие алгоритмы состоят из следующих основных шагов: 1) орган управления получает информацию о цели управления и о состоянии (поведении) объекта управления; 2) орган управления формирует управляющие воздействия, подбирая их так, чтобы в результате свести к минимуму рассогласование между заданной целью и достигнутым на данном шаге результатом; 3) совершается управляющее воздействие над объектом; 4) анализируется состояние объекта; 5) совершается процедура выбора из двух возможностей: – если в результате воздействия сведено к минимуму рассогласование между заданной целью и достигнутым на данном шаге результатом, т.е. достигнуты цели управления, происходит переход к п.6.; – если в результате воздействия цели управления не достигнуты, происходит возвращение к п.2; 6) дается сигнал об окончании процесса управления. Характерно, что описанный алгоритм является рекурсивным, так как независимо от целей управления и природы объектов функция управления является рекурсивной и всегда характеризуется наличием одного или нескольких замкнутых контуров. С позиции теории систем к понятиям управления и управляющего алгоритма можно подойти следующим образом. Основа любого сложного процесса — взаимодействие. Часто наблюдается несимметричное взаимодействие, когда выделяется управление – некоторая главная часть, которая в процессе взаимодействия преобразует подчиненные ей объекты. С точки зрения математики при парном взаимодействии выделение управления условно и зависит только от принятого соглашения. Однако во многих случаях явное выделение главной части, управляющей процессом взаимодействия, дает дополнительную характеристику исследуемого явления. Систему с выделенным управлением называют управляющей системой. Для сложных систем характерно явное выделение состояний, в которых может находиться управление системы. Например, состояниями электронных часов являются «тройки»: час, минута, секунда. Такая система имеет 24´ 60´60 – 86400 состояний. Если часы показывают дату и месяц, число состояний — около 31 млн. Для того чтобы проектировать сложные системы, используют принцип укрупнения состояний на разных уровнях детализации и другие приемы проектирования. Выделение управления в принципе характерно для любого алгоритма, так как наличие информации всегда предполагает потенциальную возможность ее целенаправленной переработки. Поясним связь понятий управления и информации. Капитан корабля не может без риска провести корабль по фарватеру, не имея информации о последнем. Физик не сможет составить уравнение, не зная всех входящих в него величин. Приезжий без плана города с трудом ориентируется в незнакомой обстановке. Вся наша жизнь состоит из постоянного решения задач с неполной информацией. Чем больше информации, тем лучше можно управлять ситуацией. Во всех случаях информация выступает активным началом, позволяющим совершать необходимые действия. Иными словами, информация проявляется в процессе взаимодействия с неким устройством управления. Без управления информация мертва так же, как без информации не может правильно функционировать управление. Управляющим устройством может выступать человек, машина, программа, общество и т.д. Человек, изучая закономерности мира, старается получить как можно больше информации — это дает ему возможность создавать наиболее оптимальные алгоритмы. Управляющее устройство работает по определенному, управляющему, алгоритму. Другими словами, можно сказать, что взаимодействие управления и доступной информации задает алгоритм (рис. 10).
Рис.10. Схема алгоритма управления По сути, предлагаемое определение управляющего алгоритма совпадает с понятием системы с обратной связью, в которой управляемые объекты являются информацией. Взаимодействие управления и информации осуществляется следующим образом. Управление обладает возможностью получать некоторые сигналы от обрабатываемой информации и вырабатывать операции, преобразующие эту информацию. Реакция управления на те или иные сигналы описывается правилами управляющей системы. Под воздействием сигналов управление меняет свои внутренние состояния и вырабатывает преобразующие информацию операторы. Рассмотрим, например, процесс чтения книги. Сигналами здесь служат слова, вызывающие у читателя зрительные образы, преобразованиями — простые операторы чтения — движение глаз по тексту. Различные устройства могут иметь разные возможности интерпретации сигналов и выполнения преобразующих операторов. Например, одна и та же музыка у разных людей вызывает разные чувства: некоторые могут даже плакать, когда другие остаются равнодушными. Один игрок в шахматы почти всегда выигрывает, другой проигрывает. Важно, что определение управляющего алгоритма в виде взаимодействующей схемы «управление + информация» дает «энергетическое» толкование понятия информации. В физике энергия означает способность совершить работу. Информация означает способность совершить, управляемую работу. Чем больше накоплено энергии, тем проще что-то сделать. Аналогично, чем больше информации, тем проще может функционировать управление. Управление относительно информации выступает в роли силы, прикладываемой к объекту. При вычислении совершается «работа». Аналогично тому, как делается в физике, эту «работу» можно вычислить, если известна «сила» каждой команды управления и мера «отрезка пути» – изменения порции информации при применении оператора управления. Отметим, что способы измерения информации, учитывающие функцию цели системы, все еще находятся в стадии изучения и разработки. Литература