Дискретная математика. Лекции. 2016

<< |

↑

Предисловие

ГЛАВА 1. Элементы алгебры высказываний и булевой алгебры

§1.1. Высказывания

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

Свойства операций над высказываниями

Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы

Правильные рассуждения

§1.2. Функции алгебры логики

Основные понятия и факты, связанные с булевым кубом

Фиктивные и существенные переменные

Процедура удаления (введения) фиктивных переменных

Функции одной переменной

Функции двух переменных

§1.3. Реализация булевых функций формулами

Основные свойства элементарных функций

§1.4. Специальные представления булевых функций

Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы

Полином Жегалкина

§1.5. Полнота, замкнутость. Теорема Поста о полноте

Важнейшие замкнутые классы

§1.6. Дизъюнктивные нормальные формы

Процедура упрощения д. н. ф. (алгоритм Блейка)

Алгоритм получения тупиковой д. н. ф.

Геометрическая интерпретация

Сокращенная д. н. ф.

Аналитические методы построения сокращенной д. н. ф.

Метод Нельсона

Метод Квайна

§1.7. Схемы из функциональных элементов

§1.8. Функции -значной логики

Глава 2. Графы

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

Графы специального вида

Метрические характеристики графа

§2.2. Способы задания графов

§2.3. Связность

Деревья

Кодировка дерева

Построение дерева по коду

Второй способ кодирования

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

Теорема о цикломатическом числе

§2.4. Раскраски графов. Планарность

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

§2.5. Потоки в сетях

Примеры решения задач

Глава 3. Автоматы

§3.1. Определение и примеры автоматов

§3.2. Диаграмма Мура и таблица автомата

§3.3. Продолжение функций и

§3.4. Приведённый автомат

§3.5. Периодичность выходной последовательности конечного автомата

§3.6. Теоремы Мура

§3.7. Ограниченно-детерминированные функции. Информационное дерево

Глава 4. Алгоритмы и машины Тьюринга

§4.1. О понятии алгоритма. Тезис Чёрча

§4.2. Машина Тьюринга

§4.3. Рекурсивные функции

§4.4. Алгоритмически неразрешимые задачи

Книги и учебники по дисциплине Дискретная математика:

- Аналитическая геометрия - Вариационное исчисление - Векторный и тензорный анализ - Высшая геометрия - Высшая математика - Вычислительная математика - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комплексное исчисление - Линейная алгебра - Линейное программирование - Математика для экономистов - Математическая логика - Математическая физика - Математический анализ - Пределы - Ряды - Статистика - Теория вероятностей - Теория графов - Теория игр - Теория принятия решений - Теория случайных процессов - Теория чисел - Функциональный анализ -

- Архитектура и строительство - Безопасность жизнедеятельности - Библиотечное дело - Бизнес - Биология - Военные дисциплины - География - Геология - Демография - Диссертации России - Естествознание - Журналистика и СМИ - Информатика, вычислительная техника и управление - Искусствоведение - История - Культурология - Литература - Маркетинг - Математика - Медицина - Менеджмент - Педагогика - Политология - Право России - Право України - Промышленность - Психология - Реклама - Религиоведение - Социология - Страхование - Технические науки - Учебный процесс - Физика - Философия - Финансы - Химия - Художественные науки - Экология - Экономика - Энергетика - Юриспруденция - Языкознание -