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

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

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

Асмик Гаряка Статус: Академик Рейтинг: 10499 ∙ повысить рейтинг »

Коцюрбенко Алексей aka Жерар Статус: Советник Рейтинг: 4217 ∙ повысить рейтинг »

CradleA Статус: Бакалавр Рейтинг: 2492 ∙ повысить рейтинг »

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

Номер выпуска:	280
Дата выхода:	22.05.2012, 18:00
Администратор рассылки:	Асмик Гаряка (Академик)
Подписчиков / экспертов:	36 / 41
Вопросов / ответов:	5 / 5

Консультация # 186100: Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос: помогите пожалуйста с заданием.......заранее спасибо! Задание. 1) Составить таблицу истинности для данной формулы и привести ее к атомарному виду (А). И получить: (А) в ДНФ ДНФ в СДНФ ДНФ в КНФ ДНФ в СКНФ 2) Булева функция задана единичным на...

Консультация # 186100:

Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
помогите пожалуйста с заданием.......заранее спасибо!
Задание.
1) Составить таблицу истинности для данной формулы и привести ее к атомарному виду (А).
И получить:
(А) в ДНФ
ДНФ в СДНФ
ДНФ в КНФ
ДНФ в СКНФ
2) Булева функция задана единичным набором Е. Получить формулу СДНФ.
Получить СДНФ по Блейку.

