Методические указания по выполнению контрольной работы прошли экспертизу уму утверждено на заседании кафедры информационных технологий

жүктеу/скачать 415.48 Kb.

бет	4/4
Дата	26.08.2023
өлшемі	415.48 Kb.
	#476240
түрі	Методические указания

1 2 3 4

РГР

ПРИЛОЖЕНИЕ А МИНОБРНАУКИ РОССИИ федеральное государственное бюджетное образовательное учреждение высшего образования

Вариант 3
1.Формула включений и исключений.
2.Для каждого из приведенных ниже множеств используйте диаграммы Венна для двух множеств и заштрихуйте те ее части, которые изображают заданные множества
(A ) ))
Рассмотрим множества A={ Выпишите множества
A A ,A .
3.Построить на координатной плоскости отношения r и s , если
r R , r={(x,y) : + }, s R , s={(x ,y) : y . Найти отношения , r ο s ,
r ο . Построить указанные отношения на координатной плоскости .
4. .Существует, ли пример симметричного и транзитивного , но не рефлексивного отношения. Если существует, то привести пример .
5.Найдите код Прюфера дерева

	1		2 
				6
3 		 4	5

	7		8

6. Найти решение рекуррентного соотношения = +3 +1 ,n>2 , =2 , =6 .

7 . Опишите изоморфизм или покажите , что графы не изоморфны

	3 		a 	c

	 4
1		2	b	d

8. Определить являютсяли данные последовательности графическими . В случае положительного ответа нарисовать соответствующий граф
(4,4,4,4,3,3,2,2,2) , (4,4,4,3,3,2,1 ) .
9. Для указанного ниже графа построить его дополнение , реберный граф и геометрически двойственный граф

1 		5
	•
2	3	

10.Доказать , что всякое дерево с n>1вершинами есть двудольный граф .
11. Определите хроматическое число графа

		b
	a		c
h				d
	g 		e
		f

12. Найдите коэффициент при после раскрытия скобок в выражении
.
13.По каналу связи передаются шесть различных символов . Между этими символами нужно поместить 12 пробелов , по крайней мере по два пробела между каждой парой символов . Сколько имеется различных способов расположить символы и пробелы ? Сколько имеется различных способов расположить их , если пробелов 25 ?
14.Сколькими способами можно рассадить 12 человек вокруг стола ,если двое из них отказываются сидеть рядом ?
15.Найти число способов разложить n различных шаров по m различным корзинам ?
16. Поступающий в высшее учебное заведение должен сдать четыре экзамена . Он полагает , что для поступления будет достаточно набрать 17 баллов . сколькими способами он сможет сдать экзамены , набрав не менее 17 баллов и не получив ни одной двойки ? Построить дерево решений .
17. С помощью метода Шеннона –Фано построить двоичный код для вероятностного ансамбля сообщений с указанными распределениями вероятностей :P=(0,2; 0,1; 0,03; 0,03;0,01) Подсчитать энтропию ансамбля сообщений и сравнить ее со средней длиной кодовых слов.

18.Заданы следующие символы с их частотами :

a)постройте дерево Хаффмана ; б) определите код Хаффмана ;
в) найдите вес кода ; г) закодируйте слово moonlightandroses;
д) закодируйте слово roosters ;

символ	частота	символ	частота
a	19	m	7
d	8	n	9
e	20	o	12
i	11	r	11
g	3	s	16
h	1	t	14
l	5

