Студопедия


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram

Основные определения комбинаторного анализа




Бытует мнение, что комбинаторные задачи элементарны. Конечно, это не так. Число комбинаторных задач и их разнообразие быстро растет. К их решению прямо или косвенно приводят многие практические задачи. При этом оказывается, что несмотря на заманчивую простоту постановки, комбинаторные задачи в большинстве очень трудны; многие из них не поддаются решению до сих пор. К числу современных задач, решаемых комбинаторными методами, относятся:

1. Задачи на размещения – задачи о расположении, например, на плоскости предметов, обладающих свойствами дальнодействия.

2. Задачи о покрытиях и заполнениях – например, задачи о заполнении заданных пространственных фигур меньшими телами заданных форм и размеров.

3. Задачи о маршрутах – задачи оптимального плана, например, задачи отыскания кратчайшего пути и т.п.

4. Комбинаторные задачи теории графов – задачи сетевого планирования, например, задачи транспортных и электрических сетей, задачи об окрашивании графов, задачи о перечислении вершин и т.п.

5. Перечислительные задачи, в которых идет речь о числе предметов, составляемых из данного набора элементов при соблюдении определенных правил.

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

С операцией отбора подмножеств связано понятие выборки, с которым можно связать как осуществление операции отбора, так и ее результат - само выбранное подмножество.

Подмножество из r элементов, выбранное из множества Sп, состоящего из п элементов,называется (п, r) – выборкой, а r – объемом этой выборки. Если (п, r) – выборки рассматриваются с учетом порядка элементов в них, то он называются (п, r) – перестановками. Если же порядок элементов в выбранных подмножествах не важен, то соответствующие выборки называются (п, r) – сочетаниями.

В выборках могут допускаться и не допускаться повторения элементов. Упорядоченная (п, r) – выборка, в которой элементы могут повторяться, называется перестановкой с повторениями из п элементов по r или (п, r) – перестановкой с повторениями. Если элементы упорядоченной (п, r) – выборки попарно различны, то такая выборка называется (п, r) – перестановкой без повторений. Число (п, r) – перестановок обозначается символом Рп,r, или Р(п, r), а число перестановок с повторениями - , или . Р – первая буква слова permutation (англ. перестановка). До сих пор во многих учебниках (п, r) – перестановки называются размещениями и обозначаются символом , собственно же перестановками называются упорядоченные (п,п) – выборки. А – первая буква слова arrangement (англ. размещение, приведение в порядок). Неупорядоченная (п, r) – выборка, в которой элементы могут повторяться, называется сочетанием с повторениями из п элементов по r. Число сочетаний без повторений обозначается символами С (п, r), , , с повторениями , или . С – первая буква слова combination (англ. Сочетание). Наиболее употребительным является обозначение . Символ называется символом Аппеля.[1]




Пример 1. Пусть А={a, b, c}, r=2. Указать все упорядоченные и неупорядоченные выборки с повторениями и без повторений из трех элементов по два.

1. aa, ab, ac, ba, bb, bc, cb, ca, cc – девять перестановок с повторениями,

2. ab, ac, ba, bb, bc, cb, ca – шесть перестановок без повторений, Р3,2 =6.

3. ab, ac, bc – три сочетания без повторений, .

4. aa, ab, ac, bb, bc, cc – шесть сочетаний с повторениями, .





Дата добавления: 2015-01-07; просмотров: 675; Опубликованный материал нарушает авторские права? | Защита персональных данных | ЗАКАЗАТЬ РАБОТУ


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Увлечёшься девушкой-вырастут хвосты, займёшься учебой-вырастут рога 9712 - | 7629 - или читать все...

Читайте также:

 

34.204.173.45 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.


Генерация страницы за: 0.002 сек.