Соотнесите понятие и формулу

Вопросы к экзамену по Дискр. Мат.

Б) Экзаменационные вопросы по дисциплине:

1. Способы задания множеств Операции над множествами

2. Характеристическая функция множества Декартово произведение множеств

3. Понятие отображения множеств

4. Конечные множества и комбинаторика

5. Перестановки, размещения и сочетания

6. Метод включений и исключений

7. Метод рекуррентных соотношений

8. Счетные множества и производящие функции

9. Несчетные и континуальные множества

10. Многоместные отношения

11. Бинарные отношения на множестве .

12. Отношение эквивалентности (сходства)

13. Отношение порядка (превосходства)

14. Определение и примеры графов

15. Связность графа

16. Обзор основных задач теории графов

17. Расчет сетевого графика

18. Плоские графы

19. Теорема о раскраске графа в пять цветов

20. Сети Петри

В)Вопросы для контроля самостоятельной работы по дисциплине:

Варианты заданий для самостоятельной работы студентов за 3 семестр:

Тест 1

1. Множество всех первых элементов пар из R называется

a) областью значения отношения;

b) областью определения отношения ;

c) бинарным отношением.

2. это свойство называется

a) рефлексивность;

b) транзитивность;

c) симметричность;

d) антисимметричность.

3.Бинарное отношение, которое является рефлексивным, антисимметричным и транзитивным называется отношением

a) порядка;

b) квазипорядка;

c) доминирования;

d) эквивалентности.

1. Наибольший элемент является максимальным

a) является;

b) не является.

2. Граф называется связным, если любые две его вершины соединены хотя бы

a) одним путем;

b) двумя путями;

c) тремя путями;

d) четырьмя путями.

ТЕСТ 2

Соотнесите понятие и формулу

1) Правило равенства.

2) Правило суммы.

3) Правило произведения.

а)

б) , то |A| = |B|

в)

Правильный ответ: 1-б, 2-а, 3-в

2) Отношение толерантности– это …

А) Бинарное отношение R на множестве А которое не рефлексивно и не симметрично.

Б) Бинарное отношение R на множестве А которое рефлексивно и симметрично.

С) Бинарное отношение R на множестве А которое рефлексивно но не симметрично.

Д) Бинарное отношение R на множестве А которое не рефлексивно но симметрично.

Правильный ответ: Б

В чём состоит суть теоремы 5

а) Для того, чтобы сумма отношений толерантности T₁, T₂ было отношением толерантности, необходимо и достаточно, чтобы выполнялось усло­вие:

б) Для того, чтобы разность отношений толерантности T₁, T₂ было отношением толерантности, необходимо и достаточно, чтобы выполнялось усло­вие:

с) Для того, чтобы произведение отношений толерантности T₁, T₂ было отношением толерантности, необходимо и достаточно, чтобы выполнялось усло­вие:

д) Для того, чтобы частное отношений толерантности T₁, T₂ было отношением толерантности, необходимо и достаточно, чтобы выполнялось усло­вие:

Правильный ответ: С

Правильный ответ: 1-с, 2-д, 3-а, 4-б

Правильный ответ: 4

Правильный ответ: 2

7) Лемма. Для любой геометрической реализации на плоскости связного планарного графа с q рёбрами выполняется равенство: где:

1. Суммирование ведётся по всем граням (включая внешнюю).

2. Суммирование ведётся по всем граням (не включая внешнюю).

3. Суммирование ведётся по верхним граням.

4. Суммирование ведётся по нижним граням.

Правильный ответ: 1

ТЕСТ3:

1. Чему будет равно выражение :

а)

б)

в)

г)

2. Чему будет равно выражение :

а)

б)

в)

г)

3. Дано , , , . Чему будет равно выражение :

а)

б)

в)

г)

4. Чему будет равно выражение :

а)

б)

в)

г)

5. Дано , , . Чему будет равно выражение :

а)

б)

в)

г)

ТЕСТ4

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

А) 182

Б) 377

В) 60

Г) 542

Ответ. Имеет место рекуррентное соотношение F(n+1)=F(n)+F(n-1). Так как, по условию, F(0)=1 и F(1)=2, то последовательно находим F(2)=3, F(3)=5, F(4)=8 и т.д. В частности, F(12)=377.

Какое наименьшее количество новых ребер нужно добавить к графу С₆, чтобы получился непланарный граф?

А) 3

Б) 4

В) 5

Г) 6

Ответ. 3 (?)

