uzluga.ru
добавить свой файл
Вопросы для подготовки к экзамену по курсу «Дискретная математика»


Тема 1.Множества

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

Свойства операций над множествами (свойство коммутативности, ассоциативности, дистрибутивности операций). Законы поглощения, идемпотентности, де Моргана. Диаграммы Вьенна. Произведение множеств. Понятие прямого произведения множеств. Степень множества. Порядок и мощность множества. Конечные, счетные, несчетные множества. Порядок конечных множеств. Континуум- гипотеза.


Тема 2. Отношения

Бинарные отношения. Понятие бинарного отношения. Графическое и матричное представление отношений. Теоретико-множественные операции над отношениями. Произведение отношений. Обратное отношение. Транзитивное замыкание отношения. Свойства операций над отношениями. Теоретико-множественные свойства. Алгебраические свойства. Свойства отношений (свойство рефлективности, антирефлексивности, симметричности, антисимметричности, асимметричности, транзитивности, линейности). Инвариантность свойств отношений. Отношение эквивалентности. Классы эквивалентности. Отношения порядка. Понятие нестрогого и строгого порядка. Максимальные элементы множества. Отношение квазипорядка.

Тема 3. Функции

Функции и отображения. Понятие функции. Области определения и значений функции. Способы задания функций. Отображение, сюръекция, инъекция, биекция. Составная функция. Специальные виды функций. Подстановки. Последовательности. Функционалы.


Тема 4. Алгебраические структуры

Алгебраические операции и их свойства. Понятие операции. Свойства коммутативности, ассоциативности, дистрибутивности, существования единичного и обратных элементов операций. Алгебраические структуры. Понятие алгебраической структуры. Гомоморфизм и изоморфизм. Коммутативная диаграмма. Полугруппы и группы. Понятие полугруппы, моноида, группы. Свойства полугруппы и группы. Решение алгебраических уравнений в группе. Кольца и поля. Понятие кольца и поля. Делители нуля в кольце и область целостности. Свойства кольца и поля. Решение алгебраических уравнений над полем. Конечные поля. Упорядоченные поля.


Тема 5. Линейная алгебра

Векторное пространство. Понятие векторного пространства. Свойства пространства. Арифметическое (координатное) пространство. Базис и размерность векторного пространства. Линейная комбинация и линейная независимость векторов. Понятие базиса и размерности пространства. Разложение вектора по базису. Векторные подпространства. Понятие векторного подпространства. Линейная оболочка векторов и ее размерность. Свойство суммы размерностей двух подпространств.


Тема 6. Булевы структуры

Решетка. Верхние и нижние границы подмножества упорядоченного множества. Понятие решетки. Дистрибутивная решетка. Булева алгебра. Понятие и свойства булевой алгебры. Алгебра множеств. Алгебра высказываний. Простые и сложные высказывания, связки. Исчисление высказываний и таблицы истинности. Основные принципы логического вывода.


Тема 7 Комбинаторика

Перестановки и сочетания. Упорядоченная и неупорядоченная выборки. Понятие перестановок (размещений) и сочетаний. Формулы для числа перестановок и сочетаний с повторениями и без повторений. Формула включений и исключений. Разбиения. Понятие разбиения. Формулы для упорядоченных разбиений. Рекуррентные соотношения для числа неупорядоченных разбиений.


Тема 8 Графы

Неориентированные графы. Понятие неориентированного графа. Представление графа бинарным отношением, матрица смежности графа. Подграфы. Маршруты, циклы, связность. Ориентированные графы (орграфы). Понятие орграфа. Представление орграфа бинарным отношением, матрица смежности орграфа. Маршруты, циклы, петли. Типы связности орграфа. Подграфы и ориентированные деревья.


Рекомендуемая литература:

1. Акимов О.Е. Дискретная математика: логика, группы, графы. – М.: Лаборатория базовых знаний, 2001. – 352 с.

2. Белоусов А.И., Ткачев С.Б., Под ред. Зарубина В.С. Дискретная математика. – М.: МГТУ им Баумана, 2002. – 744 с.

3. Москинова Г.И. Математика для менеджера в примерах и упражнениях: учебное пособие. – М.: Логос, 2002. – 240 с.

4. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2004. – 304 с.

5. Романовский И.В. Дискретный анализ: Учебное пособие. – 2-е изд. исправ. – СПб.: Невский диалект, 2000. – 240 с.