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

Решив эти вопросы, мы сможем задавать правильные исходные данные дзя алгоритмов и правильно интерпретировать сообщения, полученные в результата их прнменення. Лекция 5 1.1() Интерпретация дискретных сообщений Сообщения интерпретируются:подьми в соответствии с их представлениями о внепшем мире, о среде (сстл<чвениай изи искусстяснной), информацию о которой содержат эти сообщения. Именно этим обстоятельством объясняется то, что одно и то же сообщение ннтерпротируется разными л<одьми по-разному. Прежде. чем зашпься уточненном этих нескатько туманных утверждений. поясням их смысз на прил<ере. Притлчл. Однажды седобородый философ и одноглазый вор вели на языке >костов беседу о смысле жизни.

Философ (Ф) показал о>нюглазому (О) один па.<сц; в ответ О показал два пальца: тогда Ф показал три пальца, а О ответ из тем, что показал кулак. после этого Ф сделал жссг. имитирующий процесс питья из бслыпой чмпн: О в ответ показа« ему луковицу. На этом беседа завершилась я собеседники разошлись. очень дава.<ьныс собой и друг другом. Од»ш нз:побопытных свидетелей беседы обратился к философу за разьяснением ее содержания.

«Мой собссетпшк оказа.<ся очень мудрым человеком», сказал философ. «Сначаза я сказал ему, что плоха жить одному. как перст. На что он ответил, что, конечно. вдвоем жить лучше. Тогда я сказал ел<у; что еше лучше. когда в семье трое, имея в визу ребенка. Он согласн.юя н заметил, что ребенок сн>ютит семью. И жизнь пойдет по.нюй чашей, отметил я напоследок, а он, показав луковицу, как бы сказал, что тогда даже мелкие ноприятиаши не бу тут омрачать ра,юсти жизни». Свидетель усомиязся в интерпретации Ф и пошел за разъяснениями к одноглазому. «Он. ничего. парень смелый, по куда ему против меня».. сказал О.

«Скала>а он говорит лшс: Эй ты, од<юглазый черт», на <то я отвечал: .<Л ты со свои»и двумя пе оченьто задавайсяв. А он никак ие уймется: «Л ведь на двоих-то у нас всего три г.<аза». '1ут я показал ел<у кулак. Он нспуга.кя н решил мнряться. «Выпьел<, что лиу» предложил он, на что я ответил> «Идн за бутылкой, закуска найдется». Мораль очевидна.

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

