Дискретная математика. Рабочая программа дисциплины. Файзрахманов Р.А. - 4 стр.

                                                                                                  4

                                      2. Содержание дисциплины

                            2.1. Наименование тем, их содержание

     1. ОСНОВЫ ТЕОРИИ МНОЖЕСТВ [5, с. 2-11; 7, с. 19-32]. Понятие множества.
Парадоксы. Способы задания множеств. Разновидности множеств. Свойства отношения
включения. Основные операции над множествами. Диаграмма Эйлера - Венна. Основные
законы алгебры множеств, их использование. Решение уравнений алгебры множеств с одним
неизвестным

     2. ГРАФИКИ, СООТВЕТСТВИЯ, ОТНОШЕНИЯ[5, с. 11-18; 7, с. 33-49]. Графики,
композиция графиков, понятие соответствия. Свойства соответствий. Функции и отображения.
     Отношения, операции над отношениями, свойства отношений. Разбиения и отношения
эквивалентности, отношения порядка.

     3. РЕШЕТКИ, МОЩНОСТЬ МНОЖЕСТВ. [5, с. 19-23; 7, С. 67-71]. Частично-
упорядоченное множество, их экстремальные элементы. Понятие решетки. Понятие алгебры.
Алгебраическое представление решеток. Основные законы алгебры решеток, Разновидности
решеток.

      4. ОСНОВЫ ТЕОРИИ ГРАФОВ [7,8, 9]
      Основные понятия теории графов. Виды графов. Элементы графов, маршруты, циклы [7,
c. 189-201; 8, c. 15-24; 9, c. 195-201; 16, c. 101; 17, c. 67-72]. Операции над графами [7, c. 199-
200; 8, c. 28-34; 9, c. 210-214]. Способы представления графов [7, c. 201-205; 8, c. 56-61; 9, c.
201-210]. Основные характеристики графов: степени графов, цикломатическое число,
хроматическое число, функция Гранди, внутренне-устойчивое и внешне-устойчивое множества
и их числа, ядро графа, клика графа. Ярусно-параллельная форма графа. Алгоритмы
определения основных характеристик и приведения графа к ярусно-параллельной форме [8, c.
34-55; 16, c. 102-110; 17, c. 75-76]. Эйлеровы графы, Эйлеровы цепи, теорема Эйлера. Алгоритм
построения Эйлерова цикла [7, c. 263-265; 8, c. 66-67; 9, c. 215-217]. Гамильтоновы графы,
Гамильтоновы цепи [7, c. 265-267; 8, c. 68-69; 9, c. 217; 16, c. 104]. Полные графы и деревья [7,
c. 197, 234-242; 8, c. 16-17, 69-71; 9, c. 197, 223-225; 16, c. 103-104]. Связность графа. Плоские и
планарные графы. Эйлерова характреристика, теорема о пяти красках [7, c. 283-286; 8, c. 24; 16,
c. 111]. Определение путей и расстояний в графе [7, c. 195-196, 228-232; 8, c. 61-66]. Задачи на
графах: коммивояжера, о наименьшем покрытии, о кратчайшем расстоянии, о раскрашивании
(общая постановка и принципы решения) [7, c. 267-268, 277-279, 285-289, 228-233].

      5. ОСНОВЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ И ПЕРЕКЛЮЧАТЕЛЬНЫЕ ФУНКЦИИ [1;
7, с. 79-98; 3, с. 2-11; 9, с. 111-168]. Алгебра высказываний. Операции логики высказываний,
приоритетность операций. Противоречие и тавтологий. Основные равносильности алгебры
высказываний, их толкование.              Нормальные формы представления высказываний.
Преобразование высказываний от нормальных форм к совершенным нормальным формам.
Преобразование высказываний от СДНФ к СКНФ и наоборот. Минимизация сложных
высказываний. Методы минимизации. Переключательные (булевы) функции (ПФ). Способы
задания ПФ, разложения ПФ, неполностью определенные ПФ, минимизация ПФ, теорема о
функциональной полноте, примеры функционально-полных базисов. Разрешимость класса
формул (наличие нормальной формы)


     6. ОСНОВЫ ТЕОРИИ АВТОМАТОВ [7, с. 2-10]. Понятие автомата. Описание автоматов.
Законы функционирования автоматов. Преобразование автомата Мили к эквивалентному
автомату Мура. Преобразование автомата Мура к эквивалентному автомату Мили.
Минимизация автоматов. Распознающие автоматы.