Читать онлайн «Сборник задач по дискретному анализу. Комбинаторика. Элементы алгебры логики. Теория графов»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Московский физико-технический институт (государственный университет) СБОРНИК ЗАДАЧ ПО ДИСКРЕТНОМУ АНАЛИЗУ Комбинаторика. Элементы алгебры логики. Теория графов Рекомендовано Учебно-методическим советом Московского физико-технического института (государственного университета) в качестве учебного пособия для студентов высших учебных заведений по направлению "Прикладпые математика и физика' МОСКВА 2000 удктад С23 Авторы: Ю. И. Журавлев, Ю. А. Флеров, О. С. Федько, Т. М. Дадашев Рецензенты: Кафедра математической кибернетики Московского государственного университета им. М. В. Ломоносова Доктор физико-математических наук, профессор В. К. Леонтьев С23 СБОРНИК ЗАДАЧ ПО ДИСКРЕТНОМУ АНАЛИЗУ. Комбинаторика. Элементы алгебры логики. Теория графов: Учеб. пособие. — М. : МФТИ, 2000. — 100 с. ISBN 5-7417-0154-Х Включены задачи и упражнения, связанные с курсом лекций по одноименной дисциплине, читаемой студентам факультета прикладной математики и экономики в первом семестре. Сборник может быть использован в учебном процессе для подготовки семинарских занятий, заданий, экзаменационного материала и как источник проблемных задач. УДК 519. 95 © Московский физико-технический институт (государственный университет), 2000 © Журавлев Ю. И. , Флеров Ю. А. , ISBN 5-7417-0154-х Федько О. С. , Дадашев Т. М. , 2000 СОДЕРЖАНИЕ ПРЕДИСЛОВИЕ 4 Глава I. КОМБИНАТОРНЫЕ МЕТОДЫ ДИСКРЕТНОЙ МАТЕМАТИКИ 5 § 1. Комбинаторные задачи о числе функций, слов в алфавите и размещений объектов по ячейкам при различных ограничениях 5 § 2. Биномиальные и полиномиальные коэффициенты, производящие функции для них 11 § 3. Разбиения и размещения. Рекуррентные соотношения. 33 § 4. Логические методы комбинаторного анализа. Принцип включений-исключений. Системы представителей множеств 54 Глава 2. ЭЛЕМЕНТЫ АЛГЕБРЫ ЛОГИКИ 61 § 1. Функции алгебры логики и способы их задания 61 § 2. Функционально замкнутые классы 67 Глава 3. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 76 § 1. Основные понятия теории графов 76 § 2. Пути и циклы в графе. Связность 82 § 3. Эйлеровы и гамильтоновы пути и циклы 86 § 4. Деревья 91 § 5. Ориентированные графы '. . '. '. '. '. . ". '. ". 96 3 ПРЕДИСЛОВИЕ Сборник предназначен для студентов первого курса факультета прикладной математики и экономики МФТИ. Включены задачи и упражнения но комбинаторике, элементам алгебры логики, теории графов. Представление о содержании сборника дает оглавление. Среди задач и упражнений выделены две группы. Первая ориентирована на первоначальное знакомство с предметом м со/держит, и частности, теоремы и утверждения, рассматриваемые на лекциях и семинарах. Их решение необходимо для начального освоения дисциплины. Решение задач, отмеченных знаком «*», потребует от студентов определенных (в некоторых случаях значительных) усилий. Эти задачи - повышенной трудности, предназначены для достаточно глубокого изучения комбинаторики, чес-рии графов и их связей с другими разделами курсов математики, информатики и их приложений.