Задания для кр-1144ст_Дискретные структуры

Дискретные структуры Задание на контрольную работу

Задание 1. В таблице задано множество ребер неориентированного графа . Построить остовное дерево графа. Найти центр этого дерева. Найти его высоту.

№	Множество ребер Е
	{(a, b), (a, d), (a, f), (b, c), (c, d), (d, e), (d, f), (f, e), (g, b)}
	{(a, b), (a, d), (a, f), (b, c), (c, f), (d, e), (d, a), (f, e), (g, f)}
	{(a, b), (a, c), (b, c), (c, f), (d, e), (d, f), (f, e), (e, g), (g, c)}
	{(a, b), (a, e), (a, f), (b, c), (c, f), (c, e), (d, e), (f, e), (g, a)}
	{(a, e), (b, c), (b, f), (b, e), (c, d), (c, e), (d, g), (g, e), (g, c)}
	{(a, b), (a, f), (b, d), (b, c), (b, f), (c, d), (d, e), (f, e), (g, e)}
	{(a, b), (a, d), (a, g), (b, c), (c, d), (c, e), (e, f), (e, g), (g, f)}
	{(a, b), (a, d), (a, g), (b, c), (b, e), (c, e), (c, d), (d, f), (e, f), (g, f)}
	{(a, g), (a, f), (b, d), (b, c), (b, e), (c, e), (d, e), (d, f), (e, f), (g, f)}
	{(a, b), (a, g), (b, d), (b, c), (c, d), (c, e), (d, g), (d, f), (e, f), (g, f)}
	{(a, c), (a, f), (b, g), (b, d), (b, e), (c, e), (c, f), (d, g), (d, e)}
	{(a, b), (a, d), (a, g), (b, d), (c, f), (c, e), (e, g), (e, f), (g, f)}
	{(a, b), (a, e), (b, g), (b, c), (b, e), (c, f), (d, f), (g, f), (g, c)}
	{(a, b), (a, g), (b, g), (b, c), (b, e), (c, e), (d, g), (d, e), (e, f), (g, f)}
	{(a, b), (a, g), (b, g), (b, c), (b, e), (b, d), (c, e), (d, f), (e, f), (g, f)}

Задание 2. Пользователем была получена последовательность чисел (см. таблицу) с целью ее сохранения. Разместить указанные числа в вершинах двоичного дерева, одновременно обеспечив упорядочение данной последовательности.

Определить последовательности, которые образуются в результате:

• обхода дерева в прямом порядке;

• обхода дерева в обратном порядке;

• обхода дерева в симметричном порядке.

№	Последовательность чисел
	6, 12, 7, 9, 10, 1, 5, 6, 9, 11, 14, 19, 12, 7, 5, 3, 8, 18, 2, 16
	16, 1, 17, 3, 14, 11, 15, 6, 9, 10, 12, 19, 13, 7, 5, 1, 8, 20, 2, 12
	8, 2, 17, 10, 19, 1, 5, 16, 9, 15, 14, 19, 0, 7, 1, 3, 7, 4, 2, 3
	10, 5, 7, 12, 18, 1, 3, 6, 19, 11, 14, 9, 11, 20, 5, 2, 4, 13, 17, 3
	26, 12, 7, 9, 20, 1, 5, 6, 9, 21, 14, 19, 22, 7, 25, 3, 28, 18, 2, 16
	22, 32, 7, 29, 10, 15, 5, 6, 23, 11, 14, 29, 12, 7, 5, 3, 8, 18, 32, 1
	11, 42, 7, 29, 10, 17, 5, 36, 9, 11, 24, 19, 12, 27, 5, 33, 2, 18, 20, 16
	3, 2, 17, 9, 10, 21, 5, 26, 9, 11, 34, 19, 12, 27, 5, 3, 38, 18, 2, 36
	15, 12, 27, 9, 10, 31, 5, 26, 9, 11, 19, 29, 12, 7, 35, 33, 8, 18, 2, 13
	17, 2, 17, 29, 30, 28, 5, 6, 11, 16, 24, 19, 32, 7, 5, 3, 1, 18, 2, 16
	14, 22, 3, 9, 10, 21, 5, 36, 9, 11, 34, 19, 12, 27, 5, 3, 8, 25, 10, 6
	10, 21, 7, 5, 10, 19, 35, 6, 9, 11, 24, 29, 16, 7, 35, 3, 8, 28, 2, 23
	18, 33, 27, 9, 1, 3, 5, 26, 9, 14, 17, 19, 22, 37, 5, 23, 7, 18, 4, 6
	26, 12, 37, 9, 20, 1, 25, 6, 29, 11, 34, 19, 12, 18, 5, 33, 8, 38, 2, 26
	21, 30, 12, 19, 10, 1, 11, 6, 9, 5, 14, 19, 12, 7, 3, 32, 28, 8, 26, 17

