Вопросы к экзамену по курсу “Дискретная математика” (стр. 8 )

Пример 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 местах(порядок важен - перестановка с повторениями, занятия с одним названием считаются эквивалентными.)

Расчет:.

В данном случае имеем: