lekcii5 (Лекции), страница 8

Таким образом, «обработка информации» -- это,как правило, сокращение количества информации. Во всяком случае, верно утверждение: обработка информации никогда не добавляет информацию, она состоит в том, что извлекает интереснук> информацию из той, которая содержится в сообщении. Лекция 4 1.8 Автоматизация обработки информации Вернемся к рассмотрению диаграммы (*"'). Если заменить па ней отображение р обратным отображением 6 = с>, получим новую диаграмму: Лсс-'-' — 1 м) )о.

Л"с — "- 1' Автоматизация обработки информации заклн>чается в выполнении и или»» > о и о,р' при помс>щи физичс,*ских устройств. Однако в программировании изучан> сея методы автоматического выполнения только отображения и, т.

е. обработки сообщений. Программноаппаратная реализация отображений «6.,,г' изучается в другом разделе информатики, который называется «Искусственный интеллект» — и потому выходят за рамки нашсто курса. Для автоматизации обработки сообщений нсобходимо иметь физическое устройство, работа которого «моделировала бы выполнение отображения гс Для этого необходимо располагать тремя физическими представлениями: 1, физическим представлением для множества исходных сообщений Х его мы будем обозначать буквой О и называть множеством исходных донных: 2. физическим представлением для множества результирутощих сообщений Лн его мы будем обозначать буквой 1)' и называть множестнеом резузтьтируютттих данных (резуттьтатов); 3.

физическим представлением правила обработки м, которое должно быть преобразованием, или последовательностью преобразований, оттерирующих над 1) и дающих в результате элемент 1)', — его мы будем обозначать буквой Р; преобразование Р должно быть физичсски реализуемым, т. е. выполняться на некотором физическом устройстве. Таким образом, для того, чтобы выполнить автоматическую обработку сообщений, необходимо автоматизировать выполнение т1тех отображеттий: 1, отображения кодирования С, которое гюзволяет представить (абстрактное) сообщение из Х с ттомощью элемента множества данных 1), т.

е., с помощью конкретного ссн:тояния некоторого физического устройства: 2. отображения Р, которое ттереводит э:темент 1) в элемент 1)' конкретное состояние еще одного физического устройства; 3. отображения декодирования 1,?, которое позволяет проиптерттретировать результат конкретное состояние физического устройства, представляющее элемент из В', пе1эеведя его В соотьетствующее сооощсние из множества ттт . Таким образом, .автомтати"ттюкая обработка информации может быть представлена диаграммой 1) ' — М вЂ”,"1 Рт', ),и ) а. 1)' — Ж' — Р ,д Из диаграммы следует и = С о Р с ф причем все три отображения С, Р и с) должны выполняться автоматом. 1.9 Конструктивное описание процесса обработки дискретных сообщений Обработка (дттскретттьтх) сообщений состоит в применении отображения (ттравила обработки) и (сьт. и.

1.6), или в последовательном применении отображений С, Р и Я (см. п. 1.8). Чтобы отображение Р могло служить основой для автоматизации обработки сообщений, оно должно задавать некоторый способ построения сообщения д.' = Р1д), исходя из сообщения д. Е 1). Етпти Р -- конечное множество, то отображение Р может быть задано таблицей, в которой перечисляются все сообщения (1 Е 13 и соответствуклцие им сообщения Рг'(1). Примером такой таблицы может служить таблица умножения (или таблица сложения) однозначных чисел в позипиопной системс счисления.

