78189

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

Лекция

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

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

Русский

2015-02-07

169 KB

35 чел.

екция: Основные комбинаторные алгоритмы  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.  Принцип алгоритма сочетаний. Математическая формула алгоритма.


 

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

41620. Решение задачи Дирихле для уравнения Пуассона методом Чебышева 103.07 KB
  Разностную задачу 5 будем решать явным итерационным методом с чебышевским набором параметров который выражается следующей формулой: 10 где заданное число итераций . 11 Результаты: В вычислениях использовался следующий алгоритм: Задаём количество итераций полагаем тогда шаг сетки =01. Полученный ответ с точностью до...
41621. Генерация таблицы переходов и функций возбуждения тригеров 141.5 KB
  В результате выполнения данной лабораторной работы я приобрёл навыки анализа графовых структур и автоматизации процедуры построения таблицы переходов. Мной был разработан класс для генерации таблицы переходов.
41622. Решение первой начальной краевой задачи для уравнения теплопроводности по схеме Кранка-Николсона 102.29 KB
  Задача: Используя метод простых итераций метод Чебышева и метод наискорейшего спуска найти по схеме КранкаНиколсона приближенное решение задачи: 1 2...
41623. Дослідження структури поля в металевих хвилеводах і резонаторах 179.46 KB
  Київ 2010 Мета роботи дослідити розподіл електромагнітного поля в призматичних та циліндричних хвилеводах та резонаторах методом електричного зонду. Структура поля досліджується за допомогою електричного зонду з детекторною голівкою.
41624. Робота з операторами INSERT, UPDATE, DELETE 47.12 KB
  VLUES із списком з декількох значень підтримується у версії MySQL 3. Синтаксис виразу col_nme=expression підтримується у версії MySQL 3. У MySQL завжди передбачено значення за умовчанням для кожного поля. Ця вимога нав'язана MySQL щоб забезпечити можливість роботи як з таблицями які підтримують транзакції так і з таблицями що не підтримують їх.
41625. Створення резервної копії та відновлення даних з неї 218.34 KB
  Вибрати базу даних. У вікні Загрузка файла вибрати Сохранить та вказати місце на диску для збереження дампу бази даних. Відновлення бази даних за допомогою програми phpMydmin Щоб виконати відновлення бази даних потрібно: Вилучити існуючу базу даних.
41628. Синтез моделей тіла людини за дії допустимих напруг дотику 616.17 KB
  Львів 2013 Мета роботи: розрахувати параметри моделі тіла людини за дії на неї довготривалих допустимих напруг. Загальні відомості про синтез моделей тіла людини Тіло людини як елемент електричного кола складається з декількох шарів з різними електричними характеристиками. За інших рівних умов напруженість електричного поля в тілі тим менша чим вища його електрична проникність що характеризує здатність тіла до поляризації.