Здравствуйте, Посетитель - 367793!

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

1. S[sub]1[/sub] = A[$8745$]B[$8745$]D, S[sub]2[/sub] = (B[$8745$]C)[$8746$](B[$8745$]E), S[sub]3[/sub] = (F\C)[$8746$](F[$8745$]E). Соответственно, S = S[sub]1[/sub] [$8746$] S[sub]2[/sub] [$8746$] S[sub]3[/sub] = A[$8745$]B[$8745$]D [$8746$] (B[$8745$]C) [$8746$] (B[$8745$]E) [$8746$] (F\C) [$8746$] (F[$8745$]E).

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

1. X[$215$]X = {x[sub]1[/sub]x[sub]1[/sub], x[sub]1[/sub]x[sub]2[/sub], x[sub]1[/sub]x[sub]3[/sub], x[sub]1[/sub]x[sub]4[/sub], x[sub]2[/sub]x[sub]1[/sub], x[sub]2[/sub]x[sub]2[/sub], x[sub]2[/sub]x[sub]3[/sub], x[sub]2[/sub]x[sub]4[/sub], x[sub]3[/sub]x[sub]1[/sub], x[sub]3[/sub]x[sub]2[/sub], x[sub]3[/sub]x[sub]3[/sub], x[sub]3[/sub]x[sub]4[/sub], x[sub]4[/sub]x[sub]1[/sub], x[sub]4[/sub]x[sub]2[/sub], x[sub]4[/sub]x[sub]3[/sub], x[sub]4[/sub]x[sub]4[/sub]} для всех R. Остальные свойства - в таблице:

