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

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

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 106 RSS
←   Апрель 2011   →
 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


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


Сайт рассылки: http://rusfaq.ru/issues/8/19/525
Открыта: 17-04-2009

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

Статистика

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

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


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

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

Лучшие эксперты данной рассылки

Асмик Александровна
Статус: Академик
Рейтинг: 7769
∙ повысить рейтинг » 		Абаянцев Юрий Леонидович aka Ayl
Статус: Профессионал
Рейтинг: 2332
∙ повысить рейтинг » 		Лиджи-Гаряев Владимир
Статус: Профессионал
Рейтинг: 1822
∙ повысить рейтинг »

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

Номер выпуска:237
Дата выхода:19.04.2011, 20:00
Администратор рассылки:Асмик Александровна (Академик)
Подписчиков / экспертов:62 / 65
Вопросов / ответов:1 / 1

Вопрос № 182855: Уважаемые эксперты! Пожалуйста, решите задания http://rfpro.ru/upload/5211 BBCode: 21_diskretnaya_matem.doc (7.22 Mб) Ниже приведены условия заданий, взятые из файла, указанного в тек...

Вопрос № 182855:

Уважаемые эксперты! Пожалуйста, решите задания http://rfpro.ru/upload/5211 BBCode: 21_diskretnaya_matem.doc (7.22 Mб)

Ниже приведены условия заданий, взятые из файла, указанного в тексте вопроса.






Отправлен: 14.04.2011, 19:19
Вопрос задал: Посетитель - 367793 (Посетитель)
Всего ответов: 1
Страница вопроса »

Отвечает Жерар (Специалист) :
Здравствуйте, Посетитель - 367793!

1.10 Контрольные задания

1. S1 = A∩B∩D, S2 = (B∩C)∪(B∩E), S3 = (F\C)∪(F∩E). Соответственно, S = S1 ∪ S2 ∪ S3 = A∩B∩D ∪ (B∩C) ∪ (B∩E) ∪ (F\C) ∪ (F∩E).

2.8 Контрольные задания

1. X×X = {x1x1, x1x2, x1x3, x1x4, x2x1, x2x2, x2x3, x2x4, x3x1, x3x2, x3x3, x3x4, x4x1, x4x2, x4x3, x4x4} для всех R. Остальные свойства - в таблице:

R Подмножество Матрица C Рефлексивность Симметричность Транзитивность
< {x1x2, x1x3, x1x4, x2x3, x2x4, x3x4} =
= {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}		 нет, например
1 < 1 - неверно		 x<y ⇒ y>x -
асимметрично,
например,
1<3 ⇒ 3>1		 x<y ∧ y<z ⇒ x<z,
например,
1<2 ∧ 2<4 ⇒ 1<4
> {x2x1, x3x1, x3x2, x4x1, x4x2, x4x3} =
= {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3)}		 нет, например
2>2 - неверно		 x>y ⇒ y<x -
асимметрично,
например,
4>2 ⇒ 2<4		 x>y ∧ y>z ⇒ x>z,
например,
3>2 ∧ 2>1 ⇒ 3>1
≥ {x1x1, x2x1, x2x2, x3x1, x3x2, x3x3, x4x1, x4x2, x4x3, x4x4} =
= {(1,1), (2,1), (2,2), (3,1), (3,2), (3,3), (4,1), (4,2), (4,3), (4,4)}		 x≥x,
например,
3≥3		 x≥y ∧ y&# 8805;x ⇒ x=y -
антисимметрично,
например,
x≥3 ∧ 3≥x ⇒ x=3		 x≥y ∧ y≥z ⇒ x≥z,
например,
2≥1 ∧ 1≥1 ⇒ 2≥1
= {x1x1, x2x2, x3x3, x4x4} = {(1,1), (2,2), (3,3), (4,4)} x=x,
например,
1=1		 x=y ⇒ y=x -
симметрично,
например,
x=4 ⇒ 4=x		 x=y ∧ y=z ⇒ x=z,
например,
x=2 ∧ 2=y ⇒ x=y
≠ {x1x2, x1x3, x1x4, x2x1, x2x3, x2x4, x3x1, x3< /sub>x2, x3x4, x4x1, x4x2, x4x3} =
= {(1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3)}		 нет, например
4≠4 - неверно		 x≠y ⇒ y≠x -
симметрично,
например,
1≠2 ⇒ 2≠1		 x≠y ∧ y≠z ⇒ x≠z
неверно, например,
4≠3 ∧ 3≠4, но 4=4


2. Пусть в первой квартире живут {x1, x2}, во второй - x3, в третьей - все остальные. Тогда






Свойства отношения R:

рефлексивность (xRx) - любой человек живёт в одной квартире с самим собой;

