Задача о линейной упорядоченности элементов декартова произведения

Целесообразно разъяснить решение этой важной для анализа различных ситуаций задачи на примерах.

Пример 1. Имеются 3 бригады школьников, которые убирают овощи и картофель в подшефном совхозе. За неделю они выполнили план работы следующим образом

Как распределить места между бригадами, предполагая, что важность выполнения плана по каждой культуре одинакова? Можно упорядочить эти бригады по выполнению плана по картофелю, что, кстати, и делается в сводных публикациях в газетах, а если показатели по первой культуре одинаковы, то смотреть по второй и так далее. Это лексикографический способ упорядочения. Ясно, что по этому принципу 1 место надо присудить 3 бригаде.

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

Приведенный способ имеет и свои минусы, так как неравноценно то место, которое занимает бригада по разным показателям. Например, по картофелю 1 место от 3 отличается всего на 0,05 плана, а 3 от 2 - на 0,67 плана. Третий способ упорядочения более тонкий. А именно, поскольку все показатели в первой таблице относительны, то можно сложить показатели по строкам. У кого больше сумма, тот получает первое место. Однако и этот способ не всегда целесообразно применять, ибо даже относительные показатели не всегда имеет смысл складывать.

Приведем следующий пример, иллюстрирующий эту мысль.

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

Хотя все показатели и относительны, складывать их нецелесообразно, так как третий показатель “забьет” первые два. В таких случаях применяется другой способ упорядочения декартовых произведений, открытый совсем недавно и названный способом нормирования. Это на сегодня наиболее тонкий способ оценки положения, который широко сейчас применяется в информатике. Суть его такова:

1) находим наибольший из показателей по данному показателю, и этой школе присваиваем новый показатель 1;

2) остальным школам присваивается та доля единицы, которую составляет ее показатель от показателя, принятого за единицу;

3) складываем все новые показатели школ, и та из них, которая имеет наибольший показатель, занимает 1 место и т.д. Окончательный вид таблицы распределения мест по школам будет такой

Тезаурус

Определение. Пусть р=(А,А,F) - бинарное отношение на множестве А, являющееся упорядоченностью (£). Это отношение r называется древесным порядком, если для всякого xÎА множество S={yÎА½у³x} образует линейно упорядоченное множество.

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

Предметы окружающего мира

Предметы живой природы Предметы неживой природы

Растения Животные Твердые Жидкие Газы

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

Чрезвычайно важным приложением древесного порядка является синтаксический (или другой) анализ фраз естественного языка. Фраза - это как бы ствол дерева, ветвящийся на все более мелкие синтаксические группы - ветви дерева.

Фраза

Группа подлежащего Группа сказуемого

Наречие

Подгруппа сказуемого

Глагол Группа

дополнения

Дополнение

Определение к дополнению

Можно дерево изображать и “растущим вверх”. Такое “дерево” составляющих представляет синтаксическую структуру фразы. Структура непосредственных синтаксических зависимостей (разбор по вопросам), грамматическое управление тоже представляет собой древесный порядок. Оно называется “деревом управления”.

об успехе своих

намерений

Д о п о л н е н и я

Группа дополнения

Подгруппа сказуемого

Группа сказуемых

беспокоился

менее

Иван Петрович

Группа подлежащих

Фраза

Итак, это бинарное отношение позволяет анализировать фразу, чтобы понимать в ней главное и второстепенное. Большинство фраз хорошо организованных естественных языков можно так анализировать. Именно такими фразами мы передаем информацию друг другу. Значит, необходимо изучать саму математическую модель - древесный порядок. Какими свойствами он обладает? Какие взять свойства для составления искусственных языков, в частности языков программирования? Интересное свойство древесного порядка для большинства фраз естественного языка было подмечено американским физиком Ингве, успешно изучающим математическую лингвистику, в 1960 году. Если подниматься от корня дерева (максимального элемента) к верхнему ярусу до концевой точки, то в основном движение будет, во-первых, в одну сторону, а, во-вторых, число поворотов в эту сторону (глубина дерева) не превосходит семи. Средняя глубина фраз русского языка, вообще говоря, не превышает трех. Ингве доказал строго теорему о связи глубины дерева с максимальным количеством названий составляющих (групп). На основании этой теоремы он высказал гипотезу о том, что объем памяти, который участвует в составлении фразы, ограничен величиной примерно семи заполняемых символов (семь отростков дерева). Причиной этого, по Ингве, является ограниченность оперативной памяти у человека (число запоминаемых символов). Эта гипотеза показывает, что создание и изучение математической модели приводит к новым содержательным выводам о связи естественного языка с мыслительными процессами человека. Было бы полезно составить “дерево” непосредственно составляющих каждому школьнику по своей осмысленной фразе. Затем все эти “деревья” схематически изобразить на досках. Проверить указанные свойства. Может быть, всем выбрать минимальный путь по “дереву” для передачи той же информации (сократить число слов во фразе)? Какие ветви дерева “главные”? Таким образом можно придти к идее реферативного перевода с одного языка на другой “пофразно”.

Толерантность

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

1. То, что каждый элемент множества похож сам на себя, можно математически выразить так: для каждого элемента x, принадлежащего множеству Х с бинарным отношением сходства r, упорядоченная пара (x,x)Îr. Как известно, это - свойство рефлексивности бинарного отношения r.

2. Далее: если элемент хÎX похож на элемент yÎХ, то и элемент y похож на элемент x. Это не противоречит нашей интуиции для отношения сходства (похожести). Математически это запишется так:

"x,yÎX((x,y)ÎrÞ(y,x)Îr).

А это уже четкое определение симметричности бинарного отношения r на множестве х. Итак, исследуемое отношение сходства на множестве рефлексивно и симметрично. Но этими свойствами обладает и отношение эквивалентности. Чем же они отличаются? Вероятно, свойством транзитивности. Отношение эквивалентности обладает этим свойством. Отношение “сходства” по интуитивному нашему его пониманию этим свойством, вообще говоря, не обладает. Действительно, мать и дочь могут быть в каком-то смысле похожи друг на друга, дочь и отец - тоже, но жена и муж совсем могут быть в этом смысле не похожи друг на друга.

Приведенные рассуждения наводят на мысль как можно строго определить отношение “сходства”. Но чтобы не было разночтений в смысле слова “сходство” (ведь ему нет определения в естественном языке), новому бинарному отношению дадим и новое название - толерантность. Именно так предложил английский ученый Зиман называть бинарное отношение, соответствующее нашему интуитивному представлению о сходстве (от лат. tоlеrаntiа - терпение). В обиходном языке толерантность означает терпимость к мнениям, взглядам других людей. Зиман же предложил следующее определение этого бинарного отношения.

Определение. Бинарное отношение r на множестве х называется толерантностью (отношением толерантности), если оно рефлексивно и симметрично.

Таким образом, отношение эквивалентности является толерантностью, так как оно обладает этими свойствами, а отношение упорядоченности - нет.

Примеры отношения толерантности.

1. Все отношения эквивалентности.

2. На множестве людей отношение “быть другом”.

3. Отношение принадлежности русских слов одной и той же части речи толерантность, но не эквивалентность, так как слова “стол” и “течь” - существительные, слова “течь" и “идти" - глаголы, но слова “стол” и “идти” не принадлежат одной части речи.

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

А В

С

5. Отношение согласования слов в предложении. Например, существительные согласуются по роду, числу, падежу и т.д. Это отношение толерантно.

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