Если же 0 бесконечно или по крайней мере так велико, что задание Р с помощью таблицы оказывается непрактичным, то нужно представить Р в виде по(.лсдовательности элементарных шагов обработки (или тактов), каждый из которых со('.тоит В выполнении Одного или н('.скольких доста.— точно простых отооражений, называемых операциями: Р = Р> о Р2 о... о Р».. Примеры операций: переписывание»копирование) буквы или слова, приписывание буквы к слову, приггисывание слова, к другому слову Отметим, что любое отоораженис, допускающее о>>иоанне с помощью достаточно простой таблицы, может быть объявлено операцией.

Конечно же, оператор языка программирования высокого уровня, машинная команда,, директива или системный вызов операционной системы также удовлетворяют критерию элементарности шагов обработки. Пример 1.9.1. Пусть исходное сообщение -- это пара»иг, иэ) слов над некоторым (на»гример, латинским) алфавитом, к которому перед буквой а добавлен пробел, и пусть требуется, чтобы резутгьтирующее сообщение 1и(, гвэ) состояло из тех же слов, но расположенных в лексиг.ографи~геском ггорядке. Правило об1эаботг(и может быть задано следующей последовательностью элементарных шагов: (1) завести пустые слова г(>» и гг>э (это можно сделать, например, написав ганг =" и газ = "), уравнять количество букв в словах иг и и>п добавив в коггец более короткого слова пробелы и перейти к и>агу (2); (2) сравнить (ггоэгьзуясь списком букв в алфавипюм порядке, или таблицей для отношения алфавитного предшествования -с) гдг»>) и г.'1и2) (1(и) -- обозначение для крайней левой буквы слова и, отличной от пробела); если г."1иг) -с (1и2), перейти к шагу (3); если с»и2) -с (»г»г), перейти к шагу»4).

Если буквы (»ид) и (»иэ) совпадают и не являются щ>обетгами, то приписать ('1>г,г) 1»гли К(иэ)) к словам п>г и гг>2. Заменить 1>(г»г) и (»ггв) пробелами и снова выполнить шаг (2). Наконец, если г'1>г>) и (.'(ггэ) пробелы, закончить обработку сообщения; (3) приписать слово вг к слову п>г, слово нэ к слову гг>э и закончить обработку сообщения; (4) приписать слово вг к слову гг>2, слово г»2 к слову и>» и закончить обработку сообщения.

Нетрудно показать, что последовательность шагов (1) — (4) действительно обеспечивает лексикографическое упорядочивание слов в любом исходном сообщении. Обработка сообп»ений, описанная в примере г'1.9.1), называется эффективной процедурой или алгоритмом. Более точно, алгоритм это точно заданная последовательность правил, указывающая, каким образом можно за конечное число шагов получить выходное сообщение определенного вида...

используя заданное исходное сообщение. Пример»1.9.1) позволяет обнаружить некоторые свойства алгоритмов, а именно: (1) массовость, т. е. потенциальная бесконечность исходных сообщений, предназначенных для переработки алгоритмом; (2) детерминированность процесса применения алгоритма, заключающегося в последовательном выполнении дискретных действий 1шагов), однозначно определяемых результатами каждого предыдугцего и>ага; (3) элементарность каждого шага обработки, который должен быть достаточно легко выполним: (4) результативность алгоритма, т. е.

точное описание того, что считается результатом применения алгоритма, после выполнения всех требуемых шагов. Чрезвычайно важным с точки зрения практической эффективности алгоритмов является еще одно свойство: (5) сложность алгоритма определяется количеством простых операций, которые нужно совершить для обработки сообщения. Это количество прямо зависит от длины входного сообщения и, и обычно задается некоторой функцией ~(и). Таким образом, сложность ограничивает применимость алгоритма. Алгоритм, выполняющийся за, постоянное время, можно применять к любому входному сообщеникь Если время выполнения пропорционально и или и~, то такой алгоритм неприменим к длинным исходным сообщениям, поскольку время выполнения становится неприемлемо болыпим. Иногда очевилный алгоритм можно существенно улучшить за счет другого подхода к проблеме. Пусть необходимо вычислить значение многочлена а„,х" + а„их" ' +...

1 а,х + пв и1и+ 1) Прямое вычисление потребует и, +и.— 1+ и — 2+ . + 1 = операций умпо- 2 и(и, 1- 3) жения и и операций сложения, всего ',, т. е. его сложность 0(и ). А если переписать задачу в виде (... ((и х + и — дх+ а .— 2) ° ° )х + ао то можно обойтись и умножениями и и, сложениями всего лишь 2и операциями, т. е. порядок сложности этого алгоритма, называемого схемой Гориера, 0(и). Сложность алгоритма определяет,как долго придется ждать, пока будет получен результат его работы.

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

Кроме обычной временной сложности алгоритмов часто рассматривают и пространственную сложность .-- объем памяти, необходимый алгоритму для переработки входного сообщения ллины и. Для обозначения класса сложности используется 0-нотация [93, 761. У всякого алгоритма, как у функции, есть главная часть, которая занимает больше всего времени для выполнения.

Анализируя количество выполнений главной части делают вывод о поведении алгоритма в зависимости от длины исходного сообщения Щ. Тогда появляется возможность сказать, какие задачи могут быть решены за приемлемое время, а какие не будут решены практически никогда. ЕЗсс алгоритмы можно разбить на классы по их сложности ~881: 34 Класс сложности Описание 0(1) Алгоритмы с постоянным временем выполнения, например доступ к элементу массива. При увели >ении размера задачи вдвое время выполнения не меняется.