Методические рекомендации по освоению учебной дисциплины 17 1 Самостоятельная работа студента 17 2 Оценочные средства для контроля успеваемости и результатов освоения учебной дисциплины 20

3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

План.

1. 
   Операции над множествами. Диаграммы Эйлера-Венна.
   
2. 
   Упрощение выражений над множествами с использованием основных тождеств алгебры множеств.
   
3. 
   Решение задач на подсчет количества элементов с использованием формулы количества элементов в объединении нескольких конечных множеств.
   

План.

1. 
   Прямое произведение.
   
2. 
   Бинарное отношение. Способы задания бинарных отношений.
   
3. 
   Матрицы бинарных отношений.
   
4. 
   Рефлексивные, симметричные, транзитивные бинарные отношения.
   
5. 
   Отношения порядка.
   

План.

1. 
   Объединение, пересечение, дополнение, разность и симметрическая разность нечетких множеств.
   
2. 
   Мощность нечёткого конечного множества. Нечёткое равенство нечётких множеств.
   
3. 
   Прямое произведение нечётких множеств. Композиция нечетких отображений. Композиция нечетких отношений.
   
4. 
   Нечеткие алгоритмы.
   
5. 
   Теория неопределенности.
   

План.

1. 
   Правила суммы и произведения.
   
2. 
   Размещения, перестановки, сочетания с повторениями.
   
3. 
   Размещения, перестановки, сочетания без повторений.
   
4. 
   Решение комбинаторных уравнений.
   
5. 
   Метод включений и исключений.
   
6. 
   Рекуррентные соотношения. Возвратные последовательности.
   

1. 
   Логические переменные.
   
2. 
   Логические связки.
   
3. 
   Таблицы истинности. Правила расстановки скобок в формулах.
   
4. 
   Символическая форма для высказываний.
   
5. 
   Булева функция. Вектор значений булевой функции.
   
6. 
   Эквивалентность формул.
   
7. 
   Выполнимая и опровержимая формула. Тождественно-истинная формула. Тождественно-ложная формула.
   

1. 
   Понятие литеры. Дизъюнкт. Конъюнкт.
   
2. 
   Построение дизъюнктивной и совершенной конъюнктивной нормальных форм.
   

1. 
   Представление булевой функции в виде совершенной дизъюнктивной и совершенной конъюнктивной нормальных форм.
   
2. 
   Представление булевой функции в виде минимальной дизъюнктивной нормальной формы.
   

1. 
   Представления булевой функции в виде многочлена Жегалкина двумя способами.
   
2. 
   Проверка булевой функции на линейность.
   
3. 
   Важнейшие замкнутые классы: Т0 (класс функций, сохраняющих константу 0), Т1 (класс функций, сохраняющих константу 1), S (класс самодвойственных функций), L (класс линейных функций), M (класс монотонных функций).
   
4. 
   Полные системы булевых функций. Теорема Поста.
   

1. 
   Предикаты. Область истинности предиката
   
2. 
   Кванторы.
   
3. 
   Формулы логики предикатов.
   
4. 
   Равносильные формулы логики предикатов.
   
5. 
   Приведенные и нормальные формы в логике предикатов.
   

1. 
   Виды и способы задания графов.
   
2. 
   Матрица смежности. Матрица инцидентности. Степень вершины.
   
3. 
   Однородный граф. Полный граф. Дополнение графа.
   
4. 
   Операции над графами: дополнение, объединение, пересечение, сумма по модулю два, произведение.
   

1. 
   Маршруты, цепи, простые цепи, циклы, простые циклы. Длина цепи.
   
2. 
   Связность графа.
   
3. 
   Нахождение простых цепей.
   
4. 
   Матрица расстояний, эксцентриситеты вершин, радиус, диаметр, центр графа. Переферийные и центральные вершины.
   
5. 
   Взвешенный граф. Нахождение кратчайщих маршрутов.
   
6. 
   Эйлеров цикл. Критерий Эйлера. Алгоритм построения эйлерова цикла.
   
7. 
   Гамильтоновы графы. Задача о коммивояжере.
   
8. 
   Двудольные графы.
   

1. 
   Гомеоморфизм.
   
2. 
   Теорема Эйлера о плоских графах.
   
3. 
   Критерий планарности Понтрягина-Куратовского.
   
4. 
   Двойственные графы.
   
5. 
   Деревья и лес.
   
6. 
   Раскраска графа. Хроматическое число графа.
   

1. 
   Орграф. Матрица смежности. Изоморфизм.
   
2. 
   Степень вершины орграфа.
   
3. 
   Маршруты, цепи, циклы в орграфах.
   
4. 
   Связность орграфа.
   
5. 
   Эйлеровы цепи и циклы в орграфе.
   
6. 
   Полный орграф.
   
7. 
   Нахождение кратчайщих маршрутов