Читать онлайн «Методы комбинаторных вычислений: учеб. пособие»

Московский государственный технический университет имени Н. Э. Баумана Т. М. Волосатова, С. В. Родионов МЕТОДЫ КОМБИНАТОРНЫХ ВЫЧИСЛЕНИЙ Рекомендовано Научно-методическим советом МГТУ им. Н. Э. Баумана в качестве учебного пособия Москва Издательство МГТУ им. Н. Э. Баумана 2011 УДК 519. 1 ББК 22. 17 В44 Р е ц е н з е н т ы : Н. В. Чичварин, Н. В. Филиппов Волосатова Т. М. В44 Методы комбинаторных вычислений : учеб. пособие / Т. М. Волосатова, С. В. Родионов. — М. : Изд-во МГТУ им. Н. Э. Баумана, 2011. — 103, [1] с. : ил. Рассмотрены комбинаторные вычисления, их основные операци- онные объекты: сочетания, перестановки, размещения и разбиения элементов конечных множеств и натуральных чисел. Рекомендовано для изучения в рамках курса «Лингвистическое и программное обеспечение САПР» для студентов 2–5-го курсов. УДК 519. 1 ББК 22. 17 Учебное издание Волосатова Тамара Михайловна Родионов Сергей Владимирович МЕТОДЫ КОМБИНАТОРНЫХ ВЫЧИСЛЕНИЙ Редактор К. А. Осипова Корректор М. А. Василевская Компьютерная верстка С. А. Серебряковой Подписано в печать 26. 08. 2011. Формат 60×84/16. Усл. печ. л. 6,05. Тираж 100 экз. Изд. № 134. Заказ . Издательство МГТУ им. Н. Э. Баумана. Типография МГТУ им. Н. Э. Баумана. 105005, Москва, 2-я Бауманская ул. , 5. © МГТУ им. Н. Э. Баумана, 2011 2  ВВЕДЕНИЕ Разнообразные комбинаторные задачи, связанные с вычисли- тельной обработкой дискретных конечных структур, часто встре- чаются в технической практике и других предметных областях. Кроме того, комбинаторные категории и методы традиционно ак- туальны в ряде математических дисциплин. В частности, они при- меняются в теории вероятностей, теории графов, теории кодиро- вания, теории чисел и теории игр. Необходимо также упомянуть их наиболее современные приложения, например, в статистиче- ской физике, математической биологии и для криптографического анализа информации. Основными операционными объектами таких комбинаторных вычислений являются сочетания, перестановки, размещения и раз- биения элементов конечных множеств и натуральных чисел. Соче- тания образуются неупорядоченной выборкой элементов конечно- го множества. Перестановки получаются расположением всех элементов конечного множества в различной последовательности. Размещения можно рассматривать как упорядоченные выборки элементов конечного множества, где они переставлены в различ- ном порядке. Под разбиением множества понимается разделение его элементов на непересекающиеся подмножества, а разбиение целых чисел означает представление их в форме арифметической суммы слагаемых. Во всех случаях физическая природа, техниче- ские свойства или информационный смысл элементов, которые образуют такие комбинаторные объекты, не имеет существенного значения, важна только их комбинаторная конфигурация, отра- жающая условия комбинаторной задачи.