[table]
[row]
[col]R[/col]
[col]Подмножество[/col]
[col]Матрица C[/col]
[col]Рефлексивность[/col]
[col]Симметричность[/col]
[col]Транзитивность[/col]
[/row]
[row]
[col]<[/col]
[col]{x[sub]1[/sub]x[sub]2[/sub], x[sub]1[/sub]x[sub]3[/sub], x[sub]1[/sub]x[sub]4[/sub], x[sub]2[/sub]x[sub]3[/sub], x[sub]2[/sub]x[sub]4[/sub], x[sub]3[/sub]x[sub]4[/sub]} =
= {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}[/col]
[col][/col]
[col]нет, например
1 < 1 - неверно[/col]
[col]x<y [$8658$] y>x -
асимметрично,
например,
1<3 [$8658$] 3>1[/col]
[col]x<y [$8743$] y<z [$8658$] x<z,
например,
1<2 [$8743$] 2<4 [$8658$] 1<4[/col]
[/row]
[row]
[col]>[/col]
[col]{x[sub]2[/sub]x[sub]1[/sub], x[sub]3[/sub]x[sub]1[/sub], x[sub]3[/sub]x[sub]2[/sub], x[sub]4[/sub]x[sub]1[/sub], x[sub]4[/sub]x[sub]2[/sub], x[sub]4[/sub]x[sub]3[/sub]} =
= {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3)}[/col]
[col] [/col]
[col]нет, например
2>2 - неверно[/col]
[col]x>y [$8658$] y<x -
асимметрично,
например,
4>2 [$8658$] 2<4[/col]
[col]x>y [$8743$] y>z [$8658$] x>z,
например,
3>2 [$8743$] 2>1 [$8658$] 3>1[/col]
[/row]
[row]
[col][$8805$][/col]
[col]{x[sub]1[/sub]x[sub]1[/sub], x[sub]2[/sub]x[sub]1[/sub], x[sub]2[/sub]x[sub]2[/sub], x[sub]3[/sub]x[sub]1[/sub], x[sub]3[/sub]x[sub]2[/sub], x[sub]3[/sub]x[sub]3[/sub], x[sub]4[/sub]x[sub]1[/sub], x[sub]4[/sub]x[sub]2[/sub], x[sub]4[/sub]x[sub]3[/sub], x[sub]4[/sub]x[sub]4[/sub]} =
= {(1,1), (2,1), (2,2), (3,1), (3,2), (3,3), (4,1), (4,2), (4,3), (4,4)}[/col]
[col][/col]
[col]x[$8805$]x,
например,
3[$8805$]3[/col]
[col]x[$8805$]y [$8743$] y[$8805$]x [$8658$] x=y -
антисимметрично,
например,
x[$8805$]3 [$8743$] 3[$8805$]x [$8658$] x=3[/col]
[col]x[$8805$]y [$8743$] y[$8805$]z [$8658$] x[$8805$]z,
например,
2[$8805$]1 [$8743$] 1[$8805$]1 [$8658$] 2[$8805$]1[/col]
[/row]
[row]
[col]=[/col]
[col]{x[sub]1[/sub]x[sub]1[/sub], x[sub]2[/sub]x[sub]2[/sub], x[sub]3[/sub]x[sub]3[/sub], x[sub]4[/sub]x[sub]4[/sub]} = {(1,1), (2,2), (3,3), (4,4)}[/col]
[col][/col]
[col]x=x,
например,
1=1[/col]
[col]x=y [$8658$] y=x -
симметрично,
например,
x=4 [$8658$] 4=x[/col]
[col]x=y [$8743$] y=z [$8658$] x=z,
например,
x=2 [$8743$] 2=y [$8658$] x=y[/col]
[/row]
[row]
[col][$8800$][/col]
[col]{x[sub]1[/sub]x[sub]2[/sub], x[sub]1[/sub]x[sub]3[/sub], x[sub]1[/sub]x[sub]4[/sub], x[sub]2[/sub]x[sub]1[/sub], x[sub]2[/sub]x[sub]3[/sub], x[sub]2[/sub]x[sub]4[/sub], x[sub]3[/sub]x[sub]1[/sub], x[sub]3[/sub]x[sub]2[/sub], x[sub]3[/sub]x[sub]4[/sub], x[sub]4[/sub]x[sub]1[/sub], x[sub]4[/sub]x[sub]2[/sub], x[sub]4[/sub]x[sub]3[/sub]} =
= {(1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3)}[/col]
[col][/col]
[col]нет, например
4[$8800$]4 - неверно[/col]
[col]x[$8800$]y [$8658$] y[$8800$]x -
симметрично,
например,
1[$8800$]2 [$8658$] 2[$8800$]1[/col]
[col]x[$8800$]y [$8743$] y[$8800$]z [$8658$] x[$8800$]z
неверно, например,
4[$8800$]3 [$8743$] 3[$8800$]4, но 4=4[/col]
[/row]
[/table]

2. Пусть в первой квартире живут {x[sub]1[/sub], x[sub]2[/sub]}, во второй - x[sub]3[/sub], в третьей - все остальные. Тогда






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

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

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

транзитивность (xRy [$8743$] yRz [$8658$] xRz) - сосед моего соседа тоже мой сосед.

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

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



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



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



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




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











Тогда



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



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




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



которое уже содержит только операции [$172$], [$8743$], [$8744$]. К базису ИЛИ-НЕ (стрелка Пирса, [$8595$]) можно перейти с помощью эквивалентных замен:




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



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




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




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 переменных он содержит 2[sup]k[/sup] строк и 2[sup]n-k[/sup] столбцов (для удобства выбирают k = n/2 или k = (n-1)/2). При этом переменные в ней упорядочиваются с помощью кода Грея, то есть соседние значения отличаются только одним разрядом.

Для f[sub]1[/sub] карта Карно будет иметь вид:



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

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



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



то есть тот же самый результат. Аналогично для f[sub]2[/sub] карта Карно будет иметь вид:



и множество единиц можно покрыть областями 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 - конечное событие (сток)

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

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



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




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

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


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


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


В данном случае имеем I = 1, C = 6, L[sub]кр[/sub] = {(1,2), (2,4), (4,5), (5,6)}, T[sub]кр[/sub] = 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.

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

Законы функционирования автомата Мура:
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) = a2,
w2(t) = a1 V a3,
w3(t) = a4.

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