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