Skip to content

Blog

02 Окт

У нас вы можете скачать книгу графы и их применение. комбинаторные алгоритмы для программистов н. и. костюкова в fb2, txt, PDF, EPUB, doc, rtf, jar, djvu, lrf!

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

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

Комбинаторные вычисления Лекция 2. Целые и последовательности последовательное распределение Лекция 3. Последовательности связанное распределение, стеки и очереди Лекция 4. Последовательности деревья Лекция 5. Комбинаторика разбиений Лекция 6. Последовательности множества и мультимножества Лекция 7. Рекуррентные соотношения Лекция 8. Алгоритмы рекуррентных соотношений Лекция 9. Комбинаторика и ряды Лекция Производящие функции и рекуррентные соотношения Лекция Алгоритмы на абстрактных структурах данных Лекция Определения и примеры Лекция Сортировка часть 1 Лекция Сортировка часть 2 Лекция Алгоритмы на графах Лекция Калейдоскоп из комбинаторных алгоритмов Скачать Комбинаторные алгоритмы для программистов.

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

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

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

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

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

Решение Пусть сомнительные монеты занумерованы числами. Монете, о которой известно, что она настоящая, поставим в соответствие номер 0. Пусть - множество монет. Если — непересекающиеся непустые подмножества множества , то через обозначим операцию сравнения весов множества. При сравнении возможны три исхода, которые обозначим следующим образом: Дерево решений для задачи о фальшивой монете с четырьмя монетами.

Корень дерева на рисунке изображен полой окружностью и помечен отношением. Это означает, что алгоритм начинает работу сравнением весов монет с номерами 1 и 2.

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

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

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

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

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

Для получения такого, как на рис. Они же вместо этого разбиваются, соответственно, в отношении 2, 5, 2 и 4,1,4. Таким образом, заключаем, что задачу для четырех монет нельзя решить за два сравнения, не используя дополнительную настоящую монету. Наконец, рассмотрим те деревья решений, которые используют монету 0 в корне. В этом случае видно, что в корне фактически возможны только два сравнения: Для первого сравнения набор исходов будет 1, 7, 1 , в связи с чем все алгоритмы, начинающиеся таким способом, для нас непригодны.

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

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

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

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

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

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

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

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

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

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

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

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

В системе счисления с основанием каждое положительное целое число имеет единственное представление в виде конечной последовательности 2. На протяжении истории использовались различные значения Например, древние вавилоняне использовали а индейцы племени Майя — Сегодня наиболее широко используется - десятичная система, которую мы унаследовали от арабов, и - двоичная система, которая лежит в основе современных вычислительных устройств.

В действительности она применяется лишь на самом низком уровне аппаратного оборудования; в сложных вычислительных устройствах и базисных языках удобнее использовать или. Единственность этого представления можно доказать методом от противного. Числа и очевидно, имеют единственное представление. Предположим, что представление не единственно, и пусть будет наименьшим целым числом, имеющим два различных представления: Если то без потери общности предположим, что Тогда, поскольку и поскольку мы заключаем, что 2.

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

Преобразование числа в его представление в системе счисления с основанием. Он строит последовательность путем повторения деления на и записи остатков. Пусть на первом шаге при делении на остаток будет Частное, полученное в результате первого шага, делим на вновь полученное частное делим на и так далее.

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

Рассмотрим нашу систему измерения времени: Это - в точности смешанная система с. Представление целого в смешанной системе счисления осуществляется с помощью алгоритма 2, который является простым обобщением алгоритма 1. Вместо того, чтобы для получения в качестве делителя всегда использовалась в алгоритме 2 используется. Преобразование числа в его представление в смешанной системе счисления. Бесконечная последовательность формально определяется как функция областью определения которой является множество положительных целых чисел: Во многих случаях индексирование последовательности более удобно начинать с нуля; тогда областью определения будет множество целых неотрицательных чисел.

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

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

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

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

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

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

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

Например, характеристический вектор начального сегмента последовательности 2. Здесь основной последовательностью является последовательность целых положительных чисел.

В ЭВМ с разрядными словами для запоминания простых чисел, меньших , потребуется слов. Замечая далее, что для число не простое, можно сэкономить половину этого поля, выписывая разряды только для чисел видов и запоминая, что простое число 2 отсутствует.

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

