ВОПРОСЫ НА ЭКЗАМЕН ПО КУРСУ
«ДИСКРЕТНАЯ МАТЕМАТИКА»
Тема 1. Комбинаторика
Правило суммы и произведения в комбинаторике, понятие выборки. Размещения с повторениями и без них. Перестановки с повторениями и без них. Сочетания с повторениями и без них. Бином Ньютона. Свойства биномиальных коэффициентов. Треугольник Паскаля. Применение производящих функций для решения рекуррентных соотношений. Метод математической индукции.Тема2. Множества
Множества, основные определения, задание множеств. Подмножества и их свойства. Множество всех подмножеств. Операции над множествами, диаграммы Венна-Эйлера. Свойства операций над множествами. Покрытия и разбиения множеств. Принцип Дирихле. Формулы включений и исключений. Декартово произведение множеств. Бинарные отношения и их свойства, отношение эквивалентности. Отношения строгого, нестрогого порядка, отношения соответствия, функциональные отношения. Множества бесконечные, счетные, несчетные. Сравнение бесконечных множеств. Нечеткие множества. Основные понятия, операции.Тема 3. Логика высказываний. Булева алгебра.
Высказывания, операции над ними и их основные союзы. Высказывательные формулы, тавтологии, логическое следование. Законы алгебры логики. Понятие предиката, местность предиката. Кванторные операции. Булевы функции. Замкнутые классы. Полные системы булевых функций. Критерий полноты Поста. Представление булевой функции в виде формулы. Свойства совершенства. Геометрическая форма. Аксиомы и теоремы булевой алгебры. Дизъюнктивная нормальная форма (ДНФ).Совершенная дизъюнктивная нормальная форма (СДНФ): способы ее получения. Конъюнктивная нормальная форма (КНФ). Совершенная конъюнктивная нормальная форма (СКНФ): способы ее получения. Минимизация БФ. Минтермы, их свойства. Метод Квайна. Методы минимизация БФ: Квайна - Мак-Класки, Блейка-Порецкого, испытания остатков. Основные характеристики методов. Минимизация БФ. Понятие импликанты, метод получения простых импликант по карте Вейча. Алгоритм построения всех тупиковых ДНФ. Понятие порядка БФ. Граф-схема БФ. Повышение порядка БФ. Проблема интерпретации в многозначной логике. Трехзначное исчисление высказываний Лукасевича. Понятие о функциях k-значной логики, их особенности.Тема 4. Графы
Графы: основные понятия. Способы задания. Виды графов. Операции над графами. Графы: матрицы смежности и инцидентности. Изоморфизм в теории графов. Графы: маршруты, цепи, циклы. Связность графа. Эйлеровы и гамильтоновы циклы. Метод нахождение всей простых цепей в графе, его применение. Задача о коммивояжере. Метрики графа. Планарные и плоские графы. Теорема Эйлера о плоских графах. Гомеоморфизм в теории графов. Критерий Понтрягина-Куратовского. Двойственные графы, их применение. Деревья и лес. Цикломатическое число графа и фундаментальная система циклов. Алгоритм кодирования деревьев. Построение дерева по его коду. Хроматическое число графа. Гипотеза четырех красок. Орграфы: основные понятия, способы задания. Степень вершины. Орграфы: связность, эйлеровы цепи и циклы. Полный орграф. Теория трансверсалей. Сети. Нахождение максимальной пропускной способности транспортной сети. Бинарные отношения и орграфы. Диаграмма Хассе. Задачи теории расписаний. Диаграмма Гантта. Расчет сетевой модели.Тема 5. Формальные грамматики
Формальные грамматики: основные понятия. Некоторые свойства грамматик. Формальные грамматики: иерархия языков. Грамматический разбор.Тема 6. Алгоритмы
Интуитивное понятие алгоритма и необходимость его уточнения. Машины Тьюринга (одноленточные детерминированные), функции ими вычислимые.