Дата отправки: 19.05.2012, 17:27
Вопрос задал: Посетитель - 349343 (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Коцюрбенко Алексей aka Жерар (Советник):

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

1. Составим таблицу истинности:

Множество единиц функции можно покрыть областями 0xx, x11, что соответствует ДНФ:

Для перехода к СДНФ каждую конъюнкцию, в которой недостаёт переменных x, y или z, домножаем соответственно на , или , после чего раскрываем скобки и сокращаем повторяющиеся слагаемые. В данном случае

Для проверки можно сравнить полученную СДНФ с множеством единичных наборов таблицы истинности: каждому набору будет соответствовать одна из конъюнкций, причём переменным с инверсией буд ет соответствовать нулевое значение в таблице.
Для перехода от ДНФ к КНФ ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. Затем верхнее отрицание полученной ДНФ по правилу де Моргана сразу дает нам КНФ:

Для перехода от КНФ к СКНФ в каждую дизъюнкцию, в которой недостаёт переменных x, y или z, добавляем соответственно , или , после чего раскрываем скобки с использованием распределительного закона. В данном случае

Для проверки можно сравнить СКНФ с множеством нулевых наборов таблицы истинности: каждому набору будет соответствовать одна из дизъюнкций, при чём переменным с инверсией будет соответствовать единичное значение в соответствующей строке таблицы.

2. Для единичного набора E = {3, 4, 6, 7} = {011, 100, 110, 111} соответствующая СДНФ получается непосредственно (каждому двоичному набору соответствует одна конъюнкция, нулевым значениям из набора соответствует знак инверсии над соответствующей переменной):

Сокращение ДНФ (СДНФ) по правилу Блейка производится следующим образом: для всех возможных пар конъюнкций вида к ДНФ добавляем слагаемое K₁K₂ (если оно не равно тождественно 0), повторяющиеся слагаемые сокращаем, затем применяем обычное поглощение. В данном случае

Консультировал: Коцюрбенко Алексей aka Жерар (Советник) Дата отправки: 19.05.2012, 20:03 5 нет комментария ----- Дата оценки: 20.05.2012, 16:16

Рейтинг ответа: 0 поблагодарить эксперта

Консультация # 186101:

Здравствуйте! Прошу помощи в следующем вопросе:
помогите пожалуйста с заданием.......заранее спасибо!

Дата отправки: 19.05.2012, 17:32
Вопрос задал: Посетитель - 349343 (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Коцюрбенко Алексей aka Жерар (Советник):

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

1. Составим таблицу истинности:

Множество единиц функции можно покрыть областями xx1, 01x, что соответствует ДНФ:

Для перехода к СДНФ каждую конъюнкцию, в которой недостаёт переменных x, y или z, домножаем соответственно на , или , после чего раскрываем скобки и сокращаем повторяющиеся слагаемые. В данном случае

Для проверки можно сравнить полученную СДНФ с множеством единичных наборов таблицы истинности: каждому набору будет соответствовать одна из конъюнкций, причём переменным с инверсией буд ет соответствовать нулевое значение в таблице.
Для перехода от ДНФ к КНФ ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. Затем верхнее отрицание полученной ДНФ по правилу де Моргана сразу дает нам КНФ:

Для перехода от КНФ к СКНФ в каждую дизъюнкцию, в которой недостаёт переменных x, y или z, добавляем соответственно , или , после чего раскрываем скобки с использованием распределительного закона. В данном случае

Для проверки можно сравнить СКНФ с множеством нулевых наборов таблицы истинности: каждому набору будет соответствовать одна из дизъюнкций, при чём переменным с инверсией будет соответствовать единичное значение в соответствующей строке таблицы.

2. Для единичного набора E = {1, 5, 6, 7} = {001, 101, 110, 111} соответствующая СДНФ получается непосредственно (каждому двоичному набору соответствует одна конъюнкция, нулевым значениям из набора соответствует знак инверсии над соответствующей переменной):

Сокращение ДНФ (СДНФ) по правилу Блейка производится следующим образом: для всех возможных пар конъюнкций вида к ДНФ добавляем слагаемое K₁K₂ (если оно не равно тождественно 0), повторяющиеся слагаемые сокращаем, затем применяем обычное поглощение. В данном случае

Консультировал: Коцюрбенко Алексей aka Жерар (Советник) Дата отправки: 19.05.2012, 20:31 5 спасибо большое!!! ----- Дата оценки: 20.05.2012, 14:39

Рейтинг ответа: 0 поблагодарить эксперта

Консультация # 186102:

Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
Помогите с задание.......пожалуйста....

Задание:

1-Посторить таблицу соседей
2-Посторить матрицу Кирхгофа
3-Вычислить число остовных деревьев
4-Построить остовное дерево минимального веса( по алгоритму Прима)
5- Начертить диаграмму полученного оставного дерева и вычислить его вес
6-Найти цикломатическое число
7- Построить дерево кратчайших путей от вершины (1) с помощью алгоритма Кирхгофа и привести таблицу кратчайших путей
(ниже фото задания)

Дата отправки: 19.05.2012, 17:36
Вопрос задал: Посетитель - 349343 (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Коцюрбенко Алексей aka Жерар (Советник):

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

1. Таблица соседей:

1	2	3	6	8	10
2	1	3	4	7	9
3	1	2	4	9
4	2	10
5	3	8	10
6	1	8	9	10
7	2
8	1	5	6
9	2	3	6
10	1	4	5	6

2. Матрица Кирхгофа K для графа с n вершинами имеет размер n x n. При этом диагональный элемент K_ii равен сумме весов рёбер, смежных с i-ой вершиной; элементы K_ij и K_ji равны взятому со знаком "минус" весу ребра, соединяющего i-ую и j-ую вершины (если вершины не связаны ребром, оба элемента равны 0). Для невзвешенного графа матрицу Кирхгофа определяют аналогично, принимая веса всех рёбер равными единице. В данном случае


3. Согласно теореме Кирхгофа-Трента, если K - матрица Кирхгофа некоторого графа, то все её алгебраические дополнения равны между собой и их общее значение есть число остовных деревьев данного графа. В нашем случае, например,


4. Алгоритм Прима состоит в следующем: на первом шаге искомое дерево состоит из одной произвольно выбранной вершины; на каждом очередном шаге среди рёбер, соединяющих одну из вершин дерева с любой вершиной, не принадлежащей дереву, выбирается ребро с наименьшим весом и добавляется к дереву (вместе с соответствующей вершиной); процесс заканчивается, когда все вершины графа принадлежат дереву.
В данном случае алгоритм Прима даёт следующее минимальное остовное дерево (начинаем с вершины 1):
1→8 (1), 1→6 (2), 1→10 (2), 8→5 (3), 1→3 (5), 3→2 (5), 2→4 (6), 2→9 (8), 2͛ 4;7 (9).

5. Вес полученного минимального остовного дерева будет равен 1 + 2 + 2 + 3 + 5 + 5 + 6 + 8 + 9 = 41.

6. Цикломатическое число графа — минимальное число ребер, которые надо удалить, чтобы граф стал ациклическим (не содержащим циклов). Существует соотношение: сумма цикломатического числа и числа вершин графа равна сумме числа рёбер и числа компонент связности. В данном случае имеем граф с 10 вершинами, 17 рёбрами и 1 компонентой связности, поэтому цикломатическое число будет равно 17 + 1 - 10 = 8.

7. Дерево кратчайших путей от определённой вершины (корня дерева) строится следующим образом. Каждой вершине присваивается определённый "вес" - кратчайшее известное расстояние от него до корня. Первоначально вес корня равен 0, вес остальных вершин - ∞, и все вершины считаются непосещёнными. На очередном шаге выбирается непосещённая вершина с наименьшим весом, и для всех соседних с нею непосещённых вершин их вес сравнивается с суммой весов выбранной вершины и соединяющего их ребра (эта сумма даёт кратчайший путь от корня). Новый вес соседней в ершины равен минимуму этих двух величин. После обновления весов всех соседних непосещённых вершин (если такие имеются) выбранная вершина считается посещённой. Если нет непосещённых вершин, алгоритм завершается.
В данном случае имеем:

	Шаг 1	Шаг 2	Шаг 3	Шаг 4	Шаг 5	Шаг 6	Шаг 7	Шаг 8	Шаг 9	Шаг 10
1	0	0	0	0	0	0	0	0	0	0
2	∞(0+10=10)	10	10	10	10	10(5+5=10)	10	10	10	10
3	∞(0+5=5)	5	5	5	5(4+12=16)	5	5	5	5	5
4	∞	∞	∞	∞(2+13=15)	15	15	15(10+6=16)	15	15	15
5	∞	∞(1+3=4)	4	4(2+3=5)	4	4	4	4	4	4
6	∞(0+2=2)	2(1+12=13)	2	2	2	2	2	2	2	2
7	∞	∞	∞	∞	∞	∞	∞(10+9=19)	19	19	19< /b>
8	∞(0+1=1)	1	1	1	1	1	1	1	1	1
9	∞	∞	∞(2+8=10)	10	10	10(5+9=14)	10(10+8=18)	10	10	10
10	∞(0+2=2)	2	2(2+13=15)	2	2	2	2	2	2	2

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

Путь	Вес
1	0
1→2	10
1→3	5
1→10→4	15
1→8→5	4
1→6	2
1→2→7	19
1→8	1
1→6→9	10
1→10	2

Консультировал: Коцюрбенко Алексей aka Жерар (Советник) Дата отправки: 20.05.2012, 10:37 5 нет комментария ----- Дата оценки: 21.05.2012, 10:28

Рейтинг ответа: 0 поблагодарить эксперта

Консультация # 186103:

Здравствуйте! Прошу помощи в следующем вопросе:
Помогите с заданием...пожалуйста!!!
Задание:

1-Посторить таблицу соседей
2-Посторить матрицу Кирхгофа
3-Вычислить число остовных деревьев
4-Построить остовное дерево минимального веса( по алгоритму Прима)
5- Начертить диаграмму полученного оставного дерева и вычислить его вес
6-Найти цикломатическое число
7- Построить дерево кратчайших путей от вершины (1) с помощью алгоритма Кирхгофа и привести таблицу кратчайших путей
(фото ниже)

Дата отправки: 19.05.2012, 17:38
Вопрос задал: Посетитель - 349343 (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Коцюрбенко Алексей aka Жерар (Советник):

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

1. Таблица соседей:
< td bgcolor="gray"> 5

1	3	5	7	8
2	3	6	7	8
3	1	2	4	5	6	8
4	1	5
5	1	3	6	8	9
6	2	3	9	10
7	1	2	9
8	1	2	3	4	5	9	10
9	5	6	7	8
10	6	8

2. Матрица Кирхгофа K для графа с n вершинами имеет размер n x n. При этом диагональный элемент K_ii равен сумме весов рёбер, смежных с i-ой вершиной; элементы K_ij и K_ji равны взятому со знаком " ;минус" весу ребра, соединяющего i-ую и j-ую вершины (если вершины не связаны ребром, оба элемента равны 0). Для невзвешенного графа матрицу Кирхгофа определяют аналогично, принимая веса всех рёбер равными единице. В данном случае


3. Согласно теореме Кирхгофа-Трента, если K - матрица Кирхгофа некоторого графа, то все её алгебраические дополнения равны между собой и их общее значение есть число остовных деревьев данного графа. В нашем случае, например,


4. Алгоритм Прима состоит в следующем: на первом шаге искомое дерево состоит из одной произвольно выбранной вершины; на каждом очередном шаге среди рёбер, соединяющих одну из вершин дерева с любой вершиной, не принадлежащей дереву, выбирается ребро с наименьшим весом и добавляется к дереву (вместе с соответствующей вершиной); процесс заканчивается, когда все вершины граф а принадлежат дереву.
В данном случае алгоритм Прима даёт следующее минимальное остовное дерево (начинаем с вершины 8):
8→4 (1), 8→5 (2), 4→3 (5), 3→1 (2), 8→2 (6), 2→7 (3), 7→9 (4), 3→6 (7), 6→10 (11).

5. Вес полученного минимального остовного дерева будет равен 1 + 2 + 5 + 2 + 6 + 3 + 4 + 7 + 10 = 40.

6. Цикломатическое число графа - минимальное число ребер, которые надо удалить, чтобы граф стал ациклическим (не содержащим циклов). Существует соотношение: сумма цикломатического числа и числа вершин графа равна сумме числа рёбер и числа компонент связности. В данном случае имеем граф с 10 вершинами, 21 ребром и 1 компонентой связности, поэтому цикломатическое число будет равно 21 + 1 - 10 = 12.

7. Дерево кратчайших путей от определённой вершины (корня дерева) строится следующим образом. Каждой вершине присваивается опр еделённый "вес" - кратчайшее известное расстояние от него до корня. Первоначально вес корня равен 0, вес остальных вершин - ∞, и все вершины считаются непосещёнными. На очередном шаге выбирается непосещённая вершина с наименьшим весом, и для всех соседних с нею непосещённых вершин их вес сравнивается с суммой весов выбранной вершины и соединяющего их ребра (эта сумма даёт кратчайший путь от корня). Новый вес соседней вершины равен минимуму этих двух величин. После обновления весов всех соседних непосещённых вершин (если такие имеются) выбранная вершина считается посещённой. Если нет непосещённых вершин, алгоритм завершается.
В данном случае имеем:

	Шаг 1	Шаг 2	Шаг 3	Шаг 4	Шаг 5	Шаг 6	Шаг 7	Шаг 8	Шаг 9	Шаг 10
1	0	0	0	0	0	0	0	0	0	0
2	∞	∞(2+6=8)	8	8	8(7+6=13)	8	8	8	8	8
3	∞(0+2=2)	2	2	2	2	2	2	2	2	2
4	∞	∞(2+5=7)	7	7	7	7	7	7	7	7
5	∞(0+5=5)	5(2+13=15)	5	5	5	5	5	5	5	5
6	∞	∞(2+7=9)	9(5+9=14)	9	9	9(8+14=22)	9	9	9	9
7	∞(0+10=10)	10	10	10	10	10(8+3=11)	10	10	10	10
8	∞(0+12=12)	12(2+8=10)	10(5+2=7)	7(7+1=8)	7	7	7	7	7	7
9	∞	∞	∞(5+14=19)	19	19(7+8=15)	15	15(9+10=19)	15(10+4=14)	14	14
10	∞	∞	∞	∞	∞(7+11=18)	18	18(9+11 =20)	18	18	18

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

Путь	Вес
1	0
1→3→2	8
1→3	6
1→3→4	7
1→5	5
1→3→6	9
1→7	10
1→5→8	7
1→7→9	14
1→5→8→10	18

Консультировал: Коцюрбенко Алексей aka Жерар (Советник) Дата отправки: 20.05.2012, 14:43 5 нет комментария ----- Дата оценки: 21.05.2012, 10:28

Рейтинг ответа: 0 поблагодарить эксперта

Консультация # 186104:

Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
Помогите с заданием...пожалуйста!!!
Задание:

1-Посторить таблицу соседей
2-Посторить матрицу Кирхгофа
3-Вычислить число остовных деревьев
4-Построить остовное дерево минимального веса( по алгоритму Прима)
5- Начертить диаграмму полученного оставного дерева и вычислить его вес
6-Найти цикломатическое число
7- Построить дерево кратчайших путей от вершины (1) с помощью алгоритма Кирхгофа и привести таблицу кратчайших путей
(фото ниже)

Дата отправки: 19.05.2012, 17:43
Вопрос задал: Посетитель - 349343 (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Коцюрбенко Алексей aka Жерар (Советник):

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

1. Таблица соседей:

1	3	4	5	8	9
2	3	4	5	7	8
3	1	2	7	8	10
4	1	2	5	6	7	8	9
5	1	2	4	7	10
6	4	7	10
7	2	3	4	5	6	9
8	1	2	3	4	9
9	1	4	7	8
10	3	5	6

2. Матрица Кирхгофа K для графа с n вершинами имеет размер n x n. При этом диагональный элемент K_ii равен сумме весов рёбер, смежных с i-ой вершиной; элементы K_ij и K_ji равны взятому со знаком "минус" весу ребра, соединяюще го i-ую и j-ую вершины (если вершины не связаны ребром, оба элемента равны 0). Для невзвешенного графа матрицу Кирхгофа определяют аналогично, принимая веса всех рёбер равными единице. В данном случае


3. Согласно теореме Кирхгофа-Трента, если K - матрица Кирхгофа некоторого графа, то все её алгебраические дополнения равны между собой и их общее значение есть число остовных деревьев данного графа. В нашем случае, например,


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

В данн ом случае алгоритм Прима даёт следующее минимальное остовное дерево (начинаем с вершины 1):
1→9 (1), 1→8 (3), 9→7 (3), 9→4 (4), 4→2 (2), 7→5 (3), 3→10 (4), 4→6 (2), 7→5 (6).

5. Вес полученного минимального остовного дерева будет равен 1 + 3 + 3 + 4 + 2 + 3 + 4 + 2 + 6 = 28.

6. Цикломатическое число графа - минимальное число ребер, которые надо удалить, чтобы граф стал ациклическим (не содержащим циклов). Существует соотношение: сумма цикломатического числа и числа вершин графа равна сумме числа рёбер и числа компонент связности. В данном случае имеем граф с 10 вершинами, 24 рёбрами и 1 компонентой связности, поэтому цикломатическое число будет равно 24 + 1 - 10 = 15.

7. Дерево кратчайших путей от определённой вершины (корня дерева) строится следующим образом. Каждой вершине присваивается определённый "вес" - крат чайшее известное расстояние от него до корня. Первоначально вес корня равен 0, вес остальных вершин - ∞, и все вершины считаются непосещёнными. На очередном шаге выбирается непосещённая вершина с наименьшим весом, и для всех соседних с нею непосещённых вершин их вес сравнивается с суммой весов выбранной вершины и соединяющего их ребра (эта сумма даёт кратчайший путь от корня). Новый вес соседней вершины равен минимуму этих двух величин. После обновления весов всех соседних непосещённых вершин (если такие имеются) выбранная вершина считается посещённой. Если нет непосещённых вершин, алгоритм завершается.
В данном случае имеем:

	Шаг 1	Шаг 2	Шаг 3	Шаг 4	Шаг 5	Шаг 6	Шаг 7	Шаг 8	Шаг 9	Шаг 10
1	0	0	0	0	0	0	0	0	0	0
2	∞	∞	∞(3+8=11)	11(4+8=12)	11(5+2=7)	7(6+13=19)	7	7	7	7
3	∞(0+6=6)	6	6(3+10=13)	6	6	6	6	6	6	6
4	∞(0+11=11)	11(1+4=5)	5(3+7=10)	5(4+11=15)	5	5	5	5	5	5
5	∞(0+7=7)	7	7	7(4+6=10)	7(5+13=18)	7	7(7+9=16)	7	7	7
6	∞	∞	∞	∞(4+10=14)	14(5+14= 19)	14	14	14	14(10+2=12)	12
7	∞	∞(1+3=4)	4	4	4	4	4	4	4	4
8	∞(0+3=3)	3(1+14=15)	3	3	3	3	3	3	3	3
9	∞(0+1=1)	1	1	1	1	1	1	1	1	1
10	∞	∞	∞	∞	∞	∞(6+4=10)	10	10(7+12=19)	1 0	10

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

Путь	Вес
1	0
1→9→4→2	7
1→3	6
1→9→4	5
1→5	7
1→3→10→6	12
1→9→7	4
1→8	3
1→9	1
1→3→10	10

Консультировал: Коцюрбенко Алексей aka Жерар (Советник) Дата отправки: 21.05.2012, 05:51 5 огромное спасибо!!!!!!!!! ----- Дата оценки: 21.05.2012, 10:28

Рейтинг ответа: 0 поблагодарить эксперта

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль