Множества и операции над ними. Основные понятия
Лемма.
Пустое множество единственно
Операции над множествами
Диаграммы
Эйлера-Венна
Свойства операций над множествами. Алгебра
множеств
Декартово произведение множеств Изобретение
парового лифта (первый образец был установлен
в Нью-Йорке в 1857 г.), а вслед за ним и открытие электричества (1880 г.) практически
решало проблемы подъема на большую высоту Луис Кан совершенствовал принципы развивающейся
с течением времени пространственной структуры, принципы
единства архитектуры и конструкции.
Отображения множеств
Основные понятия
Произведение (композиция) отображений
Обратные
отображения
Мощности множеств и комбинаторика Вычислим
объем шара Примеры решения и оформления задач контрольной работы
Перестановки
и размещения
Сочетания
Бином
Ньютона. Понятие о производящей функции
Примеры и свойства счетных
множеств
Несчетные множества. Мощность континуума
Кардинальные
числа. Гипотеза континуума
Основные понятия и способы задания отношений
Отношения
на числовых множествах удобно иллюстрировать графически
Отношения
на конечных множествах
Операции над бинарными
отношениями и их свойства.
Отношения эквивалентности
Свойства
классов смежности
Отношения частичного
порядка
примеры
Понятие об алгебраических
структурах
Примеры
Примеры
Коммутативное
тело называется полем
Пусть m – натуральное число
Алгебраические
структуры с тремя операциями
Элементы математической логики
Логика
высказываний Понятие логического высказывания
Логические
операции
Дизъюнкция высказываний
Эквиваленция
высказываний
Пропозиционные формулы
Тавтологии
Равносильные
формулы
Булевы функции
Представление булевых
функций пропозиционными формулами
Двойственные
функции. Принцип двойственности
Совершенные конъюнктивные
нормальные формы (СКНФ)
Полиномы Жегалкина
Полнота
и замкнутость
Полные системы функций и замкнутые классы
Основные
замкнутые классы
Многочлены Жегалкина первой степени
Теоремы
о функциональной полноте
Базисы пространства
булевых функций
Минимизация булевых функций. Постановка
задачи
Метод Квайна-Макклоски
Нахождение первичных минитермов
Расстановка
меток
Вычёркивание лишних строчек
Карты
Карно булевой функции
пример
Карта Карно
для функций пяти переменных
Реализации булевых функций
Контактные
схемы
Проанализировать и упростить следующую схему
Схемы
из функциональных элементов
Синтезировать
логическую схему, реализующую булеву функцию
Пример . Синтез
n–разрядного сумматора
Предикаты
Основные понятия
и определения
Операции над предикатами
Навешивание
кванторов
Равносильные формулы логики предикатов
Приведенная
форма и предваренная нормальная форма предиката
Элементы теории графов
Основные
определения и типы графов
Основные
типы графов
Обобщения понятия графа
Изоморфные
графы
Основные числовые характеристики и матрицы графа
Степени
вершин графа
Матрица смежности
Матрица
Кирхгофа
Матрица инцидентности
Подграфы
и операции на графах.
Пересечение графов
Маршруты
в графах. Связные графы
Компоненты связности. Связность
графа и его дополнения
Расстояния на графах
Метод
поиска в ширину
Выяснение вопросов связности, достижимости и расстояний
на графе по матрице смежности
Деревья и остовы Критерии
дерева
Корневое дерево
Типы вершин
дерева, радиус и центры
Остовы графа, циклический ранг
и ранг разрезов
Задача о минимальном остове
Алгоритм
Краскала
Разрезы графа. Фундаментальная система
циклов и фундаментальная система разрезов
Линейное
пространство графа
Эйлеровы и гамильтоновы графы
Эйлеровы
графы Замечания
Гамильтоновы графы
Задача
о коммивояжере
Планарные графы
Вложимость графов
в трехмерное пространство
Формула Эйлера
Следствия
из формулы Эйлера
Гомеоморфные графы. Критерий
планарности
Раскраски графов Хроматическое число графа
Задача
о распределении оборудования
Хроматическое
число 2–дольного графа. Критерий 2-дольности
Некоторые
оценки хроматического числа
Раскраски планарных графов
Паросочетания
графа
Задача о свадьбах
Теорема
Холла о свадьбах
Сети Основные понятия
Потоки
в сетях
Сетевое планирование
Алгоритм поиска
критического пути
Резервы времени