Классы алгоритмов

Оглавление

Введение. Ошибка! Закладка не определена.

Проблема представления. 1

Классы алгоритмов. 2

Анализ алгоритмов. 3

Алгоритм размещения без повторений. 3

Алгоритм перестановки. 4

Алгоритм сочетания. 4

Контрольные вопросы.. 4

Лекция 20. Алгоритмы генерирования перестановок, множества всех подмножеств, к-элементных подмножеств множества, разбиения множеств.

Предмет теории комбинаторных алгоритмов - вычисления на дискретных математических структурах. Это новое направление исследований. Лишь в последние… Комбинаторные вычисления развиваются в следующем направлении: · интенсивно изобретаются новые алгоритмы;

Проблема представления

Приведем примеры, в которых задаются весьма специфические операции над целыми. Целые определяются как данные простейшего типа почти во всех… Проблемы кодов, сохраняющих разности, касаются случаев 2 и 3. В задачах…

Классы алгоритмов

Для того чтобы сравнивать алгоритмы между собой, необходимо четко определить понятие класса алгоритмов. Тогда можно говорить об алгоритме оптимальном в своем классе относительно некоторого свойства, характеризующего этот класс.

Рассмотрим, как можно определить класс алгоритмов на примере задачи о фальшивой монете. Рассматриваемый в этом примере класс алгоритмов порождает более обширный и более важный класс алгоритмов - так называемые деревья решений.

Задача. Имеется n монет, о которых известно, что n-1 из них являются настоящими и не более чем одна монета, фальшивая (легче или тяжелее остальных монет). Дополнительно к группе из n сомнительных монет дается еще одна монета, причем заведомо известно, что она настоящая. Имеются также весы, с помощью которых можно сравнить общий вес любых m монет с общим весом любых других m монет и тем самым установить, имеют ли две группы по m монет одинаковый вес либо одна из групп легче другой. Задача состоит в том, чтобы найти фальшивую монету, если она есть, за наименьшее число взвешиваний, или сравнений.

Решение. Пусть сомнительные монеты занумерованы числами. Монете, о которой известно, что она настоящая, поставим в соответствие номер 0. Пусть {0, 1, 2, …., n } - множество монет. Если S1, S2 — непересекающиеся непустые подмножества множества S, то через S1:S2 обозначим операцию сравнения весов множества S1, S2. При сравнении возможны три исхода, которые обозначим следующим образом:S1<S2, S1=S2, S1>S2 в зависимости от того, является ли вес S1 меньшим, равным или большим веса S2.

Рассматриваемые алгоритмы можно представить в форме дерева решений.

 

Рис. 1.1. Дерево решений для задачи о фальшивой монете с четырьмя монетами

 

Корень дерева на рисунке изображен полой окружностью и помечен отношением 1:2 . Это означает, что алгоритм начинает работу сравнением весов монет с номерами 1 и 2. Три исходящие из корня ветви ведут к поддеревьям, определяющим продолжение работы алгоритма после каждого из трех возможных исходов первого сравнения. Окружности, залитые черной краской, называются листьями дерева и означают, что работа алгоритма заканчивается. Метки соответствуют исходам: "1л" - монета 1 легкая, "1т" - монета 1 тяжелая, "н" - все монеты настоящие. Непомеченная вершина дерева означает, что при наших предположениях этот случай возникнуть не может.

Алгоритм, приведенный на рис 1.1, требует двух сравнений в одних случаях и трех - в других. Скажем, что он требует "трех сравнений в худшем случае". Обычно важно знать, сколько работы требует алгоритм в среднем, однако для этого требуется задать вероятности различных исходов. Если предположим, что все исходы 1л, 1т, 2л, 2т, 3л, 3т, 4л, 4т, - равновероятны, то тогда этот алгоритм требует в среднем 7/3 сравнений.

На одну чашку весов можем положить больше одной монеты. Например, можно начать сравнения, положив на одну чашку весов монеты 1 и 2, а на другую - монеты 3 и 4 (рис. 1.2).

