2.9. Представления

Наш мозг воспринимает не окружающую реальность, а модель этой реальности, которая формируется с помощью наших органов восприятия: зрительной, слуховой, обонятельной, вкусовой и тактильной системами. Затем эта модель получает представление в нервной системе с помощью нейронов и их синапсов. Нам почти неизвестен физиологический механизм, с помощью которого информация кодируется и запоминается и как осуществляется доступ к ней. Согласно К. Лоренцу это представление является визуальным отображением реальности. У приматов необходимость в интеллекте возникла потому, что они были принуждены, чтобы выжить во враждебном мире, “планировать” свои действия и поступки, “размышлять”. Многочисленные следы этого преобладающего влияния отношений с окружающим миром на нашу систему мышления сохранились в лексике современного языка, например: видеть, схватить,

понять; уровень, план, глубина; очевидный, скрытый, темный. Это тот вид лексики, который связан с абстрактными понятиями и служит для их выражения. Несмотря на то что способность к абстрактному восприятию является свойством именно человека, тем не менее это свойство не является врожденным. Ребенок вырабатывает в себе эти абстрактные понятия постепенно, шаг за шагом, постигая физические инварианты только после долгого ученичества. Согласно Пиаже, способность к внутреннему представлению о весе или объеме объектов формируется у человека к 13—14 годам. Недостатком при этом является только то, что мало-помалу это абстрактное представление о мире ведет индивидуума к чистому абстрактному мышлению, уже независимому от всякой опоры на окружающее и отделенное от любого немедленного действия.

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

2.9.1. Математическая форма записи

