Предмет теорії комбінаторних алгоритмів. Правила множення і суми.

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ Комбинаторикой называется раздел математики, в котором рассматриваются вопросы о том, сколько различных комбинаций, подчиненных тем или иным законам, можно составить из элементов, принадлежащих заданному множеству. Задачи комбинаторики можно условно разделить на три основных типа: 1. Решение вопроса о числе возможных решений (т.е. требуемых выборок или расположений). 2. Решение вопроса о существовании решений. 3. Способы отыскания оптимальных решений.

Основное правило комбинаторики Пусть нужно установить, сколькими способами можно осуществить некоторое действие. Предположим также, что удалось разбить это действие на две части, причём первую часть можно осуществить n способами, а вторую часть – m способами. Тогда очевидно, что всё действие целиком можно осуществить m · n способами. Это утверждение называется основным правилом комбинаторики.

Задачи Пример 1. В меню в столовой предлагается два варианта первого блюда, четыре варианта второго и три варианта третьего, тогда выбрать обед из трёх блюд можно 2 · 4 · 3 = 24 способами. Пример 2. В городе происходят два чрезвычайных происшествия в день. На место происшествия отправляют оперативную группу из трех человек: следователя, оперативника и эксперта. В УВД несут службу 3 следователя, 2 оперативника и 3 эксперта. График их работы составляется таким образом, чтобы каждая очередная опергруппа отличалась от всех предыдущих (пока это будет возможно). Трое друзей – следователь Зубов, оперативник Прокопенко и эксперт Зульфия – всегда добиваются успеха. Как часто эта группа попадает в график?

Дерево возможных вариантов. Пример 3. « Этот вечер свободный можно так провести …» ( А. Кушнер ): пойти прогуляться к реке, на площадь или в парк и потом пойти в гости к Вите или к Вике. А можно остаться дома, сначала посмотреть телевизор или почитать книжку, потом поиграть с братом или разобраться наконец у себя на столе. Нарисовать дерево возможных вариантов. Вечер Прогулка Дом Парк ПлощадьРека Витя ВикаВитя Вика ТВКнижка Брат СтолБрат Стол

Пример 4. У преподавателя радиотехнического факультета В.И. произошла досадная неприятность с компьютером: сразу после включения ОС зависла и на экране монитора появилось сообщение: «Привет! Я – компьютерный вирус «Загадка Сфинкса». Ты должен ответить на 12 вопросов, которые записаны с помощью древнеегипетских иероглифов. На каждый вопрос можно ответить только «да» или «нет». Если через 10 дней ты не сможешь правильно ответить на мои вопросы или попытаешься выключить компьютер, твой винчестер умрет». В.И. решил перебирать все возможные комбинации ответов «да» и «нет» на 12 непонятных вопросов, пока не обнаружится правильный вариант. Чтобы не сбиться, преподаватель решил записывать каждую комбинацию ответов в виде следующей таблицы: На составление очередной комбинации ответов и ввод ее в компьютер В.И. тратит одну минуту. Успел ли он сделать работу вовремя и спасти винчестер, если работал по 6 часов в сутки, а правильная комбинация оказалась последней? да нетда нетданет

Правило суммы Если все варианты делятся на k взаимоисключающих типов, причем имеется n1 вариантов первого типа, n2 вариантов второго типа, …, nk вариантов k-го типа, то общее число вариантов есть Если пересечение конечных множеств A и B пусто, то число элементов в их объединении равно сумме чисел элементов множеств A и B: Если конечные множества A 1, A 2,..., A K попарно не пересекаются, то имеет место равенство.

Пример 5. Если на одной полке книжного шкафа стоит 30 различных книг, а на другой – 40 различных книг (и нет таких, как на первой полке), то выбрать одну книгу из стоящих на этих полках можно = 70 способами. Пример 6. При формировании экипажа космического корабля имеется 10 претендентов на пост командира экипажа, 20 – на пост бортинженера и 25 – на пост космонавта-исследователя. Ни один кандидат не претендует одновременно на два поста. Сколькими способами можно выбрать одну из кандидатур или командира, или бортинженера, или космонавта- исследователя?.

Правило умножения Если множества А и В конечны, то число N всевозможных пар равно произведению чисел элементов этих множеств: С помощью метода математической индукции это правило обобщается на любое конечное число множеств. Следствие из правила умножения: если имеется k конечных множеств A 1, A 2,..., A k то число N всевозможных наборов (a 1, a 2, …, a k ), где a 1 A 1, a 2 A 2, …, a k A k, равно N = n(A 1 ) · n(A 2 ) ·…· n(A k ).

На завтрак можно выбрать булочку, кекс, пряники или печенье, запить можно чаем, соком или кефиром. Сколько вариантов завтрака есть ? х/б изд. напитки булочкакекспряникипеченье чай сок кефир чай кефир сок кефир булочка кекс пряники печенье Выбор напитка - испытание АВыбор хл./ бул. изделия.- испытание ВИспытание А имеет 3 варианта ( исхода ), а испытание В -4, всего вариантов независимых испытаний А и В 34=12. Для того, чтобы найти число всех возможных исходов (вариантов) независимого проведения двух испытаний А и В, надо перемножить число всех исходов испытания А на число всех исходов испытания В 2. Правило умножения.

В комнате 3 лампочки. Сколько имеется различных вариантов освещения комнаты, включая случай, когда все лампочки не горят. 1 лампочка 2 лампочка лампочка способ: метод перебора исходов (вариантов) 2 способ: правило умножения. Испытание А- действие 1 лампочки, испытание В-действие 2 лампочки, испытание С-действие 3 лампочки. Решим задачу : У каждого испытания 2 исхода: «горит» и «не горит» Всего исходов: 222=8

Правило произведения Пример 6. Из города А в город Б ведет 6 дорог, из города Б в город В – 4 дороги, и больше никаких дорог из этих городов не выходит. Сколькими способами можно проехать из города А в город В? Пример 7. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево? Пример 8. Сколько существует шестизначных чисел, которые делятся на пять?