3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
3.1 Обязательный минимум содержания образовательной программы
Множества и их спецификации; диаграммы Венна; отношения; свойства отношений; разбиения и отношение эквивалентности; отношение порядка; функции и отображения; операции; основные понятия теории графов; маршруты; циклы; связность; планарные графы; переключательные функции (ПФ); способы задания ПФ; специальные разложения ПФ; неполностью определенные (частные) ПФ; минимизация ПФ и неполностью определенных ПФ; теорема о функциональной полноте; примеры функционально-полных базисов; разрешимые и неразрешимые проблемы; схемы алгоритмов; схемы потоков данных.
3.2 Содержание разделов учебной дисциплины
(дидактические единицы)
ДЕ 1 Множества и отношения
Тема 1. Множества и отношения
Аудиторное изучение: Понятие множества, подмножества. Задание множеств. Сравнение множеств. Операции над множествами (объединение, пересечение, дополнение, разность). Диаграммы Венна. Универсальное множество. Разбиения и покрытия. Булеан. Свойства операций над множествами. Мощность множества.
Прямое произведение. Бинарное отношение. Способы задания бинарных отношений. Операции над бинарными отношениями. Обратные отношения. Композиция бинарных отношений. Свойства бинарных отношений и их распознавание. Свойства матриц бинарных отношений. Рефлексивные, симметричные, транзитивные бинарные отношения. Отношение эквивалентности и классы эквивалентности. Отношение порядка.
Самостоятельное изучение: Функции и отображения. Линейный порядок и частичный порядок. Диаграммы Хассе. Лексикографический порядок.
Тема 2. Комбинаторика
Аудиторное изучение: Классификация комбинаторных задач и характеристика их основных типов. Основные правила комбинаторики. Основные комбинаторные конфигурации: размещения, сочетания, перестановки. Метод включений и исключений. Бином Ньютон, биномиальные коэффициенты, треугольник Паскаля. Основные биномиальные тождества.
Самостоятельное изучение: Рекуррентные соотношения и производящие функции. Числа Стирлинга и их свойства.
Тема 3. Алгебраические системы
Аудиторное изучение: Алгебраические структуры. Фундаментальные алгебры. Морфизмы.
Самостоятельное изучение: Решение задач.
ДЕ 2 Теория графов
Тема 4. Основные понятия теории графов
Аудиторное изучение: Понятие графа, простого графа, полного графа, однородного графа, мультиграфа, псевдографа. Подграф, надграф, частичный граф. Степень вершины. Операции над графами: дополнение, объединение, пересечение, сумма по модулю два, произведение. Способы задания графов: аналитический, графический, матричный. Матрица смежности. Матрица инцидентности.
Самостоятельное изучение: Изоморфизм графов.
Тема 5. Связные графы
Аудиторное изучение: Понятия маршрута, цепи, простой цепи, цикла, простого цикла. Связный граф. Степень связности. Матрица расстояний, эксцентриситеты вершин, радиус, диаметр, центр графа. Переферийные и центральные вершины. Обходы графов. Эйлеров цикл. Критерий Эйлера. Алгоритм построения эйлерова цикла. Гамильтонов цикл.
Самостоятельное изучение: Двудольные графы.
Тема 6. Планарные и плоские графы
Аудиторное изучение: Плоский граф. Теорема Эйлера о плоских графах. Гомеоморфизм. Подразбиение и надразбиение ребра. Критерий Понтрягина-Куратовского. Двойственные графы. Дерево и лес. Остовы графа. Цикломатическое число. Мост. Разделяющее множество. Разрез.
Самостоятельное изучение: Раскраска графа. Хроматическое число графа.
Тема 7. Ориентированные графы
Аудиторное изучение: Понятие орграфа. Матрица смежности вершин и дуг. Матрица инциденций. Степень вершин орграфа. Изоморфизм. Маршруты, цепи, циклы в орграфах. Связность орграфа: сильно связный, слабосвязный и несвяхный орграф. Эйлеровы цепи и циклы в орграфе. Полный орграф. Операции в орграфе. Орграфы и бинарные отношения. Диаграммы Хассе. Взвешенный граф
Самостоятельное изучение: Нахождение кратчайщих маршрутов.
ДЕ 3 Переключательные функции
Тема 8. Переключательные функции и способы их задания
Аудиторное изучение: Булевы функции. Понятие о переключательных функциях. Двоичные переключательные функции и способы их задания. Основные бинарные логические операции. Понятие о переключательных схемах и технической реализации ПФ.
Самостоятельное изучение: Использование логических операций в теории графов.
Тема 9. Основные законы булевой алгебры и преобразование ПФ
Аудиторное изучение: Основные законы булевой алгебры ПФ. Равносильные преобразования. Упрощение формул алгебры ПФ. Преобразование форм представления ПФ. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ. КНФ). Совершенная дизъюнктивная и конъюнктивная нормальные формы (СДНФ и СКНФ).
Самостоятельное изучение: Решение задач.
Тема 10. Минимазация ПФ
Аудиторное изучение: Цель минимазации переключательных функций. Основные понятия и определения, используемые при минимизации. Аналитические методы минимизации ПФ. Минимизация ПФ по картам Карно.
Самостоятельное изучение: Минимизация ПФ МНК. Метод Квайна — Мак-Класки.
Тема 11. Функциональная полнота систем ПФ
Аудиторное изучение: Многочлены Жегалкина. Теорема Жегалкина. Методики представления булевой функции в виде многочлена Жегалкина. Замыкание множества функций. Понятие замкнутого класса функций. Важнейшие замкнутые классы: Т0 (класс функций, сохраняющих константу 0), Т1 (класс функций, сохраняющих константу 1), S (класс самодвойственных функций), L (класс линейных функций), M (класс монотонных функций). Понятие функциональной полноты. Полные системы булевых функций. Теорема Поста. Базисы представлений ПФ.
Самостоятельное изучение: Базисы представления ПФ.
Содержание семинарских занятий
Тема 1. Множества и отношения
Семинарское занятие – 4 часа.
План.
Операции над множествами. Диаграммы Эйлера-Венна.
Упрощение выражений над множествами с использованием основных тождеств алгебры множеств.
Решение задач на подсчет количества элементов с использованием формулы количества элементов в объединении нескольких конечных множеств.
Прямое произведение.
Бинарное отношение. Запись бинарных отношений с помощью специальной математической символики.
Определение свойств бинарных отношений и их принадлежности к специальным типам бинарных отношений.
Матрицы бинарных отношений.
Эквивалентность и порядок.
Функции и отображения.
Тема 2. Комбинаторика
Семинарское занятие – 4 часа.
План.
Правила суммы и произведения.
Размещения, перестановки, сочетания без повторений.
Размещения, перестановки, сочетания с повторениями.
Метод включений и исключений.
Решение комбинаторных уравнений
Тема 3. Алгебраические системы
Семинарское занятие – 4 часа.
План.
Операции и алгебры.
Морфизмы.
Алгебры с одной и двумя операциями.
Векторные пространства.
Решетки.
Тема 4. Основные понятия теории графов
Семинарское занятие – 2 часа.
План.
Виды и способы задания графов.
Матрица смежности. Матрица инцидентности. Степень вершины.
Однородный граф. Полный граф. Дополнение графа.
Операции над графами: дополнение, объединение, пересечение, сумма по модулю два, произведение.
Изоморфизм.
Тема 5. Связные графы
Семинарское занятие – 1час.
План.
Маршруты, цепи, простые цепи, циклы, простые циклы. Длина цепи.
Связность графа.
Нахождение простых цепей.
Матрица расстояний, эксцентриситеты вершин, радиус, диаметр, центр графа. Переферийные и центральные вершины.
Взвешенный граф. Нахождение кратчайщих маршрутов.
Эйлеров цикл. Критерий Эйлера. Алгоритм построения эйлерова цикла.
Гамильтоновы графы. Задача о коммивояжере.
Двудольные графы.
Тема 6. Планарные и плоские графы
Семинарское занятие – 1 час.
План.
Гомеоморфизм.
Теорема Эйлера о плоских графах.
Критерий планарности Понтрягина-Куратовского.
Двойственные графы.
Деревья и лес.
Раскраска графа. Хроматическое число графа.
Тема 7. Ориентированные графы
Семинарское занятие – 4 часа.
План.
Орграф. Матрица смежности. Изоморфизм.
Степень вершины орграфа.
Маршруты, цепи, циклы в орграфах.
Связность орграфа.
Эйлеровы цепи и циклы в орграфе.
Полный орграф.
Нахождение максимальной пропускной способности транспортной сети
Тема 8. Переключательные функции и способы их задания
Семинарское занятие – 2 часа.
План.
ПФ. Двоичные переключательные функции и способы их задания.
Основные бинарные логические операции.
Понятие о переключательных схемах и технической реализации ПФ.
Использование логических операций в теории графов.
Тема 9. Основные законы булевой алгебры и преобразование ПФ
Семинарское занятие – 4 часа.
План.
Основные законы булевой алгебры ПФ.
Равносильные преобразования.
Упрощение формул алгебры ПФ. Преобразование форм представления ПФ.
Дизъюнктивные и конъюнктивные нормальные формы (ДНФ. КНФ).
Совершенная дизъюнктивная и конъюнктивная нормальные формы (СДНФ и СКНФ).
Тема 10. Минимазация ПФ
Семинарское занятие – 4 часа.
План.
Аналитические методы минимизации ПФ.
Минимизация ПФ по картам Карно.
Минимизация ПФ МНК.
Метод Квайна — Мак-Класки.
Тема 11. Функциональная полнота систем ПФ
Семинарское занятие – 6 часов.
План.
Представления булевой функции в виде многочлена Жегалкина двумя способами.
Проверка булевой функции на линейность.
Важнейшие замкнутые классы: Т0 (класс функций, сохраняющих константу 0), Т1 (класс функций, сохраняющих константу 1), S (класс самодвойственных функций), L (класс линейных функций), M (класс монотонных функций).
Полные системы булевых функций. Теорема Поста.
Базисы представлений ПФ.
Контрольная работа.
|
