### Дискретная математика 2016

Досрочный экзамен: 26.12.2016 11:00 (место будет известно позднее)

Экзамены по группам: см. расписание на сайте ИТМО.

Рассмотренные темы:

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