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

Комбинаторные алгоритмы. Сочетания (выборки) Задачу имеет смысл называть комбинаторной, если ее решение состоит в переборе элементов x множества X. Задача: Сколькими способами можно выбрать M из N различных предметов? Ответ

Слайд 1Комбинаторные алгоритмы Индикативные множества
Пример комбинаторной задачи: построение сочетаний с помощью индикативных множеств.


Полное построение алгоритма для решения комбинаторной задачи

Слайд 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)!)]
(применить формулу Стирлинга для вычисления факториала)

Слайд 12Задание 1: Пусть все члены СК имеют номера членских билетов от

1 до n. Написать программу, которая выводит все возможные составы делегаций из k членов согласно их членским билетам (все возможные сочетания из n по k - Сkn )
Задание 2: Пусть имеется алфавит, состоящий из n символов. Описать полное построение алгортима, который для заданной строки, составленной из символов данного алфавита, вычисляет частоту появления каждого символа.

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика