Задание

ЗАДАНИЕ 1.

Для заданных множеств А, В и С найти следующие множества:

(Здесь использованы следующие обозначения:

N – множество натуральных чисел,

Z – множество целых чисел).

№ варианта	A	B	C
5.	{a, b, c, d, f, g}	{c, d, f, g, h, e, j}	{первые 12 букв латинского алфавита}

ЗАДАНИЕ 2.

По заданной диаграмме Эйлера–Венна описать множество, заданное штриховкой.

5.

ЗАДАНИЕ 3.

Решите следующие задачи, используя диаграммы Эйлера–Венна.

№ варианта	Задание
5.	Из 64 студентов на вопрос, занимаются ли они в свободное время спортом, утвердительно ответили 40 человек; на вопрос, любят ли они слушать музыку, 30 человек ответили утвердительно, причем 22 студента занимаются спортом и любят слушать музыку. Сколько человек не увлекается ни спортом, ни музыкой?

ЗАДАНИЕ 4.

Описать на языке теории множеств запрос к базе данных о нахождении указанного множества.

№ варианта	Задание
5.	Найти множество иногородних студентов института, поступивших по результатам единого государственного экзамена, обучающихся на втором курсе, с указанием их фамилий и результатами ЕГЭ по каждому из вступительных испытаний.

ЗАДАНИЕ 5.

Для заданных множеств А и В установить тип соответствия.

№ варианта	А	В	у=f(х)
5.	{x: }	{x: |x|£2}

ЗАДАНИЕ 6.

Построить матрицу и граф бинарного отношения и определить тип этого отношения.

№ варианта	Задание
5.	Быть в сумме чисто мнимым числом на множестве {1+2i, -1-3i, -2+4i, 2-5i, 6}

ЗАДАНИЕ 7.

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

№ варианта	Задание
5.	(–5a – b + 3)2

ЗАДАНИЕ 8.

Решите следующие задачи по комбинаторике (в случае возможности различных толкований условий выбрать любое и пояснить).

№ варианта	Задание
5.	В портмоне 4 отделения. Сколькими способами можно разложить 2 денежные купюры, чтобы в отделении было не более одной купюры?

ЗАДАНИЕ 9.

Построить таблицу истинности для следующих выражений и представить их в СДНФ и СКНФ.

№ варианта	Задание
5.

ЗАДАНИЕ 10.

Упростить логическое выражение. Осуществить переход к стандартному базису (отрицание только над логическими переменными) и построить схему из функциональных элементов.

№ варианта	Задание
5.

ЗАДАНИЕ 11.

Найти МДНФ и МКНФ для логической функции f(x1,x2,x3), заданной таблицей истинности

а) методом Квайна-Мак-Клосски;

б) методом карт Вейча.

№ варианта Переменные	5.
х1	х2	х3	f(x1,x2,x3)
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

ЗАДАНИЕ 12.

Найти инварианты неориентированных графов (число вершин, число ребер, число компонент связности, цикломатическое число, хроматическое число, плотность графа, вектор степеней вершин, матрицу смежности, матрицу инциденций).

ЗАДАНИЕ 13.

Найти инварианты ориентированного графа (число вершин, число дуг, число компонент связности, цикломатическое число, хроматическое число, плотность графа, вектор степеней и полустепеней вершин, матрицу смежности, матрицу инциденций).

ЗАДАНИЕ 14.

1. Проверить, является ли граф, изображенный на рисунке, эйлеровым или полуэйлеровым.

2. Найти эйлеров путь или эйлеров цикл.

3. Проверить достаточное условие гамильтоновости графа, изображенного на рисунке (теорему Г. Дирака).

4. Найти гамильтонов путь или цикл, если они существуют.

5. Сделать вывод о гамильтоноввости или полугамильтоновости заданного графа.

5.

ЗАДАНИЕ 15.

Найти кратчайший путь и его длину из вершины v0 в вершину u.

5.

ЗАДАНИЕ 16.

Найти минимальное остовное дерево

·  для четных номеров вариантов - с помощью жадного алгоритма (алгоритма Краскала);

·  для нечетных номеров вариантов - с помощью алгоритма ближайшего соседа (алгоритма Краскала).

Для выполнения этого задания используйте графы из задания 15, предварительно заменив дуги на рёбра.

ЗАДАНИЕ 17.

Для заданной таблицы конечного абстрактного инициального автомата выполнить следующие действия:

1) описать автомат;

2) построить диаграмму Мура;

3) для заданного начального состояния автомата, отмеченного символом «*» и заданного входного слова x, найти выходное слово y и конечное состояние, в котором будет находиться автомат.

5.	Состояния Входные символы	S0	S1	S2*
П	(S0, 1)	(S0, 0)	(S2, 0)
Е	(S1, 0)	(S0, 0)	(S1, 1)
Л	(S1, 1)	(S2, 1)	(S2, 0)
Входное слово	ПЕПЕЛ