- •Учебно-методический комплекс дисциплины сд.12 дискретная математика
- •061800 «Математические методы в экономике»
- •Раздел 1. Программа учебной дисциплины. Структура программы учебной дисциплины
- •1.3 Пояснительная записка:
- •1.5. Объем дисциплины и виды учебной работы.
- •1.6 Содержание дисциплины.
- •1.7 Методические рекомендации по организации изучения дисциплины.
- •1.8 Учебно-методическое обеспечение дисциплины.
- •1.9 Материально-техническое обеспечение дисциплины.
- •1.10 Примерные зачетные тестовые задания.
- •1.11 Примерный перечень вопросов к зачету (экзамену).
- •1.12 Комплект экзаменационных билетов
- •1.13 Примерная тематика рефератов.
- •1.14 Примерная тематика курсовых работ.
- •Элементы теории множеств
- •§ 2. Бинарные операции и их свойства
- •§ 3. Операции над множествами. Законы де Моргана
- •§ 4. Вектор. Прямое произведение
- •§ 5. Мощность конечного множества
- •§ 6. Отношения и их свойства
- •§ 7. Отношение эквивалентности
- •§ 8. Отношение порядка
- •§ 9. Отображения и их свойства
- •Глава II. Элементы теории графов
- •§ 1. Графы, их вершины, рёбра и дуги
- •§ 2. Операции над графами
- •§ 3. Способы задания псевдографов. Степени вершин
- •§ 4. Отношение связности для вершин неориентированного графа
- •§ 5. Отношение достижимости для вершин орграфа
- •§ 6. Эйлеров граф и условия его существования
- •§ 7. Гамильтонов граф и условия его существования
- •§ 8. Деревья и их свойства. Цикломатическое число
- •§ 9. Формула Кэли
- •§ 10. Двудольный граф
- •§ 11. Планарность
- •§ 12. Раскраска графов
- •Глава III. Булевы функции
- •§ 1. Основные определения
- •§ 2. Свойства булевых функций
- •§ 3. Переключательные функции
- •§ 4. Совершенные нормальные формы
- •§ 5. Полнота. Примеры полных систем
- •§ 6. Замыкание и его свойства
- •§ 7. Важнейшие замкнутые классы
- •§ 8. Теорема о функциональной полноте
- •Раздел 4. Словарь терминов (глоссарий) Элементы теории множеств
- •Конечные графы
- •Функциональные системы с операциями: алгебра логики
- •Раздел 5. Практикум по решению задач (практических ситуаций) по темам лекций (одна из составляющих частей итоговой государственной аттестации) Элементы теории множеств
- •Задачи для самостоятельного решения
- •Конечные графы
- •Задачи для самостоятельного решения
- •Функциональные системы с операциями: алгебра логики
- •Задачи для самостоятельного решения
- •Раздел 6. Изменения в рабочей программе, которые произошли после утверждения программы.
- •Раздел 7. Учебные занятия по дисциплине ведут:
1.9 Материально-техническое обеспечение дисциплины.
1.9.1 Электронный конспект лекций
1.9.2 Тестовые программы: «Способы задания псевдографов» и «Фрмула Кэли. Коды Прюфера»
1.9.3 Тридцать два варианта индивидуальных заданий в электронном виде по теме: «Булевы функции».
1.10 Примерные зачетные тестовые задания.
Контрольная работа №1. «Конечные графы»
Пример одного варианта
|
1 |
2 |
3 |
4 |
5 |
6 |
|
1. По данной матрице смежности ориентированного псевдографа а) нарисовать диаграмму; б) восстановить список ребер; в) составить матрицу достижимости; г) определить степени всех вершин. 2. Подсчитать количество помеченных орграфов с 5 вершинами, содержащих от 2 до 3 ребер. |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
||
2 |
0 |
0 |
0 |
3 |
0 |
0 |
||
3 |
0 |
0 |
0 |
0 |
0 |
0 |
||
4 |
0 |
0 |
0 |
0 |
1 |
0 |
||
5 |
0 |
0 |
0 |
1 |
0 |
0 |
||
6 |
1 |
2 |
0 |
0 |
0 |
0 |
3. С помощью алгоритма Прюфера восстановить по вектору дерево. Нарисовать диаграмму. Сделать проверку. (2,1,6,4,4,4,6).
4. В неориентированном графе F имеется 45 ребер. Сколько вершин в F, если
а) F дерево; б) F полный граф?
Контрольная работа №2 «Функции алгебры логики»
Пример одного варианта
1. Для данных булевых функций
а) f(, ) = (()) ()
б) f(, , ) = () (~) (→) ()
1.1. составить таблицы их значений;
1.2. пользуясь таблицами значений, составить СДНФ и СКНФ;
1.3. пользуясь таблицами значений, составить функции, двойственные к данным;
1.4. записать двойственные функции в виде наиболее экономичных СНФ.
2. Дана переключательная (булева) функция:
f(, , ) = () (→).
2.1. Путем эквивалентных преобразований упростить формулу, реализующую данную функцию.
2.2. По упрощенной формуле нарисовать наиболее простую релейно-контактную схему, соответствующую данной функции.
3. Дана булева функция трех переменных: f(, , ) = ().
3.1. Путем эквивалентных преобразований привести данную функцию к СДНФ и СКНФ.
3.2. Используя принцип двойственности, записать логическую формулу, реализующую функцию, двойственную к данной.
4. Преобразовать логическую формулу: () так, чтобы в ее записи остались только:
4.1. конъюнкция и отрицание; 4.3. стрелка Пирса;
4.2. дизъюнкция и отрицание; 4.4. штрих Шеффера.
5. Разложить данные булевы функции в полином Жегалкина:
а) f(, ) = [ ~ ()] 1,
б) f(, , ) = (~) .
6. Определить, к каким из пяти основных замкнутых классов (Т0, Т1, S, M, L) принадлежит данная булева функция и к каким она не принадлежит. Ответ обосновать.
f(, , ) = () (→).
1.11 Примерный перечень вопросов к зачету (экзамену).
Конечные графы
1. Основные определения (графы, мультиграфы, псевдографы; вершины, ребра, дуги; смежность, инцидентность; графы ориентированные, неориентированные, изоморфные; пустой граф; полный граф).
2. Часть графа. Подграф. Собственный подграф. Дополнение графа.
3. Число помеченных графов с n вершинами и m ребрами.
4. Операции над графами: объединение, соединение, произведение, композиция. Число вершин и ребер графа результата операции.
5. Матрица инцидентности псевдографа. Список рёбер. Матрица смежности. Определение степени вершины с помощью матриц смежности и инцидентности.
6. Степени вершин графа. Лемма о рукопожатиях (с доказательством). Однородный (регулярный) граф. Теорема о существовании вершин с одинаковыми степенями (с доказательством).
7. Маршрут, путь, цикл, цепь. Теорема о существовании простой ориентированной цепи, проходящей через все вершины графа (с доказательством).
8. Отношение связности в неориентированном графе и его свойства. Связный граф. Компоненты связности. Точка сочленения. Мост.
9. Отношение достижимости в ориентированном графе и его свойства. Базисный граф и способ его построения.
10. Эйлеров граф. Условия, при которых граф эйлеров (с доказательством). Эйлерова цепь. Условия существования эйлеровой цепи.
11. Гамильтонов граф и простейшие условия его существования (с доказательством).
12. Деревья и их свойства: теоремы о связи между вершинами дерева, о числе концевых вершин и ребер, о соотношении числа вершин и числа ребер (с доказательством).
13. Теорема Кэли о числе различных деревьев с “n” вершинами (с доказательством).
14. Двудольный граф. Условия, при которых граф двудольный (с доказательством).
15. Плоский граф. Планарный граф. Теорема Эйлера о связи между количеством вершин, ребер и граней плоского графа (с доказательством).
16. Следствия из теоремы Эйлера: относительно количества ребер планарного графа; относительно графов K5 и K3,3; относительно степени вершины планарного графа (с доказательством). Теорема Понтрягина-Куратовского.
17. Раскраска графа. Хроматическое число графа. Теорема о пяти красках (с доказательством).
Функциональные системы с операциями: алгебра логики
18. Простейшие булевы функции: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность и т.д. Количество булевых функций от n переменных.
19. Свойства элементарных булевых функций (одно с доказательством). Формулы. Эквивалентные формулы в булевой алгебре. Проверка формул на эквивалентность.
20. Двойственная булева функция и ее построение. Принцип двойственности.
21. Теорема о разложении булевой функции по n переменным.
22. Совершенная дизъюнктивная нормальная форма (СДНФ) и ее построение. Способы приведения функции к СДНФ.
23. Совершенная конъюнктивная нормальная форма (СКНФ) и ее построение. Способы приведения функции к СКНФ.
24. Полнота. Примеры полных систем с доказательствами их полноты (без использования теоремы о функциональной полноте).
25. Теорема о представлении булевой функции при помощи полинома Жегалкина.
26. Замыкание. Свойства замыкания.
27. Замкнутые классы Т0 и Т1 функций, сохраняющих константы.
28. Замкнутый класс S самодвойственных функций. Лемма о несамодвойственной функции.
29. Замкнутый класс М монотонных функций. Лемма о немонотонной функции.
30. Замкнутый класс L линейных функций. Лемма о нелинейной функции.
31. Теорема о функциональной полноте.
32. Постановка задачи о минимизации булевых функций в аналитической форме. Метод минимизирующих карт.