Вопросы к экзамену по курсу Дискретная математика

Вопросы к экзамену по курсу Дискретная математика

1Высказывание. Операции дизъюнкции, конъюнкции и отрицания.

2Операция импликации, эквивалент и суммы по модулю 2.

3Пропозициональные формулы, булевы функции и их количество.

4Реализация булевых функций многочленами Жегалкина.

5Реализация булевых функций в ДНФ. Теорема о сокращенной ДНФ.

6Минимизация ДНФ. Релейно-контактные схемы.

7Полнота системы булевых функций.

8Классы функций, сохраняющих 0 или 1.

9Класс самодвойственных функций.

10Класс монотонных функций.

11Класс линейных булевых функций

12Теорема Поста о полноте системы булевых функций.

13Понятие предиката. Свободные и связанные переменные.

14Кванторы и их свойства.

. Множества и отношения.

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

2Декартово произведение множеств, бинарные отношения.

3Отношения эквивалентности и порядка.

4Функции.

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

1Перестановки, размещения и их количество.

2Перестановки с повторениями-

3Полиномиальная формула.

4Сочетания и их свойства.

5Сочетания с повторениями.

6Формула включений и исключений.

7Беспорядки, латинские прямоугольники: производящие функции.

8Линейные однородные рекуррентности.

Графы

1Понятие графа. Матрица смежности и её свойства.

2Подграф. Частичный, нулевой, полный, дополнительный граф. Соединение графов.

3Изоморфизм графов. Реализация графов в R3.

4Плоские и планарные графы.

5Цепи, циклы, связность.

6Теорема Эйлера о плоских графах.

7Следствия из теоремы о плоских графах.

8Эйлеровы графы. Задача о Кёнигсбергских мостах.

9Деревья. Цикломатическое число графа.

10Хроматическое число графа.

11Хроматический многочлен.

Литература

1Насыров 3.Х, Насыров А. 3. Дискретная математика. Учебное пособие - Обнинск: ИАТЭ, 2005.-80 с.

2Насыров 3.Х. Сборник задач по дискретной математике - Обнинск: ИАТЭ,

2003. – 76 с.

3Шевелев Ю.П. - Дискретная математика. - Издательство: Лань, 2016 — 592 с.

4Тишин В.В. - Дискретная математика в примерах и задачах. – СПб.: БХВПетербург, 2008 — 352 с.

5Гаврилов Г. П., Сапоженко А. А. Задачи и упражнения по дискретной математике: Учеб. пособие. — 3-е изд., перераб. — М.: ФИЗМАТЛИТ, 2009. — 416 с.

Дополнительная литература:

1Алексеев В.Б. Дискретная математика (курс лекций, 2-ой семестр). Сост. А.Д. Поспелов. — Москва, 2002.

2Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера.

— М.: Энергоатомиздат, 1988.

3Яблонский С.В. Введение в дискретную математику. — М.: Наука, 1986.

4Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. — М.: Наука, 1975.

5Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов — М.: Наука, 1985.

6Биркгоф Г., Барти Т. Современная прикладная алгебра. — М.: Мир, 1976.

7Холл М. Комбинаторика. — М.: Мир, 1970.

8Комбинаторный анализ. Задачи и упражнения./Под ред. К.А. Рыбникова. —

М.: Наука, 1982.

9Липский В. Комбинаторика для программистов. — М.: Мир, 1988.

10Зыков А.А. Основы теории графов. — М.: Наука, 1987.

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

12Харари Ф. Теория графов. — М.: Мир, 1973.