Уч. пос. — М.: Новое знание,2005г. — 288 с.
Теория множеств, Теория графов, элементы алгебры и мат. логики, минимизация булевых функций, эл. комбинаторики, эл. теории алгоритмов, о разрешимости конструктивных комбинаторных задач.
Описание некоторых алгоритмов и отлаженные Паскаль-программы для наиболее важных из них.
Содержание:
I. Введение в теорию множеств.
Понятие множества и способы его задания. Подмножества.
Операции над множествами. Свойства операций над множествами.
Упорядоченные множества. Прямое произведение множеств.
Бинарные отношения. Свойства бинарных отношений.
Отношение эквивалентности. Отношение порядка.
Разбиение частично упорядоченного множества на цепи.
Наименьший и наибольший элементы, границы упорядоченного множества.
Функциональные бинарные отношения.
Мощность множеств. Матроиды.
II. Введение в теорию графов.
Основные понятия. Способы задания графа.
Части графов. Операции на графах.
Связность графов и деревья. Числа графов.
Эйлеровы и гамильтоновы графы.
Изоморфные графы. Покрывающие деревья.
Кратчайший путь в графе.
Паросочетания в графе. Потоки в сетях.
III. Элементы алгебры.
Понятие алгебраической системы.
Группоиды и полугруппы. Понятие группы.
Кольца, тела и поля.
Гомоморфизм и изоморфизм.
IV. Элементы математической логики.
Общие сведения о математической логике.
Понятие простого и сложного высказывания.
Булевы функции. Свойства булевых функций. Классы булевых функций.
Функционально полные системы.
Дизъюнктивная нормальная форма. Конъюнктивная нормальная форма.
Полиномиальные представления.
Способы задания булевых функций.
Задача выполнимость ИЗ.
Предикаты.
Построение математических моделей. Реализация математических моделей.
V. Минимизация булевых функций.
Задача минимизации булевых функций.
Постановка задачи минимизации в классе ДНФ.
Сокращенная ДНФ. Тупиковые ДНФ.
Построение сокращенной ДНФ. Поиск минимальных ДНФ.
Vi. Элементы комбинаторики.
Предмет комбинаторики. Понятие выборки.
Основные правила комбинаторики. Пересчет упорядоченных выборок.
Число упорядоченных выборок с повторениями.
Число упорядоченных выборок без повторений.
Порождение перестановок.
Пересчет числа неупорядоченных выборок.
Порождение подмножеств. Число разбиений множества на подмножества.
Генерирование разбиений множеств и чисел.
Метод включений и исключений. Метод рекуррентных соотношений.
Решение линейных рекуррентных соотношений.
Понятие производящей функции. Свойства биномиальных коэффициентов.
VII. Элементы теории алгоритмов.
Предмет теории алгоритмов. Интуитивное понятие алгоритма.
Примитивно-рекурсивные функции.
Машина Тьюринга. Композиция машин Тьюринга.
Алгоритмически неразрешимые проблемы.
Понятие сложности алгоритма. Асимптотические оценки функций сложности.
Трудноразрешимые задачи.
Класс NP. NP-полные задачи.
Пример полиномиального сведения.
Приближенные алгоритмы
VIII. O разрешимости конструктивных комбинаторных задач.
Введение. Последовательностный принцип построения решения.
Теоретико-множественная модель комбинаторных задач.
Один пример комбинаторной задачи.
Задачи без предвидения.
Разрешающая последовательность комбинаторных задач.
К методике решения задач класса NP.
О недетерминированной машине Тьюринга.
Теоретико-множественные свойства экстремальных комбинаторных задач.
Теоретико-множественная модель экстремальных комбинаторных задач.
Способы задания ЭКЗ. Вспомогательные множества решений ЭКЗ.
Конституенты.
Нормальная форма ЭКЗ. Двойственные ЭКЗ.
Циклические и ациклические ЭКЗ. Каноническая ЭКЗ.
Книга написана на основе лекций, которые автор читал на протяжении 20 лет работы в Винницком техническом университете.
Теория множеств, Теория графов, элементы алгебры и мат. логики, минимизация булевых функций, эл. комбинаторики, эл. теории алгоритмов, о разрешимости конструктивных комбинаторных задач.
Описание некоторых алгоритмов и отлаженные Паскаль-программы для наиболее важных из них.
Содержание:
I. Введение в теорию множеств.
Понятие множества и способы его задания. Подмножества.
Операции над множествами. Свойства операций над множествами.
Упорядоченные множества. Прямое произведение множеств.
Бинарные отношения. Свойства бинарных отношений.
Отношение эквивалентности. Отношение порядка.
Разбиение частично упорядоченного множества на цепи.
Наименьший и наибольший элементы, границы упорядоченного множества.
Функциональные бинарные отношения.
Мощность множеств. Матроиды.
II. Введение в теорию графов.
Основные понятия. Способы задания графа.
Части графов. Операции на графах.
Связность графов и деревья. Числа графов.
Эйлеровы и гамильтоновы графы.
Изоморфные графы. Покрывающие деревья.
Кратчайший путь в графе.
Паросочетания в графе. Потоки в сетях.
III. Элементы алгебры.
Понятие алгебраической системы.
Группоиды и полугруппы. Понятие группы.
Кольца, тела и поля.
Гомоморфизм и изоморфизм.
IV. Элементы математической логики.
Общие сведения о математической логике.
Понятие простого и сложного высказывания.
Булевы функции. Свойства булевых функций. Классы булевых функций.
Функционально полные системы.
Дизъюнктивная нормальная форма. Конъюнктивная нормальная форма.
Полиномиальные представления.
Способы задания булевых функций.
Задача выполнимость ИЗ.
Предикаты.
Построение математических моделей. Реализация математических моделей.
V. Минимизация булевых функций.
Задача минимизации булевых функций.
Постановка задачи минимизации в классе ДНФ.
Сокращенная ДНФ. Тупиковые ДНФ.
Построение сокращенной ДНФ. Поиск минимальных ДНФ.
Vi. Элементы комбинаторики.
Предмет комбинаторики. Понятие выборки.
Основные правила комбинаторики. Пересчет упорядоченных выборок.
Число упорядоченных выборок с повторениями.
Число упорядоченных выборок без повторений.
Порождение перестановок.
Пересчет числа неупорядоченных выборок.
Порождение подмножеств. Число разбиений множества на подмножества.
Генерирование разбиений множеств и чисел.
Метод включений и исключений. Метод рекуррентных соотношений.
Решение линейных рекуррентных соотношений.
Понятие производящей функции. Свойства биномиальных коэффициентов.
VII. Элементы теории алгоритмов.
Предмет теории алгоритмов. Интуитивное понятие алгоритма.
Примитивно-рекурсивные функции.
Машина Тьюринга. Композиция машин Тьюринга.
Алгоритмически неразрешимые проблемы.
Понятие сложности алгоритма. Асимптотические оценки функций сложности.
Трудноразрешимые задачи.
Класс NP. NP-полные задачи.
Пример полиномиального сведения.
Приближенные алгоритмы
VIII. O разрешимости конструктивных комбинаторных задач.
Введение. Последовательностный принцип построения решения.
Теоретико-множественная модель комбинаторных задач.
Один пример комбинаторной задачи.
Задачи без предвидения.
Разрешающая последовательность комбинаторных задач.
К методике решения задач класса NP.
О недетерминированной машине Тьюринга.
Теоретико-множественные свойства экстремальных комбинаторных задач.
Теоретико-множественная модель экстремальных комбинаторных задач.
Способы задания ЭКЗ. Вспомогательные множества решений ЭКЗ.
Конституенты.
Нормальная форма ЭКЗ. Двойственные ЭКЗ.
Циклические и ациклические ЭКЗ. Каноническая ЭКЗ.
Книга написана на основе лекций, которые автор читал на протяжении 20 лет работы в Винницком техническом университете.