lekcii6 (Лекции), страница 4

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

чтобы диаграмма (**) была коммугативной. Если и — обратимое (взаиыно однозначное) отображение. т. е. если информация при обработке по правилу а яа терястсяг то соответслвующую обработку сообщений и называют пере>цифровкой. Пусть — обратилгая пе1юшифровка. Тогда по сообщению и' =- и(п) можно восстановить не только исходную лгггг)>арлгацггюг но и само исходное сообщение и. Иными словалги.

в этом случае и' лг«Уар1>енг и (см. и. 1.4). Обратимшг перешифровка и ггазываетт>г перекадировкай. Пусть псрсшифровка и нс явлжтсн обратпыой. т. е. пусгь несколько сообщений из Лг кодирузагся одним и тем >ке сообщением пз Ли. Но так как при псрсшифровке информация не терястсяг это означает. что исходное лшожсспю сообщений Л! является избыточным: некоторые сообщения из !д содер>кат одну и ту жс информацию (г>ублиругот друг друга). В К' таких,зублирующих сообщений меныпег чем в Лг твк как при обработке по правилу и пекоторыс из длбзируюших друг друга сообщеннй «сливаются» в одно сааб>ценив.

Перепшфровка и, которая не является обратимой, называс>си сжимающей. Сжатяю подвергается множссгво сообщений. То есть в результата >>>обрати»лай парашифровкя сообщений пх количество уменыпаезсяг а информация можш либо сохраняться, либо теряться. Пример Е>.1. Пусть сообщения (агЬ)г составленные из пар целых чисел (например, в дсстгтлгчгготг позиционной записи), переда>от инфорлшцию >рациональное число г, пред- а ставлыгное дробью — ».

Тогда !г' =- К х Я (где К вЂ” множество целых чисач, И вЂ” множество Ь нату раяьных чисел)., 1 = лз («1-- множесгво рациональных чисел). Отображение у>г Лг 1 нс является обратимым, твк как при любом целоы и парам (а, Ь) и (па, пЬ) соотвшствует одно н то же рациональное чпсло г. Пусть Ли . множество пар (р,д) взвилшо просгых целых чисел и пУсть и > Лгг — г гг' псРеводит все (пйг пд) в (Р, д). Тогда и — сжимающее отображение, а уа': Лг' 1 — обратимое олабражснгго (мы считаелг Р— — 1). Такое отображение и называется вполне сжимающей перел>нфровкой.

поскольку после обработки сообщений соответствие между сообщениями и инфорлгацией биективно. Здесь информация не теряется. Етли о — необратимое щабражение, т. с. если разные сведения из ! отображшотся в одну и ту жс информацию л' е !', та соответствугащую обработку сообщений яазывают избирательной. Особенно часто встречается случай, когда !' с 1, а гт тождественное отображение для всех л' Е Р. В этом случае производится амбар из данного множгства сведений. Таким образом, «обрабагка информации» этог как правило, сокращение количества информации.

Во всяком случае, верно утверждение: обработка ипформацни никогда не добавляет информацию., опа состоит в том, что извлекает интересную инфорыацию из той, которая содержится в сообщении. Лекция 4 1и8 Автоматизация обработки информации Вернемся к рассмотреюпа диаграммы (**). Если заменить на ней отображение уг обратным отображениелг й = у>, получим новую дивграмыу: Лвтаматнзапин обработки информации закгпочвется в вьпголвении а илв уа ' а и а ю' при помощи физических устройств. Однако в программировании изучаются методы автоматического выполнения только отображения и, т. с.

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

физи >ескил> представлением правила обрабогки и, кгаорое должно быть преобразоеанисл>., и.>и пос |едовательносгью преобразований, опернрующих над П и дающих в результате элемент Л'., его мы бушел> обозна>ать буквой Р; преобразовавие Р должно бьн>, физически реализуемым, т. е. выполнятьс» на некогорол> физическом устройстве. '1аким образом, для того, чтобы выполнить антоматичсскую обработку сообщений, необхо;гилю автоматизировать выполнение трех отображений: !. отображения коднровапня С, которое пснволяет представлггь (абстрактное) сообщение из Ж с помощыа элемента лшожества данных П, т. е., с помощью конкретно>о состояния некоторого физического устройства; 2. отображения Р, которое переводит элемент П в алемент П' конкретное состояние еще одного физического устройства; 3.

отображения декодирования л), которое позволяет проинтерпретировать результат конкретное состояние физическою уатройсгва, предстанляющее алел>е>п нз П', переведя его в соответствующее сгюбшепяе из множества >>и. Таким образом. ашоматичсская обработка инфорл>ации люжет быль представлена диаграммой Пл — Мл~ — 1 Р( (и )а П' — 14' — Р , >у Из ди>итал>л>ы следует и =. С а Р о О, причем все трн отображения С, Р и О. должны выполняться ав>амж:ом, 1.9 Конструктивное описание процесса обработки дискретных сообщений Обработка (дискретных) сообщений состоит в примоненяи отображения (правиза обработки) и (см.

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

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

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

Если буквы 4(и>) и 4(из) совпадают и не явля>атея пробеламн, то приписать 4(и>) (илн 4(из)) к сдавал> и> и юз. Заменить |(и>) и 4(из) пробелами и снова выполннтыцаг (2). Наконец, если Ю(и>) и 4(нз) пробелы, закончить обработку сообщения; (3) приписать слово и, к слову я>л, слово ил к слову ю> и закончить обработку сообщения; (4) приписать слона и> к слову ыз, слово из к слову ю> и закончять обработку сосбгцення. Нетрудно показать, что послсдоваты>ьность шагов (1) (4) з!ействительно обеспечивает .>ексикографнчсскос упорядочивание слов в любом исходном сообщении.