Характеристические векторы полезны в ряде случаев. Их полезность вытекает из их компактности, существования простого фиксированного соотношения между и адресом -го разряда и возможности при таком представлении очень легко исключать элементы.

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

Если последовательности недостаточно плотные, то значительным может оказаться объем памяти. В случае простых чисел между и имеется простое соотношение: Теорема о простых числах утверждает, что число простых чисел, меньших приблизительно равно ; таким образом, простые числа относительно плотно распределены в множестве целых чисел. В лекции 11 даны примеры и программные реализации списков, стеков и очередей. Неудобство включения и исключения элементов при последовательном распределении происходит из-за того, что порядок следования элементов задается неявно требованием, чтобы смежные элементы последовательности находились в смежных ячейках памяти.

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

При связанном распределении последовательности связанном списке каждому поставлен в соответствии указатель ссылка , отмечающий ячейку, в которой записаны и. Существует также указатель , который указывает начальную ячейку последовательности, то есть ячейку с символами и.

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

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

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

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

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

Тривиальной модификацией связанного списка, изображенного на рис 3. Такая форма списка дает возможность достигнуть любой элемент из любого другого элемента последовательности.

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

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

Таким образом, элементы включаются в стек и исключаются из него в соответствии с правилом "Первым пришел - последним ушел ". Очередь - это последовательность, в которой все включения производятся на правом конце списка в конце очереди , в то время как все исключения производятся на левом конце в начале очереди.

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

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

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

Нужно описать алгоритм и его реализацию включения и исключения для очередей с приоритетом. Конечное корневое дерево формально определяется как непустое множество упорядоченных узлов, таких, что существует один выделенный узел, называемый корнем дерева , а оставшиеся узлы разбиты на поддеревьев. Будем рассматривать только корневые деревья. Узлы, не имеющие поддеревьев, называются листьями ; остальные узлы называются внутренними узлами. В первой лекции уже было использовано дерево - при изучении необходимого числа взвешиваний в задаче о фальшивой монете с монетами.

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

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

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

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

Каждая из вершин бинарного дерева может иметь 0, 1 или 2 поддерева, и существует различие между левым и правым поддеревьями. Почти все машинные представления деревьев основаны на связанных распределениях. Каждый узел состоит из поля и нескольких полей для указателей. Например, представление, которое будет удобным для изложения множества и мультимножества , для каждого узла имеет единственное поле для указателя , указывающего на отца данного узла.

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

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

Каждый узел в этом случае имеет три поля: Можно представлять деревья как бинарные, используя узлы фиксированного размера, представляя каждый узел леса в виде узла, состоящего из полей , ,.

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

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

Такой порядок особенно полезен в процедурах поиска. Прохождение снизу вверх, известное также как обратный порядок или концевой порядок, осуществляется согласно следующей рекурсивной процедуре:.

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

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

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

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

В связи с этим возникает потребность в количественных измерениях различных характеристик деревьев и, в частности, бинарных деревьев. Наиболее важные количественные характеристики деревьев связаны с уровнями узлов.

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

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

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

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

Сколько различных перестановок можно сделать из предметов первого типа, предметов второго типа, Число элементов в каждой перестановке равно. Поэтому если бы все элементы были различны, то число перестановок равнялось бы! Но из-за того, что некоторые элементы совпадают, получится меньшее число перестановок. В самом деле, возьмем, например, перестановку 5.

Элементы первого типа можно переставлять друг с другом! Но так как все эти элементы одинаковы, то такие перестановки ничего не меняют. Точно так же ничего не меняют! Перестановки элементов первого типа, второго типа и так далее можно делать независимо друг от друга. Поэтому элементы перестановки 5. То же самое верно и для любого другого расположения элементов.

Значит, число различных перестановок с повторениями, которые можно сделать из данных элементов, равно 5. Здесь у нас одна буква "м", четыре буквы "и", три буквы "с" и одна буква "п", а всего 9 букв. Значит, по формуле 5. Каждой перестановке соответствует распределение номеров мест на классов. В первый класс попадают номера тех мест, на которые попали предметы первого типа, во второй - номера мест предметов второго типа и так далее.

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

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

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

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