Вариант 4
1. Число всех беспорядков на конечном множестве.
2.Доказать тождество: A Для каждого из приведенных ниже множеств используйте диаграммы Венна для двух множеств и заштрихуйте те ее части , которые изображают заданные множества ;
Выпишите все подмножества множестваA={a , {b,c}, { }.
3.Построить на координатной плоскости отношения r и s , если
r ]0,2[ , r={(x,y) : y= }, s R , s={(x ,y) : y . Найти отношения , r ⃘s ,
r ⃘ . Построить указанные отношения на координатной плоскости .
4.Во множестве положим по определению
Если a+d=b+c. Докажите .что является отношением эквивалентности на данном множестве .Какой вид имеет график этого отношения . Опишите классы эквивалентности .
5.Постройте все деревья с числом вершин
6.Найти решение рекуррентного соотношения =-2 - +1 ,n>2 ,
=1 , =2 .
7.Опишите изоморфизм или покажите , что графы не изоморфны

1 	 3		a 	b
		5			c
2	4		e	d

8. Определить являются ли данные последовательности графическими . В случае положительного ответа нарисовать соответствующий граф
(6;4;3;2;2;2;2;1) , (5;5;5;4;4;3;2;2 ) .
9. Для указанного ниже графа построить его дополнение , реберный граф и геометрически двойственный граф

			

				

10.Восстановите дерево по его коду Прюфера : .
11.Найдите хроматический многочлен графа/

	 d
a 		b
	 e

12.В разложении найдите коэффициент при .
13.Для того, чтобы определить булеву функцию от n булевых переменных , присваивают значение 0 или 1 каждому из 2n упорядоченных наборов из n значений переменных , они могут быть равны 0 или 1 . Напомним , что традиционно 0 означает FALSE ( ложь ) , а 1 означает TRUE ( истина ): a)сколько существует различных булевых функций от n переменных ?b) найдите приблизительно число булевых функций от восьми булевых переменных. Сколько десятичных цифр в этом числе.?с) самодвойственной булевой функцией , принимающей два значения , и определенной на n–битовых двоичных числах с битами , , …, , называетсяфункцияFтакая , что F( , , …, )=F(1- ,1- , …,1- ) .Сколькосуществует самодвойственных булевых функций от n переменных ?
14.В классе , в котором два ряда по восемь стульев , присутствуют 14 учеников . Пять учеников всегда сидят в переднем ряду , а четверо всегда сидят в заднем ряду . Сколькими способами можно рассадить учеников в классе ?
15.Найти число способов раскладки n одинаковых шаров по m различным ящикам ?
16.Сколькимиспособами можно раскрасить квадрат , разделенный на 9 частей , четырьмя цветами , таким образом ,чтобы в первый цвет были окрашены три части, во второй -2 , в третий -3 , в четвертый-1часть.
17.С помощью метода Шеннона –Фано построить двоичный код для вероятностного ансамбля сообщений с указанными распределениями вероятностей: P=(0,24; 0,1; 0,02; 0,02;0,02) Подсчитать энтропию ансамбля сообщений и сравнить ее со средней длиной кодовых слов.
18.Заданы следующие символы с их частотами :
a)постройте дерево Хаффмана ; б) определите код Хаффмана ;в) найдите вес кода ; г) закодируйте слово eastofthesunandwestofthemoon;
д) закодируйте слово lightsout ;

символ	частота	символ	частота
a	25	n	12
b	10	o	20
e	30	r	9
g	7	s	11
h	6	t	15
i	18	u	3
l	8	y	13

Вариант 5
1. Степенная последовательность графа. Лемма о рукопожатиях. Критерий графичности степенной последовательности.
2.Найти элементы множества P , если A={0,3,4,9} , B={1,3,4,7},
C={0,1,2,4,7,8,9} , I={0,1,2,3,4,5,6,7,8,9} и =
Можно ли операцию , ;Доказать тождество
A\B=A
3.Построить на координатной плоскости отношения r и s , если
r ]-2,2[ , r={(x,y) : }, s ]-2,2[ , s={(x ,y) : y . Найти отношения , r ⃘s , r ⃘ . Построить указанные отношения на координатной плоскости .
4. Отношение , где m означает , что n делится на m , частично упорядочивает множество Z+. Доказать ,что любая пара целых чисел имеет относительно этого упорядочивания наименьшую верхнюю границу и наибольшую нижнюю границу .
5.Начертить двоичное дерево с корнем глубины 2 , у которого листьев будет на единицу меньше , чем внутренних вершин .
6. Найти решение рекуррентного соотношения = +1 ,n>1 , =1 .
7. Опишите изоморфизм или покажите , что графы не изоморфны

		1 		b 		d
					c
2 	3	4	5	a		e

8. Определить являютсяли данные последовательности графическими . В случае положительного ответа нарисовать соответствующий граф
(6;3;3;3;3;2;2) , (4;3;2;2;1 ) .
9. Для указанного ниже графа построить его дополнение , реберный граф и геометрически двойственный граф

		
		
				
	
		
			

10.Описать графы , в которых максимальные длины простых цепей равны 2 .
11. Найти хроматический многочлен графа

	f 
	e
	d 
a 		c
	b

12.В разложении найдите коэффициент при .
13.Сколько существует r-значных последовательностей, состоящих из цифр
0,1,2 и 3 , если каждая из этих цифр должна входить в последовательность хотя бы по одному разу ?
14.Сколько решений в целых числах имеет уравнениеx+y+z =8 , причем
x
15.Сколькимиспособами можно разбить 30 рабочих на 3 бригады по 10 человек в каждой бригаде на 10 групп по 3 человека в каждой группе ?
16.Пусть имеется последовательность из 12 чисел. Сколькими способами можно перемножить эти числа , не меняя их порядка записи.
17.С помощью метода Шеннона –Фано построить двоичный код для вероятностного ансамбля сообщений с указанными распределениями вероятностей: P=(0,21; 0,08; 0,04; 0,01;0,01) Подсчитать энтропию ансамбля сообщений и сравнить ее со средней длиной кодовых слов.
18.Заданы следующие символы с их частотами и три множества кодов

символ	частота	код 1	код 2	код 3
a	8	111	1111	111
c	4	101	1110	011
e	13	01	1100	101011
i	9	11011	1001	11011
g	5	0010	1011	001
h	2	1001	1000	000
m	3	0001	1010	100
s	7	10001	0011	10111
t	11	11001	0111	10110

Найдите вес каждого кода и выберите наиболее подходящий для компактного хранения данных .
Вариант 6
1. Двудольные графы. Критерий двудольности графа.
2.Можно ли определить операцию \ через операции Доказать тождество
A\(B ) Упростить выражение с учетом того , что A
3.Построить на координатной плоскости отношения r и s , если
r ]-2,2[ , r={(x,y) : }, s ]-2,2[ , s={(x ,y) : x . Найти отношения ,rο s , r ο . Построить указанные отношения на координатной плоскости .
4.Существует ли пример транзитивного , но ни рефлексивного , ни симметричного отношения. Привести пример в случае существования .
5.Начертите полное двоичное дерево с корнем глубины 3 .
6. Найти решение рекуррентного соотношения = - ,n>2 ,
=1 , =3 .
7.Опишите изоморфизм или покажите , что графы не изоморфны .

	4 		d 	c
	3 
1		2	a	b

8. Определить являются ли данные последовательности графическими . В случае положительного ответа нарисовать соответствующий граф
(6;5;4;4;4;2;1) , (4;4;3;3;3;2;2;1 ) .
9. Для указанного ниже графа построить его дополнение , реберный граф и геометрически двойственный граф


1	2	3
4 	 5	6

10.Описать все деревья реберные графы которых являются деревьями.
11.Определить хроматическое число графа , полученного из полного n-
вершинного графа удалением : а) одного ребра ;б) двух ребер ; в) трех ребер.
12.В разложении найдите коэффициент при .
13.Сколькимиспособами можно расположить вряд девять троек и шесть
пятерок , чтобы никакие две пятерки не стояли рядом .
14.Сколькими способами пять одинаковых рекламных листовок можно распределить по трем почтовым ящикам , если в каждый ящик должна попасть хотя бы одна листовка ? Сколько будет способов , если некоторые ящики могут оказаться пустыми ( порядок размещения листовок по ящикам роли не играет ) .
15.На школьном вечере присутствуют 12 девушек и 15 юношей . Сколькими способами можно выбрать из них 4 пары ?
16.Сколькимиспособами можно разложить 10 книг в 5 бандеролей по 2 книги в каждую ( порядок бандеролей не принимать во внимание )?
17.С помощью метода Шеннона –Фано построить двоичный код для вероятностного ансамбля сообщений с указанными распределениями вероятностей: P=(0,4; 0,04; ) Подсчитать энтропию ансамбля сообщений и сравнить ее со средней длиной кодовых слов.
18. С помощью метода Хаффмена построить двоичный код с минимальной избыточностью для сообщений со следующим распределением вероятностей :
P=(0,3;0,2;0,1;0,1;0,05;0,05; 0,04;0,04;0,04;0,03;0,03;0,02) .

