Лекции по дискретной математике

Учебное пособие для студентов математических факультетов педагогических университетов 224 с. Не распознано.
Предисловие.
Предлагаемое учебное пособие подготовлено на основе спецкурса "Введение в дискретную математику", читаемого одним из авторов в течении ряда лет для магистрантов математического факультета МПГУ им. В.И.Ленина. Появление такого спецкурса было вызвано тем, что в наше время - время бурного развития дискретной математики выпускник математического факультета педагогического института не владеет ее основными понятиями. Существующие курсы по информатике и вычислительной технике не меняют сути дела, поскольку посвящены более технической стороне вопроса, чем основопологающим понятиям. Конечно, при отборе материала авторы столкнулись с большими трудностями. Существующие университетские курсы по дискретной математике, по мнению авторов, не пригодны для будущих учителей. "Нельзя объять необъятное!" - вот основной принцип, которым пользовались авторы при отборе материала.
Пособие состоит из четырех глав. Первая глава посвящена булевым функциям и функциям k-значной логики. Как известно они являются основой моделирования цифровых управляющих устройств и раздел дискретной математики, посвященный их описанию, давно стал классическим. При написании этой главы авторы в основном следовали учебнику С.В.Яблонского "Введение в дискретную математику". Вторая глава - Элементы комбинаторики. Здесь авторы из обширного круга вопросов остановились на теории производящих функций и рекуррентных соотношений. Такой выбор определился тем, что выпускник математического факультета педагогического института владеет основными понятиями теории степенных рядов и элементарной комбинаторики, поэтому указанные темы являются логическим продолжением ранее изучавшегося материала. С другой стороны, являясь наиболее разработанными, они находят обширные приложения. Третья глава посвящена теории графов. Аргументировать такой выбор нет особой нужды и все же хотелось бы сказать несколько слов. Кроме того, что теория графов является удобным языком формулирования задач самого разнообразного характера, от электротехники до социологии и различных математических головоломок, теория графов является также удобным материалом для развития формального мышления.
Четвертая глава посвящена алгоритмам на графах. Здесь авторы преследовали двоякую цель. Во-первых, познакомить с основными идеями заложенными в хорошо известных комбинаторных алгоритмах. Здесь теория графов является очень удобным языком для описания таких алгоритмов. Во-вторых, дать представление о сложности алгоритма. Возникновение теории сложности можно считать основным результатом развития дискретной математики и информатики после создания дескриптивной теории алгоритмов и вычислительных машин. Однако, к сожалению, в настоящее время вопросы теории сложности оказались вне обязательных программ педвузов. (Отчасти это объясняется тем, что ее понятия еще не сложились в единую и стройную систему.) Вместе с тем эти вопросы чрезвычайно важны для усвоения понятия эффективных алгоритмов и методов их построения. Существующее мнение о том, что улучшение характеристик вычислительных машин (быстродействие, объем памяти) является панацеей от всех существующих трудностей при решении практических задач является глубоко ошибочным. Повышение эффективности алгоритма зачастую дает значительно более лучший результат. С другой стороны, необходимо понимать, что существует обширный класс задач (это, в первую очередь, так называемые NP-полные задачи) для которых создание эффективных алгоритмов - весьма проблематично.
В книге - 4 главы (темы).Содержание:
Конечные функции.
Булевы функции. Основные способы задания булевых функций.
Формулы. Реализация булевых функций формулами.
Принцип двойственности.
Разложение булевых функций по переменным.
Полином Жегалкина.
Полнота и замкнутость.
Функции k-значной логики.
Итеративные алгебры Поста.
Элементы комбинаторики.
Производящие функции и их применения.
Производящие функции. Теория формальных степенных рядов .
Основной принцип теории производящих функций.
Простейшие производящие функции.
Производящие функции числа основных комбинаторных объектов Рекуррентные соотношения.
Основные понятия.
Линейные рекуррентные соотношения с постоянными коэффициентами.
Линейные рекуррентные соотношения с переменными коэффициентами.
Числа Каталана.
Числа Стирлинга второго рода.
Конечные графы.
Основные понятия Связные графы Обходы графа Деревья.
Планарные графы Раскраски.
Алгоритмы на графах.
Понятие о сложности алгоритма.
Задачи о покрытии. Жадный алгоритм.
Задача о минимальном остове и ее обобщение. Теорема Радо - Эдмондса Задача о кратчайшем пути. Метод динамического программирования Задача о максимальном потоке.
Некоторые приложения задачи о максимальном потоке.
Нахождение максимального паросочетания в двудольном графе.
Системы различных представителей.
Организация движения в динамической сети.
Оптимальный подбор интенсивностей выполнения работ.
Труднорешаемые задачи.
Список литературы.