Задание 3. Для заданного в таблице арифметического выражения с помощью стека:

• получить постфиксную форму записи выражения;

• вычислить значение выражения в постфиксной форме записи для a=2, b=5, c=4, d=1, e=-2, f=6.

№	Арифметическое выражение
	a/b^(c+d)/(e+f-a*c)
	(a+b)^c+d/f-e/(b*d)
	a*e/(c+d-b*f)^(a-b)
	a^b+c-d*(e+f)*((a-d)/a)
	(d+(b+c/d)^e-f)*b/a
	(b*c)^(e+f)/(d*a-c/f)
	b-(a+b)/c*d-(e+a)*f
	a+b/c/d*e^(f-a)/c
	a^b/(c*d)+e-f/(a+b)
	(c-d)*a/b*e/f*a^b
	(c+a*(b-c))/d^a-e*f
	(b*c)/(a-b)/d+e^f/a
	(a+b)*(c+d*e)/f-a^b
	a-(b/c+d*e)/f+a^b*c/f
	(a+b/c)*d*e^f+a-b/(d*b)

Задание 4. Проверьте правильность рассуждений средствами логики:

• с помощью эквивалентных преобразований;

• применив правило резолюций.

Вариант 1

Если равнодействующая всех сил, действующих на движущееся тело, не равна 0, то оно движется неравномерно или непрямолинейно, так как известно, что если эта равнодействующая равна 0, то тело движется равномерно и прямолинейно.

Вариант 2

Если все посылки истинны и рассуждение правильно, то заключение правильно. В данном рассуждении заключение ложно. Значит, или рассуждение неправильно, или не все посылки истинны.

Вариант 3

Если в суффиксе данного полного прилагательного или причастия пишется два н, то они пишутся и в соответствующем наречии. Неверно, что в суффиксе данного наречия пишется два н. Следовательно, в суффиксе полного прилагательного или причастия, из которого образовалось наречие, пишется одно н.

Вариант 4

Если целое число больше 1, то оно простое или составное. Если целое число больше 2 и чётное, то оно не является простым. Следовательно, если целое число больше 2 и чётное, то оно составное(здесь присутствует скрытая посылка).

Вариант 5

Если каждый раз в полдень солнце находится в зените и сейчас полдень, то сейчас солнце находится в зените.

Вариант 6

Если нельзя получить воду, то неверно, что имеется в наличии водород и оксид магния. Если имеется углерод, но углекислого газа получить не удалось, то не было в наличии кислорода. Если имеется углекислый газ и вода, то можно получить углекислоту. Можно ли получить углекислоту, если имеется в наличии оксид магния, кислород, водород и углерод.

Вариант 7

Он сказал, что придёт, если не будет дождя.(а на его слова можно полагаться). Но идёт дождь. Значит, он не придёт.

Вариант 8

Джонс утверждает, что не встречал этой ночью Смита. Если Джонс не встречал этой ночью Смита, то либо Смит был убийцей, либо Джонс лжёт. Если Смит не был убийцей, то Джонс не встречал его этой ночью, а убийство было совершено после полуночи. Если убийство было совершено после полуночи, то либо Смит был убийцей, либо Джонс лжёт. Следовательно, убийцей был Смит.

