Пример 2. Найти все максимальные подмножества графа 
методом построения дерева вариантов.
Решение. Строим дерево вариантов по описанному выше алгоритму. Получаем следующий результат.
Анализируя состав терминальных узлов, получаем ответ 
.
9. Теория множеств.
Провести грамматический разбор формулы алгебры множеств над заданным набором базисных подмножеств данного универсума 
, вычислить значение формулы, как некоторого(искомого) подмножества того же универсума.
Дано:
- универсум,
- набор базовых множеств, подмножеств универсума, где 
,
,
,
.
Решение.
Анализируем главную формулу 
.
Находим индексы всех связок формулы и определяем центральную связку.
Таким образом, центральной связкой в формуле 
является операция пересечения и относительно ее имеем 
, где 
и 
. Таким образом на данном этапе построено начальное дерево высоты 2 с корнем 
, имеющим два потомка 
и 
. Это начальное дерево имеет вид:
Анализируем формулу 
.
Находим индексы всех связок формулы и определяем центральную связку.
Таким образом, центральной связкой в формуле 
является операция пересечения и относительно ее имеем 
, где 
.
В исходное дерево вместо узла
подставляем структуру
Анализируем формулу 
. Имеем: 
- лист.
Замещаем узел
на узел
Анализируем формулу 
.
Находим индексы всех связок формулы и определяем центральную связку.
В данной формуле центральной и единственной связкой является операция объединения, относительно которой, анализируемая подформула имеет структуру:
т. е. является поддеревом высоты 2, завершаемым листьями. Грамматический разбор формулы алгебры множеств завершен. Дерево формулы имеет вид:
Вычислим теперь значение формулы, совершая обход дерева по слоям от листьев к корню и вычисляя при этом значения внутренних узлов.
Имеем:
- дано,
- дано,
- дано,
Таким образом, получено значение анализируемой формулы.
10. Комбинаторика.
Подсчитать комбинаторные величины:
- количество сочетаний без повторений из 10 предметов по 4;
Типичная задача: Сколькими способами можно выбрать 3 книги из 10 имеющихся в библиотеке(порядок книг в выборе не важен).
Расчет: 
В данном случае:
.
2) 
- количество размещений из 8 предметов на 3 местах;
Типичная задача: Сколькими способами можно распределить первую, вторую и третью премию среди 8 участвующих конкурсантов(порядок в выборе важен)
Расчет: 
.
В данном случае:
.
3) 6!- количество перестановок из 6 предметов;
Типичная задача: сколькими способами можно разместить 4 картины в ряд на стене.(Размещение n различных объектов на n местах, порядок важен.)
Расчет: 
.
В данном случае 
.
4) 
- количество сочетаний с повторениями по 4 из 3-х(Подсказка: количество наборов по 4 из 3-х типов пирожных =
)
Типичная задача. В туристской группе должно быть 5 человек. Имеется 4 типа туристов: мужчина, женщина, мальчик, девочка.
Сколько типичных составов групп по 5 человек может быть.
(Выбор 5 предметов из 4 типов предметов с неограниченным запасом, порядок в выборке не важен).
Расчет: 
В данном случае имеем: 
- типов туристских групп.
5) 
- количество перестановок n предметов k различных типов с количеством неразличимых экземпляров типа i, равным 
. Предметы внутри групп не различимы.
Типичная задача:
В течение 5 дней должно быть проведено 2 занятия по химии, два по математике и одно по физике. В день проводится одно занятие. Сколькими способами можно составить расписание занятий.
Таким образом, имеем 3 типа занятий данным количеством каждого типа, всего 5 занятий. Нужно разместить эти 5 занятий на 5 местах(порядок важен - перестановка с повторениями, занятия с одним названием считаются эквивалентными.)
Расчет:
.
В данном случае имеем:
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 |
