78189

Основные комбинаторные алгоритмы

Лекция

Информатика, кибернетика и программирование

Контрольные вопросы Введение Комбинаторные алгоритмы с их акцентом на разработку анализ и реализацию практических алгоритмов являются продуктом века вычислительных машин. Предмет теории комбинаторных алгоритмов вычисления на дискретных математических структурах.

Русский

2015-02-07

169 KB

33 чел.

екция: Основные комбинаторные алгоритмы  5 из 5 с.

Оглавление

[1] Оглавление

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

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

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

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

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

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

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

Введение

Комбинаторные алгоритмы с их акцентом на разработку, анализ и реализацию практических алгоритмов являются продуктом века вычислительных машин.

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

Комбинаторные вычисления развиваются в следующем направлении:

  •  интенсивно изобретаются новые алгоритмы;
  •  происходит быстрый прогресс (главным образом в математическом плане) в понимании алгоритмов, их разработки и анализа;
  •  происходит переход от изучения отдельных алгоритмов к исследованию свойств, присущих классам алгоритмов.

В отличие от некоторых других разделов математики, комбинаторные вычисления не имеют "ядра", то есть некоторого количества "фундаментальных теорем", составляющих суть предмета, из которых выводится большинство результатов. Сначала может показаться, что в целом эта область состоит из наборов специальных методов и хитрых приемов. Однако после того как было исследовано достаточно много комбинаторных алгоритмов стали вырисовываться некоторые общие принципы. Именно эти принципы делают комбинаторные вычисления связной областью знаний и позволяют изложить ее в систематизированном виде

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

Чрезвычайно важной проблемой в комбинаторных вычислениях является задача эффективного представления объектов, подлежащих обработке. Она возникает потому, что обычно имеется много возможных способов представления сложных объектов более простыми структурами, которые можно заложить в языки программирования, но не все такие представления в одинаковой степени эффективны с точки зрения времени и памяти. Более того, идеальное представление зависит от вида производимых операций.

Приведем примеры, в которых задаются весьма специфические операции над целыми. Целые определяются как данные простейшего типа почти во всех вычислительных устройствах и языках программирования. Таким образом, проблема представления, как правило, не возникает. Имеющееся представление почти всегда наилучшее. Однако существуют некоторые заслуживающие внимания исключения, когда выгодно или даже необходимо использовать представление целых в вычислительном устройстве иным способом. Эти исключения появляются в следующих случаях:

  1.  Необходимы целые, больше имеющихся непосредственно в аппаратном оборудовании.
  2.  Необходимы только небольшие целые, и требуется сэкономить память, упаковывая их по несколько в одну ячейку.
  3.  Действия с целыми производятся не общепринятыми арифметическими операциями.
  4.  Целые используются для представления других типов объектов, и необходимо иметь возможность легко обращать целое в соответствующий ему объект и обратно.

Проблемы кодов, сохраняющих разности, касаются случаев 2 и 3. В задачах распознавания образов и классификации для решения вопроса, будут ли два объекта X,Y эквивалентными, стандартной является следующая процедура. X,Y представляются векторами признаков 1, x2,…,xf), (y1,y2,…,yf) соответственно, где каждая компонента означает признак объекта, выраженный целым значением. Считается, что X,Y эквиваленты тогда и только тогда, если  где t — целое, называемое порогом.

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

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

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

Задача. Имеется  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), обладающих следующими свойствами:

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

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

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

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

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

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

В анализе алгоритмов существуют две фундаментальные проблемы:

  •  Какими свойствами обладает данный алгоритм?
  •  Какие свойства должен иметь любой алгоритм, решающий данную проблему?

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

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

Имеется n  различных предметов. Сколько из них можно составить k-расстановок? При этом две расстановки считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке. Такие расстановки называют размещениями без повторений, а их число обозначают . При составлении k -размещений без повторений из n предметов нам надо сделать k выборов. На первом шаге можно выбрать любой из имеющихся n предметов. Если этот выбор уже сделан, то на втором шаге приходится выбирать из оставшихся n-1 предметов. На k -м шаге n-k-1 предметов. Поэтому по правилу произведения получаем, что число k -размещений без повторения из n предметов выражается следующим образом:

 

