Экзаменационные вопросы по дискретной математике. Экзаменационные вопросы по дискретной математике
 Скачать 4.54 Kb.
|
|
Экзаменационные вопросы по дискретной математике Определение множества. Простейшие операции над множествами. Понятие булеана и мощности множеств. Мощность бесконечных множеств. Алгебра множеств. Основные тождества теории множеств. Нечеткие множества. Декартово произведение множеств. Свойства декартова произведения. Отношения. Графические представления отношений. Способы задания отношений. Свойства бинарных отношений. N-арные отношения. Реляционные отношения. Операции реляционной алгебры. Отношения эквивалентности. Отношения порядка. Отношения порядка. Диаграмма Хассе. Миноранта и мажоранта. Инфимум и супремум. Минимум и максимум. Мощности множеств. Бесконечные множества. Равномощность. Отображения и функции. Обратные функции и отображения. Способы задания функций. Функционал, оператор. Биекция, суръекция и инъекция. Размещения, перестановки и сочетания (без повторений и с повторениями). Биномиальные коэффициенты. Бином Ньютона. Графы, их вершины и ребра. Основные понятия графов. Классификация графов. Мультиграфы. Псевдографы. Операции на графах. Способы задания графов. Матрица инцидентности графа. Матрица смежности графа. Подграфы. Степени вершин графа. Эксцентриситет, радиус и диаметр графа. Матрица достижимости графа. Маршруты, цепи и циклы. Гамильтовы и эйлеровы графы и циклы. Ориентированные графы. Определение орграфа. Двойственные графы. Сети Петри. Социальные сети. Связный граф. Компоненты связности. Вершинная и реберная связность графа. Цикломатическое число графа. Древесные графы. Остовный граф. Построение минимального остовного графа. Алгоритм Краскала, алгоритм Прима. Матрица Кирхгофа. Определение числа остовов графа. Алгоритм Дейкстры. Булева алгебра. Высказывания. Операции на множестве высказываний. Основные тождества булевой алгебры. Функции алгебры логики. Булевые функции от одной переменной. Булевые функции от двух переменных. Функционально-полный набор функций. Специальные разложения БФ. СДНФ и СКНФ. Минимизация булевых функций. Карты Карно. Существенные и несущественные переменные. Грани, ребра гиперкуба. Максимальный интервал. Метод Квайна. Решение задачи покрытия. Релейно-контактные схемы. Теорема Шеннона. Логические схемы. Производные логических функций. Метод каскадов при синтезе логических схем. Элементы традиционной логики. Силлогизмы. Формальная система. Исчисление высказываний. Методы доказательства теорем. Метод Вонга. Метод резолюции. Дизъюнкты Хорна. Исчисление предикатов. Кванторы существования и всеобщности. Взаимосвязь кванторов. Основные соотношения алгебры предикатов. Предваренная нормальная форма. Сколемовская нормальная форма. Резолюция в исчислении предикатов. Определение кода и кодирования. Классификация кодов. Алфавитное кодирование. Разделимые схемы. Неравенство Макмиллана. Неравномерное кодирование. Кодирование с минимальной избыточностью. Метод Фано. Метод Хаффмана. Представление чисел в ЭВМ. Системы счисления. Перевод чисел из одной системы счисления в другую. Профессор В. Наумов |