симметричность (xRy ⇒ yRx) - если я живу в одной квартире с кем-то, то и он живёт в одной квартире со мной;

транзитивность (xRy ∧ yRz ⇒ xRz) - сосед моего соседа тоже мой сосед.

3.12 Контрольные задания

1.1. Таблица истинности:



1.2. Таблица истинности для равносильностей 5, 6:



Таблица истинности для равносильностей 10, 11:



Таблица истинности для равносильностей 7 - 9 и 12 - 17:




1.3. Воспользуемся эквивалентными преобразованиями:







< img src="/php/formula.php?id=6170" border="0">



Тогда



1.4. Таблица истинности:



1.5. С учётом эквивалентных преобразований (см. задание 1.3) имеем




1.6. Для реализации функции f в классическом базисе можно взять её исходное представление:



которое уже содержит только операции ¬, ∧, ∨. К базису ИЛИ-НЕ (стрелка Пирса, ↓) можно перейти с помощью эквивалентных замен:


< br>
В данном случае имеем



Аналогично, к базису И-НЕ (штрих Шеффера, \) можно перейти с помощью эквивалентных замен:




В данном случае имеем




1.7. СДНФ на единичных наборах:



Аналитический вид на нулевых наборах (СКНФ):



1.8. СДНФ:



СКНФ:



2. Единичные наборы - (0, 2, 3, 6, 7) = (000, 010, 011, 110, 111) и (1, 2, 5, 6, 10, 13, 14, 15) = (0001, 0010, 0101, 0110, 1010, 1101, 1110, 1111) . Соответственно,




Кар та Карно представляет собой таблицу истинности в двухмерном виде, то есть для функции n переменных он содержит 2k строк и 2n-k столбцов (для удобства выбирают k = n/2 или k = (n-1)/2). При этом переменные в ней упорядочиваются с помощью кода Грея, то есть соседние значения отличаются только одним разрядом.

Для f1 карта Карно будет иметь вид:



Теперь проводим минимизацию. Для этого объединяем клетки, содержащие одинаковые значения (1 для ДНФ и 0 для КНФ) и расположенные по соседству или симметрично относительно осей, в области как можно большего размера, содержащие 2k таких клеток (k = 0...n). При этом крайние строки и столбцы считаются соседними (таблица как бы закольцована в тор), а разные области могут перекрываться. Необходимо найти минимальный набор таких областей, покрывающих все единицы (для ДНФ) и ли нули (для КНФ).

В данном случае очевидно, что множество единиц покрывается двумя областями: x1x и 000 (x означает оба значения - 0 и 1), то есть минимальная ДНФ будет иметь вид:



Путём склеивания (xy ∨ x¬y = x) и поглощения (x ∨¬x = 1, x¬x = 0) получаем:



то есть тот же самый результат. Аналогично для f2 карта Карно будет иметь вид:



и множество единиц можно покрыть областями xx10, 11x1 и 0x01, то есть минимальная ДНФ будет:



Путём склеивания и поглощения получаем:




6.2 Контрольные задания

Для о пределённости пронумеруем вершины графа от 1 до 9 слева направо и сверху вниз, как показано на рисунке.



Минимальное остовное дерево содержит все вершины графа, не содержит циклов и имеет минимальную сумму весов входящих в него рёбер.

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

В данном случае имеем два ребра с минимальным весом 1 - (1,5) и (9,7), начать построение дерева можно с любого из них, например, с (9,7). Затем в соответствии с алгоритмом добавляем рёбра (5,9) (вес 2), (1,5) (вес 1), (1,4) (вес 2), (5,2) (вес 2), (2,6) (вес 3), (3,4) (вес 5) и (8,5) (вес 5). Получаем минимальное остовное дерево, содержащее 8 рёбер общим весом 21.

Алгоритм Прима: на первом шаге в дерево включается любая вершина. На каждом последующем шаге к дереву добавляется вершина, для которой ребро, связывающее её с деревом, имеет минимальный вес. Процесс завершается, когда все вершины оказываются включёнными в дерево.

В данном случае, если начать, например, с вершины 5, то можно добавить вершины 1 (вес ребра 1), 4 (2), 2 (2), 9 (2), 7 (1), 6 (3), 3 (5) и 8 (5). Получаем то же самое минимальное остовное дерево с весом 21.

7.3 Контрольные задания

Пронумеруем вершины графа так же, как и в предыдущем задании.

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

В данном случае вершины имеют следующие степени: 5 - степень 6, 1, 2, 4, 6, 8 и 9 - степень 4, 3 и 7 - степень 3. На первом шаге раскрашиваем в цвет 1 вершины 5, 3, 7, нераскрашенными остаются 1, 2, 4, 6, 8 и 9. На втором шаге раскрашиваем в цвет 2 вершины 1, 6 и 8, нераскрашенными остаются 2, 4 и 9.
На третьем шаге раскрашиваем в цвет 3 оставшиеся вершины (они все несмежные). Хроматическое число графа равно 3.