Обьектам, нх атрибутам и отношениям ставя<та в соответстние знаки (имена), нз которых строятся сообщения (напомним, что дискретное сообщение это посзедователыюсгь знаков). Интерпретация дискретного сообщения при наличии модели сводится к тому, что каждому знаку, входящему в сослан сообщения, ставится в соотвегствно обьект, свойство (атрибут) объекта, или отношение между объектами, прелсгавляелюе этим знаком (23, 32). Определение 1.10.1. Назовем й-мостным отношением на множестве И совокупность (лшожество) т упорядоченных наборов из к элементов множества <И вида (хмх>, ..., хв) (иначе говоря, атно<пенис т — это подмножество декартова произведения тв С М~; верхний индекс у т указывает местность (чис.ю мест) отношения. Определение 1.10.2.

Моделью (или реляционной системой) называется некоторое множество М с заданным на пем набором отношений (т ',т ',... „т ь), Иначе говоря., людсль М вЂ” это упорядочопная пара объектов М =- (3«, (тв', тв',, т"* )), где тл'. тэЧ ..., т " - отношения па множестве ЛХ. Пример 1.10.3. Модель М, = (Л, »< «), <де Л - множество вещее<венных чисш<, »<" — отношение «меныпе». В математике и физико рассматривается специальный класс моделей, в которых на исходном множестве заданы пскоторыс числовые функции, а отношения выражаются через значения этих функций (см.

Пример 1.10.4). Пример 1.104. Модель Мч =- (Е, (тч, тл,тз)). Пусть на множестве Е задана вещественная неотрицательная функция двух переменных р(х, у), такая, что р(х, у) = 0 тогда н только тогда. когда х .— — у. По опредевен>по, х и у б Е находятсн в отношении тл тогда н только тогда, ко<у<а р(х, у) = 0:, х и у б Е находятся в отношении тл тогда и только тогда, когда р(х., у) = р(у,х):, х и у б Г находятся в отношении тэ тогда и только тогда, ковда р(х,у) < р(х, х) -~- р(з, у). Нелрнмер. в качестяе множества Е »южно взять евклидова пространство. а в качестве функции р(х, у) расстояние между точкамв этого нросзранст на.

В определения в<оды<и не указано, что же модстнруется. Примеры моделей 1З0.3 и 1.104 также пе да<от ответа на этот вопРос: что моде.чиРУют модеш <И< и йуэ. Длн ращения этого воп1юса введсл< понятия теории и сигнатуры. 37 Пусть й» нмя (знак) отношспяя г". Бу"гем говорить. тю модегп М .=- (ЛХ. (г,"'. г. ', ..., г )) нмсет сягнатуру Й. сслв суепествуег правило ннтерпрегэцнн еде такое.

что л. з»(Г»л) =- гц для всех е. = 1, 2,..., т. Если задана сягнатура Й н какая-нибудь шпсрпречвцяя эа этой сигнатуры па множестве е!Й то пара (еее,еа) определяет леодсль (мы будем называть сс модыеыо в снгнатурс Й). Сягнатура - это перечень знаков (пмен) отношсняй. Теория — это упорядоченная паря Т вЂ” (Й, А)е где Й вЂ” сягнатура. а А множество нксяоле. высказываняй о свойствах сяпеатуры Й (обычно в качестве аксяом попользуются форм!ыы спецяального вяла). Модель М назьеваетсее моделью теории Т, если М я Т нмекгг гдянаковую спгнатуру н если после ннтсрпретацяя са каждого яменя отношения чэорян, как одноямсешого о"пюшеняя в модечн, паж!чая акенома теоряя сшановячся нстннныле высказьеваняом. Таким образом, теоряя это перечень названий опюшенпй в свойств эчях огцошеняй, а модель — шо множество, па кочором заданы соствнествуеощеее отпошспяя в выполнены требуемые свойства.

Одна н та же тсоряя люжет пметь много разных моделей. Например, моде.шмн теории Т вЂ” — ((е): (Аь Ам Аз)) еде А, е (Чх)(ее»у)((х еу) о (у<х)); Аз: (»х)(е!у)д»»~)((хау)1«(у з) о (хе )); Аз: (»Ух)(»У»у)((хеу)Ыу«х) о (х =- у)) являются побыв множества чисел, если в качестве с взять отношение «В»яля «>», .любой алфавит с огпошеняеле «-С»(еле. Прнмср 1 9.1) я т. и.

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

е. четко описать модель, па кочорой став»пса задача, н попытеться сфорлеуляровать теорню чуш этой моделя. Так поступают, напрнмср, пря реа.еязацян языка программирования высокого уровня (23). Глава 2 Элементы теории алгоритмов Лекции 6 2.1 Необходимость формального определения алгорит- Переход оч неформального к формальному существенно яеформален! е!Х. Р. Шура-Бура В и. 1.9 мы определили нлгорятм (плн эффектнвнуке процедуру) как то ню заданнуео последовательность правеш, указывающую, какнм образом можно за коночное число шагов получить выходное сообщение определенного вида, пспользуя заданное входное сообщение. Пря этом подчеркнвалось, что действяя, предпнсываемые еьегореетлеоле, должны быть чееоео механя чоскнмн, всем понятнымн я легко выполннмымн; все исполнители алгоритма (людн я автоматы) должны понимать я вьепшенеечь этя дойствяя одинаково. Основным недостатком этого неформалыеого апре;!слепня алгоритма являсггя его расплывчатость: непонятное что зна ент «понямать я выполню ь дсйсчвяя одинаково» я что значит «всем понятные, легко выпшшямые действия».

В самоле деле, 1) алгоритм вычнслення производной многочлена и-й степана прост я яеен тем, кто знып начала аналяза, по д.ш прочих он может быль совершенно непонятным; 2) агшорятле ялн пе алгорятм процедура завязывания пшурков на ботннкаху Скорее всего, неч (попробуйте опшжгь его хепя бы сзовеспо: точное опнсанне требует знания общей чопологнн), хотя шнурки завязываются чисто мсханнчегкя всеми людьми старпю 5 6 лот (эчо проверяется на «вступнтельных экзаменах» вдетскяе сады). Голи бы есс поставленныо мателеатнчсскяе задачи могля быль алгорнтмпчсскя решсные можно бы,ю бы не уточнять понятне алгорятмае когда для рсепеееяя какого-нябчщь класса задач предлаг:сеся конкретный азгорптле, вознпка:ю соглашеняс считать указанный а.егорятм дойствнтельно аепорнтлюм.

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