Какой граф называется планарным?

А) если он может быть изображен на плоскости так, что его ребра пересекаются

Б) если он может быть изображен на плоскости так, что его ребра не пересекаются

В) если он может быть изображен на плоскости так, что бы его ребра были попарно параллельны

Ответ. Б

Тест 6

Вопрос 1: Связный граф G(V,E), не имеющий циклов, называется…

1) Ветвлением

2) Деревом

3) Окном

4) Развилкой

Вопрос 2: Если множество, состоит из тех и только тех элементов, которые принадлежат хотя бы одному из множеств А и В, то это..

1) Разность

2) Пересечение

3) Объединение

4) Дополнение

Вопрос 3: Какой из символов обозначает пустое множество?

1)

2)

3)

4)

Вопрос 4: это…

1) Ассоциативный закон

2) Дистрибутивный закон

3) Свойство обращения

4) Правило обращения произведения

Вопрос 5: Разностью множеств А и В называют..

1) множество, состоящее из тех и только тех элементов, которые принадлежат хотя бы одному из множеств А и В

2) множество, состоящее из тех и только тех элементов А, которые не принадлежат В

3) множество, состоящее из тех и только тех элементов, которые принадлежат обоим множествам А и В

4) множество, состоящее из элементов пустого множества

Ответы к тесту:

1. 2)

2. 3)

3. 4)

4. 1)

5. 2)

Тест.7

1. называется инъективным, если

a)

b)

c)

d)

2. Соотнесите понятие и формулу:

1. Свойство обращения

2. Ассоциативный закон

3. Правило обращения произведения

4. Дистрибутивный закон

a)

b)

c)

d)

3.Дана подстановка , ее цикловое разложение будет:

a) (1 7 9 4 8 2)(3)(6 5)

b) (1 7 9 4 8 2)(3)(5 6)

c) (1 7 9 4 7 9)(3)(5 6)

d) (9 4 1 7 8 2)(3)(5 6)

4.Корневым деревом называется:

a) Любое дерево, в котором выделена одна или более вершин, называемые корнями, называется корневым деревом

b) Граф, состоящий из двух вершин, которые выделены, называется корневым деревом

c) Любое дерево, в котором выделена одна вершина, называемая корнем, называется корневым деревом.

d) Любой граф, состоящий более чем из двух вершин, называется корневым деревом.

5. Соотнесите понятие и формулу

1. Правило равенства.

2. Правило суммы.

3. Правило произведения.

а)

б) , то |A| = |B|

в)

Ответы к тесту 1: 1, 2: 1 d,2 c, 3 b, 1 a,3: 2,4: 3

Вопросы к экзамену по Дискр. Мат.

Б) Экзаменационные вопросы по дисциплине:

1. Способы задания множеств Операции над множествами

2. Характеристическая функция множества Декартово произведение множеств

3. Понятие отображения множеств

4. Конечные множества и комбинаторика

5. Перестановки, размещения и сочетания

6. Метод включений и исключений

7. Метод рекуррентных соотношений

8. Счетные множества и производящие функции

9. Несчетные и континуальные множества

10. Многоместные отношения

11. Бинарные отношения на множестве .

12. Отношение эквивалентности (сходства)

13. Отношение порядка (превосходства)

14. Определение и примеры графов

15. Связность графа

16. Обзор основных задач теории графов

17. Расчет сетевого графика

18. Плоские графы

19. Теорема о раскраске графа в пять цветов

20. Сети Петри

В)Вопросы для контроля самостоятельной работы по дисциплине:

Варианты заданий для самостоятельной работы студентов за 3 семестр:

Тест 1

1. Множество всех первых элементов пар из R называется

a) областью значения отношения;

b) областью определения отношения ;

c) бинарным отношением.

2. это свойство называется

a) рефлексивность;

b) транзитивность;

c) симметричность;

d) антисимметричность.

3.Бинарное отношение, которое является рефлексивным, антисимметричным и транзитивным называется отношением

a) порядка;

b) квазипорядка;

c) доминирования;

d) эквивалентности.

1. Наибольший элемент является максимальным

a) является;

b) не является.

2. Граф называется связным, если любые две его вершины соединены хотя бы

a) одним путем;

b) двумя путями;

c) тремя путями;

d) четырьмя путями.

ТЕСТ 2

Соотнесите понятие и формулу

1) Правило равенства.

2) Правило суммы.

3) Правило произведения.

а)

б) , то |A| = |B|

в)