Программа курса Теория множеств

Множества, способы задания множеств. Диаграммы Венна. Операции над множествами. Бинарное отношение между элементами множества, виды бинарных отношений. Свойства операций над множествами.

Комбинаторика

Перестановки, размещения, сочетания без повторений. Выборки из множества с повторением элементов. Правило суммы, правило произведения. Формула включений и исключений.

Последовательности, рекуррентные соотношения. Возвратные последовательности. Характеристический многочлен возвратной последовательности. Общее и частное решение рекуррентного соотношения.

Алгебра логики

Булевы переменные, булевы функции. Основные булевы функции одного и двух аргументов. Существенные и фиктивные переменные. Булева алгебра, основные законы. Элементарная дизъюнкция, элементарная конъюнкция, дизъюнктивная и конъюнктивная нормальные формы. Нахождение нормальных форм с использованием законов булевой алгебры. Конституента единицы, конституента нуля. Совершенные дизъюнктивная и конъюнктивная нормальные формы. Построение совершенных форм по таблице истинности и с использованием законов булевой алгебры.

Импликанта, простая импликанта. Сокращенная дизъюнктивная нормальная форма, тупиковая дизъюнктивная нормальная форма, минимальная ДНФ. Метод Квайна, операции склеивания и поглощения, импликантная таблица, процедура ветвления. Нахождение минимальной ДНФ с помощью карт Карно, покрытие.

Булева алгебра в применении к переключательным схемам.

Графы

Графы, вершины, ребра, порядок графа. Смежные вершины, понятие инцидентности ребра и вершины. Полные графы, мультиграфы, псевдографы, орграфы, взвешенные графы. Степень вершины, лемма о "рукопожатиях". Способы задания графа, матрицы смежности и инцидентности. Изоморфные графы.

Маршрут, его длина. Цепь, простая цепь. Цикл, простой цикл. Связный граф, компоненты связности графа.

Эйлеровы циклы, эйлеровы графы. Теорема Эйлера. Алгоритм Флери нахождения эйлеровой цепи в связном графе.

Остов графа. Минимальный остов взвешенного графа, алгоритм Краскала. Кратчайший маршрут, алгоритм Флойда-Уоршалла нахождения матрицы кратчайших расстояний.

Конечные автоматы

Определение автомата, функция переходов, функция выходов, входной и выходной алфавиты, команды автомата. Функционирование автомата. Способы задания автоматов. Автомат, реализующий двоичное суммирование n-разрядных чисел. Эквивалентные автоматы. Минимальный автомат, алгоритм Мили поиска минимального автомата, разбиение состояний на классы.

Рекомендуемая литература

1. Горбатов В.А. Основы дискретной математики. – М.: Высшая школа, 1986 г.

2. Каскевич В.И., Побегайло А.П., Янцевич В.А. Элементы дискретной математики. – Минск, 1998 – 57 с.

3. Кук Д., Бейз Д. Компьютерная математика – М.: Наука, 1990.

4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженеров. М.: Энергоатомиздат, 1988. – 476 с.

5. Лавров В.И., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Наука, 1984. – 223 с.

6. Насыров З.Х. Дискретная математика. – Обнинск, 1999. – 125 с.

7. Оре О. Теория графов. М.: Наука, 1980.

8. Фудзисава Т., Касами Т. Математика для радиоинженеров. Теория дискретных структур. – М.: Радио и связь, 1984.