Вопросы к экзамену по курсу Дискретная математика
.pdfВопросы к экзамену по курсу Дискретная математика
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.