Дискретная математика для информатиков и экономистов, Гусева А.И., Тихомирова А.Н., 2010

Дискретная математика для информатиков и экономистов, Гусева А.И., Тихомирова А.Н., 2010.
  Пособие состоит из семи глав, в которых последовательно излагаются основы теории множеств, отношений, математической логики и исчислений, комбинаторики, теории графов и нечетких моделей, объединенные в рамках дисциплины «Дискретная математика». В конце каждой главы приведены задачи и упражнения. Книга предназначена для студентов институтов и университетов, обучающихся по специальностям «Прикладная математика и информатика», «Прикладная информатика», «Математические методы в экономике», «Экономика и управление на предприятии», а также будет полезна аспирантам и научным сотрудникам, работающим в области информатизации экономики и управления.

Понятие компьютинга и дискретной математики.
Компьютинг (computing) - это широкая область знаний, которая не может быть сведена к рамкам какой-либо из составляющих ее дисциплин. Основы компьютинга включают в себя основы информатики и математики, необходимые для проектирования и разработки программных продуктов. Данная область знаний включает в себя также знания о трансформации проекта в реализацию, используемых при этом средствах и о формальных методах создания программного обеспечения. Основываясь на математике и компьютинге. программная инженерия занимается разработкой систематических моделей и надежных методов производства высококачественного программного обеспечения, и данный подход распространяется на все уровни - от теории и принципов до реальной практики создания программного обеспечения, которая лучше всего заметна сторонним наблюдателям.
Программная инженерия посвящена систематическим, управляемым и эффективным методам создания высококачественного программного обеспечения. Поэтому особое внимание уделяется анализу и оценке, спецификации, проектированию и эволюции программного обеспечения. Кроме того, в рамки данной дисциплины попадают вопросы, связанные с управлением и качеством, новизной и творчеством, стандартами, индивидуальными навыками и командной работой, а также профессиональной деятельностью, которые играют жизненно важную роль в программной инженерии. Программная инженерия является такой формой инженерии, которая применяет принципы информатики (computer science) и математики д.ля получения рентабельных решений в области программного обеспечения.
Оглавление
Предисловие
Глава 1. Теория множеств и бинарные отношения
1.1. Понятие компьютинга и дискретной математики
1.2. Теория множеств
1.2.1. Основные понятия теории множеств
1.2.2. Способы задания множеств
1.2.3. Операции над множествами
1.2.4. Свойства операций над множествами
1.2.5. Аксиоматика теории множеств
1.3. Бинарные отношения и их свойства
1.3.1. Декартово произведение и бинарное отношение
1.3.2. Функции и операции
1.3.3. Способы задания бинарных отношений
1.3.4. Свойства бинарных отношений
1.3.5. Типы бинарных отношений
1.3.6. Экстремальные характеристики отношения упорядочивания
1.3.7. Отношение толерантности
1.3.8. Операции над отношениями
Контрольные вопросы и задания
Глава 2. Алгебры и алгебраические системы
2.1. Фундаментальные алгебры
2.2. Алгебра высказываний
2.3. Формализация логических высказываний
2.4. Таблицы истинности сложных высказываний
2.5. Равносильности алгебры высказываний
2.6. Булевы функции
2.7. Формы представления логических функций
2.7.1. Дизъюнктивные нормальные формы
2.7.2. Конъюнктивные нормальные формы
2.8. Минимизация булевых функций. Метод Квайна - МакКласки
2.8.1. Законы алгебры Буля
2.8.2. Упрощение логических функций
2.8.3. Метод Квайна - МакКласки
2.9. Функционально полные системы логических функций
2.9.1. Теорема о полноте системы булевых функций
2.9.2. Критерий Поста-Яблонского
2.10. Построение логических схем
Контрольные вопросы и задания
Глава 3. Формальные теории
3.1. Основные свойства формальных теорий
3.1.1. Выводимость
3.1.2. Интерпретация
3.1.3. Разрешимость
3.1.4. Общезначимость
3.1.5. Непротиворечивость
3.1.6. Полнота
3.1.7. Независимость
3.2. Исчисление высказываний
3.2.1. Интерпретация
3.2.2. Правило подстановки
3.2.3. Связь между исчислением высказываний и алгеброй высказываний
3.2.4. Основные результаты исследования исчисления высказываний
3.2.5. Другие формализации исчисления высказываний
3.2.4.    Методы проверки тождественной истинности формул
3.3. Исчисление предикатов
3.3.1. Основные понятия исчисления предикатов
3.3.2. Кванторные операции над предикатами
3.3.3. Формальное определение исчисления предикатов
Контрольные вопросы и задания
Глава 4. Теория математических доказательств
4.1. Прямые доказательства
4.1.1. Правило подстановки
4.1.2. Правило вывода
4.1.3. Дедукция
4.1.4. Математическая индукция
4.2. Косвенные доказательства
4.2.1. Доказательство «от противного»
4.2.2. Доказательство через контрпример
Контрольные вопросы и задания
Глава 5. Основы комбинаторики
5.1. Правила суммы и произведения
5.2. Перестановки
5.3. Размещения и сочетания
5.4. Разбиения
5.5. Формула включений и исключений
5.6. Рекуррентные соотношения
5.7. Производящие функции
5.8. Числа Стирлинга второго и первого рода
Контрольные вопросы и задания
Глава 6. Основы теории графов
6.1.Основные понятия
6.1.1. Классификация графов
6.1.2. Способы задания графов
6.2. Операции над графами
6.2.1. Удаление вершин и ребер
6.2.2. Дополнение
6.2.3. Объединение графов
6.2.4. Сложение графов
6.2.5. Произведение графов
6.3. Связность в графах
6.3.1. Компоненты связности
6.3.2. Вершинная и реберная связность
6.3.3. Сильная связность в графах
6.4. Цикломатика графов
6.4.1. Ациклические графы
6.4.2. Базисные циклы и цикломатическое число
6.4.3. Базисные разрезы и ранг
6.4.4. Эйлеровы графы
6.4.5. Гамильтоновы графы
6.5. Диаметр графа
6.5.1. Основные определения
6.5.2. Алгоритм нахождения диаметра
6.5.3. Поиск диаметра при операциях над графами
6.6. Устойчивость графов
6.6.1. Внутренняя устойчивость
6.6.2. Внешняя устойчивость
6.7. Хроматика графов
6.7.1. Хроматическое число
6.7.2. Поиск хроматического числа при операциях над графами
6.7.3. Двудольное представление графов
6.7.4. Хроматический класс
6.8. Преобразование графов
6.8.1. Реберные графы
6.8.2. Изоморфизм графов
6.8.3. Гомеоморфизм графов
6.8.4. Автоморфизм графов
6.9. Планарность
6.9.1. Основные определения
6.9.2. Критерии непланарности
6.10. Построение графов
6.10.1. Преобразование прилагательных в числительные
6.10.2. Оценка количества ребер на основе степеней вершин
6.10.3. Оценка количества ребер сверху и снизу
6.10.4.    Получение недостающих данных на основе формул
Контрольные вопросы и задания
Глава 7. Нечеткие модели дискретной математики
7.1. Введение в теорию нечетких моделей
7.1.1. Принятие решений в условиях неопределенности
7.1.2. Основы нечетких моделей
7.2. Нечеткие множества. Базовые определения
7.2.1. Базовые и нечеткие значения переменных
7.2.2. Основные определения
7.2.3. Типовые функции принадлежности
7.3. Операции над нечеткими множествами
7.3.1. Операция «дополнение»
7.3.2. Операция «пересечение»
7.3.3. Операция «объединение»
7.3.4. Операция «включение»
7.3.5. Операции «равенство» и «разность»
7.3.6. Операция «дизъюнктивная сумма»
7.3.7. Операции «концентрирование» и «растяжение»
7.3.8. Операция «отрицание»
7.3.9. Операция «контрастная интенсивность»
7.3.10. Операция «увеличение нечеткости»
7.4. Обобщенные нечеткие операторы
7.4.1. Треугольные нормы
7.4.2. Треугольные конормы
7.4.3. Декомпозиция нечетких множеств
7.5. Индекс нечеткости
7.5.1. Оценка нечеткости через энтропию
7.5.2. Метрический подход к оценке нечеткости
7.5.3. Аксиоматический подход
7.6. Нечеткие бинарные отношения
7.6.1. Нечеткие бинарные отношения
7.6.2. Свойства нечетких бинарных отношений
7.6.3. Операции над нечеткими отношениями
7.7. Нечеткие числа
7.8. Приближенные рассуждения
7.8.1. Нечеткая лингвистическая логика
7.8.2. Композиционное правило вывода
7.8.3. Правило modus ponens
Контрольные вопросы и задания
Список литературы.