78189

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

Лекция

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

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

Русский

2015-02-07

169 KB

27 чел.

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


 

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

54754. Опера М.И. Глинки «Иван Сусанин» 163.5 KB
  Задачи урока: Способствовать осознанию детьми мотивов поведения героев и определению личностного отношения к событиям и персонажам. Развивать умение чувствовать настроение героя музыкального произведения. Воспитывать чувство гордости за русский народ, патриотизм. Способствовать накоплению навыков работы с литературой.
54755. Модель «совокупный доход – совокупные издержки» 59.84 KB
  Однако сами издержки бывают внешними (явными) и внутренними (неявными). К внешним издержкам относятся платежи внешним (по отношению к данной фирме) поставщикам.
54756. Природа в опасности! Охрана природы 1.36 MB
  Развитие у детей умения осуществлять самоконтроль. Развитие восприятия: Развитие целостности предметности осмысленности восприятия. Развитие речи: Развитие диалогической и монологической речи развитие содержательности понятности и выразительности речи. Развитие памяти: Развитие образной эмоциональной словесно-логической памяти.
54757. Проценты 58 KB
  Цели урока: Формирование у учащихся понятия Процент; умений перевода процентов в дробь и обратно; умений нахождения процента от числа разными способами; Развитие кругозора и математической культуры у учащихся; Воспитание активности аккуратности точности. Тип урока: комбинированный Время проведения: 40 минут Оснащение: опорный конспект заранее приготовленные записи на доске прилагается презентация по теме Ход урока: Этап урока Деятельность учителя Деятельность ученика Организационный момент...
54758. Попит, пропозиція, ціна 94 KB
  Яка залежність між величиною попиту й ціною: пряма чи обернена 3.Чи завжди зі зменшенням ціни збільшується величина попиту 5. Дайте характеристику еластичності попиту за доходом для нижчих і нормальних товарів. Що означають поняття зміна обсягу попиту і зміни що відбулися у попиті 6.
54759. Мягкий знак после шипящих на конце существительных женского рода 46 KB
  Цели урока: Познакомить учащихся с правописанием мягкого знака на конце существительных женского рода 3 склонения. Закреплять и развивать умения и навыки в определении падежей и склонения имен существительных, правописания слов с безударными гласными непроверяемых ударением. Развивать умения работать самостоятельно, делать выводы, рассуждать, получать новые знания. Воспитывать усидчивость, любовь к родному языку, старательность.
54760. Сочинение по картине А. К. Саврасова «Грачи прилетели» 112.5 KB
  Сегодня на уроке мы познакомимся с картиной Алексея Кондратьевича Саврасова Грачи прилетели и будем учиться писать сочинение по этой картине. Какие чувства вызывает у вас эта картина Выслушиваются ответы учащихся Почему картина называется Грачи прилетели История создания картины Первоначальные этюды к картине Грачи прилетели А.
54761. Правила поведения хозяина при приёме гостей и культура гостя 67.5 KB
  Правила поведения хозяина при приёме гостей и культура гостя. Таблички: Хозяин дома должен быть щедрым добрым вежливым. Хозяин дома должен быть приветливым. Хозяин дома должен уметь занять своих гостей.
54762. РОЛЬ ТЕЛЕВИДЕНИЯ В ЖИЗНИ ПОДРОСТКА 108.5 KB
  Good morning, my dear pupils! Good morning, our guests! Today we are having quite an unusual lesson. You see a lot of new faces. But I hope that you’ll feel comfortable at this lesson and together we’ll try to make our lesson useful and interesting. Are you ready for work? Let’s start our English lesson. How are you today? Mary, you look so sad, what’s the matter?