Дискретная математика. Файзрахманов Р.А. - 5 стр.

www.asu.pstu.ac.ru


          Методические указания по самостоятельному изучению курса


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]. Алгебра высказываний.
Операции логики высказываний, приоритетность операций. Противоречие и
тавтологий. Основные равносильности алгебры высказываний, их толкование.