Комбинаторные алгоритмы. Индикативные множества

Август 10, 2022

Главная
Информатика
Комбинаторные алгоритмы. Индикативные множества

Содержание

2. Комбинаторные алгоритмы. Сочетания (выборки) Задачу имеет смысл называть комбинаторной, если ее решение состоит в переборе элементов
3. Комбинаторные алгоритмы. Сочетания Задача. В союзе кинематографистов (СК) состоит определенное количество кинематографистов. Ежегодно в Канны на
4. Постановка задачи. Дано: Общее количество кинематографистов, состоящих в СК Количество человек, уезжающих в одну командировку. Надо:
5. Построение модели Пусть количество кинематографистов 5, а количество членов делегации 3. Пометим всех их целыми числами
6. Организация сочетаний с помощью индикативных множеств. C35 = 5! / (3!⋅(5-3)!) = 5! / (3!2!) =
7. Организация сочетаний с помощью индикативных множеств Можно составить множество всех возможных делегаций, количество которых 2n. Для
8. Организация сочетаний с помощью индикативных множеств
9. Построение алгоритма Входные данные: n - количество членов союза кинематографистов (СК); K - количество членов делегации.
10. Проверка правильности алгоритма Среди всех двоичных чисел от 0 до 2n найдутся числа с k единицами
11. Анализ алгоритма и его сложности Размерность задачи n. Количество двоичных чисел 2n, Сл-но, эта часть алгоритма
13. Скачать презентацию

Слайд 2

Комбинаторные алгоритмы. Сочетания (выборки)
Задачу имеет смысл называть комбинаторной, если ее решение

состоит в переборе элементов x множества X.
Задача: Сколькими способами можно выбрать M из N различных предметов?
Ответ - сочетания
Формула Ньютона
Σ СiN = 2N

Слайд 3

Комбинаторные алгоритмы. Сочетания
Задача. В союзе кинематографистов (СК) состоит определенное количество кинематографистов.

Ежегодно в Канны на кинофестиваль едет некоторое количество из них. Сформировать и вывести последовательность командировок (все возможные варианты), если каждая следующая делегация содержит в себе одного нового члена СК.
(Вариант формулировки: отправка делегации болельщиков на Олимпиаду)

Слайд 4

Постановка задачи.
Дано:
Общее количество кинематографистов, состоящих в СК
Количество человек, уезжающих в

одну командировку.
Надо:
Вывести последовательность ежегодных командировок.
Дополнительная информация:
Каждая новая командировка содержит одного нового члена делегации.

Слайд 5

Построение модели
Пусть количество кинематографистов 5, а количество членов делегации 3.
Пометим

всех их целыми числами (1, 2, 3, 4, 5).
Таким образом, необходимо выписать последовательность сочетания трех чисел из пяти.
Сколько сочетаний по 3 из 5?
Сkn=n!/(k!⋅(n-k)!)

Слайд 6

Организация сочетаний с помощью индикативных множеств.
C35 = 5! / (3!⋅(5-3)!) =

5! / (3!2!) = 1*2*3*4*5 / (1*2*3*1*2) =10
Как выписать сочетания?
Обозначим состояние поездки одного кинематографиста: 1 - едет; 0 - не едет (бинарная арифметика).
Тогда состав делегации может быть обозначен вектором с пятью компонентами.
Например, вектор (1, 0, 0, 1, 1) означает, что 1, 4, 5 кинематографисты включены в делегацию, а 2 и 3 нет.

Слайд 7

Организация сочетаний с помощью индикативных множеств
Можно составить множество всех возможных делегаций,

количество которых 2n. Для нашего примера 25=32.
Определение:
Индикативное множество - множество, состоящее только из единиц и нулей. (Индикатор – место, на котором они стоят.)
Составим индикативное множество из n элементов

Слайд 8

Организация сочетаний с помощью индикативных множеств

Слайд 9

Построение алгоритма
Входные данные:
n - количество членов союза кинематографистов (СК);
K

- количество членов делегации.
Выходные данные:
Составы делегаций
Алгоритм:
Ввести n и k.
Выписать числа в двоичном коде от 0 до 2N
Выбрать числа, у которых ровно k единиц.
Для каждого такого числа выписать номера разрядов, в которых стоит единица, и вывести эти номера разрядов (список сочетаний).

Слайд 10

Проверка правильности алгоритма
Среди всех двоичных чисел от 0 до 2n найдутся

числа с k единицами (kДля каждого выбранного i-того двоичного числа можно указать номер разряда, где стоит единица, а значит, выписать сочетание Сni
Алгоритм конечен, так как просматривается конечное количество двоичных чисел.

Слайд 11

Анализ алгоритма и его сложности
Размерность задачи n.
Количество двоичных чисел 2n,
Сл-но,

эта часть алгоритма потребует О(2n) шагов. В каждом числе ищем количество единиц за О(n) шагов (либо сумм, либо сравнений).
Для каждой Сkn выписываем k разрядов за О(Сkn) = О(n!/(k!(n-k)!)⋅k) шагов.
Итого fA(n)=O(2n⋅n+ n!/(k!(n-k)!)⋅k) = O(n⋅[2n+(n-1)!/((k-1)! ⋅(n-k)!)]
(применить формулу Стирлинга для вычисления факториала)

Комбинаторные алгоритмы. Индикативные множества

Содержание

Комбинаторные алгоритмы. Сочетания (выборки)Задачу имеет смысл называть комбинаторной, если ее решение

Комбинаторные алгоритмы. СочетанияЗадача. В союзе кинематографистов (СК) состоит определенное количество кинематографистов.

Постановка задачи. Дано: Общее количество кинематографистов, состоящих в СККоличество человек, уезжающих в

Построение модели Пусть количество кинематографистов 5, а количество членов делегации 3. Пометим

Организация сочетаний с помощью индикативных множеств. C35 = 5! / (3!⋅(5-3)!) =

Организация сочетаний с помощью индикативных множествМожно составить множество всех возможных делегаций,