Вариант 7
1.Деревья. Характеризация дерева. Код Прюфера дерева.Восстановление дерева по коду Прюфера.
2.Упростить выражение с учетом того , что A ; Можно ли определить операцию через операции\ , ;A= ⟺A и A
3.Построить на координатной плоскости отношения r и s , если
r R , r={(x ,y) : }, s R , s={(x ,y) : y . Найти отношения , r ⃘s , r ⃘ . Построить указанные отношения на координатной плоскости .
4.Существует ли пример симметричного , но ни рефлексивного . ни транзитивного отношения . Если существует привести пример .
5.Сколько компонент связности имеет лес . содержащий 12 вершин и 10 ребер ?
6.Найти решение рекуррентного соотношения =-6 - +10 ,n>2 ,
=-6 , =27
7. Опишите изоморфизм или покажите , что графы не изоморфны .

1 		4			f 
	5 			d 		e
	6 		a 
2 		3		b 		c

8. Определитьявляютсяли данные последовательности графическими . В случае положительного ответа нарисовать соответствующий граф
(2;2;2;2;1;1;1;1) , (3;3;3;1 ) .
9.Для указанного ниже графа построить его дополнение , реберный граф и геометрически двойственный граф

	1 
			5
2	3	4	6

10. Постройте все деревья с пятью вершинами
11. Определите хроматическое число графа

1 	 2	3

4 	5	6

12.В разложении найдите коэффициент при .
13.Сколько целочисленных решений имеет уравнение x1+x2+x3=14 ,если
-2 x1 x2 и 2 x3 .
14.В группе 25 студентов. Для лабораторных работ их нужно разбить на три подгруппы так , чтобы в каждой подгруппе было хотя бы 5 студентов .Сколькими способами это можно сделать ?
15. Сколькими способами можно посадить n мужчин и n женщин за круглый стол , чтобы никакие два лица одного пола не сидели рядом ? Та же задача , но стол может вращаться и способы , переходящие при вращении друг в друга считаются одинаковыми .
16.Сколькими способами можно разложить в 9 лузах 7 белых шаров и 2 черных ? Часть луз может оказаться пустыми и лузы считаются различными .
17.С помощью метода Шеннона –Фано построить двоичный код для вероятностного ансамбля сообщений с указанными распределениями вероятностей: P=(0,3; 0,04; ) Подсчитать энтропию ансамбля сообщений и сравнить ее со средней длиной кодовых слов.
18.Заданы следующие символы с их частотами :
a)постройте дерево Хаффмана ; б) определите код Хаффмана ;
в) найдите вес кода ; г) закодируйте слово break;
д) закодируйте слово barber ; е) декодируйте 11011011000;
ж)декодируйте11110110111101101;

