1 семестр – Дискретные структуры

Часы: 72 Лекции 36 Практикум (решение задач) : да 36 часов
Преподаватель:

Описание:

1. Логика высказываний, высказывание, связки, истинность, тавтология и противоречие, эквивалентность пропозициональных форм, законы Де Моргана, полные системы связок. Понятие исчисления высказываний, понятие формальной аксиоматической теории; логический вывод, аксиомы и правила вывода
2. Булевы функции (функция, порождаемая пропозициональной формой; построение формы, порождающей заданную функцию). Цифровые логические схемы (типы вентилей, синтез схем по таблицам истинности, дизъюнктивные нормальные формы).
3. Логика предикатов (высказывания с кванторами, истинность,отрицание высказываний с кванторами). Понятие исчисления предикатов (понятие формальной аксиоматической теории; логический вывод, аксиомы и правила вывода).
4. Методы доказательств. Структура формальных доказательств. Прямое доказательство. Доказательство с помощью контрпримеров. Доказательство от противного. Доказательство посредством контрапозиции.
5. Математическая индукция. Использование принципа математической индукции (провести доказательство какого-нибудь утверждения с использованием индукции).
6. Теория множеств (принадлежность, включение, операции над множествами, тождества, законы Де Моргана). Понятие булевой алгебры, примеры.
7. Отношения, бинарные отношения. Отношение эквивалентности на множестве. Порождаемое им разбиение на смежные классы, их свойства. Отношение порядка.
8. Формальные языки. Понятие конечного автомата, распознающего язык.
9. Комбинаторика (размещения, перестановки, сочетания, сочетания с повторениями). Бином Ньютона
10. Графы (ориентированные/неориентированные, подграфы, степень вершины, теоремы о сумме степеней и о кол-ве нечетных вершин в графе).
11. Пути, цепи и контуры (определения, эйлеровы и гамильтоновы контуры — теоремы и следствия существования в ориентированных и неориентированных графах). Связность графов. Представление графов с помощью матриц инцидентности. Теорема о степени матрицы инцидентности.
12. Деревья и их свойства, каркасы (остовные деревья). Графы с весами. Алгоритм построения каркаса минимального веса (алгоритм Kruskal’а).
13. Бинарные деревья, полные бинарные деревья и их свойства. Организация хранения упорядоченных данных в виде бинарного дерева. Алгоритмы поиска, вставки и удаления узлов в деревьях.
14. Сбалансированные деревья (определение, преимущества организации хранения упорядоченных данных в виде бинарного / сбалансированного/ дерева). Алгоритм балансировки.