Все обычные системы заииси содержат, с одной стороны, символы, представляющие объекты, и, с другой стороны, символы, представляющие операторы, позволяющие связывать объекты между собой. Так, в выражении являются объектами, а знаки и — операторами. Операторы могут связывать некоторое множество объектов (например, операторы и два объекта (бинарные операторы , а также относиться к одному объекту (унарные операторы ). Операторы типа “если ... то, ... иначе ...” (“если да ... то, ... если нет ...”) встречаются в языках программирования. В общем случае правильно построенное выражение или терм представляет собой -арный оператор вместе с объектами. По отношению к -арному оператору говорят также, что его вес равен

Правильно построенное выражение само может рассматриваться как новый объект, который в свою очередь может быть связан с другими объектами с помощью какого-то оператора, следуя тому же закону образования выражений, что и ранее. В результате мы получаем терм — -арный оператор вместе с термами. Такое определение терма через другие термы называется рекурсивным. Оно имеет смысл только тогда, когда априорно существуют исходные термы, являющиеся объектами

Среди этих исходных объектов в общем случае некоторые могут быть заменены другими объектами или даже термами (переменные), а другие — не могут быть заменены (константы). Так, в тригонометрическом выражении может быть заменен любым термом, чего нельзя сказать символах 1 и 2, ни о символах Эти понятия будут уточнены в гл. 3 при рассмотрении формальных систем.

2.9.2. Линейные формы записи

Книгопечатание привело математиков к тому, что они стали записывать свои формулы в виде линейной строки, читаемой слева направо в европейском мире. В этой форме записи, называемой линейной, существуют три возможности расположения оператора: впереди или позади термов, которыми они управляют, или же между ними. Находят применение все эти три формы записи, но они не являются равнозначными.

В наиболее общей форме записи, называемой инфиксной (или нефиксированной формой), операторы расположены среди термов и, чтобы облегчить чтение, приходится добавлять новые символы — скобки: которые не входят в основной набор символов. Они не очень удобны при письме, и ими пользуются, только чтобы устранить неоднозначность или разделить на части слишком длинное выражение: Кроме того, для устранения неоднозначности условились об определенной иерархии применения операторов. Например, в алгебре выражение с будет интерпретироваться как , а не как Свойства ассоциативности и коммутативности некоторых операторов (и особенно операторов и неявно подразумеваются в обычном математическом анализе. Например, пишут или или причем чаще всего оператор умножения при записи формул опускается. Однако фантазия математиков идет дальше, и, например, унарные операторы записываются на трех уровнях. Основные варианты записи таковы: Знак — является одновременно унарным и бинарным оператором. Следовательно, обычная нефиксированная форма записи выражений далека от определенности и строгости.

В математической логике предпочтительной является префиксная форма записи. Каждый оператор в этом случае записывается перед термами, которыми он управляет. Таким образом, обычная запись “х оператор у" приобретает вид “оператор ху”, причем запись “оператор z” не изменяется.

В этой форме записи любые скобочные системы становятся ненужными, а лаконичность и определенность формы записи с

расположением оператора в начале каждого терма делает ее (после некоторой тренировки) весьма удобной для использования.

Выражение записанное в инфиксной форме, получает в префиксной форме вид

Выражение (Т)

будет выглядеть так

Основная теорема префиксной формы записи. Последовательность символов является правильно построенной в форме польской префиксной записи, если и только если:

(см. скан)

Доказательство этой теоремы проводится по индукции на множестве символов Важным следствием этого результата является возможность построения алгоритма для отыскания в заданном выражении места, где заканчивается терм, который начинается в заданной позиции.

Так, например, для идущей ниже последовательности символов (с соответствующими им рангами) имеем для терма, который начинается стрелкой, его окончание на знаке 2:

Заметим, что запись в инфиксной форме, если она дополнена скобками, может рассматриваться как префиксная запись и поддается верификации с помощью описанной выше процедуры. При этом открывающая скобка рассматривается как бинарный оператор, а закрывающая скобка — как константа. Другие ранги остаются при этом неизменными. Тогда, например, выражение с бинарным оператором будет выглядеть так:

В суффиксной (или постфиксной) форме записи оператор помещается сразу после соответствующих термов и выражение “х оператор у" будет записано как “ху оператор”, а выражение “оператор z” запишется как “z оператор”.

Выражение (Т) в суффиксной форме записи выглядит так:

Эта форма записи удобна, в частности, когда хотят оценить, т. е. вычислить, представленное выражение; например, при машинных вычислениях или при компиляции языков программирования формулы, введенные в инфиксной форме, переводят в постфиксную форму. В такой форме записи при прочтении выражения слева направо удается вычислить его значение за один проход (рис. 2.10 а).

Рис. 2.10 а.

2.9.3. Нелинейные формы записи

При типографском способе печати линейная форма записи в виде строк не дает наглядного представления о структуре выражений. Все символы выглядят равнозначными, хотя известно, что некоторые из них являются терминальными (переменные и константы), а другие нет. Если быть точным, то следует отметить, что каждый оператор управляет заданным числом известных термов. Чтобы отразить этот факт, используются представления выражений в форме чертежей или диаграмм. Примеры таких графических схем (графов) представлены ниже:

Графы такого типа получили название деревьев. Они хорошо соответствуют нашим зрительным представлениям,

Рис. 2.106. Представление выражения в виде дерева.

например, о таких выражениях, как выражение граф котарого представлен на рис. 2.10б.

Следует отметить тот факт, что такая форма записи содержит и три другие формы записи:

• префиксная форма выявляется при просмотре дерева сверху вниз и слева направо при записи символов в том порядке, в котором они при этом встречаются;

• постфиксная форма образуется при просмотре дерева в последовательности, обратной предыдущей;

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

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

2.9.4. Машинное представление выражений

Память ЭВМ характеризуется большим объемом и высокой скоростью обращения к ней, что позволяет избежать ограничений, присущих возможностям человека, передав ЭВМ обработку структур типа дерева. При этом каждому символу какого-либо выражения соответствуют три определяющие его характеристики: собственно имя символа, имя символа-“сына”, расположенного слева от основного символа, и имя символа - “брата”, расположенного справа. “Сыновьями” являются первые символы соответствующих термов. Множество имен символов выражения последовательно образует столбец таблицы множество имен “сыновей" дает столбец таблицы, а множество имен “братьев” — столбец Все три столбца, объединенные

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

Рис. 2.10 в. Машинное представление выражения (7).

Если соответствующие элементы столбцов и на уровнях не пусты, они позволяют продолжить просмотр дерева.

Терминальные вершины дерева или листья, являющиеся переменными или константами, не имеют “сыновей”. В этом случае соответствующее значение равно пустому символу 0.

Таким образом, для данного индекса имеем

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

Множество столбцов таблиц образует списковую структуру, которая удобна для обработки символов на ЭВМ. Уже встречавшееся нам выражение (7)

представлено на рис. 2.11 в виде списка.

Замечания

1. Само выражение маркируется заголовком списка, т. е. индексом его первого символа в системе Следовательно, в нашем примере выражение будет обозначено числом 112.

2. Чаще всего в столбце содержится на самом деле не имя символа, а индекс, который отсылает к специальному машинному словарю, используемому программой.

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

(кликните для просмотра скана)

4. При использовании рассматриваемого представления выполнение фундаментальной операции замещения переменной термом (операции подстановки) существенно облегчается. Например, допустим, что в выражении нужно заменить на Последний терм уже присутствует в списке, представленном на рис. 2.11, например, с индексом 432. В этом случае для выполнения подстановки достаточно изменить номер слева от и положить . В этом случае указатель 140 становится ненужным, так как он не соответствует никакому элементу в или

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

6. Иногда списки забиваются узлами, ставшими ненужными, поэтому для помещения в них новых триплетов предварительно запускают программу-чистильщика — сборщик мусора”.