Электронная книга

Высказывание, связки, истинность, тавтология и противоречие, эквивалентность пропозициональных форм, законы Де Моргана, полные системы связок). Понятие исчисления высказываний (понятие формальной аксиоматической теории; логический вывод, аксиомы и правила вывода. Функция, порождаемая пропозициональной формой; построение формы, порождающей заданную функцию). Цифровые логические схемы (типы вентилей, синтез схем по таблицам истинности, дизъюнктивные нормальные формы.Высказывания с кванторами, истинность, отрицание высказываний с кванторами). Понятие исчисления предикатов (понятие формальной аксиоматической теории; логический вывод, аксиомы и правила вывода. Структура формальных доказательств. Прямое доказательство. Доказательство с помощью контрпримеров. Доказательство от противного. Доказательство посредством контрапозиции.Использование принципа математической индукции (провести доказательство какого-нибудь утверждения с использованием индукции). Принадлежность, включение, операции над множествами, тождества, законы Де Моргана. Понятие булевой алгебры, примеры. Бинарные отношения. Отношение эквивалентности на множестве. Порождаемое им разбиение на смежные классы, их свойства. Отношение порядка. Понятие конечного автомата, распознающего язык. Размещения, перестановки, сочетания, сочетания с повторениями. Бином Ньютона. Ориентированные/неориентированные, подграфы, степень вершины, теоремы о сумме степеней и о кол-ве нечетных вершин в графе. Пути, цепи и контуры (определения, эйлеровы и гамильтоновы контуры — теоремы и следствия существования в ориентированных и неориентированных графах). Связность граов. Представление графов с помощью матриц инцидентности. Теорема о степени матрицы инцидентности. Деревья и их свойства, каркасы (остовные деревья). Графы с весами. Алгоритм построения каркаса минимального веса (алгоритм Kruskal’а). Бинарные деревья, полные бинарные деревья и их свойства. Организация хранения упорядоченных данных в виде бинарного дерева. Алгоритмы поиска, вставки и удаления узлов в деревьях. Сбалансированные деревья (определение, преимущества организации хранения упорядоченных данных в виде бинарного сбалансированного дерева). Алгоритм балансировки.

Темы: Программирование, Алгоритмы и дискретные структуры