Например, при генерации всех размещений из 5 элементов по 3 в случае, когда сами элементы обозначены латинскими буквами А, B, C, D, E, нужно получить следующую последовательность, представленную для компактности в виде 10 строк, каждая из которых представляет все возможные сочетания из 3 букв первого элемента строки (первые элементы строк представляют все возможные сочетания из 5 букв по 3:

ABC  ACB  BAC  BCA  CAB  CBA.

ABD …

ABE …

ACD …

ACE …

ADE …

BCD …

BCE …

BDE …

CDE  CED  DCE  DEC  ECD  EDC

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

При составлении размещений без повторений из n элементов по k мы получили расстановки, отличающиеся друг от друга и составом, и порядком элементов. Но если брать расстановки, в которые входят все n элементов, то они могут отличаться друг от друга лишь порядком входящих в них элементов. Такие расстановки называют перестановками из n элементов, или, короче, n -перестановками. 

Общее число перестановок из 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, ADCB, BDCA, CDBA, DCBA. 

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

В тех случаях, когда нас не интересует порядок элементов в комбинации, а интересует лишь ее состав, говорят о сочетаниях. Итак, k -сочетаниями из n элементов называют всевозможные k - расстановки, составленные из этих элементов и отличающиеся друг от друга составом, но не порядком элементов. Число k-сочетаний, которое можно составить из n элементов, обозначают через  .

Формула для числа сочетаний получается из формулы для числа размещений. В самом деле, составим сначала все k -сочетания из n элементов, а потом переставим входящие в каждое сочетание элементы всеми возможными способами. При этом получается, что все k -размещения из n  элементов, причем каждое только по одному разу. Но из каждого k - сочетания можно сделать  перестановок, а число этих сочетаний равно . Значит, справедлива формула: 

Из этой формулы находим, что 

Например, имеем 5 компонент, обозначенных латинскими буквами A, B, C, D, E. Тогда все сочетания из этих 5 компонент по 3, выписанные в лексикографическом порядке, будут таковы:

  •  для букв – ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE;
  •  для цифр – 123, 124, 125, 134, 135, 145, 234, 235, 245, 345.

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

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


 

А также другие работы, которые могут Вас заинтересовать

70574. Износ деталей и промышленного оборудования 18.04 KB
  Срок службы оборудования определяется износом его деталей - изменением размеров, формы, массы или состояния его поверхностей вслед изнашивания, т.е. остаточной деформации от постоянно действующих нагрузок либо разрушения поверхностного слоя при фении.
70575. Создание, регистрация, лицензирование и расширение деятельности кредитной организации 24.75 KB
  Для оценки финансового положения учредителей и участников УК кредитных организаций Банк России либо ТУБР вправе запрашивать у учредителей кредитной организации любую информацию о финансовом положении и деятельности лиц способных прямо или косвенно определять решения принимаемые...
70576. Реформа банковской системы России 25.56 KB
  Преимущественно экстенсивный характер развития оказал негативное влияние на устойчивость банков что проявилось в условиях международного финансового кризиса и потребовало принятия Правительством Российской Федерации и Банком России экстренных мер по обеспечению системной стабильности...
70579. Виды деятельности, не относящиеся к предпринимательской 63 KB
  К предпринимательской деятельности не относятся: ремесленная деятельность; организация агроэкотуризма; ведение личного подсобного хозяйства. Деятельность по оказанию услуг в сфере агроэкотуризма осуществляется физическими лицами без государственной регистрации в качестве...
70580. Методологические основы государственного регулирования экономики 53.5 KB
  Государственное регулирование экономики в условиях рыночного хозяйства представляет собой систему государственных мер законодательного исполнительного и контролирующего характера осуществляемых правомочными государственными учреждениями и общественными организациями в целях...
70581. Формы и методы государственного регулирования экономики 63.5 KB
  Директивное планирование (ДП) - форма ГРЭ, длительное время существовавшая в СССР и других социалистических странах. При ДП план экономического развития имеет силу закона и является обязательным для исполнения воли звеньями экономической системы: регионами, отдельными предприятиями.
70582. Теоретические основы формирования и реализации макроэкономической политики государства (МПГ) 50 KB
  МПГ в системе государственного регулирования экономики Экономика любого государства не может развиваться без определения цели ее развития. Под экономической целью понимается основное направление развития экономики которое раскрывается с помощью поставленных задач.