символ	частота
a	8
b	5
e	10
k	1
r	3

Вариант 8
1.Планарные графы. Формула Эйлера для полиэдров.
2.A⊆B ⊆ ; Доказать тождество A\(A\B)=A Найдите элементы множества P ,если A={0,2,3,7,8} ,B={1,3,6,7,9} , C={0,1,4,7,8,9} ,
I={0,1,2,3,4,5,6,7,8,9} .P=A .
2.Построить на координатной плоскости отношения r и s , если
r R , r={(x,y) : x=5y+3 }, s R , s={(x ,y) : y . Найти отношения , r ⃘s ,
r ⃘ . Построить указанные отношения на координатной плоскости.
4.Сществует ли рефлексивное, но ни симметричное , ни транзитивное отношение .Если существует привести пример .
5.Известно , что дерево T имеет одну вершину степени 4 , семь вершин степени 2 и шесть – степени 1 .Остальные вершины дерева имеют степень 3 .Сколько вершин степени 3 есть у дерева T ?
6. Найти решение рекуррентного соотношения = +4n ,n>1 , =2 .
7.Опишите изоморфизм или покажите , что графы не изоморфны

1 		4	e 		f
	5			d 
	6 			c
2		3	a		b

8 . Определить являютсяли данные последовательности графическими . В случае положительного ответа нарисовать соответствующий граф

(5;2;1;1;1;1;1;1) , (5;5;3;3;3;3 ) .
9. Для указанного ниже графа построить его дополнение , реберный граф и геометрически двойственный граф

	1 		 2
		 3
4				5	6

10.Доказать , что в графе у любых двух простых цепей максимальной длины есть общая вершина .
11.Найти хроматический многочлен графа

c 		d

a		b

12.Определить , сколько рациональных членов содержится в разложении
.
13.Сколькими способами можно выбрать 10 фруктов из трех груш , четырех яблок и пяти бананов ?
14.В магазине Вы решили купить продукты на сумму от 180 до 200 рублей . Магазин предлагает вам молоко: цена одного пакета -38 рублей , выбираем из семи наименований ;яйца –стоимость одного десятка -52 рубля ,выбираем из четырех наименований ;овощную смесь6 цена одной упаковки -46 рублей , выбираем из шести наименований .Сколько разных покупок вы можете совершить в указанном ценовом диапазоне ?
15.У мамы 5 яблок , 7 груш и 3 апельсина .Каждый день в течении15 дней подряд она вручает сыну по одному фрукту. Сколькими способами это может быть сделано ?
16.Сколькими способами можно разложить красных , желтых и зеленых шаров по mразличным корзинам ?.
17.С помощью метода Шеннона –Фано построить двоичный код для вероятностного ансамбля сообщений с указанными распределениями вероятностей: P=(0,4; 0,04; ) Подсчитать энтропию ансамбля сообщений и сравнить ее со средней длиной кодовых слов .
18. С помощьюметода Хаффмена построить двоичный код с минимальной избыточностью для сообщений со следующим распределением вероятностей :
P=(0,2;0,2;0,1;0,1;0,1;0,05;0,05; 0,04;0,04;0,04;0,03;0,03;0,02) .

Вариант 9
1.Эйлеровы графы. Критерий эйлеровости графа.
2.Упростите выражение A ;Известно , что
= =29 , =19 , =11 , , =5 .
Вычислите .
3.Построить на координатной плоскости отношения r и s , если
r ]0,2[ , r={(x,y) : y=x/3 }, s R , s={(x ,y) : y . Найти отношения , r ⃘s ,
r ⃘ . Построить указанные отношения на координатной плоскости.
4. Найдите замыкание относительно рефлексивности , симметричности и транзитивности отношения {(a,a),(a,c),(a,t),(c,e),(e,a),(e,t),(t,t),(t,c)}, заданного на множестве A={a ,c ,e ,t} .
5.Известно , что дерево T имеет две вершины степени 4 , четыре вершины степени 2 и десять –степени 1 . Остальные вершины дерева имеют степени 2 . Сколько вершин степени 2 есть у дерева T.
6.Найти решение рекуррентного соотношения = +3n+4 ,n>1 , =1.
7.Опишите изоморфизм или покажите , что графы не изоморфны

	6 				a 
1 		5	d 	c 		b	f
2 	3	4			e

8.Определитьявляютсяли данные последовательности графическими . В случае положительного ответа нарисовать соответствующий граф
(4;3;3;2;2;2) , (4;4;3;2;1 ) .
9.Для указанного ниже графа построить его дополнение , реберный граф и геометрически двойственный граф.

	1	2

5	4	3

10.Докажите , то два графа G и H изоморфны тогда и только тогда , когда граф
изоморфен .
11.Найдите остовное дерево наименьшей цены для графа

	2	1 	5
5 	3	3		2
1	4		6	1
	4	3	3

12.Найдите коэффициент при в разложении .
13.Сколькими способами можно переставить 26 букв латинского алфавита , чтобы в получившуюся последовательность не входили подпоследовательности
car ,dog , punиbjte .
14.В шкатулке находится семь пар сережек , три пары клипс , одна цепочка и четыре подвески .Сколько различных комплектов украшений из них можно составить , если допускается надеть либо сережки , либо клипсы , а поверх цепочки подвесить только одну подвеску .
15.Надо послать 6 срочных писем . Сколькими способами это можно сделать . если любое письмо можно передать любому изтрех курьеров .
16. Имеется m различных шаров иk различных корзин . Сколькими способами можно разложить шары по корзинам , если пустые корзины не допускаются?
17.С помощью метода Шеннона –Фано построить двоичный код для вероятностного ансамбля сообщений с указанными распределениями вероятностей: P=(0,4; 0,04; ) Подсчитать энтропию ансамбля сообщений и сравнить ее со средней длиной кодовых слов.
18.Заданы следующие символы с их частотами :
a)постройте дерево Хаффмана ; б) определите код Хаффмана ;
в) найдите вес кода ; г) закодируйте слово ghost;
д) закодируйте слово choose ; е) декодируйте 100010010000111101;
ж)декодируйте10001001110111101;з)декодируйте 11100010000100110001;

