Преподаватель Таланова В.А.

I. ВВЕДЕНИЕ

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

Требования к знаниям и умениям по завершению изучения дисциплины.

                        иметь представление: об основных направлениях дискретной математики. 

                       знать и уметь использовать:   методы дискретной математики, наиболее употребительные при решении практических задач. 

                        владеть: основными приемами доказательств и способами решения задач дискретной математики. 

                        иметь опыт: применения алгоритмов решения задач дискретной математики и способов представления математических объектов в программах.

Период прохождения курса (1 курс, 2 семестр, экзамен)

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

Лекционный материал (36 часов)

1.       Введение. Предмет дискретной математики. Множества и операции над ними. Декартово произведение множеств, его свойства, кортежи.

2.       Отображение множеств. Функции, способы их задания, рекурсивные процедуры. Общие свойства отображений.

3.       Отношения, их свойства Отношения порядка и отношения эквивалентности. Мощность множества.

4.       Упорядоченные, частично упорядоченные, вполне упорядоченные множества. Отображения, сохраняющие порядок. Метод математической индукции.

5.       Предмет комбинаторики. Правила суммы и произведения. Правила включений и исключений Размещения с повторениями. Число отображений к- множества в m-множество.

6.       Размещения без повторений. Перестановки без повторений. Упорядоченные множества и обратимые отображения.

7.       Сочетания без повторений. Перестановки с повторениями. Сочетания с повторениями. Рекуррентные соотношения.

8.       Операции и алгебры. Алгебраические структуры. Замыкания и подалгебры. Алгебра термов. Свойство операций.  

9.       Гомоморфизм. Изоморфизм. Полугруппы, моноиды, группы, кольца. Булевы алгебры.

10.   Булевы функции: элементарные, функции алгебры логики, существенные и несущественные переменные, булевы функции одной переменной, булевы функции двух переменных.

11.   Формулы подстановки и замены. Алгебра булевых функций. Разложение булевых функций по переменным. Алгоритм вычисления значений булевой функции. Замыкание множества булевых функций. Полнота.

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

13.   Виды графов и операции над ними. Представление графов в ЭВМ. Требования к представлению. Матрица смежности. Матрица инцидент-ности. Списки смежности. Обход графов. Релейно -контактные схемы для реализации булевых функций.

14.   Связность. Объединение графов и компоненты связности. Вершинная и реберная связность. Взвешенные графы. Алгоритм Краскала  для нахождения графа минимального веса.

15.   Деревья и лес. Свободные деревья. Основные свойства деревьев. Ориентированные, упорядоченные и бинарные деревья. Представление деревьев в ЭВМ.

16.   Планарность. Укладка графов. Теорема Эйлера. Циклы и коциклы. Эйлеровы циклы. Эйлеровы графы.

17.   Независимость и покрытия. Раскраска графов. Теорема о пяти красках. Алгоритмы раскрашивания.

Практические занятия (семинары)  (36 часов)

1.       Операции над множествами.

2.       Соответствия и отображения, отношения порядка

3.       Равномощные множества. Счетные множества.

4.       Метод математической индукции.

5.       Правило включений и исключений. Размещения.

6.       Перестановки, Сочетания.

7.       Комбинаторика разбиений, рекуррентные соотношения.

8.       Булевы векторы, способы задания булевых функций. Формулы.

9.       Специальные виды формул. Минимизация булевых функций, существенные и фиктивные переменные.

10.   Основные понятия теории графов, числовые характеристики, ориентированные графы.

11.   Деревья и двухполюсные сети. Реализация булевых функций релейно-контактными схемами.

Форма отчетности:

2.       Дискретная математика для программистов./ Новиков Ф.А.-СПб.; Питер,2001.

3.       Введение в дискретную математику/ Наука. Москва. 1986.

4.       Дискретная математика (часть I)./ Солон Б.Я. Учебное пособие. Иваново, ИГХТУ 1997.

5.       Дискретная математика/Таланова В.А. Методические указания. Иваново, ИГХТУ 2004.

Дополнительная

1.       Дискретный анализ./ Романовский И.В. Невский диалект, 1999.

2.       Элементы математической логики./ Новиков СП. Москва, Наука, 1973.

3.       Сборник задач по дискретной математике ./ Гаврилов ГЛ., Сапоженко А.. Москва. Наука 1977.