Реферат: Множества

Глава 1. Множества

Определить понятие множества и его элементов. Какие есть способы задания множеств? Подмножества и собственные подмножества. Привести примеры.

Операции над множествами (объединение, пересечение, дополнение, разность, симметрическая разность) – дать определение и изобразить графически.

Способы представления множеств в ЭВМ – перечислить, дать характеристику основных особенностей, пояснить различия в применении.

Дать определение основных свойств операций над множествами (коммутативность, ассоциативность, дистрибутивность, двойственность…). Где используются эти свойства? Привести примеры.

Основная идея алгоритма типа слияния применительно к операциям над множествами (взять для примера две – три операции).

Чем отличаются разбиения и покрытия? Что такое отношение эквивалентности? (дать определения, проиллюстрировать на примерах).

Определить понятие отношений на множествах. Перечислить способы задания отношений, привести примеры.

Специальные отношения (обратное, универсальное, тождественное) – дать определение, проиллюстрировать графически. Понятие композиции отношений. Привести примеры.

Свойства отношений (рефлексивность, симметричность, транзитивность, антирефлексивность, антисимметричность, полнота) – дать определение, привести пример. Проверка свойств отношений с помощью матриц.

Представление отношений в ЭВМ и проверка свойств отношений с помощью матриц; привести примеры.

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

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

Понятие принципа математической индукции (индуктивное определение, индуктивное доказательство, с примерами).

Глава 2 Комбинаторика

Понятие комбинаторных задач. Сформулировать основные комбинаторные принципы (сложения и умножения), привести примеры.

Что такое перестановка элементов множества? Как определить количество различных перестановок? Чем отличается перестановка с повторениями элементов? Привести примеры.

Что такое выборка в комбинаторике? Объяснить различие между размещениями и сочетаниями, выборками с повторениями и без. Привести примеры.

Размещения и сочетания без повторений – дать определения, охарактеризовать общие черты и различия; привести формулы для расчета числа вариантов. Привести примеры.

Размещения и сочетания с повторениями – дать определение, охарактеризовать общие черты и различия; привести формулы для расчета числа вариантов. Привести примеры.

Биномиальные коэффициенты C(n,k) – дать определение. Сформулировать свойства биномиальных коэффициентов. Использование треугольника Паскаля для нахождения С(n,k).

Перестановки с повторениями – дать определение, привести формулу для расчета числа вариантов. В чем отличие от перестановок без повторений? Привести примеры.

Комбинаторный принцип сложения для пересекающихся множеств, его отличие от случая непересекающихся множеств. Формулировка принципа включения и исключения и иллюстрация его графически; привести пример использования.

Понятие разбиений. Упорядоченные и неупорядоченные разбиения – различие, способ подсчета числа вариантов. Формулировка полиномиальной теоремы.

Бином Ньютона и полиномиальная теорема – привести формулировки; охарактеризовать общие черты и различия. Привести примеры.

Биномиальные коэффициенты C(n,k) – дать определение. Сформулировать свойства биномиальных коэффициентов. Использование треугольника Паскаля для нахождения С(n,k).

^ Глава 3 Графы

Графы – основные понятия, способы представления. Как связаны графы с бинарными отношениями? Изобразить в виде графа соответственно рефлексивное, симметричное, антисимметричное отношения, эквивалентность.

Виды графов (простой, орграф, псевдограф, мультиграф) и их связь с бинарными отношениями. Произведение графов. Примеры.

Понятие дерева и ориентированного дерева, их свойства, общие черты и различия. Привести примеры. Операции добавления и удаления вершин и ребер в графе – описать, проиллюстрировать на примерах.

Способы представления графов в ЭВМ, их связь с бинарными отношениями.

Виды графов – пустой, полный, двудольный, сети. Определить и проиллюстрировать операцию стягивания ребер в графе.

Подграфы – дать определение, привести примеры. Дать определение собственного подграфа. Какой подграф является остовом? Минимальный остов и алгоритм его построения.

Понятие обхода графа. Поиск в глубину и в ширину – общее и различия.

Эйлеровы и гамильтоновы графы, понятия эйлеровой цепи, цикла, гамильтонова цикла. Алгоритм поиска эйлеровой цепи. Привести примеры.

Понятие связности, компонент связности, сильной и слабой связности орграфа. Построение фактор-графа. Привести пример.

Маршруты, цепи, циклы в графе – дать определение понятий. Расстояние между вершинами, диаметр графа. Операция соединения графов. Привести примеры.

Алгоритмы поиска кратчайших расстояний в графе – назвать, кратко охарактеризовать. Пояснить, в чем различие алгоритмов Флойда-Уоршалла и Дейкстры.

Какие существуют классические задачи, для решения которых применяются графы (краткая характеристика)? Что позволяет найти алгоритм Дейкстры?

Глава 4 Алгебра логики

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

Понятие нормальных форм. Формулировка и использование теоремы о разложении булевой функции по k переменным.

Совершенные нормальные формы булевой функции – определение, способы их построения. Привести примеры.

Высказывания алгебры логики, операции над ними. Таблицы истинности основных операций и их приоритет. Как можно изменить порядок выполнения действий в формуле алгебры логики?

Какова взаимосвязь контактных схем и булевых функций? Применение булевой алгебры для упрощения контактных схем – привести примеры.

Карта Карно – внешний вид, способ построения, использование для упрощения булевых функции. Привести примеры.

Карты Карно: построение, определения, использование для нахождения упрощенного представления функции, для упрощения частично определенной функции. Привести примеры.

Функции алгебры логики частичные и полностью определенные – дать определения, привести примеры, пояснить, как выполняется их упрощение.

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

Классы булевых функций, примеры.

Алгебра Жегалкина. Переход от алгебры Жегалкина к алгебре Буля. Многочлен Жегалкина.

Теорема Поста (формулировка, применение, примеры)