Вопрос о том, какой статистике подчиняются те или иные частицы, зависит от вида этих частиц. В классической статистической физике, созданной Максвеллом и Больцманом, частицы считаются различимыми друг от друга. Такой статистике подчиняются, например, молекулы газа. Известно, что различных частиц можно распределить по ячейкам способами. Если все эти способов при заданной энергии имеют равную вероятность, то говорят о статистике Максвелла-Больцмана.

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

Однако для многих частиц, например таких как электроны, протоны и нейтроны, не годится и статистика Бозе-Эйнштейна. Для них в каждой ячейке может находится не более одной частицы, причем различные распределения, удовлетворяющие указанному условию, имеют равную вероятность. В этом случае может быть различных распределений. Эта статистика называется статистикой Дирака-Ферми. С помощью леса можно представить перестановки из элементов множества множество мы определяем так: Подсчитаем, сколько можно получить перестановок.

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

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

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

Сколькими способами можно оплатить ее марками стоимостью 4, 6, и 10 рублей, если два способа, отличающиеся порядком марок, считаются различными запас марок различного достоинства считаем неограниченным? Обозначим через число способов, которыми можно наклеить марки в 4, 6 и 10 рублей так, чтобы общая стоимость этих марок равнялась Тогда для справедливо следующее соотношение: Тогда все остальные марки стоят рубля.

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

Поскольку любая комбинация оканчивается на марку одного из указанных типов, то по правилу суммы получаем соотношение 5. Но при малых значениях задачу легко решить непосредственно. Простой подсчет показывает, что Равенство означает, что сумму в 0 рублей можно уплатить единственным образом: А сумму в 1,2,3,5,7 и 9 рублей вообще никак нельзя получить с помощью марок стоимостью 4, 6 и 10 рублей.

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

Точно так же получаем значение а для имеем. Разобранная задача является частным случаем следующей общей задачи: Имеются марки достоинством в Сколькими способами можно оплатить с их помощью сумму в рублей, если два способа, отличающиеся порядком, считаются различными?

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

Обозначим число этих разбиений через На первом месте мы будем указывать число слагаемых, на втором - разбиваемое число и на последнем — ограничения на величину слагаемых.

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

Предположим, что сообщение передается с помощью сигналов нескольких типов. Длительность передачи сигнала первого типа равна второго типа - -го типа - единиц времени.

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

Обозначим число сообщений, которые можно передать за время через Рассуждая точно так же, как и в задаче о марках, получаем, что удовлетворяет соотношению 5. Не существует формального определения множества ; считается что это понятие первичное и не определяется.

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

Конечное множество будем записывать в следующем виде: Мощность множества обозначается как , для выписанного выше множества мощность записывается так. Если - конечное мультимножество, то будем записывать его в следующем виде: Здесь все различны и - кратность элемента. В этом случае мощность равна Наиболее общими операциями на множествах и мультимножествах являются операции объединения и пересечения. Для множеств эти операции будем обозначать и , а для мультимножеств - и.

Последовательное и связанное представление последовательностей можно использовать для множеств и мультимножеств очевидным способом. Индуцируя искусственный порядок элементов множества или используя собственный порядок, если он существует, можно рассматривать множество как последовательность.

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

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

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

Рассмотрим, например, множество разбитое на четыре непересекающихся подмножества 6. Если нам нужно найти подмножество, в котором содержится восьмерка, искомым ответом будет 7, то есть имя подмножества, содержащего восьмерку. Если нужно взять объединение подмножеств с именами 2 и 10, получим разбиение множества следующего вида: Именем множества может быть или 2, или Предполагаем, что вначале имеется разбиение множества на подмножеств, каждое из которых состоит из одного элемента 6.

Это разбиение преобразуется путем применения операций объединения вперемешку с операциями отыскания. Такая кажущаяся на первый взгляд надуманной задача чрезвычайно полезна в определенных комбинаторных алгоритмах; пример ее полезности виден в "жадном" алгоритме лекция Для реализации операций и объединения, и отыскания опишем процедуры операции и.

Процедура операция по именам двух различных подмножеств и образует новое подмножество, содержащее все элементы множеств и.

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

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

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

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