Вариант 9

Если элементарная частица имеет античастицу или не относится к числу стабильных, то она имеет массу покоя. Следовательно, если элементарная частица не имеет массы покоя, то она относится к числу стабильных.

Вариант 10

Прямые a и b или параллельны, или пересекаются, или скрещиваются. Если прямые a и b лежат в одной плоскости, то они не скрещиваются. Прямые a и b лежат в одной плоскости и не пересекаются. Следовательно, прямые a и b параллельны.

Вариант 11

Если философ - дуалист, то он не материалист. Если он не материалист, то он диалектик или метафизик. Он не метафизик. Следовательно, он диалектик или дуалист.

Вариант 12

Перед последним туром футбольного чемпионата сложилась турнирная ситуация, позволяющая утверждать следующее. Если "Динамо" проиграет свой последний матч, то в случае выигрыша "Спартака" он станет чемпионом. Если же "Спартак" выиграет матч и станет чемпионом, то "Торпедо" займёт второе место. В последнем туре первыми стали известны результаты встреч с участием "Динамо" и "Спартака": "Динамо" проиграло, а "Спартак" выиграл. Можно ли в этом случае, не дожидаясь результатов других встреч, утверждать, что "Спартак" стал чемпионом, а "Торпедо" заняло второе место?

Вариант 13

Докажите следующую теорему: если прямая l, принадлежащая плоскости P, не перпендикулярна прямой n, то она не перпендикулярна проекции m прямой n на плоскость P, если верна следующая теорема: если прямая l принадлежит плоскости P и перпендикулярна проекции m прямой n на плоскость P, то прямая l перпендикулярна прямой n.

Вариант 14

Известно, что, если данный многоугольник правильный, то в него можно вписать окружность.

Данный многоугольник правильный, следовательно, в него можно вписать окружность.

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

В данный многоугольник можно вписать окружность, следовательно, он правильный.

Проверить эти утверждения.

Вариант 15

Если число делится на 4, то оно чётное. Число - чётное. Значит,оно делится на 4.

Задание 5. Найти компоненты сильной связности ориентированного графа G=(V,E).

№	Арифметическое выражение
	E={(1,2),(1,6),(2,3),(3,5),(4,2),(5,6),(6,2),(6,4)}
	E={(1,6),(2,1),(3,1),(3,5),(3,6),(4,3),(5,4),(5,6),(6,2)}
	E={(1,4),(1,6),(2,1),(3,1),(3,2),(4,3),(4,5),(4,6),(6,5)}
	E={(1,2),(1,3),(1,4),(2,5),(3,6),(4,2),(4,6),(5,4),(6,5)}
	E={(1,3),(2,1),(4,2),(4,6),(5,4),(6,1),(6,2),(6,3),(6,5)}
	E={(1,2),(1,5),(3,1),(3,2),(4,1),(4,3),(5,4),(6,1),(6,5)}
	E={(1,5),(2,3),(2,6),(3,6),(4,3),(5,4),(6,1),(6,4)}
	E={(1,5),(1,6),(2,1),(2,3),(2,4),(3,4),(4,1),(4,5),(5,6)}
	E={(1,3),(1,4),(1,5),(2,1),(2,5),(2,6),(4,2),(5,3),(6,4)}
	E={(1,6),(2,1),(2,6),(3,1),(3,2),(3,5),(4,3),(5,1),(5,4)}
	E={(1,2),(2,6),(3,1),(3,2),(3,5),(4,1),(4,3),(5,4),(6,1)}
	E={(1,3),(1,4),(1,6),(2,1),(2,3),(3,4),(3,5),(4,5),(6,2)}
	E={(1,2),(2,4),(3,2),(4,3),(5,1),(5,3),(5,4),(6,1),(6,5)}
	E={(2,1),(2,4),(3,2),(4,3),(4,6),(5,1),(5,4),(5,6),(6,3)}
	E={(2,4),(3,1),(3,2),(3,4),(4,5),(5,1),(5,6),(6,3)}

