8. Фонд оценочных средств для проведения промежуточной аттестации обучающихся по дисциплине (модулю):
Общие сведения
1. | Кафедра | М и ММЭ |
2. | Направление подготовки | 080500.62 «Бизнес-информатика» |
3. | Дисциплина (модуль) | Б2.Б.2 Дискретная математика |
4. | Тип заданий | Контрольная работа, домашние задания |
5. | Количество этапов формирования компетенций (ДЕ, разделов, тем и т. д.) | 2 |
Перечень компетенций
(ОК-1)владеет культурой мышления, способен к обобщению, анализу, восприятию информации, постановке цели и выбору путей ее достижения; |
(ПК-19)использовать основные методы естественнонаучных дисциплин в профессиональной деятельности для теоретического и экспериментального исследования; |
(ПК-20)использовать соответствующий математический аппарат и инструментальные средства для обработки, анализа и систематизации информации по теме исследования. |
Критерии и показатели оценивания компетенций
Знания: - основные понятия, алгоритмы и теоремы дискретной математики; - основные свойства графов и булевых функций, теоремы курса; |
Умения: - строить матрицы смежности и инцидентности для графов, таблицы истинности булевых функций, сднф и скнф; - определять к каким классам принадлежат графы (эйлеров, гамильтонов и т. д.), принадлежит булева функция; - используя определения и алгоритмы, проводить исследования, связанные с основными понятиями; |
Навыки: - современными знаниями о дискретной математике и ее приложениях; - основными понятиями дискретной математики. |
Опыт деятельности: уметь решать задачи курса дискретная математика. |
Этапы формирования компетенций (Количество этапов формирования компетенций: ДЕ, разделов, тем и т. д.)
1. Теория графов |
2. Булевы функции |
Шкала оценивания «2» – 60% и менее «3» – 61-80% «4» – 81-90% «5» – 91-100% |
Типовое контрольное задание (контрольная работа, тест, кейс-задание и пр.)
Вариант №1
1. Дан список ребер (1,2), (1,4), (1,1), (1,3), (1,3), (2,7), (2,5), (3,4), (4,5), (4,6), (4,7), (7,1), (7,6), (7,6) псевдо орграфа 
, 
построить диаграмму графа, матрицу инцидентности и матрицу соседства вершин. Для соотнесенного псевдо графа построить матрицу соседства вершин.
2. С помощью алгоритма Прюфера восстановите по вектору дерево. Сделайте проверку. (9,1,3,5,6,8,9,10).
3. Для функции 
построить СДНФ и СКНФ. Определить к каким замкнутым классам она относится.
Вариант №2
1. Дан список ребер (1,2), (1,2), (1,3), (1,3), (1,3), (2,2), (2,5), (3,4), (4,5), (4,6), (4,7), (7,1), (7,7), (7,6) псевдо орграфа , построить диаграмму графа, матрицу инцидентности и матрицу соседства вершин. Для соотнесенного псевдо графа построить матрицу соседства вершин.
2. С помощью алгоритма Прюфера восстановите по вектору дерево. Сделайте проверку.(9,1,1,5,6,2,9,10).
3. Для функции 
построить СДНФ и СКНФ. Определить к каким замкнутым классам она относится.
Вариант №3
1. Дан список ребер (1,2), (2,4), (2,2), (3,3), (4,3), (5,7), (5,5), (6,4), (6,5), (6,6), (7,7), (7,1), (7,6), (7,6) псевдо орграфа , построить диаграмму графа, матрицу инцидентности и матрицу соседства вершин. Для соотнесенного псевдо графа построить матрицу соседства вершин.
2. С помощью алгоритма Прюфера восстановите по вектору дерево. Сделайте проверку. (2,1,1,5,6,8,9,1).
3. Для функции 
построить СДНФ и СКНФ. Определить к каким замкнутым классам она относится.
Вариант №4
1. Дан список ребер (1,1), (2,4), (2,1), (2,3), (2,3), (2,7), (3,5), (3,3), (4,5), (4,6), (5,7), (6,1), (7,6), (7,6) псевдо орграфа , построить диаграмму графа, матрицу инцидентности и матрицу соседства вершин. Для соотнесенного псевдо графа построить матрицу соседства вершин.
2. С помощью алгоритма Прюфера восстановите по вектору дерево. Сделайте проверку. (9,9,3,5,6,8,2,3).
3. Для функции 
построить СДНФ и СКНФ. Определить к каким замкнутым классам она относится.
Вариант №5
1. Дан список ребер (2,2), (2,4), (2,1), (3,3), (4,3), (4,7), (4,5), (5,4), (5,5), (5,6), (6,7), (7,1), (7,1), (7,6) псевдо орграфа , построить диаграмму графа, матрицу инцидентности и матрицу соседства вершин. Для соотнесенного псевдо графа построить матрицу соседства вершин.
2. С помощью алгоритма Прюфера восстановите по вектору дерево. Сделайте проверку. (1,1,3,5,2,8,9,9).
3. Для функции 
построить СДНФ и СКНФ. Определить к каким замкнутым классам она относится.
Вариант №6
1. Дан список ребер (1,2), (1,2), (1,1), (3,3), (2,3), (2,7), (5,5), (3,4), (6,5), (4,6), (4,7), (7,1), (7,6), (7,6) псевдо орграфа , построить диаграмму графа, матрицу инцидентности и матрицу соседства вершин. Для соотнесенного псевдо графа построить матрицу соседства вершин.
2. С помощью алгоритма Прюфера восстановите по вектору дерево. Сделайте проверку.(2,1,3,2,6,2,9,5).
3. Для функции 
построить СДНФ и СКНФ. Определить к каким замкнутым классам она относится.
Методические материалы, определяющие процедуры оценивания знаний
Теория графов
№1. Дан список ребер E={{1,2}, {1,2}, {2,2}, {2,3}, {3,4}, {4,5}, {5,6}}, псевдорграфа , V={1,2,3,4,5,6} построить диаграмму графа, матрицу инцидентности и матрицу соседства вершин, создание списка смежности и создание списка степеней вершин.
№ | Действие | Результат | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Создание диаграммы графа. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1 | Изображение вершин и ребер. Изобразите множество вершин и подпишите их. V={1,2,4,4,5,6}. Изобразите соответствующими отрезками ваше множество E={{1,2}, {1,2}, {2,2}, {2,3}, {3,4}, {4,5}, {5,6}}. Подпишем ребра е1, е2, е3, е4, е5, е6, е7. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Создание матрицы смежности. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2 | Построим матрицу смежности. Размерность этой матрицы |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
3 | Заполним главную диагональ матрицы смежности. Заполним главную диагональ матрицы, на ней ставится количество петель у каждой вершины, в нашем графе есть одна петля у второй вершины, поэтому в матрице на в ячейке (2,2) будет стоять 1, а остальные элементы 0. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4 | Заполняем первую строку матрицы смежности. Заполняем первую строку: вершина 1 соединена с вершиной 2 двумя ребрами, поэтому в ячейке (1,2) ставим 2. С вершиной 3 – 0 ребрами, с 4 – 0 ребрами, с 5 – 0 ребрами, с 6 – 0 ребрами, поэтому остальные ячейки первой строки 0. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
5 | Заполним матрицу смежности. Остальные строки заполняются аналогично. Матрица смежности вершин неориентированного графа симметрична относительно главной диагонали. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Создание матрицы инцидентности. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
6 | Построим матрицу инцидентности. Размерность этой матрицы |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
7 | Заполняем первую строку матрицы инцидентности. Заполняем первый столбец: первое ребро е1 – ребро {1, 2}, инцидентно двум вершинам 1 и 2, следовательно в первом столбце будут две единицы в первой и второй строке, а остальные элементы нули. Второе ребро е2 – ребро {1, 2}, инцидентно двум вершинам 1 и 2, следовательно во втором столбце будут две единицы в первой и второй строке, а остальные элементы нули. Аналогично заполняются остальные столбцы, кроме последнего. Последнее ребро е7 – петля у вершины 2, поэтому в последнем столбце на второй строке стоит 2, а остальные элементы 0. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Создание списка смежности. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
8 | Список смежности. Вершина 1 соединена только с вершиной 2; вершина 2 – с 1, 3; вершина 3 – с 2, 4; вершина 4 – с 3, 5; вершина 5 – с 4, 6; 6 – только с 5. Составим список смежности: {2; 1, 3; 2, 4; 3, 5; 4, 6; 5}. |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Создание списка степеней вершин | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
9 | Список степеней вершин. Вершина 1 имеет степень 2 (количество ребер); вершина 2 – степень 5 (петля вносит вклад 2); вершина 3 – степень 2; вершина 4 – степень 2; вершина 5 – степень 2; 6 – степень 1. Составим список смежности: {2; 5; 2; 2; 2; 1}. Степень вершины можно определить по матрице смежности. Она будет равна сумме элементов по строке (столбцу), соответствующему вершине. Петля вносит в степень вершины вклад равный двум. |
|
, так как граф имеет шесть вершин. Заполним название строк и столбцов – именами вершин.
, так как граф имеет шесть вершин и 7 ребер. Заполним название строк и столбцов – именами вершин.
№2. С помощью алгоритма Прюфера восстановите по вектору дерево. Сделайте проверку.
№ | Действие | Результат |
Восстановить дерево Т, если соответствующий ему вектор имеет вид: (1, 2, 2, 1, 4, 4, 4). | ||
1 | Определим количество вершин. Данный кортеж содержит 7 компонент, значит, дерево Т должно иметь 7+2=9 вершин. Выпишем последовательность номеров этих вершин: V={1, 2, 3, 4, 5, 6, 7, 8, 9}. |
|
2 | Построение первого ребра дерева. В векторе (1, 2, 2, 1, 4, 4, 4) находим первое число, которое не содержится в множестве вершин V={1, 2, 3, 4, 5, 6, 7, 8, 9}: - 3. Получаем ребро {1,3}. Удаляем первую координату 1 в векторе (2, 2, 1, 4, 4, 4) и вершину 3 из множества вершин V1={1, 2, 4, 5, 6, 7, 8, 9}. |
|
3 | Построение ребер дерева. В векторе (2, 2, 1, 4, 4, 4) находим первое число, которое не содержится в множестве вершин V={1, 2, 4, 5, 6, 7, 8, 9}: - 5. Получаем ребро {2,5}. Удаляем первую координату 2 в новом векторе(2, 1, 4, 4, 4) и вершину 5 из множества вершин V2={1, 2, 4, 6, 7, 8, 9}. Повторяя эту процедуру ещё 3 раза, получим рёбра {2,6}, {1,2}, {4,1}, {4,7}, {4,8}. После этого в последовательности вершин останутся два числа - 4 и 9. Они определяют последнее ребро {4,9}. |
|
4 | Изменение диаграммы дерева В ИГС GeoGebra изобразим вершины и ребра произвольным образом, затем передвигая вершины, найдем стандартный вид дерева. |
|
Сделаем проверку | ||
5 | Определим количество координат в векторе В дереве 9 вершин, поэтому вектор будет содержать 9-2=7 координат: (_,_,_,_,_,_,_). | |
6 | Заполнение вектора Находим концевую вершину с наименьшим номером – это вершина 3 ей соответствует ребро {3,1}, поэтому в вектор записывается число 1 (1, , ), а ребро {3,1} вычеркивается из дерева. Получаем новое дерево. Ищем в новом дереве концевую вершину наименьшего номера – вершина 5 ей соответствует ребро {5,2}, поэтому в вектор записывается число 2 (1,2, , ), а ребро {5,2} вычеркивается из дерева. Получаем новое дерево. Ищем в новом дереве концевую вершину наименьшего номера – вершина 6 ей соответствует ребро {6,2}, поэтому в вектор записывается число 2 (1,2,2, , ), а ребро {6,2} вычеркивается из дерева. Получаем новое дерево. Ищем в новом дереве концевую вершину наименьшего номера – вершина 2 ей соответствует ребро {2,1}, поэтому в вектор записывается число 1 (1,2,2,1, , ), а ребро {2,1} вычеркивается из дерева. Повторяя эту операцию еще 3 раза, получим код исходный вектор (1, 2, 2, 1, 4, 4, 4). |
|
Булевы функции
1. Для формулы 
построим таблицу истинности. Считаем количество переменных их две x и y. Таблица истинности будет содержать пять строк: одна строка для обозначений, а остальные 
соответствуют всем возможным наборам переменных. Количество столбцов: число переменных (2) плюс количество операций (3) всего 5 столбцов. Порядок столбцов соответствует порядку выполнения операций.
Столбец 
строится из столбца x , заменой 0 на 1, а 1 на 0.
Столбец x&y соответствует операции конъюнкция, т. е. 0&0=0, 0&1=0, 1&0=0, 1&1=1.
Столбец значений функции получается импликацией из столбца x&y и ⌐x при помощи сводной таблицы. Значение первой строки 0→1=1, второй - 0→1=1, третей - 0→0=1, четвертой - 1→0=0.
x | y |
| x&y |
|
0 | 0 | 1 | 0 | 1 |
0 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 0 | 1 |
1 | 1 | 0 | 1 | 0 |
2. Дана формула 
. Считаем количество переменных (три), следовательно, таблица истинности содержит 9 строк: одна для обозначений, а остальные 
соответствуют всем возможным наборам переменных. Определим количество столбцов: три переменных плюс две операции всего 5 столбцов.
Столбцы переменных заполняются так: первый столбец (для переменной x число наборов в группе 
): четыре 0, четыре 1; второй столбец (для переменной y число наборов в группе 
): два 0, две 1, два 0, две 1; третий столбец (для переменной z число наборов в группе 
): чередование нулей и единиц начиная с 0.
Столбец y
z получаем из сводной таблицы так: 00=0, 01=1, 10=1, 11=1 затем значения столбца повторяются.
Столбец значений функции получается импликацией первого и четвертого столбца.
x | y | z | y |
|
0 | 0 | 0 | 0 | 1 |
0 | 0 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 1 | 1 |
1 | 1 | 0 | 1 | 1 |
1 | 1 | 1 | 1 | 1 |
3. С помощью теоремы Поста проверить на полноту следующие системы булевых функций
, 
.
Решение. Принадлежность функций системы классам Поста будем помечать знаком +.
В каждом столбце таблицы содержится хотя бы один минус. Поэтому рассматриваемая система полна.
Вопросы к зачету/экзамену
1. Понятия теории графов.
2. Операции с графами.
3. Степени вершин графов.
4. Способы задания графов.
5. Маршруты, цепи, циклы.
6. Эйлеровы графы.
7. Гамильтоновы графы.
8. Двудольные графы и жесткость ферм.
9. Деревья.
10. Коды Прюфера.
11. Задача об остове минимального веса.
12. Мультиграфы
13. Понятие булевой функции.
14. Понятие фиктивной переменной.
15. Основные булевы функции от 1-ой и 2-х переменных.
16. Понятие формулы над Р.
17. Операция суперпозиции.
18. Эквивалентность формул.
19. Свойства элементарных функций.
20. Принцип двойственности.
21. Разложение булевых функций по переменным.
22. СДНФ.
23. СКНФ.
24. Полнота и замкнутость.
25. Полином Жегалкина.
26. Класс Т0.
27. Класс Т1.
28. Класс S.
29. Класс L.
30.
31. Теорема о функциональной полноте.
32. Представление о результатах Поста.
Основные порталы (построено редакторами)