Поскольку каждое объединение уменьшает число подмножеств на единицу, последовательность операций может содержать не более объединений, откуда.

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

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

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

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

Число предметов, не обладающих ни одним из указанных свойств, обозначается по этому правилу через. Общий закон состоит в том, что 6. Одной из самых больших загадок математики является расположение простых чисел в ряду всех натуральных чисел. Иногда два простых числа идут через одно, например, 17 и 19, 29 и 31 , а иногда подряд идет миллион составных чисел. Сейчас ученые знают уже довольно много о том, сколько простых чисел содержится среди первых натуральных чисел.

В этих подсчетах весьма полезным оказался метод, восходящий еще к древнегреческому ученому Эратосфену. Он жил в третьем веке до новой эры в Александрии. Эратосфен занимался самыми различными вопросами - ему принадлежат интересные исследования в области математики, астрономии и других наук. Впрочем, такая разносторонность привела его к некоторой поверхностности. Современники несколько иронически называли Эратосфена "во всем второй": В математике Эратосфена интересовал как раз вопрос о том, как найти все простые числа среди натуральных чисел от 1 до.

Эратосфен считал 1 простым числом. Сейчас математики считают 1 числом особого вида, которое не относится ни к простым, ни к составным числам.

Он придумал для этого следующий способ. Сначала вычеркивают все числа, делящиеся на 2 исключая само число 2. Потом берут первое из оставшихся чисел а именно 3. Ясно, что это число - простое. Вычеркивают все идущие после него числа, делящиеся на 3.

Первым оставшимся числом будет 5. Вычеркивают все идущие после него числа, делящиеся на 5, и т. Числа, которые уцелеют после всех вычеркиваний, и являются простыми. Так как во времена Эратосфена писали на восковых табличках и не вычеркивали, а "выкалывали" цифры, то табличка после описанного процесса напоминала решето.

Поэтому метод Эратосфена для нахождения простых чисел получил название " решето Эратосфена ". Подсчитаем, сколько останется чисел в первой сотне, если мы вычеркнем по методу Эратосфена числа, делящиеся на 2, 3 и 5. Иными словами, поставим такой вопрос: Эта задача решается по формуле включения и исключения. Обозначим через свойство числа делиться на 2, через - свойство делимости на 3 и через - свойство делимости на 5.

Тогда означает, что число делится на 6, означает, что оно делится на 10, и - оно делится на Наконец, означает, что число делится на Надо найти, сколько чисел от 1 до не делится ни на 2, ни на 3, ни на 5, то есть не обладает ни одним из свойств , ,. Поэтому и значит, Таким образом, 26 числа от 1 до не делятся ни на 2, ни на 3, ни на 5. Эти числа и уцелеют после первых трех шагов процесса Эратосфена. Кроме них останутся сами числа 2, 3 и 5.

Всего останется 35 чисел. А из первой тысячи после первых трех шагов процесса Эратосфена останется чисел. Это следует из того, что в этом случае. Сколько из них можно составить -расстановок? При этом две расстановки считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке.

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

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

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

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

Но из каждого - сочетания можно сделать! Значит справедлива формула Из этой формулы находим, что. При решении многих комбинаторных задач пользуются методом сведения данной задачи к задаче, касающейся меньшего числа предметов. Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений от латинского "recurrere" - "возвращаться". Понятие рекуррентных соотношений проиллюстрируем классической проблемой, которая была поставлена около года Леонардо из Пизы, известным как Фибоначчи.

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

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

Таким образом, в очередном месяце произойдут следующие события: Старая популяция в -й момент увеличится на число родившихся в момент времени. Каждая старая пара в момент времени производит пару приплода в момент времени. В последующий месяц эта картина повторяется: Объединяя эти равенства, получим следующее рекуррентное соотношение: Выбор начальных условий для последовательности чисел Фибоначчи не важен; существенное свойство этой последовательности определяется рекуррентным соотношением.

Пара кроликов приносит раз в месяц приплод из двух крольчат самки и самца , причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов?

Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. А еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад.

Поэтому всего будет 5 пар кроликов. Обозначим через количество пар кроликов по истечении месяцев с начала года.