Дискретка_экзамен

Темы к экзамену по курсу

«Дискретная математика», семестр 2

Модуль 1. Множества и отношения

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

• Мощность множества. Биекция, инъекция, сюръекция. Понятие равномощности.

Конечные и бесконечные множества. Счетные множества (счетность множества рациональных чисел). Континуальные множества (несчетность отрезка [a,b], континуальность множества действительных чисел). Понятие мощности.

• Бинарные отношения. Понятие бинарного отношения. Понятие отношения эквивалентности. Теорема о разбиении множества на классы. Фактор-множество. График и граф бинарного отношения. Свойства бинарных отношений. Отношение порядка.

Модуль 2. Комбинаторика

• Основные типы комбинаторных объектов. Сочетания. Теорема о числе сочетаний из n элементов по k элементов. Перестановки. Число перестановок из n элементов (теорема). Перестановки с повторениями. Размещения (без повторений и с повторениями). Число размещений из n элементов по k элементов. Разбиения.

• Свойства и взаимосвязь комбинаторных объектов. Бином Ньютона. Комбинаторные тождества. Числа Стирлинга и их свойства. Принцип включения-исключения (теорема). Задача о “шляпах”.

• Перестановки и подстановки. Понятие подстановки. Теорема о числе подстановок из n элементов. Операция суперпозиции, ее свойства. Понятие инверсии. Четность перестановок и подстановок. Понятие транспозиции. Лексикографическое упорядочение перестановок.

Модуль 3. Теория графов