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

1. Теория множеств

1.1. Множества и операции над ними

1.1.1. Понятие множества

1.1.2. Способы задания множеств

1.1.3. Основные определения

1.1.4. Диаграммы Эйлера – Венна

1.1.5. Операции над множествами

1.1.6. Системы множеств

1.1.7. Законы алгебры множеств

1.1.8. Решение задач 1-3 контрольной работы № 1.

1.1.9. Контрольные вопросы и упражнения

1.2. Бинарные отношения

1.2.1. Декартово произведение множеств

1.2.2. Определение бинарного отношения

1.2.3. Способы задания бинарного отношения

1.2.4. Свойства бинарных отношений

1.2.5. Отношения эквивалентности

1.2.6. Отношения порядка

1.2.7. Решение задачи 4 контрольной работы № 1.

1.2.8. Контрольные вопросы и упражнения

1.3. Реляционная алгебра

1.3.1. Применение отношений для обработки данных

1.3.2. Теоретико-множественные операции реляционной алгебры

1.3.3. Специальные операции реляционной алгебры

1.3.4. Решение задачи 5 контрольной работы № 1.

1.3.5. Контрольные вопросы и упражнения

1.4. Конечные и бесконечные множества

1.4.1. Биекция

1.4.2. Равномощные множества

1.4.3. Классы равномощных множеств

1.4.4. Сравнение множеств по мощности

1.4.5. Определение конечного множества

1.4.6. Свойства конечных множеств

1.4.7. Определение счетного множества

1.4.8. Свойства счетных множеств

1.4.9. Несчетные множества

1.4.10. Выводы

1.4.11. Решение задачи 6 контрольной работы № 1.

1.4.12. Контрольные вопросы и упражнения

1.5. Комбинаторика

1.5.1. Задачи комбинаторики

1.5.2. Типы выборок

1.5.3. Основные правила комбинаторики

1.5.4. Размещения с повторениями

1.5.5. Размещения без повторений

1.5.6. Перестановки без повторений

1.5.7. Перестановки с повторениями

1.5.8. Сочетания

1.5.9. Сочетания с повторениями

1.5.10. Решение задач 7,8 контрольной работы № 1.

1.5.11. Бином Ньютона

1.5.12. Свойства биноминальных коэффициентов

1.5.13. Контрольные вопросы и упражнения

2. Элементы математической логики

2.1. Логика высказываний

2.1.1. История математической логики

2.1.2. Понятие высказывания

2.1.3. Операции над высказываниями

2.1.4. Таблицы истинности

2.1.5. Формулы логики высказываний

2.1.6. Равносильные преобразования формул

2.1.7. Решение задач контрольной работы № 2.

2.1.8. Контрольные вопросы и упражнения

2.2. Логические рассуждения

2.2.1. Определение логически правильного рассуждения

2.2.2. Проверка правильности логического рассуждения

2.2.3. Прямые и косвенные методы доказательств

2.2.4. Решение задачи контрольной работы № 2.

2.2.5. Контрольные вопросы и упражнения

2.3. Логика предикатов

2.3.1. Понятие предиката

2.3.2. Кванторы

2.3.3. Формулы логики предикатов

2.3.4. Равносильные преобразования формул

2.3.5. Рассуждения в логике предикатов

2.3.6. Решение задачи контрольной работы № 2.

2.3.7. Контрольные вопросы и упражнения

3. Основы теории графов

3.1. Ориентированные графы

3.1.1. Основные понятия

3.1.2. Орграфы и бинарные отношения

3.1.3. Матрицы орграфа

3.1.4. Решение задачи 5 контрольной работы № 2.

3.1.5. Контрольные вопросы и упражнения

3.2. Неориентированные графы

3.2.1. Основные термины

3.2.2. Матрицы графа

3.2.3. Решение задачи 6 контрольной работы № 2.

3.2.4. Контрольные вопросы и упражнения

3.3. Планарные графы

3.3.1. Изоморфизм графов

3.3.2. Планарность

3.3.3. Критерий планарности

3.3.4. Решение задачи 7 контрольной работы № 2.

3.3.5. Контрольные вопросы и упражнения

3.4. Связность графов

3.4.1. Маршруты

3.4.2. Компоненты связности

3.4.3. Эйлеровы цепи и циклы

3.4.4. Цикломатическое число

3.4.5. Решение задачи 8 контрольной работы № 2.

3.4.6. Контрольные вопросы и упражнения

3.5. Графы без циклов

3.5.1. Дерево и лес

3.5.2. Свойства деревьев

3.5.3. Каркасы графа

3.5.4. Обход графа “в ширину”

3.5.5. Обход графа “в глубину”

3.5.6. Решение задачи 9 контрольной работы № 2.

3.5.7. Контрольные вопросы и упражнения

Приложение 1. Контрольная работа № 1.

Приложение 2. Контрольная работа № 2.