символ	частота
c	14
e	12
g	3
h	5
o	9
r	4
s	5
t	7
u	6

Вариант 10
1. Неравенство Крафта.
2.Найдите элементы множества A , если A ={1,2,3,4,5}, ={8},
I={1,2,3,4,5,6,7,8}; Если B⊆A , то A ; Упростите выражение
.
3.Построить на координатной плоскости отношения r и s , если r ]0,1[ ,
r={(x,y) : y=x+3 }, s R , s={(x ,y) : + . Найти отношения , r ⃘s , r ⃘ . Построить указанные отношения на координатной плоскости .
4.Верно ли утверждение :если отношения Rи S транзитивны , то отношение

5.Известно , что дерево T имеет две вершины степени 4 , четыре вершины степени 3 и десять –степени 2 . Остальные вершины дерева имеют степени 1 . Сколько вершин степени 1 есть у дерева T.
6. Найти решение рекуррентного соотношения = - +11 ,n>2 , =1 , =5 .
7.Опишите изоморфизм или покажите , что графы не изоморфны

1 	4	a 	b

2 	3	d	c

8. Определить являются ли данные последовательности графическими . В случае положительного ответа нарисовать соответствующий граф
(5;3;3;3;3;2) , (4;4;4;4;3;3 ) .
9. Для указанного ниже графа построить его дополнение , реберный граф и геометрически двойственный граф

	
		

		

10.Пусть G –связный граф , в котором средняя степень вершин больше 2 . Докажите , что в G содержится по крайней мере два цикла .
11.Найдите хроматический многочлен графа

b 			e
	c	 d
a			f

12.Найдите коэффициент при в разложении выражения .
13.В кондитерской продаются шесть различных видов пирожных , Сколькими способами вы можете купить дюжину пирожных? А если нужно купить по крайней мере по одному пирожному каждого вида .
14.Найдите сумму всех четырехзначных чисел , составленных из цифр 1,2,3,4,5. Все цифры чисел должны быть различными .
15.Найти число векторов a=(a1,a2,..,an),координаты которых удовлетворяют условию i=1,2,…,n .
16.В лифт сели 8 человек. Сколькими способами они могут выйти на четырех этажах так . чтобы на каждом этаже вышел хотя бы один человек ?
17.С помощью метода Шеннона –Фано множества построить двоичный код для вероятностного ансамбля сообщений с указанными распределениями вероятностей: P=(0,3; 0,05; ). Подсчитать энтропию ансамбля сообщений и сравнить ее со средней длиной кодовых слов.
18.Заданы следующие символы с их частотами и три множества кодов

символ	частота	код 1	код 2	код 3
a	10	111	1111	111
c	5	101	1110	011
e	12	01	1100	101011
i	9	11011	1001	11011
g	5	0010	1011	001
h	4	1001	1000	000
m	3	0001	1010	100
s	6	10001	0011	10111
t	14	11001	0111	10110

Найдите вес каждого кода и выберите наиболее подходящий для компактного хранения данных.
. Образцы решения задач
1.Доказатьтождество : \ ( )= \ \
Решение :x \ ( ) ⇒x ( ⇒
x ⇒x \ ⇒x \ )\ .
Обратно ,если x , то x \ ⇒
x ⇒⇒x ( ⇒x \ ( ) .
2.Найдите элементы множества , если I={1,2,3,4,5,6} , A\B={1,6} ,
B\A= {3}.
Решение : По определению =(A\B) I={1,2,3,4,5,6}-
универсальное множество , поэтому =I\ =(A\B)
{1,6} {3}={1,3,6}. Значит =I\ ={1,2,3,4,5,6}\{1,3,6}={2,4,5}.
3.Упростите выражение : A
Решение:Запишем A = (A =
(( A ) ( ) =(A ) )=(A I = .
Проделанные преобразования корректны так , как у операции приоритет
перед операцией
4.Найдите замыкание относительно рефлексивности , симметричности и транзитивности отношения {(a ,a), (a,c),(a,g) , (c , e) , (e , a) , (e , g ), ( g , c), (g , g) }
заданного на множестве А={a, c, e ,g }.
Решение : Определение . Замыканием отношения R относительно свойства S
называется такое отношение R*, что : 1) R* обладает свойством S ;
2)R R*; 3) R* является подмножеством любого другого отношения , содержащего R и обладающего свойством S.
Решение : Замыкание относительно рефлексивности заданного отношения имеет вид { (a ,a) ,(c , c) , (e , e) , ( g, g) , (a , c ) , (a , g ) , ( c, e ) , (e ,a ) , (e , g) ,
(g , c) }. Замыкание относительно симметричности –
{(a , a) , (a ,c) , (c ,a) , (a , g) , (g , a) , (c , e) , (e , c) , (e , a) , (a , e) , (e , g) , (g , a) , (g , c) , (c , g) , (g, g) } . Замыкание относительно транзитивности –
{ (a , a) , (a , c) , (a , g) , (c , e ) , (e , a) , (e ,g) , (g , c) , (g , g ) , (a , e) , (c , a) ,
(c , g) , (e , c) , (g , e), (c,c), (e,e), (g,a)} .
5.Является ли отношение S рефлексивным , симметричным , антисимметричным , транзитивным , если :S={ (x , y) : xy>0 , x,y
Решение : Отношение S не рефлексивно так , как пара ( 0 , 0 ) не принадлежит S . Отношение S симметрично так , как если (x , y) , то xy>0 и , следовательно, уx>0 , то есть (y , x) Отношение Sтранзитивно .
Действительно , если (x , y) и ( y , z) , то xy>0 и yz>0 . Поэтому x z>0 и значит xz>0 так , как y
6. Найти решение рекуррентного соотношения =-6 - + , n>2 ,
=1 , =2.
Решение : Если числовая последовательность . то
функция f(x)= называется производящей функцией последовательности . Левую и правую части равенства =-6 - +
умножим на и просуммируем по n от 3 до +
=-6 -9 +
f(x) –x-2 =-6x -9 . Сделав замены переменной суммирования получим f(x) –x-2 =-6x –
-9 - . Окончательно f(x) –x-2 =-6x (f(x) –x)-
-9 f(x) - . f(x)(1+6x +9 x+2 +6 - .
f(x)(1+6x +9 f(x)=
Разложение функции в степенной ряд имеет вид
1+ . При получаем
=1+ =1+ =
1+ . Таким образом f(x)=
( (1+ = –
3 +11 +
f(x)= -3 +
11 +
Таким образом при n>3 =- +11 +
= , .
7 .Докажите , что графы изоморфны

1 	 3		a 	b
		5			c
2	4		e	d

Решение : При изоморфизме вершины одинаковой степени переходят в вершины одинаковой степени , поэтому 5 .Далее возможны варианты :
3 ,4 ,либо 3 . Рассмотрим случай 3 ,4 5 ,1 ,
2 b . Это соответствие является изоморфизмом . Проверить существуют ли другие изоморфизмы .
8.Доказать , что графы не изоморфны

	1 			a 
2 		6	b		f
3 		5	c 		e
	4			d

Решение : Треугольник в графе Gдолжен отображаться на треугольник в любом графе , которому G изоморфен .Во втором графе два треугольника
(a,f,e )и (f , e , d ) , а в первом графе только один треугольник
(1 , 6 , 5 ).Значит данные графы не изоморфны .
9.Найдите коэффициент при в разложении .
Решение : Имеет место полиномиальная теорема :
= .Согласно полиномиальной теореме .= =
Получается система уравнений
2
2 =9 Решения следующие : ( , ) , ( , ) ,
2) 2 =4 Решения следующие : )
Таким образом коэффициент при равен
+ =- - + =11 -2-20+6)=
-11 =-1288 .
10.Показать , что последовательность (4 , 3 , 2,2,1) – графическая . Построить реализацию этой последовательности .
Решение : Критерий графичности правильной n-последовательности .
Правильная n-последовательность dявляется графической тогда и только
тогда . когда для каждого k= верно неравенство
(1) .
Назовемn-последовательность d правильной , если выполняются следующие два условия : 1)n-1 ,
2) -четное число .
, , , , .Проверим выполнение неравенств (1) .
При k=1 левая часть неравенства равна , а правая часть равна
min{2, +min{3, +min{4, +min{5, 2+2+2+1=7>4.
2) -четное число .
, , , , .Проверим выполнение неравенств (1) .
При k=1 левая часть неравенства равна , а правая часть равна
min{2, +min{3, +min{4, +min{5, 2+2+2+1=7>4.
При k=2 левая частьравна 4+3=7 . а правая часть- 2+2+2+1=7. При k=3
4+3+2 .При k=4 4+3+2+2=11 .Значит данная последовательность является графической .Построим ее реализацию.
Число ребер равно 6.

		
				
			
	

11.Формула включений и исключений .
Пусть имеется Nпредметов , некоторые из которых обладают свойствами
, ,…, , при этом каждый предмет может либо не обладать ни одним из этих свойств , либо обладать одним или несколькими свойствами . Обозначим
N( , ,…, –количество предметов , обладающих свойствами
, ,…, и , быть может , еще некоторыми из других свойств . Если нам надо подчеркнуть , что берутся лишь предметы , не обладающие некоторыми
Свойствами , то это свойство пишется со штрихом .например , через
N( , , обозначено количество предметов , обладающих свойствами
, и не обладающих свойством . (Вопрос об остальных свойствах остается открытым).
Формула включений и исключений :
N( )=N-N( )-…- N( ) +N( )+N( )+…+N( )-
-N( )-…-N( ) +…+ N( ).
Пример : Сколько существует перестановок букв w,e,d,i,g,m,a,t,h,в которых последовательности букв не образуют слова «we» , «dig» , «math»? Например,
перестановка d,g,i, w ,e ,t , h ,a ,m не подходит , поскольку включает сочетание букв «we» . Пусть универсум U будет множеством всех перестановок букв
w ,e ,d ,i ,g ,m ,a ,t ,h . Тогда =9!=362880. Пусть –множество всех перестановок , в которых встречается слово «we» .Пусть –множество всех перестановок , в которых встречается слово «dig» . Пусть –множество всех перестановок , в которых встречается слово «math».В задаче требуется найти
или - . Но + + –
- - + . Поскольку буквы «w ,e»должны стоять вместе , множество S1состоит из всех перестановок 8 символов
we ,d ,i , g ,m ,a ,t ,h. Поэтому =8! . Множество состоит из всех перестановок семи символов w .e ,dig ,m,a,t ,h. Следовательно , =7! Множество состоит из всех перестановок шести символов w .e ,d ,i ,g ,math. Следовательно , =6! Множество составляют все перестановки 6 символов
we ,dig ,m,a ,t ,h . Поэтому Множество составляют все перестановки четырех символов w ,e ,dig ,math .Значит
Множество составляют все перестановки пяти символов we ,d ,i ,g ,math .Значит Множество составляют все перестановки
трех символов we ,dig ,math . Поэтому Таким образом
=8!+7!+6!-6!-5!-4!+3!=45222 .Значит =
- 362880-45222=317658.
12.Сколько существует способов разделить 10 человек на две команды по 5 человек для игры в баскетбол ?
Решение: Число способов совпадает с числом сочетаний = = =
2=252.
13.Если в урне имеется 5 красных , 3 зеленых и 7 синих шаров , то сколькими различными способами можно выбрать 10 шаров ?
Решение : Производящая функция имеет вид
(1+x+ + + + )( 1+x+ + )( 1+x+ + + + + + )
Коэффициент при дает решение задачи . Коэффициент при равен 18 .
14.Сколькими способами можно расставить n нулей и k единиц , чтобы
никакие две единицы не стояли рядом .
Решение : запишем n нулей так , что между ними есть по одному свободному месту . Количество таких мест n-1 , плюс два места – перед первым нулем и за последним , итого n+1 место .На эти места требуется записать kединиц.
Если на какое-то место единица не записывается , то два нуля оказываются рядом . Количество способов записи единиц равно .
15.Сколькимиспособами можно распределить 40 одинаковых кубиков в
четыре различных ящика ?
Решение :Промоделируем распределение двоичной строкой из 40 нулей и трех единиц . Выбор мест распределения единиц в строке определяет распределение кубиков : количество нулей до первой единицы соответствует кубикам в первом ящике , между первой и второй единицами – во втором , между второй и третьей единицей – в третьем ,и , наконец . после третьей – в четвертом . Количество способов расстановки единиц равно . В общем случае , при размещении n одинаковых предметов по k ящикам ( некоторые из ящиков могут оказаться пустыми) количество способов определяется как
.Если же в каждом ящике должно быть по крайней мере rпредметов , то количество способов равно .
16.Нарисовать все различные деревья с семью вершинами .
Решение :



17.Определить хроматическое число графа

				2
1 		 2	 1
	 3
		1
2 			3

Так как в графе есть треугольники , то хроматическое число не меньше трех .
Оно равно трем . Цифры в вершинах показывают номера цветов раскраски графа .
18. Для указанного ниже графа построить его дополнение , реберный граф и геометрически двойственный граф

4 		5
	 2
1		3

Решение :

4

5



2



1 

3



1)Дополнение: 2) Реберный граф; 3) Геометрически двойственный граф.

19.Заданы следующие символы с их частотами :

а) постройте дерево Хаффмана ;
б) определите код Хаффмана ;
в) найдите вес кода ;

символ	частота
c	17
d	25
e	10
i	30
s	13
u	5

Сначала упорядочиваем частоты , приведенные в списке часто

(5 ,10 ,13 .17 ,25 , 30 ) . Затем формируем дерево , используя две буквы
С наименьшими частотами ( вероятностями) в качестве вершин и сумму частот ( вероятностей ) в качестве их родителя . Помещаем 0 на ребре к левому сыну и 1 на ребре к правому сыну . В результате получаем дерево

0	1 5	1
u		e

В списке частот заменяем значения двух наименьших частот их суммой . Gосле чего имеем (13 ,15 ,17 ,25 .30). Опять выбираем две вершины или деревья в соответствии с наименьшими числами в списке частот и формируем дерево с этими вершинами или деревьями в качестве сыновей и их суммой в качестве родителя .
В данном случае это будет дерево

0	2 8 	1
s	0	 1
	 u		e

Теперь заменим в списке частот значения двух наименьших частот их суммой .
В результате получим список (17 ,25 , 28 , 30 ) .

0	2 8 	1		0	4 2 1
s	0	 1		c		d
	 u		e

(28, 30, 42)

		5 8	1		4 2
0	 1		i	0		1
s				c		d
	0		1
	u		e

В заключение объединяем два дерева и формируем искомое дерево

		0	 1
			0	 1
0	1		0		 i
c		d	s  1	 1
			0
			 u		e

Таблица кодов Хаффмана

символ	Код Хаффмана
i	11
d	01
c	00
s	100
e	1011
u	1010

20. С помощью метода Шеннона –Фано построить двоичный код для вероятностного ансамбля сообщений с указанным распределением вероятностей : P=( 0 ,18; 0,18 ;0,11 ;0,11 ;0,11 ;0,11 ;0 ,05;0,05 ;0,05 ; 0,05 ) .

Решение :

xi	p(xi)	1-ый шаг	2-ый шаг	3-ый шаг	4-ый шаг	5-ый шаг	Кодовые слова
x1	0 ,18	׀	׀	׀			000
x2	0 ,18		׀	׀׀			001
x3	0 ,11		׀׀	׀			010
x4	0 ,11		׀׀	׀׀			011
x5	0,11	׀׀	׀	׀	׀		1000
x6	0 ,11		׀	׀	׀׀		1001
x7	0,05		׀׀	׀׀	׀		1110
x8	0 ,05				׀׀		1111
x9	0 ,05				׀׀	׀	11110
x10	0 ,05				׀׀	׀׀	11111

Метод Шеннона – Фано :

1.Упорядочить сообщения по убыванию их вероятностей .
2.Подразделить множество сообщений на Dподмножеств так , чтобы вероятности каждого из подмножеств были приблизительно одинаковыми ,
Произвольным образом перенумеровать подмножества , Для всех сообщений из i-го подмножества , i=1 ,2 ,…,D ,положить первый символ кодовых слов равным где A=( - кодовый алфавит .
3.Каждое из подмножеств рассматривать как некоторое новое множество сообщений .Выполнить на j-ом шаге , j=2 ,3 ,…, действия , указанные в пункте 2 для определения j-го символа кодовых слов. Считать ,что действия над данным подмножеством закончены , если оно содержит одно сообщение .

ПРИЛОЖЕНИЕ А

МИНОБРНАУКИ РОССИИ
федеральное государственное бюджетное образовательное учреждение
высшего образования
«Новосибирский государственный университет экономики и управления «НИНХ»
(ФГБОУ ВО «НГУЭУ», НГУЭУ)
Кафедра информационных технологий
^{(наименование кафедры)}

КОНТРОЛЬНАЯ РАБОТА

Дисциплина: _____________Информатика и информационные технологии в профессиональной деятельности______________________________________

Ф.И.О студента: ____________________________________________________
Направление/специальность __________________________________________
Направленность (профиль)/специализация _____________________________
Номер группы: _____________________________________________________
Номер варианта контрольной работы: _________________________________
Номер зачетной книжки: _____________________________________________
Дата регистрации контрольной работы кафедрой: _______________________
Проверил:_________________________________________________________

Новосибирск 2017

жүктеу/скачать 415.48 Kb.

Достарыңызбен бөлісу:

1 2 3 4