1. Теория множеств. Операции над множествами. Диаграммы Эйлера – Венна. Соответствие между множествами. Примеры.

Теория множеств Множество Элемент множества Мощность множества Подмножество Пустое множество Способы задания множеств Примеры множеств

Операции над множествами ОбъединениеПересечениеРазность Симметрическая разность Дополнение Законы алгебры множеств

Диаграммы Эйлера – Венна Графическое изображение множеств Операции над множествами Примеры задач, решаемых с помощью диаграмм Эйлера - Венна

Декартово (прямое) произведение множеств Полностью и частично определенное множество Взаимнооднозначные и функциональные множества Примеры Соответствие между множествами

2. Отношения. Бинарное отношение. Свойства бинарных отношений (рефлексивность, симметричность, транзитивность). Классы отношений (эквивалентности, порядка, доминирования). Примеры.

Отношения. Бинарное отношение Отношение Виды отношений Обратное отношение Бинарное отношение Примеры

Свойства бинарных отношений (рефлексивность, симметричность, транзитивность) РефлексивностьСимметричностьТранзитивность Транзитивное замыкание Примеры

Классы отношений (эквивалентности, порядка, доминирования) Отношение эквивалентности (равенство) Отношение порядка Отношение доминирования (строгое упорядочение) Примеры

Примеры Таблицы СУБД Множество в языке Pascal

3. Логическое высказывание. Логические операции (связки). Виды формул логики высказываний. Решение логических уравнений. Примеры.

Логическое высказывание. Логические операции (связки) Высказывание Операции логики высказываний (отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность)

Виды формул логики высказываний Общезначимые формулы (тавталогия, тождественно истинные) Невыполнимые формулы (противоречие, тождественно ложные) Нейтральная формула

Решение логических уравнений Метод установления общезначимости (Таблицы истинности, Метод от противного, Равносильные преобразования)

4. Алгебра логики (Булева алгебра). Операции алгебры логики. Переключательные функции. Минимизация переключательных функций. Практическое значение.

Алгебра логики (Булева алгебра) Логическая функция Таблица истинности

Операции алгебры логики Дизъюнкция, Конъюнкция, Инверсия, Импликация, Функция Вебба – Стрелка Пирса, Функция Шеффера, Эквивалентность, Функция сложения по модулю 2 Законы алгебры логики

Переключательные функции СДНФ – совершенная дизъюнктивная нормальная форма СКНФ - совершенная конъюнктивная нормальная форма

Минимизация переключательных функций Цель минимизации С помощью законов эквивалентностей и упрощений Геометрический Метод Квайна, Метод Квайна – Мак-Класки Метод карт Карно

Практическое значение Логические схемы, графическое представление – построение функциональной схемы устройства Техническая реализация (релейно-контактные схемы)

5. Логика предикатов. Кванторы. Метод резолюций. Применение на практике.

Логика предикатов Предикат Атомарные выражения Состояние

Кванторы Квантор существования Квантор всеобщности («для всех») Свободные и связанные переменные Стандартизация переменных

Метод резолюций. Применение на практике Интерпретация Запросы в БД Логическое программирование Интеллектуальные системы

6. Основы комбинаторики. Размещения, перестановки, сочетания. Применение на практике.

Основы комбинаторики Комбинаторные вычисления Задача пересчета Задача перечисления

Размещения, перестановки, сочетания Размещение с повторениями Размещение без повторений Перестановка без повторений Перестановка с повторением данного состава Сочетание без повторений Сочетание с повторениями

Применение на практике Задачи оптимизации Задачи массового обслуживания Кодирование

7. Теория графов. Операции над графами. Алгоритмы поиска кратчайшего пути. Центр графа. Задачи, решаемые с помощью теории графов.

Теория графов Граф Элементы графа Ориентированный граф ЦиклМультиграф Части, Суграфы, Подграфы

Операции над графами ОбъединениеСуммаПроизведение Отождествление (слияние) вершин Расщепление вершин

Алгоритмы поиска кратчайшего пути Маршрут Длина ребра, Расстояние Алгоритм Краскала Алгоритм Дейкстры

Центр графа Понятие центра графа (внешний, внутренний) Абсолютный центр

Задачи, решаемые с помощью теории графов Минимаксные задачи Задачи массового обслуживания Анализ функционирования систем (кибернетика) Построение электрических цепей Анализ химических соединений

8. Теория алгоритмов. Свойства алгоритма. Модели алгоритмов (рекурсивные, машины Тьюринга, Поста, алгорифмы Маркова). Области применения.

Теория алгоритмов. Свойства алгоритма Алгоритм Свойства алгоритма (массовость, результативность, определенность, дискретность)

Модели алгоритмов (рекурсивные, машины Тьюринга, Поста, алгорифмы Маркова) Рекурсивные функции – основа функциональных языков Машина Тьюринга – идеализированная модель ЭВМ Алгоритмы Поста – работа со словами Алгорифмы Маркова – обработка символьной информации

Области применения Оценка сложности алгоритмов Разработка эффективных алгоритмов Исключение перебора вариантов в комбинаторных алгоритмах

Материалы INTUIT Введение в теорию множеств; Основы дискретной математики; Графы и их применение; Графы и алгоритмы