Раскраска методом Ершова: используется понятие расстояния между вершинами как длины минимального пути между ними. На первом шаге окрашиваем в цвет 1 любую вершину. На каждом последующем шаге находим любую нераскрашенную верши ну на расстоянии 2 от последней раскрашенной и объединяем их в одну так, что все ребра, связывающее нераскрашенные вершины с этими вершинами, заменяются ребрами к этой объединенной вершине. Если же нераскрашенных вершин на расстоянии 2 нет, то выбираем любую нераскрашенную и окрашиваем в следующий цвет.

В данном случае, если мы окрасим в цвет 1 вершину 1, то смежными с ней будут вершины 2 - 5, а на расстоянии 2 будут находиться вершины 6 - 9. Объединим вершины 1 и 6, смежными с новой вершиной будут все остальные, кроме 8. При объединении вершин 1,6 и 8, все остальные вершины будут смежными с 1,6,8, поэтому вершину 2 окрашиваем в цвет 2. Вершина 1,6,8 уже окрашена, вершины 5 и 7 смежны с 2, вершины 3, 4 и 9 находятся на расстоянии 2. Объединим вершины 2 и 9, тогда смежными с 2,9 будут 5 и 7, а на расстоянии 2 будут на ходиться 3 и 4. При объединении вершин 2,9 и 4 оставшиеся нераскрашенными вершины будут смежны с 2,4,9, поэтому вершину 3 раскрашиваем в цвет 3. На расстоянии 2 от неё находится только вершина 5, поэтому объединяем их. На расстоянии 2 от 3,5 находится последняя нераскрашенная вершина 7, поэтому объединяем их в 3,5,7 и заканчиваем раскраску.

Оба метода дают одну и ту же минимальную раскраску графа: {3,5,7}, {1,6,8} и {2,4,9}.

8.4 Контрольные задания

I - начальное событие (исток).

C - конечное событие (сток)

tij - продолжительность работы, началом и концом которой являются события i и j соответственно.

Tр(j) - ранний срок наступления события j, то есть срок, необходимый для выполнения всех работ, предшествующих данному событию. Он определяется по правилу



Tп(i) - поздний срок наступления события i, то есть срок свершения события i, превышение которого вызовет задержку конечного события. Он определяется по правилу




Lкр - путь максимальной длины от истока к стоку.

Tкр - длина критического пути, определяемая выражением


Rп(i,j) - полный резерв времени работы, то есть максимальное количество времени, на которое можно увеличить продолжительность работы (i,j), не изменяя продолжительность критического пути. Определяется по формуле


Rс(i, j) - свободный резерв времени ра боты, то есть максимальное количество времени, на которое можно увеличить продолжительность работы (i,j) или отсрочить её начало, н е изменяя ранних сроков начала последующих работ. Определяется по формуле


В данном случае имеем I = 1, C = 6, Lкр = {(1,2), (2,4), (4,5), (5,6)}, Tкр = 3 + 6 + 5 + 6 = 20.





9.5 Контрольные задания

Законы функционирования автомата Мили:
a1(t+1) = a3z1 V a2z2,
a2(t+1) = a2z1 V a3z2,
a3(t+1) = a4z1 V a1z2,
a4(t+1) = a1z1 V a4z2,
w1(t) = a3z1 V a1z2 V a2z2,
w2(t) = a1z1 V a3z2 V a4z2,
w3(t) = a2z1 V a4z1.

Для входного слова ξ = z2z2z1z2z1z2z1z1z1z2 и начального состояния a1 будем иметь последовательность состояний a1a3a2a2a1a4a4a3a1a3a1 и выходное слово w1w2w3w1w2w2w3w1w2w2.

Законы функционирования автомата Мура:
a1(t+1) = a3 z1 V a2z2,
a2(t+1) = a2z1 V a3z2,
a3(t+1) = a4z1 V a1z2,
a4(t+1) = a1z1 V a4z2,
w1(t) = a2,
w2(t) = a1 V a3,
w3(t) = a4.

Для того же входного слова ξ = z2z2z1z2z1z2z1z1z1z2 и начального состояния a1 будем иметь ту же последовательность состояний a1a3a2a2a1a4a4a3a1a3a1, но другое выходное слово w2w1w1w2w3w3w2w2w2w2w2.

Ответ отправил: Жерар (Специалист)
Ответ отправлен: 15.04.2011, 16:21
Номер ответа: 266711
Россия, Томск
Тел.: 8-923-411-36-58

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

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

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

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

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

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

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

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