Анализ алгоритмов
В процессе разработки и реализации алгоритма естественным образом раскрываются некоторые его свойства. По мере того как алгоритмы становятся все более и более сложными, все менее и менее вероятно, что их важные свойства проявятся на стадиях разработки и реализации. Как правило, некоторые важные аспекты поведения алгоритма, такие как его корректность, необходимое число операций или объем памяти, определить трудно. Поэтому обычно глубокое понимание нового алгоритма предваряется очень длинной стадией его анализа.
Из-за трудностей анализа им зачастую просто пренебрегают. Вместо этого программа выполняется для того, чтобы увидеть, что получается (например, измеряется время работы). Такой подход можно признать удовлетворительным, если есть основание полагать, что тестовые задачи достаточно хорошо характеризуют работу алгоритма в общем случае; если же это не так, то описанный подход даст мало ценной информации. Даже если тест прекрасно характеризует работу алгоритма, он никогда не даст ответ на придирчивый вопрос, могут ли существовать лучшие алгоритмы для решения той же самой задачи. Проблему оптимальности алгоритма можно решить только путем его анализа.
В анализе алгоритмов существуют две фундаментальные проблемы:
Какими свойствами обладает данный алгоритм?Какие свойства должен иметь любой алгоритм, решающий данную проблему?
Фундаментальная разница между этими двумя вопросами состоит в подходе к ответу на них. В первом случае алгоритм задан и заключения выводятся путем изучения свойств, присущих ему. Во втором случае задается проблема и точно определяется структура алгоритма. Заключения выводятся на основе изучения существа проблемы по отношению к данному классу алгоритмов.
Классы алгоритмов
Одной из причин быстрого прогресса комбинаторных вычислений является усиление внимания к исследованию классов алгоритмов в противоположность изучению отдельных из них. Для того чтобы утверждать, например, что "все алгоритмы, предназначенные для выполнения того-то и того-то, должны обладать такими-то и такими-то свойствами" или "не существует алгоритма, удовлетворяющего тому-то и тому-то", необходимо иметь дело с четко определенным классом алгоритмов. Именно при таком определении становится возможным говорить, что данный алгоритм является оптимальным по отношению к некоторому свойству, если он работает по крайней мере так же хорошо (относительно этого свойства), как любой другой алгоритм из рассматриваемого класса.
Как можно строго определить, возможно, бесконечный, класс алгоритмов? Исследуем этот вопрос на примере задачи о фальшивой монете. Рассматриваемый в этом примере класс алгоритмов порождает более обширный и более важный класс алгоритмов - так называемые деревья решений.
Задача. Имеется






Решение Пусть сомнительные монеты занумерованы числами









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

Рис. 1.1. Дерево решений для задачи о фальшивой монете с четырьмя монетами
Корень дерева на рисунке изображен полой окружностью и помечен отношением

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

Рис. 1.2. Корень другого дерева решений для задачи о четырех монетах
Если посчастливится, задачу можно решить за одно сравнение - это может произойти, когда все монеты настоящие. Независимо от того, как дополняется это дерево решений, в худшем случае задача все равно потребует тех же трех сравнений, поскольку единственное тернарное решение не может идентифицировать один из четырех исходов, которые возможны на ветви, помеченной символом "


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

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




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

сомнительных монет из одного дерева, приведенного на рис.1.3, можно получить другие оптимальные деревья. Все они будут изоморфны дереву на рис.1.3. Исходя из этого, уточним постановку задачи и будем интересоваться попарно неизоморфными деревьями.
Рассмотрим затем, существует ли оптимальное дерево среди тех, у которых в корне не используется монета с номером n.
При таком ограничении в корне дерева можно сделать только два различных сравнения, а именно


Наконец, рассмотрим те деревья решений, которые используют монету 0 в корне. В этом случае видно, что в корне фактически возможны только два сравнения:


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




Поскольку число листьев в дереве решений должно быть по крайней мере таким же, как и число возможных исходов задачи (

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






Программа
Программа 1.Поиск фальшивой монеты
//Монета ищется простым перебором. //Алгоритм реализован на языке программирования Turbo-C++. #include <stdlib.h> #include <conio.h> #include <stdio.h> int main() { clrscr(); int k, n, flag = -1; int *mas; printf("Введите число монет: "); scanf("%i", &n); mas = (int*)malloc(sizeof(n)); randomize(); k = random (10) + 1; for (int i = 0; i < n; i++) { mas[i] = k; } for (i = k; i == k; i = random (20)); mas[random (n)] = i; printf("Масса монет: "); for (i = 0; i < n; i++) { printf("%5i", mas[i]); if (mas[i] != k) { flag = i; } } printf("\nФальшивая монета под номером %i ее вес %i", flag+1, mas[flag]); getch(); free(mas); return 0; }

Комбинаторная математика является старой дисциплиной.
Комбинаторная математика является старой дисциплиной. Она получила свое наименование в 1666 г. от Лейбница в его "Dissertation de Arte Combinatori". Комбинаторные алгоритмы с их акцентом на разработку, анализ и реализацию практических алгоритмов являются продуктом века вычислительных машин.
Предмет теории комбинаторных алгоритмов - вычисления на дискретных математических структурах. Это новое направление исследований. Лишь в последние несколько лет из наборов искусных приемов и разрозненных алгоритмов сформировалась система знаний о разработке, реализации и анализе алгоритмов.
Комбинаторные вычисления находятся в таком же отношении к комбинаторной математике (дискретной, конечной математике), как численные методы анализа - к анализу. Комбинаторные вычисления развиваются в следующем направлении:
интенсивно изобретаются новые алгоритмы;происходит быстрый прогресс (главным образом в математическом плане) в понимании алгоритмов, их разработки и анализа;происходит переход от изучения отдельных алгоритмов к исследованию свойств, присущих классам алгоритмов.
В отличие от некоторых других разделов математики, комбинаторные вычисления не имеют "ядра", то есть некоторого количества "фундаментальных теорем", составляющих суть предмета, из которых выводится большинство результатов. Сначала может показаться, что в целом эта область состоит из наборов специальных методов и хитрых приемов. Однако после того, как было исследовано достаточно много комбинаторных алгоритмов, стали вырисовываться некоторые общие принципы. Именно эти принципы делают комбинаторные вычисления связной областью знаний и позволяют изложить ее в систематизированном виде.