Наверх

Л.Е.Захарова, 2002 (Rus)
Алгоритмы дискретной математики

ПРЕДИСЛОВИЕ
Учебное пособие Московского государственного института электроники и математики (технический университет). Предназначено для изучающих дисциплину "Дискретная математика" и смежные с ней дисциплины. Полезно студентам при подготовке к семинарам и контрольным работам, школьникам, интересующимся олимпиадными задачами. Каждая глава содержит алгоритмы дискретной математики, реализованные в виде программ на языке Pascal. Программы проверены на контрольных примерах

Оглавление

1. КОМБИНАТОРИКА

2. ТЕОРИЯ ГРАФОВ
  
2.1 Нахождение кратчайших путей между вершинами в графе
   2.2 Компенсация матриц
   2.3 Планарность
   2.4 Тестирование и восстановление автоматов


3. СЛУЧАЙНЫЕ ПРОЦЕССЫ

4. МЕТОД ВЕТВЕЙ И ГРАНИЦ


Библиография






Наверх

Я.М.Ерусалимский, 2000 (Rus)
Дискретная математика: теория, задачи, приложения

ПРЕДИСЛОВИЕ
Учебное пособие по дискретной математике. Содержит разделы: алгебра предикатов и множеств, отображения, элементы комбинаторики, отношения, булевы функции, элементы теории графов. Отдельный раздел составляют задачи и упражнения. Предназначено для студентов и преподавателей ВУЗов, инженеров-системотехников, программистов. Для школьников, изучающих математику и информатику углубленно

Оглавление

1. АЛГЕБРА ВЫСКАЗЫВАНИЙ
  
1.1 Высказывания. Операции над высказываниями
   1.2 Формулы алгебры высказываний
   1.3 Двойственность в алгебре высказываний. Принцип двойственности. Закон двойственности.
   1.4 Нормальные формы. СДНФ. СКНФ. Понятие о показателе степени. Показательные уравнения
   1.5 Основные проблемы алгебры высказываний. Критерий тождественной истинности и тождественной ложности.
   1.6 Релейно-контактные схемы и схемы из функциональных элементов

2.
АЛГЕБРЫ ПРЕДИКАТОВ И МНОЖЕСТВ. ОТОБРАЖЕНИЯ
   2.1 Предикаты. Логические операции над предикатами. Кванторы.
   2.2 Кванторы, их свойства и применение
   2.3 Алгебра множеств
   2.4 Отображения. Образ и прообраз множеств при отображении. Свойства образов и прообразов.
   2.5 Типы отображений. Обратимость и односторонняя обратимость
   2.6 Семейства множеств и операции над семействами

3.
ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
   3.1 Что такое комбинаторика? Число элементов во множестве. Правило суммы.
   3.2 Декартово произведение множеств; множество степень
   3.3 Множества инъективных и биективных отображений. Размещения, перестановки
   3.4 Бином Ньютона. Сочетания. Сочетания с повторениями
   3.5 Число сюръективных отображений

4.
ОТНОШЕНИЯ
   4.1 n-местыне отношения. Булевы алгебры отношений и матриц
   4.2 Бинарные отношения на множестве. Свойства бинарных отношений.
   4.3 Отношение порядка и доминирование
   4.4 Отношение эквивалентности

5.
БУЛЕВЫ ФУНКЦИИ
   5.1 Функции алгебры логики. Многочлены Жегалкина.
   5.2 Полнота и замкнутость. Классы Поста Р0 и Р1
   5.3 Классы Поста L и S
   5.4 Класс Поста M
   5.5 Критерий полноты (теорема Поста)
   5.6 Предполные классы и их свойства

6.
ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
   6.1 Что такое алгоритм? Вводные понятия
   6.2 Машина Тьюринга. Описание. Примеры машин
   6.3 Сочетания машин Тьюринга: композиция и объединение. Машины с полулентами, разветвление и итерация машин
   6.4 Тьюрингов подход к понятию "алгоритм". Алгоритмически разрешимые и неразрешимые проблемы
   6.5 Универсальная машина Тьюринга

7.
ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
   7.1 Введение, общее определение графа. Локальные характеристики
   7.2 Изоморфизм графов. Геометрические графы. Плоские и неплоские графы. Пути, цепи, контуры, циклы
   7.3 Части графа: подграф, частичный граф
   7.4 Эйлеровы графы, критерий эйлеровости
   7.5 Деревья и леса
   7.6 Помеченные графы. Перечисление помеченных деревьев. Матрицы графов
   7.7 Взвешенные графы. Задача о кратчайшем соединении. Кратчайшие пути

8.
ЗАДАЧИ И УПРАЖНЕНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
   8.1 Алгебра высказываний
   8.2 Двойственность в алгебре высказываний
   8.3 Нормальные формы: ДНФ, КНФ, СДНФ, СКНФ
   8.4 Релейно-контактные схемы и схемы из функциональных элементов
   8.5 Предикаты и кванторы, множества, отображения
   8.6 Элементы комбинаторики. Отношения
   8.7 Функции алгебры логики
   8.8 Машина Тьюринга
   8.9 Графы и их матрицы


Рекомендуемая литература