Компьютерная математика: Часть 1. Теория множеств и комбинаторика. Волченская Т.В - 45 стр.

                      3. Комбинаторика
      Комбинаторика – один из разделов дискретной математики, который
приобрел важное значение в связи с использованием его в ВТ, кибернетике,
робототехнике. Большинство задач комбинаторики можно сформулировать
как задачи теории конечных множеств, поэтому эти две темы – элементы
теории множеств и комбинаторика – рассматриваются взаимосвязано.
      Человеку часто приходится иметь дело с задачами, в которых нужно
подсчитать число всех возможных способов расположения некоторых
предметов или число всех возможных способов осуществления некоторого
действия. Например, сколькими способами могли быть распределены золо-
тая, серебряная и бронзовая медали на Олимпийских играх в Сеуле по бас-
кетболу; или сколькими различными способами можно разместить здания
на площади? Задачи такого типа называются комбинаторными.
      С комбинаторными вычислениями приходится иметь дело представи-
телям многих специальностей: ученому-химику при рассмотрении различ-
ных возможных типов связи атомов в молекулах, биологу – при изучении
возможных последовательностей чередования аминокислот в белковых со-
единениях, диспетчеру – при составлении графика движения и т. д.
      Комбинаторика возникла в XVI веке. В то время в жизни привилеги-
рованных слоев общества большое место занимали азартные игры (карты,
кости). Были широко распространены лотереи. Возникали вопросы: сколь-
кими способами можно выбросить данное число очков, бросая две или три
кости, или сколькими способами можно получить двух королей? Эти и дру-
гие проблемы оказались движущей силой в развитии комбинаторики.
      Теоретические исследования вопросов комбинаторики предприняли
Паскаль и Ферма, Бернулли, Лейбниц и Эйлер и др.
      Для инженерных специальностей университета комбинаторные зада-
чи приходится решать в следующих случаях:
       1) при конструировании:
       o для оптимального размещения элементов системы;
       o для размещения микросхем на плате или элементов на кристалле;
       o при трассировке (выборе маршрута);
       2) при синтезе схем и проектирования:
       o при решении вопроса, какой набор стандартных микросхем вы-
брать, чтобы реализовать разработанную схему устройства;
       o при разработке схемы на подсхемы для реализации различными
блоками и т. д.;


                                 45