Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по математике

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 761 RSS
←   Август 2009   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru
Открыта: 14-07-2005

Автор
Калашников О.А.

Статистика

761 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Математика


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный платный хостинг на базе Windows 2008

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Чемпионы рейтинга экспертов в этой рассылке

Гордиенко Андрей Владимирович
Статус: Специалист
Рейтинг: 1633
∙ повысить рейтинг » 		Kom906
Статус: 5-й класс
Рейтинг: 1318
∙ повысить рейтинг » 		_Ayl_
Статус: Студент
Рейтинг: 1088
∙ повысить рейтинг »

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Математика

Номер выпуска:987
Дата выхода:18.08.2009, 20:35
Администратор рассылки:Tigran K. Kalaidjian, Профессионал
Подписчиков / экспертов:227 / 135
Вопросов / ответов:1 / 2

Вопрос № 171321: Здравствуйте эксперты, помогите пожалуйста с задачкой: Сотрудниками фирмы являются ген.директор, главный инженер, главный бухгалтер, начальник цеха, кассир. Введено отношение "начальник - подчиненный" . Определить обратное отношение и су...

Вопрос № 171321:

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

Отправлен: 13.08.2009, 22:33
Вопрос задал: Tribak, Студент
Всего ответов: 2
Страница вопроса »

Отвечает _Ayl_, Студент :
Здравствуйте, Tribak.

Введем обозначения для должностей (и людей, их занимающих):
Ген.директор = Д
Главный инженер = И
Главный бухгалтер = Б
Начальник цеха = Н
Кассир = К

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

Нарисуем матрицу смежности данного отношения:
Код:

   Д И Б Н К
Д 0 1 1 1 1
И 0 0 0 1 0
Б 0 0 0 0 1
Н 0 0 0 0 0
К 0 0 0 0 0


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

Итак, данное отношение анитирефлексивно, антисимметрично, транзитивно (а, следовательно, является отношением строгого порядка), а также асимметрично.

Вводим обратное отношение.
Нам требуется ввести отношение R-1: ∀x, y ∈ {Д, И, Б, Н, К} (x, y) ∈ R-1 ⇔ (y, x) ∈ R.
Таким отношением будет отношение "подчиненный-начальник": (x, y) находятся в данном отношении тогда и только тогда, когда x является подчиненным y.

Матрица смежности этого отношения будет отображением матрицы смежности исходного отнош ения относительно главной диагонали:
Код:

   Д И Б Н К
Д 0 0 0 0 0
И 1 0 0 0 0
Б 1 0 0 0 0
Н 1 1 0 0 0
К 1 0 1 0 0


Данное отношение, как нетрудно видеть, обладает ровно теми же самыми свойствами, что и исходное. Т.е. это отношение строгого порядка и асимметричное.

Теперь переходим к суперпозиции отношений. Мы можем составить 2 суперпозиции: S1 = R • R-1 и S2 = R-1 • R.
Суперпозиция отношений определяется таким образом.
Пусть есть два отношения: R и S на множестве M
Тогда суперпозиция R • S этих отношений будет определять отношение T следующего вида:
ͦ 4;x, y ∈ M: xTy ⇔ ∃z ∈ M: xRz ∧ zSy

Определим матрицы смежности дл я отношений S1 и S2.

S1
---------
Т.к. Н и К не являются начальниками (не входят в отношение R в качестве первого элемента пары), то строки матрицы для Н и К будут нулевыми. Аналогично, т.к. для них не существует подчиненных (не входят в отношение R-1 в качестве второго элемента пары), то столбцы матрицы для Н и К также будут нулевыми.
Далее. Рассмотрим пары (x, x), где x ∈ {Д, И, Б}. Эти пары должны быть в отношении S1, т.к. для них всегда существует такой z из исходного множества (их непосредственный подчиненный), для которого они будут начальником.
Для оставшихся 6-ти вариантов я просто приведу соответствующий элемент z, чтобы показать, что они должны принадлежать S1.
(Д, И): z = Н (ДRН ∧ НR-1И)
(Д, Б): z = К (ДRК ∧ КR-1Б)
(И, Д): z = Н (ИRН ∧ НR -1Д)
(Б, Д): z = К (БRК ∧ КR-1Д)

