78189

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

Лекция

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

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

Русский

2015-02-07

169 KB

21 чел.

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


 

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

6569. Основы биотехнологии. Генетическая инженерия и область ее применения 44.65 KB
  Основы биотехнологии Термин биотехнология прочно вошёл в современный лексикон биологов. Этим термином определяют технологию получения разнообразных продуктов и веществ с помощью живых клеток различного происхождения. При этом есть одно существенное...
6570. Мутационная изменчивость. Понятия о мутациях и их классификация 37.99 KB
  Мутационная изменчивость 1. Понятия о мутациях и их классификация. Изменчивость организмов является одним из главных факторов эволюции. Биологи различают наследственную и ненаследственную изменчивость. К наследственной изменчивости относят комбинаци...
6571. Генетические основы онтогенеза 27.97 KB
  Генетические основы онтогенеза Онтогенез - непрерывный процесс количественных и качественных изменений, происходящих в организме в течение всей жизни при постоянном взаимодействии генотипа и условий среды. Термины онтогенез и филогенез ввел...
6572. Генетика популяций. Понятие о популяции и чистых линиях. Эффективность отбора в чистых линиях и популяциях 47.82 KB
  Генетика популяций Понятие о популяции и чистых линиях. Эффективность отбора в чистых линиях и популяциях. Популяция - это группа организмов одного вида, свободно скрещивающихся друг с другом, имеющая определённый ареал обитания и изолированная...
6573. Иммлуногенетика. Группы крови человека и животных 34.01 KB
  Иммлуногенетика Группы крови человека и животных. В пределах вида особи различаются не только по морфологическим признакам, но и по ряду биохимических, которые могут быть выявлены иммуногенетически в виде системы антигенов. Антигены - это вещества б...
6574. Наследование количественных признаков 46.79 KB
  Наследование количественных признаков Все признаки у животных разделяются на две группы - качественные и количественные. К качественным признакам относятся: масть животных, пол, тип конституции, устойчивость к заболеваниям и другие....
6575. Генетические основы иммунитета. Понятие об иммунитете и иммунной системе организма 35.33 KB
  Генетические основы иммунитета Понятие об иммунитете и иммунной системе организма. Мы живем в потенциально враждебном мире, наполненном огромным множеством инфекционных агентов, которые имеют различные размеры форму, строение и раз...
6576. Наследственные аномалии и болезни с наследственной предрасположенностью. Селекция животных на устойчивость к заболеваниям 33.59 KB
  Наследственные аномалии и болезни с наследственной предрасположенностью. Селекция животных на устойчивость к заболеваниям Генетические аномалии у сельскохозяйственных животных. В результате мутаций у животных и человека возникают различные наследств...
6577. Генетика крупного рогатого скота, свиней, овец и птицы 42.86 KB
  Генетика крупного рогатого скота, свиней, овец и птицы Генетика крупного рогатого скота. Скотоводство представляет в нашей стране главную отрасль животноводства. Дальнейшее его развитие связано с увеличением генетического потенциала, возможности кот...