Б. Н. ИВАНОВ

Практическая компьютерная реализация большого количества рассматриваемых задач потребовала включения в книгу специальных разделов дискретной математики, таких как представление абстрактных объектов, сортировка и поиск, порождение комбинаторных объектов. Однако увеличение объема материала пособия только лишь усилило многие вопросы, позволило уточнить их суть, а также придать общее звучание разделам курса, которые на первый взгляд никоим образом не связаны. Книгу можно рассматривать в качестве хорошего справочника методов и алгоритмов дискретной математики, широко используемых в разработках прикладного программного обеспечения.

Уровень математической подготовки, требующийся для понимания материала книги, может меняться от главы к главе. Минимум необходимых познаний в программировании соответствует уровню первокурсника, уже научившегося писать довольно пространные программы. Необходимый уровень математического образования соответствует типичной подготовке студента, прослушавшего ряд основных математических курсов, таких как математический анализ, аналитическая геометрия, линейная алгебра.

Учебное пособие ориентировано на семестровый лекционный

курс, читаемый автором на механико-математическом факультете Дальневосточного государственного технического университета. Без сомнения, книга может составить хорошую основу курсов, примыкающих к дискретной математике, таких как информатика, алгоритмизация процессов, анализ вьгаислительньгх алгоритмов.

Учебное пособие предназначено прежде всего для студентов специальности «Прикладная математика», а также студентов других специальностей, изучающих дискретную математику и программирование. Книга будет полезна преподавателям, аспирантам и научным работникам, применяющим методы дискретной

математики в прикладных задачах.

Интерпретация. Если элемент а еА можно выбрать т способами, а элемент ЬеВ-п способами, то выбор элементах еА kjB можно осуществить т + п способами. Пусть ХЬХ2,...,Хк— попарно непересекающиеся множества, г Xj = 0, где / ?= j Тогда, оче-

видно, выполняется равенство

k

=11*

1.2. Правило прямого произведения

Пусть А и В — конечные множества, А = т и В = п, тогда [Лх Б = т п.

Интерпретация. Если элемент а еА можно выбрать т способами и если после каждого такого выбора элемент b еВ можно выбрать п способами, то выбор пары (а,Ь) еАх Явуказанном порядке можно осуществить А х Ц = т-п способами. В этом случае говорят, что выбор элементов множества А не зависит от способа выбора элементов множества В. Пусть теперь Хх,Х2,...,Хк— произвольные множества,Тогда

\Х} xX2x...xXk\=\{(xl,x2,...,xk)\xi е X) J =U}j=n, -nr-nk.

Задача. Найти число маршрутов из пункта М в пункт N через пункт К. Из Мв введут 5 дорог, из KB N-3 дороги.

Решение. Введем два множества: S= {s,, s2, s3, s4, s5}-дороги из Me К, T= [tlt t2, г3}- дороги из KB N. Теперь дорогу из Me #мож-но представить парой (st р.где /= 1, 2, 3, 4, 5;у= 1, 2, 3. Значит, Sx Т — это множество всех дорог из Мв iV, количество которых равно iSx7=5-3=15.

1.3. Размещения с повторениями

Задача формулируется следующим образом. Имеются предметы п различных видов Шу а2,..., ап. Из них составляют всевозможные расстановки длины к. Например, a2flia3fl3fl4fl3a2ai— Рас~ становка длины 8. Такие расстановки называются размещениями с повторениями из п по k (элементы одного вида могут повторяться). Найдем общее число расстановок, среди которых две расстановки считаются различными, если они отличаются друг

от друга или видом входящих в них предметов, или порядком этих предметов. При составлении указанных расстановок длины k на каждое место можно поставить предмет любого вида. Рассмотрим множества Ху.Хакж, что Х{ = Х2 = ... - Хк = {аъ а2,..., ап) . Тогда все размещения с повторениями составят множество ХххХ2 х...хХ к.Т1о правилу прямого произведения получаем, что общее число размещений с повторениями из л по к равно \Х1хХ2х...хХк\=пк.

Задача. Найти количество всех гштизначных чисел.

Решение. Введем пять множеств: А2=Аг=А\=А5= {0, 1,..., 9}, Ах = {1, 2,..., 9}. Тогда все пятизначные числа составят прямое произведение указанных множеств Д \А2 хЛ3 х Д, \А5. Согласно правилу прямого произведения, количество элементов в множестве А{ х А2 хА3 хД} х А5 равно 9 10 10 10 10 =90000.

1.4. Размещения без повторений

Имеются различных предметов./,. <ь.....а„. Сколько из них

можно составить расстановок длины к? Две расстановки считаются различными, если они отличаются видом входящих в них элементов или порядком их в расстановке. Такие расстановки называются размещениями без повторений, а их число обозначают При составлении данных расстановок на первое

место можно поставить любой из имеющихся п предметов. На второе место теперь можно поставить только любой из п — 1 оставшихся. И, наконец, на к-е место — любой из п — к + 1 оставшихся предметов. По правилу прямого произведения получаем, что общее число размещений без повторений из л по А; равно Акп =п(п-\)...{п-к + \)=п\/{п-к)\. Напомним, что п\ =л(я-1)...1 и0!= 1.

Задана. В хоккейном турнире участвуют 17 команд. Разыгрываются золотые, серебряные и бронзовые медали. Сколькими способами могут быть распределены медали?

Решение. 17 команд претендуют на 3 места. Тогда тройку призеров можно выбрать способами А\п =17 16-15 = 4080.