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

Определение 1.10.2. Моделью (или реляционной системой) называется некоторое множествО М с заданн!2!м на нем нвб01зом ОтнОшений (T! 2 Г2 ....., .T "). Иначе гОНОря, »1 ~2 й модель М это упорядоченная пара объектов М = (ЛХ, (г!', т~~', ..., г„'з')), где г~', г~~2, у;," - ОтнОН1ения на мнОжестве ЛХ. Пример 1.10.3. Модель М! = (Я2 „< ")., где Л множество вещественных чисел, ,,<' - отношение «меньш!». В математике и физике рассматривается специальный класс модел1 й, в которых на, исходном множестве заданы некоторые числовые функции, а отношения выражаются через значения этих функций (1'.м.

Пример 1.10А). Пример 1.10.4. Модель Мэ = (Е, (г2, г22 гД). Пусть на множестве Е задана вещественная неотрицательная функция двух переменных р(х, р), такая, .что р(х, у) = 0 тогда и только тогда, когда х = у, По определению, х и у Е Е находятся в отношении г, тогда и только тогда, когда р(х, р) = 0; х и р Е Е находятся в отношении г22 тогда и только тогда, когда р(х2у) = р(р,х); х и у Е Е находятся в отношении г~з тогда и только тогда, когда р(х,у) < р(х, в) + р(-., у). Например, в качестве множества Е можно взять евклидово пространство, а в качестве функции р(х, у) -- расстояние между точками этого пространства. В определении модели не указано, что же моделируется.

Примеры моделей 1.10.3 и 1.10.4 также не дают ответа на этот воп1эос: что моделируют модели ЛХ! и ЛХ2. Для решения этого вопроса введем понятия теории и сигнатуры. Пусть й» имя (знак) отношения г". Будем говорить, что модель М = 1Л1, (г>', г2', ..., г„**)) имеет сигнатуру Й, если существует правило интерпретации»>, .такое, что р(Лг) = г,>;шя всех г = 1, 2,..., т. Если задана сигнату1>а Й и какая-нибудь иптерпреь>,, тация р этой сигнатуры на множестве ЛХ., то пара 1Л(, х) определяет модель (мы будем называть ес моделью в сигнатур« Й).

Сигнатура это перечень знаков (имен) отношений. Теория это упорядоченная пара Т 1Й, А), где Й сигнатура, а А множество аксиом, высказываний о свойствах сигнатуры Й (обычно в качестве аксиом используются формулы специального вида). Модель М называется модельк> теории Г., если М и Т имен>т одинаковую сигнату- ру и если после интерпретации «> каждого имени отношения теории, как одноименного отношения в модели, каждая аксиома теории становится истинным высказыванием. Таким образом, теория -- это пере тень названий отношений и свойств этих отношений, а модель - это множество, на котором заданы соответствующие отношения и выполнены требуемые свойства.

Одна, и та же теория может иметь много разных моделей. например, моделями теории Т = ((а), (Ан Аг Аз)) где А>. 1Чх)1Чу)11хау) З 1у х)); А2 . (Чх)1Чу)1Чз)11л>ау)й(уаз) з 1х з=)); Аз . 1Чх) 1Чу)11хау)м1уах) з 1х = у)) являются любые множества чисел, если в качестве а взять отноп>ение «<» или «)», любой алфавит с отношением «-С»1скь Пример 1.9.1) и т. п. Возвращаясь к проблеме интерпретации сообщений, отметим, что теория содержит все имена (знаки) и служит основой для составления сообщений. Теория это синтаксис язы- ка сообщений, это правила построения сообщений.

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

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

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

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

е. они невозможны без строгого формального определения алгоритма. Форхлализация понятия алгоритма реализуется с помощью построения алгоритмических моделей. Можно выделить три основных тина универсальных алгоритмических моделей: рекурсивные функции (понятие алгоритма связывается с вычислениями и числовыми функциями), машины Тьюринга (алгоритм представляется как описание процесса работы некоторой машины, способной выполнять лишь небольшое число весьма простых операций), нормальные алгоритмы Маркова (алгоритмы описыван>тся как преобразования слов в произвольных алфавитах). Весьма интересной представляс тся также выбор в качестве основной алгоритмической системы клеточных автоматов [24]. 2.1.1 Рекурсивные функции Рекурсивные функции предложил использовать в 30-х годах про>плого века известный американский математллк Черч (т. н.

Л-исчисление) [29, 331. В 1960 г, другой американский математик Маккарти предложил интерпретируемый алгоритмический язык 1йэр, реализующий Л-исчисление. Изь>к 1лэр особенно популярен в США среди специалистов по искусственному интеллекту. На 1йкр'е написана начинка текстового редактора, Ешасэ, а один из диалектов 1лвр'а [А>>1о1лвр) исш>льзуется в кап'.стве внутреннего языка известной чертежно-графической системы Ап1оСА11. В нашей стране функциональное программирование наиболее последовательно преподается в МИФИ. Нельзя не отметить, что к этому классу алгоритмических моделей принадлежит и самая компактная из них комбинаторно-логическая 1С1., [96, 97[).

2.1.2 Машины Тьюринга В 1936 г. аспирант Алан '1'ьюринг при исследовании алгоритмических проблем разрешимости (одной из знаменитых проолем Гильберта) предложил для уточнения понят>ля алгоритма использовать абстрактную вычислительную машину с очень простым набором операций. Построенная на базе этой машины алгоритмическая теория Тьн>ринга оказалась настолько плодотворной, что ллредвосхитила все последулощие идеи универсальных вычислительных машин с программным управлением, включая идеи автоматизашли программирования.

В знак признания этих заслуг именем Тьюринга названа высшая награда АСМ, ежегодно присуждаемая за наиболее выдающиеся результаты в области информатики. Список лауреатов тьюринговской премии можно найти на сайте АСМ ЫСр://иии. асш. огя/аиагс1в/~аиагс1.1>гш1. В 1942 г, пру>>па британских математиков и филологов под руководством А. Тьюринга успешно применила теорию алгоритмов к разгадке шифров фаплистской Германии [99[. В послевоенное время Тьюринг принимал участие в создании реальных вычислительных машин, по на этот раз фортуна изменила ему и пи один из этих реальных проектов не был доведен до конца.