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

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

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

1 2 3 4

РГР

10.Найти все неизоморфные друг другу графы с n вершинами .

РАЗДЕЛ 3. ЗАДАНИЯ ДЛЯ ВЫПОЛНЕНИЯ КОНТРОЛЬНОЙ РАБОТЫ
Задания для выполнения итоговой контрольной работы

Вариант 1
1.Бинарные отношения. Типы бинарных отношений. Отношение эквивалентности.
2.Доказать справедливость тождеств и включений =
тоA A
3.Найти , , , P ᵒP , ᵒP , P ᵒ для отношений :
P={(x,y) |x,y y
4.Существует ли пример рефлексивного и симметричного, но не транзитивного отношения. Если существует , то привести пример .
5.Известно , что дерево имеет одну вершину степени 3 , шесть вершин степени 2 и семь вершин степени 1 . Остальные вершины дерева имеют степень четыре .
Сколько вершин степени 4 есть у дерева T.
6.Найти решение рекуррентного соотношения =-6 -9 +12 ,n>2 ,
=1 , =2 .
7. Опишите изоморфизм или покажите , что графы не изоморфны .

	2 				 c
1 			3	b 		d

	5	4		a		e

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

	

		

10.Найти все неизоморфные друг другу графы с n вершинами .

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

a 		b
c	
d 		e

12.Найдите коэффициент при в разложении .
13.Короля ,который стоит на нижнем левом поле шахматной доски
8 , нужно переместить на верхнее правое поле . Сколько существует
различных путей для короля, если его можно двигать только вверх и вправо .
14.Сколькими способами преподаватель может распределить 90 баллов между 12 вопросами, если на каждый вопрос должно приходиться не менее четырех баллов.
15. Сколькими способами можно разместить n одинаковых шаров по m
различным корзинам при следующих условиях: a) пустых корзин нет;
b) во второй корзине k шаров; c) в первых k корзинах соответственно
шаров?
16. Цветочница продает тюльпаны пяти разных цветов: пурпурные, кремовые , золотые , янтарные и лиловые . Сколько разных букетов можно составить из пятнадцати тюльпанов , если лиловые цветы не должны входить в букет ни с янтарными , ни с золотыми .
17. С помощью метода Шеннона –Фано построить двоичный код для вероятностного ансамбля сообщений с указанными распределениями вероятностей : P=( ; , ; ; ). Подсчитать энтропию ансамбля сообщений и сравнить ее со средней длиной кодовых слов.
18.Заданы следующие символы с их частотами:
a)постройте дерево Хаффмана; б) определите код Хаффмана;
в) найдите вес кода;г) закодируйте слово ghost;
д) закодируйте слово choose ; е) декодируйте 100010010000111101;
ж)декодируйте10001001110111101;з)декодируйте11100010000100110001;

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

Вариант 2

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

5 		6		b 
	4		a		c

	3 		d 		e
1		2		f

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

			
		

		


10.Найти все неизоморфные деревья с числом вершинn

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

a 			b

	c 	 d

e 			f

12.Найдите коэффициент при после раскрытия скобок в выражении
.
13.Двух первокурсников, трех второкурсников и трех третьекурсников нужно рассадить в один ряд. Сколькими способами это можно сделать, если считать , что однокурсники неразличимы , и если никакие три однокурсника не должны сидеть рядом ?
14. Пароль, открывающий доступ к файлу , состоит из 7 символов . Первые два из них – строчные буквы латинского алфавита ( всего 26 букв ) , последующие два – цифры , а остальные три могут быть как цифры так и строчные буквы . Сколько разных паролей можно написать ?
15. Сколькими способами можно составить трехцветный флаг, если имеется материал пяти различных цветов ? Та же задача, если одна из полос должна быть красной .
16.Поезду, в котором находится n пассажиров , предстоит сделать m остановок . Сколькими способами могут распределиться пассажиры между этими остановками .
17. С помощью метода Шеннона –Фано построить двоичный код для вероятностного ансамбля сообщений с указанными распределениями вероятностей :
P=( 0,25 ; ; ; ;0,01; 0,01) . Подсчитать энтропию ансамбля сообщений и сравнить ее со средней длиной кодовых cлов.
18.Заданы следующие символы с их частотами :
a)постройте дерево Хаффмана ; б) определите код Хаффмана ;
в) найдите вес кода ; г) закодируйте слово eraser;
д) закодируйте слово darker ; е) декодируйте 10010110001100;
ж)декодируйте0011011001111001;

символ	частота	символ	частота
a	8	k	1
d	7	r	4
e	12	s	6

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

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

1 2 3 4