Пары (И, Б) и (Б, И) в отношение S1 не входят.

Т.о. матрица смежности отношения S1 выглядит так:
Код:

   Д И Б Н К
Д 1 1 1 0 0
И 1 1 0 0 0
Б 1 0 1
0 0
Н 0 0 0 0 0
К 0 0 0 0 0


S2
---------
Тут все гораздо проще.
Т.к. Д не является ни для кого подчиненным, то не существуют z: ДR-1z и zRД. Т.о. строка Д и столбец Д матрицы смежности будут нулевыми.
Остальные элементы будут единичными. Действительно, ∀x, y ∈ {И, Б, Н, К} (x, y) ∈ S2, т.к. xR-1Д ∧ ДRy, т.е. z = Д.

Ма трица смежности:
Код:

   Д И Б Н К
Д 0 0 0 0 0
И 0 1 1 1 1
Б 0 1 1 1 1
Н 0 1 1 1 1
К 0 1 1 1 1

Ответ отправил: _Ayl_, Студент
Ответ отправлен: 14.08.2009, 17:53

Оценка ответа: 5

Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 253231 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
    • Вам помогли? Пожалуйста, поблагодарите эксперта за это!
    Отвечает Гордиенко Андрей Владимирович, Специалист :
    Здравствуйте, Tribak.

    Генеральный директор является начальником для главного инженера, главного бухгалтера, начальника цеха и кассира. Главный инженер является начальником только для начальника цеха. Главный бухгалтер является начальником только для кассира. Начальник цеха не является начальником ни для кого из лиц, перечисленных в условии. Кассир не является начальником ни для кого из лиц, перечисленных в условии.

    Приведенные выше пять предложений и описывают в словесной форме отношение «начальник – подчиненный».

    Примем следующие обозначения: д – генеральный директор, и – главный инженер, б – главный бухгалтер, н – начальник цеха, к – кассир. Построим следующую таблицу (таблица 1).

    Таблица 1
    _ д и б н к
    д 0 1 1 1 1
    и 0 0 0 1 0
    б 0 0 0 0 1
    н 0 0 0 0 0
    к 0 0 0 0 0

    В приведенной таблице заполнение ячеек рассмотрим на примере генерального директора. Генеральный директор (д) находится в первой строке таблицы. В ячейке, расп оложенной на пересечении первой строки и первого столбца, укажем цифру 0 – так мы покажем, что генеральный директор не является начальником для самого себя. В ячейках, расположенных на пересечении первой строки и остальных столбцов, укажем цифру 1 – так мы покажем, что генеральный директор является начальником для главного инженера, главного бухгалтера, начальника цеха и кассира. Заполним указанным способом всю таблицу. В частности, строка, соответствующая кассиру (к), будет состоять из одних нулей: кассир не является начальником ни для кого. То же в нашем случае относится к начальнику цеха.

    Заполненная указанным образом таблица и является матрицей смежности отношения «начальник – подчиненный».

    Отношением, обратным отношению «начальник – подчиненный», будет отношение «подчиненный – начальник».

    Генеральный директор не является подчиненным ни для кого из лиц, перечисленных в условии. Главный инженер является подчиненным только для генерального директора. Г лавный бухгалтер является подчиненным только для генерального директора. Начальник цеха является подчиненным только для генерального директора. Кассир является подчиненным для генерального директора и главного бухгалтера.

    Приведенные выше пять предложений описывают в словесной форме отношение «подчиненный - начальник». Матрица смежности этого отношения приведена ниже (таблица 2). Как видно, она является транспонированной по отношению к матрице смежности отношения «начальник – подчиненный».

    Таблица 2
    _ д и б н к
    д 0 0 0 0 0
    и 1 0 0 0 0
    б 1 0 0 0 0
    н 1 1 0 0 0
    к 1 0 1 0 0

    Матрицы смежности отношений «начальник – подчиненный» и «подчиненный – начальник» можно сделать более компактными. Например, в таблице 1 можно исключить строки «н» и «к», а также столбец «д». Ведь начальник цеха и кассир не являются начальниками для остальных лиц, а генеральный директор не является ничьим подчиненным. Тогда получим следующую таблицу (таблица 3).

    Т аблица 3
    _ и б н к
    д 1 1 1 1
    и 0 0 1 0
    б 0 0 0 1

    В таблице 2 можно исключить строку «д» и столбцы «н» и «к». Тогда получим следующую таблицу (таблица 4).

    Таблица 4
    _ д и б
    и 1 0 0
    б 1 0 0
    н 1 1 0
    к 1 0 1

    Вид матрицы смежности зависит от ее назначения.

    В отношении «начальник – подчиненный» генеральный директор, главный инженер и главный бухгалтер составляют множество «Начальники». Это множество является областью определения, или правой частью, данного отношения. Главный инженер, главный бухгалтер, начальник цеха и кассир составляют множество «Подчиненные» - область значений, или левую часть, данного отношения.

    В отношении «подчиненный – начальник» множество «Подчиненные» является областью определения, или правой частью, а множество «Начальники» областью значений, или левой частью, отношения.

    Обозначим отношение «начальник – подчиненный» как R. Тогда отношение «подчиненный – начальник», являющееся обратным к отношению «начальник – подчиненный» обозначим как R-1. Рассмотрим композицию, или суперпозицию, отношений R и R-1. Обозначим ее как S = R ○ R-1. Для того, чтобы найти результат этой композиции, выпишем все упорядоченные пары, составляющие отношения R и R-1. Имеем
    1) R = {(д, и), (д, б), (д, н), (д, к), (и, н), (б, к)};
    2) R-1 = {(и, д), (б, д), (н, д), (н, и), (к, д), (к, б)}.
    Для отношения R в упорядоченной паре на первом месте стоит начальник, на втором – подчиненный, а для отношения R-1 – наоборот.
    Согласно определению, композицией отношений R и S называют бинарное отношение T, состоящее из всех упорядоченных пар (a, b), для каждой из которых существует элемент c, принадлежащий одновременно правой части отношения R и левой части отношения S, такой, что упорядоченная пара (a, c) принадлежит отношению R, а упорядоченная пара (c, b) принадлежит отношению S. В соответствии с этим определением,
    R ○ R-1 = {(д, д), (д, и), (д, б), (и, д), (и, и), (б, д), (б, и)}. Матрица смежности данной композиции представлена в таблице 5.

    Таблица 5
    _ д и б н к
    д 1 1 1 0 0
    и 1 1 0 0 0
    б 1 0 1 0 0
    н 0 0 0 0 0
    к 0 0 0 0 0

    Строки «н» и «к» и одноименные столбцы из таблицы можно удалить.

    Рассматривая аналогично композицию отношений R-1 и R, получим
    R-1 ○ R = {(и, и), (и, б), (и, н), (и, к), (б, и), (б, б), (б, н), (б, к), (н, и), (н, б), (н, н), (н, к), (к, и), (к, б), (к, н), (к, к)}. Матрица смежности данной композиции представлена в таблице 6.

    Таблица 6
    _ д и б н к
    д 0 0 0 0 0
    и 0 1 1 1 1
    б 0 1 1 1 1
    н 0 1 1 1 1
    к 0 1 1 1 1

    Строки и столбцы «д» из таблицы можно удалить.

    С уважением.
    -----
    Пусть говорят дела

    Ответ отправил: Гордиенко Андрей Владимирович, Специалист
    Ответ отправлен: 14.08.2009, 18:18

    Оценка ответа: 5

    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 253232 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:
    • Вам помогли? Пожалуйста, поблагодарите эксперта за это!

    Оценить выпуск »
    Нам очень важно Ваше мнение об этом выпуске рассылки!

    Задать вопрос экспертам этой рассылки »

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)
    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров »

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

    © 2001-2009, Портал RFpro.ru, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Автор: Калашников О.А. | Программирование: Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2009.6.7 от 15.08.2009
    В избранное