Задание 6. Пусть G = (V, E), V={v₁,v₂,v₃,v₄,v₅} – полный ориентированный граф, каждой дуге (v_i,v_j), i=1..5, j=1..5 которого сопоставлен вес c_ij. Требуется найти в этом графе гамильтонов контур наименьшего веса. Матрица весов:

1	i \ j 1 2 3 4 5 1 ∞ 12 8 24 16 2 8 ∞ 11 6 4 3 17 9 ∞ 27 18 4 22 15 4 ∞ 13 5 18 7 8 23 ∞	2	i j 1 2 3 4 5 1 ∞ 3 23 11 2 2 31 ∞ 25 18 6 3 24 12 ∞ 8 14 4 17 29 13 ∞ 23 5 9 15 7 22 ∞
3	i j 1 2 3 4 5 1 ∞ 20 11 29 8 2 17 ∞ 21 22 19 3 6 15 ∞ 7 16 4 23 3 13 ∞ 25 5 26 9 10 14 ∞	4	i j 1 2 3 4 5 1 ∞ 11 13 27 9 2 15 ∞ 19 2 1 3 22 18 ∞ 25 20 4 7 5 11 ∞ 12 5 15 16 9 14 ∞
5	i j 1 2 3 4 5 1 ∞ 2 41 28 11 2 12 ∞ 35 37 25 3 16 8 ∞ 18 29 4 30 17 28 ∞ 7 5 33 22 15 16 ∞	6	i j 1 2 3 4 5 1 ∞ 16 21 28 7 2 26 ∞ 32 17 11 3 12 26 ∞ 22 8 4 4 13 27 ∞ 18 5 6 17 37 25 ∞
7	i j 1 2 3 4 5 1 ∞ 17 6 23 31 2 28 ∞ 12 11 8 3 37 14 ∞ 9 27 4 25 19 13 ∞ 7 5 8 36 22 15 ∞	8	i j 1 2 3 4 5 1 ∞ 4 18 26 11 2 3 ∞ 27 8 12 3 19 14 ∞ 7 28 4 23 17 19 ∞ 31 5 2 16 24 19 ∞
9	i j 1 2 3 4 5 1 ∞ 10 7 24 16 2 15 ∞ 5 32 26 3 18 13 ∞ 8 11 4 22 20 9 ∞ 17 5 27 30 18 19 ∞	10	i j 1 2 3 4 5 1 ∞ 15 13 22 35 2 28 ∞ 19 26 14 3 31 20 ∞ 6 11 4 28 15 8 ∞ 19 5 11 10 27 23 ∞
11	i j 1 2 3 4 5 1 ∞ 4 18 1 24 2 2 ∞ 11 20 16 3 21 13 ∞ 8 3 4 5 12 9 ∞ 17 5 25 30 27 10 ∞	12	i j 1 2 3 4 5 1 ∞ 11 24 22 7 2 5 ∞ 6 17 22 3 13 19 ∞ 8 9 4 4 14 24 ∞ 11 5 12 28 27 16 ∞
13	i j 1 2 3 4 5 1 ∞ 24 12 16 9 2 7 ∞ 24 14 11 3 13 37 ∞ 35 28 4 26 30 17 ∞ 19 5 21 10 22 23 ∞	14	i j 1 2 3 4 5 1 ∞ 42 35 19 22 2 37 ∞ 28 11 44 3 31 27 ∞ 17 24 4 26 15 28 ∞ 35 5 33 40 21 14 ∞
15	i j 1 2 3 4 5 1 ∞ 5 11 27 13 2 12 ∞ 8 20 17 3 9 18 ∞ 22 29 4 32 30 4 ∞ 14 5 16 26 13 23 ∞