Рис. 1.2. Корень другого дерева решений для задачи о четырех монетах

 

Задачу можно решить за одно сравнение - это может произойти, когда все монеты настоящие, независимо от того, как дополняется это дерево решений. В худшем случае задача все равно потребует тех же трех сравнений, поскольку единственное решение не может идентифицировать один из четырех исходов, которые возможны на ветви, помеченной символом "<", так же как и один из четырех исходов на ветви, помеченной символом ">". К тому же, независимо от того, как дополняется это дерево решений, оно потребует в среднем по крайней мере 7/3 сравнений, и в этом случае оно не лучше, чем дерево на рис 1.1.

, где 6 из 9 исходов соответствуют 2 сравнениям и 3 из 9 требуют 3 сравнения.

Используя монету 0, о которой известно, что она настоящая, можно получить приведенное на рис 1.3 дерево решений (полное двухъярусное тернарное дерево), которое и в худшем, и в среднем случае требует двух сравнений.

Рис. 1.3. Оптимальное дерево решений для задачи о четырех монетах

 

Рассматриваемый класс алгоритмов решения задачи о фальшивой монете есть множество тернарных деревьев решений (примеры на рис.1.1, рис.1.2, рис.1.3), обладающих следующими свойствами:

• каждый узел помечен сравнением S₁:S₂, где S₁ и S₂ - непересекающиеся непустые подмножества множества S={0, 1, 2, …., n} всех монет;
• каждый лист либо не помечен, что соответствует невозможному исходу в предположении существования не более чем одной фальшивой монеты, либо помечен одним из исходов i_Л, i_T, н, означающим соответственно, что все монеты настоящие.

Четко определив подлежащий дальнейшему рассмотрению класс алгоритмов, можно исследовать свойства, которыми должно обладать каждое дерево из этого класса, и определить, как найти алгоритмы, являющиеся в некотором смысле оптимальными.

Поскольку в задаче о четырех монетах требуется различить девять возможных исходов, любое дерево решений для этой задачи должно иметь, по крайней мере, девять листьев и, следовательно, не менее двух ярусов. Поэтому дерево на рис.1.3 является оптимальным и для худшего случая, и для среднего.

Анализ алгоритмов

Из-за трудностей анализа им зачастую просто пренебрегают. Вместо этого программа выполняется для того, чтобы увидеть, что получается (например,… В анализе алгоритмов существуют две фундаментальные проблемы: · Какими свойствами обладает данный алгоритм?

Алгоритм размещения без повторений

Например, при генерации всех размещений из 5 элементов по 3 в случае, когда… ABC ACB BAC BCA CAB CBA.

Алгоритм перестановки

Общее число перестановок из N элементов равно N!. Напомним, что N!=1*2*3*…*N. Например, имеем 4 компонента, обозначенные буквами A, B, C, D. Тогда множество… ABCD, BACD, CABD, DABC, ABDC, BADC, CADB, DACB, ACBD, BCAD, CBAD, DBAC,ACDB, BCDA, CBDA, DBCA, ADBC, BDAC, CDAB, DCAB,…

Алгоритм сочетания

Формула для числа сочетаний получается из формулы для числа размещений. В самом деле, составим сначала все k -сочетания из n элементов, а потом… Из этой формулы находим, что Например, имеем 5 компонент, обозначенных латинскими буквами A, B, C, D, E. Тогда все сочетания из этих 5 компонент по…

Контрольные вопросы

1. Дать определение комбинаторным вычислениям.
2. Дать понятие класса алгоритма. Какие свойства заложены в классе алгоритма решения задачи о фальшивой монете.
3. Как осуществляется анализ алгоритмов?
4. Принцип алгоритма размещения без повторений. Математическая формула алгоритма.
5. Принцип алгоритма перестановки. Математическая формула алгоритма.
6. Принцип алгоритма сочетаний. Математическая формула алгоритма.