Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны. Задачи дискретной математики, к которым относится большинство олимпиадных задач по информатике, часто сводятся к перебору различных комбинаторных конфигураций объектов и выбору среди них наилучшего, с точки зрения условия той или иной задачи. Поэтому знание алгоритмов генерации наиболее распространенных комбинаторных конфигураций является необходимым условием успешного решения олимпиадных задач в целом. Важно также знать количество различных вариантов для каждого типа комбинаторных конфигураций, так как это позволяет реально оценить вычислительную трудоемкость выбранного алгоритма решения той или иной задачи. Наблюдаемые нами события явления можно подразделить на следующие три вида: Достоверным называют событие, которое обязательно произойдет, если будет осуществлена определенная совокупность условий S. В этом примере заданные атмосферное давление и температура воды составляют совокупность условий S. Невозможным называют событие, которое заведомо не произойдет, если будет осуществлена совокупность условий S. Случайным называют событие, которое при осуществлении совокупности условий S может либо произойти, либо не произойти. Например, если брошена монета, то она может упасть так, что сверху будет либо герб, либо надпись. Невозможно учесть влияние на результат всех этих причин, поскольку число их очень велико и законы их действия неизвестны. Поэтому теория вероятностей не ставит перед собой задачу предсказать, произойдет единичное событие или нет, -- она просто не в силах это сделать. По-иному обстоит дело, если рассматриваются случайные события, которые могут многократно наблюдаться при осуществлении одних и тех же условий S, т. Оказывается, что достаточно большое число однородных случайных событий независимо от их конкретной природы подчиняется определенным закономерностям, а именно вероятностным закономерностям. Установлением этих закономерностей и занимается теория вероятностей. Итак, предметом теории вероятностей является изучение вероятностных закономерностей массовых однородных случайных событий. Знание закономерностей, которым подчиняются массовые случайные события, позволяет предвидеть, как эти события будут протекать. При этом предполагается, конечно, что монету бросают в одних и тех же условиях. Методы теории вероятностей широко применяются в различных отраслях естествознания и техники: Теория вероятностей служит также для обоснования математической и прикладной статистики, которая в свою очередь используется при планировании и организации производства, при анализе технологических процессов, предупредительном и приемочном контроле качества продукции и для многих других целей. В последние годы методы теории вероятностей все шире и шире проникают в различные области науки и техники, способствуя их прогрессу. Первые работы, в которых зарождались основные понятия теории вероятностей, представляли собой попытки создания теории азартных игр Кардано, Гюйгенс, Паскаль, Ферма и другие в XVI--XVII вв. Следующий этап развития теории вероятностей связан с именем Якоба Бернулли Дальнейшими успехами теория вероятностей обязана Муавру, Лапласу, Гауссу, Пуассону и др. Новый, наиболее плодотворный период связан с именами П. Чебышева и его учеников А. Маркова и А. В этот период теория вероятностей становится стройной математической наукой. Ее последующее развитие обязано в первую очередь русским и советским математикам С. В настоящее время ведущая роль в создании новых ветвей теории вероятностей также принадлежит советским математикам. Основными и типичными операциями и связанными с ними задачами комбинаторики являются следующие:. Число n называют порядом магического квадрата. Уже в средние века был известен алгоритм построения магических квадратов нечетного порядка. В Индии и некоторых других странах магические квадраты употреблялись как талисманы. Однако общей теории магических квадратов не существует. Неизвестно даже общее число магических квадратов порядка n. Латинский квадрат - квадратная матрица порядка n, каждая строка и каждый столбец которой являются перестановками элементов конечного множества S, состоящего из n элементов. Задача размещения - одна из классических комбинаторных задач, в которой требуется определить число способов размещения m различных предметов в n различных ячейках с заданным числом r пустых ячеек. Задача коммивояжера , задача о бродячем торговце - комбинаторная задача теории графов. В простейшем случае формулируется следующим образом: В каком порядке должен он посещать города по одному разу каждый чтобы общее пройденное расстояние было минимальным? Методы решения задачи коммивояжера, по существу, сводятся к организации полного перебора вариантов. Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с n предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, которое называется рекуррентным. Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов решение задачи легко находится. Пусть N A - число элементов множества A. Тогда методом математической индукции можно доказать, что. П An-1 П An. Метод подсчета числа элементов объединения множеств по этой формуле, состоящий в поочередном сложении и вычитании, называется методом включения и исключения. Для многих комбинаторных задач можно указать такую геометрическую интерпретацию, которая сводит задачу к подсчету числа путей траекторий , обладающих определенным свойством. Комбинаторика изучает количества комбинаций, подчиненных определенным условиям, которые можно составить из элементов, безразлично какой природы, заданного конечного множества. При непосредственном вычислении вероятностей часто используют формулы комбинаторики. Приведем наиболее употребительные из них. Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок. Размещениями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком. Число всех возможных размещений. Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом. Выше предполагалось, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам. Например, если среди n элементов есть n 1 элементов одного вида, n 2 элементов другого вида и т. Если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов А, В в указанном порядке может быть выбрана mn способами. Произведением двух событий А и В называют событие АВ, состоящее в совместном появлении совмещении этих событий. Например, если А -- деталь годная, В -- деталь окрашенная, то АВ -- деталь годна и окрашена. Произведением нескольких событий называют событие, состоящее в совместном появлении всех этих событий. Во введении случайное событие определено как событие, которое при осуществлении совокупности условий S может произойти или не произойти. Если при вычислении вероятности события никаких других ограничений, кроме условий S, не налагается, то такую вероятность называют безусловной ; если же налагаются и другие дополнительные условия, то вероятность события называют условной. Например, часто вычисляют вероятность события В при дополнительном условии, что произошло событие А. Заметим, что и безусловная вероятность, строго говоря, является условной, поскольку предполагается осуществление условий S. Условной вероятностью Р A В называют вероятность события В, вычисленную в предположении, что событие А уже наступило. Это обстоятельство и служит основанием для следующего общего применимого не только для классической вероятности определения. Условная вероятность события В при условии, что событие А уже наступило, по определению, равна. А и В; пусть вероятности Р А и Р A В известны. Как найти вероятность совмещения этих событий, т. Ответ на этот вопрос дает теорема умножения. Суммой нескольких событий называют событие, которое состоит в появлении хотя бы одного из этих событий. Пусть события A и В -- несовместные, причем вероятности этих событий известны. Как найти вероятность того, что наступит либо событие A, либо событие В? Ответ на этот вопрос дает теорема сложения. Вероятность появления одного из двух несовместных событий, безразлично какого, равна сумме вероятностей этих событий: Вероятность появления одного из нескольких попарно несовместных событий, безразлично какого, равна сумме вероятностей этих событий: Перечисленные подзадачи в программировании обычно рассматривают для следующих комбинаторных конфигураций: Большинство указанных конфигураций были подробно рассмотрены в []. Однако при генерации различных конфигураций использовались в основном нерекурсивные алгоритмы. Опытные же участники олимпиад в подобных случаях при программировании используют в основном именно рекурсию, с помощью которой решение рассматриваемых задач зачастую можно записать более кратко и прозрачно. Поэтому для полноты изложения данной темы приведем ряд рекурсивных комбинаторных алгоритмов и рассмотрим особенности применения рекурсии в комбинаторике. Московские олимпиады по программированию. Еще раз о задачах на полный перебор вариантов. Предмет, постановка и особенности задач дискретного программирования. Задачи с неделимостями и с разрывными целевыми функциями. Примеры решений задач дискретного программирования методом ветвей и границ, методом Гомори. Исследование методов решения задачи о ходе коня. Описание алгоритмов для итеративной и рекурсивной программ. Генерация перестановок элементов по индексам. Построение эйлерова цикла на графе. Поиск кратчайшего пути на графе. Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов. Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения. Решение задач по информатике, перебор различных комбинаторных конфигураций объектов и выбор наилучшего, с точки зрения условия задачи. Генерация k-элементных подмножеств, всех подмножеств данного множества, всех перестановок n-элементного множества. Краткая историческая справка и описание современной версии системы. Основные возможности современной версии MathCad, ее интерфейс. Ввод и редактирование выражений. Средства повышения эффективности вычислений и их оптимизация. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Элементарные подзадачи, на решение которых опираются решения задач вычислительной геометрии. Основные формулы и алгоритмы. Олимпиадные задачи, связанные с геометрическими понятиями. Подробные численные решения геометрических разных задач с пояснениями. Задачи, решаемые методом динамического программирования. Основные этапы нахождения деревянного алгоритма решения задачи. Решение задач средствами Excel. Алгоритм основной программы - Derevo. Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса. Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т. PPT, PPTX и PDF-файлы представлены только в архивах. Главная Библиотека "Revolution" Программирование, компьютеры и кибернетика Основные комбинаторные задачи. Предмет комбинаторики теории вероятностей , как отрасли программирования. Краткая историческая справка о ее зарождении и развитии. Комбинаторные задачи, варианты и способы их решения. Основные формулы комбинаторики, правила произведений и суммы. Краткая историческая справка 3. Основные комбинаторные задачи 4. Основные формулы комбинаторики 5. Предмет комбинаторики Наблюдаемые нами события явления можно подразделить на следующие три вида: Краткая историческая справка Первые работы, в которых зарождались основные понятия теории вероятностей, представляли собой попытки создания теории азартных игр Кардано, Гюйгенс, Паскаль, Ферма и другие в XVI--XVII вв. Основные комбинаторные задачи Основными и типичными операциями и связанными с ними задачами комбинаторики являются следующие: Метод включения и исключения. Тогда методом математической индукции можно доказать, что N A1 U A2 U Основные формулы комбинаторики Комбинаторика изучает количества комбинаций, подчиненных определенным условиям, которые можно составить из элементов, безразлично какой природы, заданного конечного множества. Заметим, что удобно рассматривать 0! Правило произведения Если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов А, В в указанном порядке может быть выбрана mn способами. Обзор задач дискретного программирования. Специальные задачи линейного программирования. Решение задач линейного программирования. Способы программирования и возможности в программе MathCAD. Решение задачи линейного программирования графическим методом. Геометрические задачи на олимпиадах по информатике. Деревянный алгоритм решения задачи коммивояжёра. Другие документы, подобные "Основные комбинаторные задачи".
Комбинаторная математика является старой дисциплиной. Она получила свое наименование в г. Комбинаторные алгоритмы с их акцентом на разработку, анализ и реализацию практических алгоритмов являются продуктом века вычислительных машин. Предмет теории комбинаторных алгоритмов - вычисления на дискретных математических структурах. Это новое направление исследований. Лишь в последние несколько лет из наборов искусных приемов и разрозненных алгоритмов сформировалась система знаний о разработке, реализации и анализе алгоритмов. Комбинаторные вычисления находятся в таком же отношении к комбинаторной математике дискретной, конечной математике , как численные методы анализа - к анализу. Комбинаторные вычисления развиваются в следующем направлении:. В отличие от некоторых других разделов математики, комбинаторные вычисления не имеют "ядра", то есть некоторого количества "фундаментальных теорем", составляющих суть предмета, из которых выводится большинство результатов. Сначала может показаться, что в целом эта область состоит из наборов специальных методов и хитрых приемов. Однако после того, как было исследовано достаточно много комбинаторных алгоритмов, стали вырисовываться некоторые общие принципы. Именно эти принципы делают комбинаторные вычисления связной областью знаний и позволяют изложить ее в систематизированном виде. Чрезвычайно важной проблемой в комбинаторных вычислениях является задача эффективного представления объектов, подлежащих обработке. Она возникает потому, что обычно имеется много возможных способов представления сложных объектов более простыми структурами, которые можно заложить в языки программирования, но не все такие представления в одинаковой степени эффективны с точки зрения времени и памяти. Более того, идеальное представление зависит от вида производимых операций. Приведем примеры, в которых задаются весьма специфические операции над целыми. Целые определяются как данные простейшего типа почти во всех вычислительных устройствах и языках программирования. Таким образом, проблема представления, как правило, не возникает. Имеющееся представление почти всегда наилучшее. Однако существуют некоторые заслуживающие внимания исключения, когда выгодно или даже необходимо использовать представление целых в вычислительном устройстве иным способом. Эти исключения появляются в следующих случаях:. Проблемы кодов, сохраняющих разности, касаются случаев 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 пар кроликов. Обозначим через количество пар кроликов по истечении месяцев с начала года. Ясно, что через месяцев будут эти пар и еще столько новорожденных пар кроликов, сколько было в конце месяца , то есть еще пар кроликов. Иными словами, имеет место рекуррентное соотношение 7. Числа называются числами Фибоначчи. Они обладают целым рядом замечательных свойств. Теперь выведем выражение этих чисел через. Для этого установим связь между числами Фибоначчи и следующей комбинаторной задачей. Найти число последовательностей,состоящих из нулей и единиц, в которых никакие две единицы не идут подряд. Чтобы установить эту связь, возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: Например, последовательность устанавливает такую "генеалогию": Исходная пара кроликов тогда зашифровывается последовательностью Ясно, что при этом ни в одной последовательности не могут стоять две единицы подряд - только что появившаяся пара не может, по условию, принести приплод через месяц. Кроме того, при указанном правиле различным последовательностям отвечают различные пары кроликов, и обратно, две различные пары кроликов всегда имеют разную "генеалогию", так как, по условию, крольчиха дает приплод, состоящий только из одной пары кроликов. Установленная связь показывает, что число -последовательностей, обладающих указанным свойством, равно. Докажем теперь, что 7. Иными словами, - целая часть числа в дальнейшем будем обозначать целую часть числа через ; таким образом,. В самом деле, - это число всех - последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число же таких последовательностей, в которые входит ровно единиц и нулей, равно. Так как при этом должно выполняться неравенство , то изменяется от 0 до. Применяя правило суммы, приходим к соотношению 7. Из равенства легко следует, что 7. Так как обе последовательности и удовлетворяют рекуррентному соотношению , то имеем и, вообще,. В предыдущем разделе непосредственно установлена связь между задачей Фибоначчи и комбинаторной задачей. Эту связь можно установить и иначе, непосредственно доказав, что число решений комбинаторной задачи удовлетворяет тому же рекуррентному соотношению 7. В самом деле, возьмем любую -последовательность нулей и единиц, удовлетворяющую условию, что никакие две единицы не идут подряд. Она может оканчиваться или на 0, или на 1. Если она оканчивается на 0, то, отбросив его, получим -последовательность, удовлетворяющую нашему условию. Если взять любую - последовательность нулей и единиц, в которой подряд не идут две единицы, и приписать к ней нуль, то получим -последовательность с тем же свойством. Таким образом доказано, что число последовательностей, оканчивающихся на нуль, равно. Пусть теперь последовательность оканчивается на 1. Так как двух единиц подряд быть не может, то перед этой единицей стоит нуль. Иными словами, последовательность оканчивается на Остающаяся же после отбрасывания 0 и 1 -последовательность может быть любой, лишь бы в ней не шли подряд две единицы. Поэтому число последовательностей, оканчивающихся единицей, равно. Но каждая последовательность оканчивается или на 0, или на 1. В силу правила суммы получаем, что. Таким образом, получено то же самое рекуррентное соотношение. Отсюда еще не вытекает, что числа и совпадают. Для решения комбинаторных задач часто применяют метод, использованный в предыдущем пункте: Если при этом совпадают и начальные члены последовательностей в достаточном числе, то обе задачи имеют одинаковые решения. Пусть дано некоторое множество из предметов, стоящих в определенном порядке. Разобьем это множество на две непустые части так, чтобы одна из этих частей лежала левее второй то есть, скажем, одна часть состоит из элементов от первого до - го, а вторая - из элементов от -го до -го. После этого каждую из частей таким же образом разобьем на две непустые части если одна из частей состоит уже из одного предмета, она не подвергается дальнейшим разбиениям. Этот процесс продолжается до тех пор, пока не получим части, состоящие из одного предмета каждая. Сколько существует таких процессов разбиения два процесса считаются различными, если хотя бы на одном шагу они приводят к разным результатам? Обозначим число способов разбиения для множества из предметов через. На первом шагу это множество может быть разбито способами первая часть может содержать один предмет, два предмета,…, предметов. В соответствии с этим множество всех процессов разбиений распадается на классов - в - класс входят процессы, при которых первая часть состоит из предметов. Подсчитаем число процессов в -м классе. В первой части содержится элементов. Поэтому ее можно разбивать далее различными процессами. Вторая же часть содержит элементов, и ее можно разбивать далее процессами. По правилу произведения получаем, что - класс состоит из различных процессов. По правилу суммы отсюда вытекает, что 7. Двоичный поиск, поиск делением пополам. Поиском по числам Фибоначчи называется поиск, основанный на том, что область поиска делится в точках, являющихся числами Фибоначчи. Бывают комбинаторные задачи, в которых приходится составлять не одно рекуррентное соотношение, а систему соотношений, связывающую несколько последовательностей. Эти соотношения выражают -у члены последовательностей через предыдущие члены не только данной, но и остальных последовательностей. Однажды мажордом короля Артура обнаружил, что к обеду за круглым столом приглашено 6 пар враждующих рыцарей. Сколькими способами можно рассадить их так, чтобы никакие два врага не сидели рядом? Если мы найдем какой-то способ рассадки рыцарей, то, пересаживая их по кругу, получим еще 11 способов. Мы не будем сейчас считать различными способы, получающиеся друг из друга такой циклической пересадкой. Пусть число рыцарей равно. Через обозначим число способов рассадки, при которых никакие два врага не сидят рядом. Через обозначим число способов, при которых рядом сидит ровно одна пара врагов, и через - число способов, при которых есть ровно две пары враждующих соседей. Выведем сначала формулу, выражающую через. Пусть пар рыцарей посажены так, что никакие два врага не сидят рядом. Мы будем считать, что все враждующие пары рыцарей занумерованы. Попросим встать из-за стола пару рыцарей с номером. Тогда возможны три случая: При последующие рассуждения теряют силу. Выясним теперь, сколькими способами можно снова посадить ушедших рыцарей за стол так, чтобы после этого не было одной пары соседей-врагов. Проще всего посадить их, если за столом рядом сидят две пары врагов. В этом случае один из вновь пришедших садится между рыцарями первой пары, а другой — между рыцарями второй пары. Это можно сделать двумя способами. Но так как число способов рассадки рыцарей, при которых две пары соседей оказались врагами, равно , то всего получилось способов. Пусть теперь рядом сидит только одна пара врагов. Один из вернувшихся должен сесть между ними. Тогда за столом окажутся рыцарей, между которыми есть мест. Из них два места - рядом с только что севшим гостем — запретны для второго рыцаря, и ему остается мест. Так как первым может войти любой из двух вышедших рыцарей, то получается способов рассадки. Но число случаев, когда рыцарей сели так, чтобы ровно одна пара врагов оказалась соседями, ровно. Поэтому мы получаем способов посадить гостей требуемым образом. Наконец, пусть никакие два врага не сидели рядом. В этом случае первый рыцарь садится между любыми двумя гостями - это он может сделать способами. После этого для его врага останется мест - он может занять любое место, кроме двух мест, соседних с только что севшим рыцарем. Таким образом, если рыцарей уже сидели нужным образом, то вернувшихся гостей можно посадить способами. Как уже отмечалось, разработанными случаями исчерпываются все возможности. Поэтому имеет место рекуррентное соотношение 7. Этого соотношения пока недостаточно, чтобы найти для всех значений. Надо еще узнать, как выражаются через. Предположим, что среди рыцарей оказалась ровно одна пара врагов-соседей. Мы знаем, что это может произойти в случаях. Во избежание ссоры попросим их удалиться из-за стола. Тогда останется рыцарей, причем возможно одно из двух: Во втором случае ушедших можно посадить обратно только на старое место - иначе появится вторая пара враждующих соседей. Но так как рыцарей можно посадить способами так, чтобы была только одна пара враждующих соседей, то мы получаем вариантов возвратившихся рыцарей можно поменять местами. В первом же случае можно посадить ушедших между любыми двумя рыцарями, то есть способами, а так как их еще можно поменять местами, то получится способов. Комбинируя их со всеми способами посадки пар рыцарей, при которых нет соседей врагов, получаем способов. Наконец, номер ушедшей и вернувшейся пары рыцарей мог быть любым от 1 до. Отсюда вытекает, что рекуррентное соотношение для имеет вид 7. Наконец, разберем случай, когда среди рыцарей было две пары врагов-соседей. Номера этих пар можно выбрать способами. Заменим каждую пару одним новым рыцарем, причем будем считать новых двух рыцарей врагами. Тогда за столом будут сидеть рыцарей, причем среди них либо не будет ни одной пары врагов-соседей если новые рыцари не сидят рядом , либо только одна такая пара. Первый вариант может быть в случаях. Вернуться к исходной компании мы можем 4 способами благодаря возможности изменить порядок рыцарей в каждой паре. Поэтому первый вариант приводит к способами. Второй же вариант может быть в случаях. Имеется случаев, когда какая-нибудь пара врагов сидит рядом. Если указать, какая именно пара должна сидеть рядом, получим в раз меньше случаев. Здесь тоже можно вернуться к исходной компании 4 способами, и мы получаем всего способов. Отсюда вытекает, что при 7. Но простой подсчет показывает, что. Поэтому из соотношений 7. Продолжая далее, находим, что гостей можно посадить за стол требуемым образом способами. Будем говорить, что рекуррентное соотношение имеет порядок , если оно позволяет выразить через. Например, рекуррентное соотношение второго порядка, а - рекуррентное соотношение третьего порядка. Если задано рекуррентное соотношение -го порядка, то ему удовлетворяет бесконечно много последовательностей. Дело в том, что первые элементов последовательности можно задать совершенно произвольно - между ними нет никаких соотношений. Но если первые элементов заданы, то все остальные элементы определяются совершенно однозначно - элемент выражается в силу рекуррентного соотношения через элемент - через и т. Пользуясь рекуррентным соотношением и начальными членами, можно один за другим выписывать члены последовательности, причем рано или поздно получим любой ее член. Однако при этом придется выписать и все предыдущие члены - ведь не узнав их, мы не узнаем и последующих членов. Но во многих случаях нужно узнать только один определенный член последовательности, а остальные не нужны. В этих случаях удобнее иметь явную формулу для -го члена последовательности. Некоторая последовательность является решением данного рекуррентного соотношения , если при подстановке этой последовательности соотношение тождественно выполняется. Например, последовательность является одним из решений рекуррентного соотношения В самом деле, общий член этой последовательности имеет вид. Но при любом имеет место тождество. Поэтому является решением указанного соотношения. Решение рекуррентного соотношения -го порядка называется общим , если оно зависит от произвольных постоянных и путем подбора этих постоянных можно получить любое решение данного соотношения. Например, для соотношения 8. Поэтому нам надо только показать, что любое решение нашего соотношения можно представить в виде 8. Но любое решение соотношения 8. Поэтому нам надо доказать, что для любых чисел и найдутся такие значения и , что и Но легко видеть, что при любых значениях и система уравнений имеет решение. Для решения рекуррентных соотношений общих правил, вообще говоря, нет. Однако существует весьма часто встречающийся класс соотношений, решаемый единообразным методом. Это - рекуррентные соотношения вида 8. Такие соотношения называют линейными рекуррентными соотношениями с постоянными коэффициентами. Сначала рассмотрим, как решаются такие соотношения при , то есть изучим соотношение вида 8. В самом деле, по условию, имеем. Умножим эти равенства на и соответственно и сложим полученные тождества. Получим, что А это означает, что является решением соотношения 8. Подставляя эти значения в соотношение 8. Заметим, что наряду с последовательностью любая последовательность вида также является решением соотношения 8. Для доказательства достаточно использовать утверждение 8. Из утверждений 1 и 2 вытекает следующее правило решения линейных рекуррентных соотношений второго порядка с постоянными коэффициентами. Пусть дано рекуррентное соотношение 8. Если это уравнение имеет два различных корня , то общее решение соотношения 8. Чтобы доказать это правило, заметим сначала, что по утверждению 2 являются решениями нашего соотношения. А тогда по утверждению 1 и является его решением. Надо только показать, что любое решение соотношения 8. Но любое решение соотношения второго порядка определяется значениями. Поэтому достаточно показать, что система уравнений имеет решение при любых. Этими решениями являются Случай, когда оба корня уравнения 8. При изучении чисел Фибоначчи мы пришли к рекуррентному соотношению 8. Мы называли числами Фибоначчи решения соотношения 8. Часто бывает более удобно добавить к этой последовательности вначале числа 0 и 1, то есть рассматривать последовательность. Ясно, что эта последовательность удовлетворяет тому же самому рекуррентному соотношению 8. Полагая в формуле 8. Рассмотрим случай, когда оба корня характеристического уравнения совпадают: В этом случае выражение уже не будет общим решением. Ведь из-за того, что , это решение можно записать в виде Остается только одно произвольное постоянное ; и выбрать его так, чтобы удовлетворить двум начальным условиям , вообще говоря, невозможно. Поэтому надо найти какое-нибудь второе решение, отличное от. В самом деле, если квадратное уравнение имеет два совпадающих корня , то по теореме Виета. Поэтому уравнение записывается так: А тогда рекуррентное соотношение имеет такой вид: Значит, - решение рассматриваемого соотношения. Итак, имеются два решения и заданного соотношения. Его общее решение запишется так: Теперь уже путем подбора можно удовлетворить любым начальным условиям. Линейные рекуррентные соотношения с постоянными коэффициентами , порядок которых больше двух, решаются таким же способом. Пусть соотношение имеет вид 8. В общем решении этому корню соответствует часть. Составляя такое выражение для всех корней и складывая их, получаем общее решение соотношения 8. Например, решим рекуррентное соотношение Характеристическое уравнение в этом случае имеет вид Решая его, получим корни Значит, общее решение нашего соотношения имеет следующий вид: В комбинаторных задачах на подсчет числа объектов при наличии некоторых ограничений искомым решением часто является последовательность , где - число искомых объектов "размерности". Например, если мы ищем число разбиений числа, то можем принять , если ищем число подмножеств -элементного множества, то и т. В этом случае удобно последовательности , поставить в соответствие формальный ряд 8. Название формальный ряд для данной последовательности означает, что 8. Поэтому мы никогда не будем вычислять значение такого ряда для конкретного значения переменной , мы будем только выполнять некоторые операции на таких рядах, а затем определять коэффициенты при отдельных степенях переменной. Для произвольных рядов мы определим операцию сложения: Из математического анализа известно, что если ряд 8. Более того, когда являются аналитическими функциями в окрестности нуля, то формулы 8. Это сохраняющее операции взаимно однозначное соответствие между рядами, сходящимися в окрестности нуля, и функциями, аналитическими в окрестности нуля, позволяет отождествить формальный ряд 8. Таким образом, будем писать, например, и т. Метод рекуррентных соотношений позволяет решать многие комбинаторные задачи. Но в целом ряде случаев рекуррентные соотношения довольно трудно составить, а еще труднее решить. Зачастую эти трудности удается обойти, использовав производящие функции. Поскольку понятие производящей функции связано с бесконечными степенными рядами , познакомимся с этими рядами. Если заданы два многочлена и , то всегда существуют многочлены частное и остаток , такие, что , причем степень меньше степени или. При этом называется делимым , а - делителем. Если же мы хотим, чтобы деление выполнялось без остатка, то придется допустить в качестве частного не только многочлены, но и бесконечные степенные ряды. Для получения частного надо расположить многочлены по возрастающим степеням и делить "углом", начиная с младших членов. Рассмотрим, например, деление на Ясно, что процесс деления никогда не закончится так же, например, как при обращении числа в бесконечную десятичную дробь. С помощью индукции легко убедиться, что все коэффициенты частного равны единице. Поэтому в качестве частного получается бесконечный ряд. Вообще, если и - два многочлена причем свободный член многочлена отличен от нуля, , то при делении на получается бесконечный ряд 9. Лишь в случае, когда делится без остатка на , ряд 9. При делении многочлена на многочлен мы получаем бесконечный степенной ряд. Чтобы выяснить это, попробуем подставлять в обе части соотношения 9. Тогда левая часть соотношения примет значение , а правая превратится в бесконечный числовой ряд. Так как мы не умеем складывать бесконечно много слагаемых, попробуем взять сначала одно слагаемое, потом - два, потом - три и так далее слагаемых. Мы получим такие суммы: Ясно, что с возрастанием эти суммы приближаются к значению , которое приняла левая часть соотношения 9. То же самое получится, если вместо подставить в обе части 9. Левая часть равенства примет значение 2, а правая превратится в бесконечный числовой ряд Беря последовательно одно, два, три, четыре, слагаемых, мы получим числа 1; ; ; ,…,. Ясно, что с возрастанием эти числа стремятся к числу 2. Однако, если взять , то левая часть 9. Мы встретились, таким образом, с двумя случаями. Чтобы их различать, введем общее понятие о сходимости и расходимости числового ряда. Пусть задан бесконечный числовой ряд 9. Иными словами, какое бы число мы ни указали, отклонение суммы от , начиная с некоторого номера , окажется меньше: В этом случае число называют суммой бесконечного ряда и пишут Если не существует числа , к которому сходится данный ряд 9. Проведенное выше исследование показывает, что в то время как ряд Более тщательное исследование показывает, что если , то ряд сходится к , а если , то он расходится. Чтобы доказать это утверждение, достаточно заметить, что и что при выражение стремится к нулю, если , и к бесконечности, если. При получаем расходящиеся числовые ряды и. Итак, если , то 9. Отметим, что равенство 9. Мы выяснили, таким образом, смысл записи Она показывает, что для значений , лежащих в некоторой области, а именно при , стоящий справа ряд сходится к. Говорят, что функция при разлагается в степенной ряд. Теперь уже можно выяснить и более общий вопрос. Пусть при делении многочлена на многочлен получился степенной ряд 9. Размеры области сходимости зависят от корней знаменателя, то есть чисел, при которых знаменатель обращается в нуль. Именно, если эти числа равны и - наименьшее из чисел , то ряд сходится в области. Иными словами, всегда есть область , в которой выполняется равенство 9. В математическом анализе доказывают, например, что Отметим еще следующее важное утверждение: Перейдем теперь к действиям над степенными рядами. Пусть функции и разложены в степенные ряды 9. Это утверждение совсем не так очевидно, как кажется на первый взгляд. Ведь в правой части равенства у нас бесконечные суммы, а в бесконечных суммах переставлять слагаемые можно далеко не всегда. После этой перегруппировки мы получим 9. Посмотрим теперь, как разлагается в степенной ряд произведение функций и. Мы опускаем доказательство этого утверждения. Найдем ряд, получающийся после почленного перемножения. Свободный член этого ряда равен. Члены, содержащие , получатся дважды: Они дают Точно так же вычисляются члены, содержащие. В частности, возводя ряд 9. Посмотрим теперь, как делят друг на друга степенные ряды. Пусть свободный член ряда 9. Покажем, что в этом случае существует такой степенной ряд 9. Для того чтобы этот ряд совпадал с рядом 9. Подставим полученное значение во второе уравнение. Мы получим уравнение из которого находим, что. Вообще, если уже найдены коэффициенты , то для отыскания имеем уравнение Это уравнение разрешимо, поскольку. Итак, мы доказали существование ряда 9. Можно доказать, что он получается при разложении функции. Таким образом, степенные ряды можно складывать, умножать и делить последнее - при условии, что свободный член делителя отличается от нуля. Эти действия соответствуют действиям над разлагаемыми функциями. С помощью степенных рядов можно доказывать многие тождества. Для этого берут некоторую функцию и двумя способами разлагают ее в степенной ряд. Поскольку функция может быть представлена лишь единственным образом в виде степенного ряда, то коэффициенты при одинаковых степенях в обоих рядах должны совпадать. Это и приводит к доказываемому тождеству. Рассмотрим, например, известное нам разложение. Возведя обе части этого разложения в квадрат, получаем Очевидно, что коэффициенты при нечетных степенях обращаются в нуль, каждое слагаемое дважды входит в эти коэффициенты с противоположными знаками. Коэффициент же равен Но функцию можно разложить в степенной ряд и иным образом. Мы имеем А разложение для получается из разложения Поэтому коэффициент при разложении Отсюда вытекает следующее тождество: Пусть дана некоторая последовательность чисел. Образуем степенной ряд Если этот ряд сходится в какой-то области к функции , то эту функцию называют производящей для последовательности чисел Например, из формулы вытекает, что функция является производящей для последовательности чисел. Нас будут интересовать производящие функции для последовательностей , так или иначе связанных с комбинаторными задачами. С помощью таких функций удается получить самые разные свойства этих последовательностей. Кроме того, мы рассмотрим, как связаны производящие функции с решением рекуррентных соотношений. Получим производящую функцию для конечной последовательности чисел. Известно, что и Эти равенства являются частными случаями более общей формулы, дающей разложение для. Запишем в виде Например, запишем в виде То же самое и в общем случае — после раскрытия скобок в формуле Подобными будут члены, содержащие одинаковое количество букв тогда и букв в них будет поровну. Найдем, сколько будет членов, в которые входит букв и, следовательно, букв. Эти члены являются перестановками с повторениями, составленными из букв и букв. Поэтому их число равно Отсюда вытекает, что после приведения подобных членов выражение войдет с коэффициентом. Итак, мы доказали, что Если положить в этом равенстве , то получим С помощью этой производящей функции можно сравнительно просто доказать многие свойства чисел. Мы назвали, как это обычно делают, формулу биномом Ньютона. Это наименование с точки зрения истории математики неверно. Формулу для хорошо знали среднеазиатские математики Омар Хайям, Гиясэдди и другие. В Западной Европе задолго до Ньютона она была известна Блэзу Паскалю. Заслуга же Ньютона была в ином - ему удалось обобщить формулу на случай нецелых показателей. Именно, он доказал, что если - положительное число и , то для любого действительного значения имеет место равенство В случае, когда - натуральное число, обращается в нуль. Но эта скобка входит в коэффициент всех членов, начиная с -го, и потому все эти члены разложения равны нулю. Поэтому при натуральном ряд Теория производящих функций тесно связана с рекуррентными соотношениями. Вернемся снова к делению многочленов. Пусть функции и разложены в степенные ряды , - два многочлена, причем. Мы будем, кроме того, предполагать, что , то есть, что алгебраическая дробь правильна в противном случае мы всегда можем выделить из нее целую часть. Мы знаем, что если Сначала мы получим соотношений такого вида: А дальше все соотношения имеют один и тот же вид: Таким образом, коэффициенты ряда Коэффициенты этого соотношения зависят лишь от знаменателя дроби. Числитель же дроби нужен для нахождения первых членов рекуррентной последовательности. Обратно, если дано рекуррентное соотношение А тогда производящей функцией для последовательности чисел является алгебраическая дробь Ведь все равно придется делить числитель на знаменатель, а это приведет к тому же самому рекуррентному соотношению Но дело в том, что над дробью При решении задачи о разбиении последовательности мы пришли к рекуррентному соотношению Покажем, как решить соотношение Для этого составим производящую функцию. Но по рекуррентному соотношению Решая его, находим, что Мы выбрали перед корнем знак минус, так как в противном случае при мы имели бы , а из разложения При этом структура данных может не зависеть от конкретных языковых конструкций абстрактная структура данных. Стеком называется одномерная структура данных, загрузка или увеличение элементов для которой осуществляется с помощью указателя стека в соответствии с правилом LIFO "last-in, first-out" "последним введен,первым выведен". Указатель стека sp stack pointer содержит в любой момент времени индекс адрес текущего элемента, который является единственным элементом стека, доступным в данный момент времени для обработки. Существуют следующие основные базисные операции для работы со стеком для случая, когда указатель стека всегда задает ячейку, находящуюся непосредственно над его верхним элементом. На стержне в исходном порядке находится дисков, уменьшающихся по размеру снизу вверх. Диски должны быть переставлены на стержень в исходном порядке при использовании в случае необходимости промежуточного стержня для временного хранения дисков. В процессе перестановки дисков обязательно должны соблюдаться правила: Очередь - одномерная структура данных, для которой загрузка или извлечение элементов осуществляется с помощью указателей начала извлечения head и конца tail очереди в соответствии с правилом FIFO "first-in, first-out" - "первым введен, первым выведен". Отметим, что при извлечении элемента из очереди все элементы могут также перемещаться на один шаг к ее началу. Связанный список представляет собой структуру данных, которая состоит из узлов как правило, записей , содержащих указатели на следующий узел. Указатель, который ни на что не указывает, снабжается значением nil. Таким образом, в каждый элемент связанного списка добавляется указатель звено связи. Приведем основные базисные операции для работы с однонаправленным связанным списком. Здесь q — индекс элемента, который должен быть вставлен в список после элемента с индексом p. Отметим, что элемент, следующий в списке за элементом x, называется преемником элемента x, а элемент, pасположенный перед элементом x, называется предшественником элемента x. Если элемент x не имеет преемника, то содержащемуся в нем указателю присваивается значение nil. Отметим, что исключение последнего элемента из однонаправленного списка связано с просмотром всего списка. В двунаправленном связанным списке каждый элемент имеет два указателя succlink - описывает связь элемента с преемником, predlink - с предшественником. Основные определения и понятия о графах даются в лекции В лекции 16 и 17 рассматриваются комбинаторные алгоритмы на графах. В данной лекции приведены несколько понятий, необходимых для описания абстрактной структуры данных, - двоичное дерево. При решении многих задач математики используется понятие графа. Граф - набор точек на плоскости эти точки называются вершинами графа , некоторые из которых соединены отрезками эти отрезки называются ребрами графа. Вершины могут располагаться на плоскости произвольным образом. Причем неважно, является ли ребро, соединяющее две вершины, отрезком прямой или кривой линией. Важен лишь факт соединения двух данных вершин графа ребром. Примером графа может служить схема линий железных дорог. Если требуется различать вершины графа, их нумеруют или обозначают разными буквами. В изображении графа на плоскости могут появляться точки пересечения ребер, не являющиеся вершинами. Говорят, что две вершины графа соединены путем , если из одной вершины можно пройти по ребрам в другую вершину. Путей между двумя данными вершинами может быть несколько. Поэтому обычно путь обозначают перечислением вершин, которые посещают при движении по ребрам. Граф называется связным , если любые две его вершины соединены некоторым путем. Состоящий из различных ребер замкнутый путь называется циклом. Связный граф, в котором нет циклов, называется деревом. Одним из основных отличительных свойств дерева является то, что в нем любые две вершины соединены единственным путем. Дерево называется ориентированным , если на каждом его ребре указано направление. Следовательно, о каждой вершине можно сказать, какие ребра в нее входят, а какие - выходят. Точно так же о каждом ребре можно сказать, из какой вершины оно выходит, и в какую - входит. Двоичное дерево - это такое ориентированное дерево , в котором:. Множество самых разнообразных задач естественно формулируется в терминах графов. Так, например, могут быть сформулированы задачи составления расписаний в исследовании операций, анализа сетей в электротехнике, установления структуры молекул в органической химии, сегментации программ в программировании, анализа цепей Маркова в теории вероятностей. В задачах, возникающих в реальной жизни, соответствующие графы часто оказываются так велики, что их анализ неосуществим без ЭВМ. Таким образом, решение прикладных задач с использованием теории графов возможно в той мере, в какой возможна обработка больших графов на ЭВМ, и поэтому эффективные алгоритмы решения задач теории графов имеют большое практическое значение. В 16 и 17 лекциях мы излагаем несколько эффективных алгоритмов на графах и используем их для демонстрации некоторой общей техники решения задач на графах с помощью ЭВМ. Конечный граф состоит из конечного множества вершин и конечного множества ребер. Каждому ребру соответствует пара вершин: Граф изображается следующим образом: Граф называется ориентированным , если пара вершин , соответствующая каждому ребру, упорядочена. В таком случае говорят, что ребро ориентированно из вершины в вершину , а направление обозначается стрелкой на ребре. Мы будем называть ориентированные графы орграфами. В неориентированном графе концевые вершины каждого ребра не упорядочены, и ребра не имеют направления. Ребро называется петлей , если оно начинается и кончается в одной и той же вершине. Говорят, что два ребра параллельны , если они имеют одну и ту же пару концевых вершин и если они имеют одинаковую ориентацию в случая ориентированного графа. Граф называется простым , если он не имеет ни петель, ни параллельных ребер. Если не указывается противное, будем считать, что рассматриваемые графы являются простыми. Всюду в 16 и 17 лекции будем использовать символы и для обозначения соответственно числа вершин и числа ребер в графе. Наиболее известный способ представления графа на бумаге состоит в геометрическом изображении точек и линий. В ЭВМ граф должен быть представлен дискретным способом, причем возможно много различных представлений. Простота использования, так же как и эффективность алгоритмов на графе, зависит от подходящего выбора представления графа. Рассмотрим различные структуры данных для представления графов. Одним из наиболее распространенных машинных представлений простого графа является матрица смежностей или соединений. Матрица смежностей графа есть -матрица , в которой , если в существует ребро, идущее из -й вершины в -ю, и в противном случае. Орграф и его матрица смежностей представлены на рис. Ориентированный граф и его матрица смежностей. Заметим, что в матрице смежностей петля может быть представлена соответствующим единичным диагональным элементом. Кратные ребра можно представить, позволив элементу матрицы быть больше 1, но это не принято, так как обычно удобно представлять каждый элемент матрицы одним двоичным разрядом. Для задания матрицы смежностей требуется двоичных разрядов. У неориентированного графа матрица смежностей симметрична, и для ее представления достаточно хранить только верхний треугольник. В случае представления графа его матрицей смежностей для большинства алгоритмов требуется время вычисления, по крайней мере пропорциональное. Граф, в котором ребру сопоставлено число , называется взвешенным графом , а число называется весом ребра. В сетях связи или транспортных сетях эти веса представляют некоторые физические величины, такие как стоимость, расстояние, эффективность, емкость или надежность соответствующего ребра. Простой взвешенный граф может быть представлен своей матрицей весов , где есть вес ребра, соединяющего вершины и. Веса несуществующих ребер обычно полагают равными или 0 в зависимости от приложений. Когда вес несуществующего ребра равен 0, матрица весов является простым обобщением матрицы смежностей. Если граф является разреженным, то возможно, что более эффектно представлять ребра графа парами вершин. Это представление можно реализовать двумя массивами и. Каждый элемент в массиве есть метка вершины, а -е ребро графа выходит из вершины и входит в вершину. Например, орграф, изображенный на рис. Ясно, что при этом легко представимы петли и кратные ребра. В ориентированном графе вершина называется последователем другой вершины , если существует ребро, направленное из в. Вершина называется тогда предшественником. В случае неориентированного графа две вершины называются соседями , если между ними есть ребро. Граф может быть описан его структурой смежности, то есть списком всех последователей соседей каждой вершины; для каждой вершины задается - список всех последователей соседей вершины. В большинстве алгоритмов на графах относительный порядок вершин, смежных с вершиной в , не важен, и в таком случае удобно считать мультимножеством или множеством, если граф является простым вершин, смежных с. Структура смежности орграфа, представленного на рис. Если для хранения метки вершины используется одно машинное слово, то структура смежности ориентированного графа требует слов. Если граф неориентированный, нужно слов, так как каждое ребро встречается дважды. Структуры смежности могут быть удобно реализованы массивом из линейно связанных списков, где каждый список содержит последователей некоторой вершины. Поле данных содержит метку одного из последователей, и поле указателей указывает следующего последователя. Хранение списков смежности в виде связанного списка желательно для алгоритмов, в которых в графе добавляются или удаляются вершины. Матрица инцидентности - задает граф: Говорят, что вершины и в графе смежны , если существует ребро, соединяющее их. Говорят, что два ребра смежны , если они имеют общую вершину. Простой путь , или для краткости, просто путь , записываемый иногда как , - это последовательность смежных ребер , в которой все вершины различны, исключая, возможно, случай. В орграфе этот путь называется ориентированным из в , в неориентированном графе он называется путем между и. Число ребер в пути называется длиной пути. Путь наименьшей длины называется кратчайшим путем. Замкнутый путь называется циклом. Граф, который не содержит циклов, называется ациклическим. Подграф графа есть граф, вершины и ребра которого лежат в. Подграф , индуцированный подмножеством множества вершин графа , - это подграф, который получается в результате удаления всех вершин из и всех ребер, инцидентных им. Неориентированный граф связен , если существует хотя бы один путь в между каждой парой вершин и. Ориентированный граф связен , если неориентированный граф, получающийся из путем удаления ориентации ребер, является связным. Граф , состоящий из единственной изолированной вершины, является тривиально связным. Максимальный связный подграф графа называется связной компонентой или просто компонентой. Несвязный граф состоит из двух или более компонент. Максимальный сильно связный подграф называется сильно связной компонентой. Иногда недостаточно знать, что граф связен; нас может интересовать, насколько "сильно связен" связный граф. Например, связный граф может содержать вершину, удаление которой вместе с инцидентными ей ребрами разъединяет оставшиеся вершины. Такая вершина называется точкой сочленения или разделяющей вершиной. Граф, содержащий точку сочленения, называется разделимым. Граф без точек сочленения называется двусвязным или неразделимым. Максимальный двусвязный подграф графа называется двусвязной компонентой или блоком. Большинство основных вопросов о графах касается связности, путей и расстояний. Нас может интересовать вопрос, является ли граф связным ; если он связен, то может оказаться нужным найти кратчайшее расстояние между выделенной парой вершин или определить кратчайший путь между ними. Если граф несвязен, то может потребоваться найти все его компоненты. В нашем курсе строятся алгоритмы для решения этих и других подобных вопросов. Связный неориентированный ациклический граф называется деревом , множество деревьев называется лесом. В связном неориентированном графе существует по крайней мере один путь между каждой парой вершин; отсутствие циклов в означает, что существует самое большее один такой путь между любой парой вершин в. Поэтому, если - дерево, то между каждой парой вершин в существует в точности один путь. Рассуждение легко обратимо, и поэтому неориентированный граф будет деревом тогда и только тогда, если между каждой парой вершин в существует в точности один путь. Так как наименьшее число ребер, которыми можно соединить вершин, равно и дерево с вершинами содержит в точности ребер, то деревья можно считать минимально связными графами. Удаление из дерева любого ребра превращает его в несвязный граф , разрушая единственный путь между по крайней мере одной парой вершин. Особый интерес представляют остовные деревья графа , то есть деревья, являющиеся подграфами графа и содержащие все его вершины. Если граф несвязен, то множество, состоящее из остовных деревьев каждой компоненты называется остовном лесом графа. Для построения остовного дерева леса данного неориентированного графа , мы последовательно просматриваем ребра , оставляя те, которые не образуют циклов с уже выбранными. Во взвешенном графе часто интересно определить остовное дерево лес с минимальным общим весом ребер, то есть дерево лес , у которого сумма весов всех его ребер минимальна. Такое дерево называется минимумом оставных деревьев или минимальное остовное дерево. Другими словами, на каждом шаге мы выбираем новое ребро с наименьшим весом наименьшее ребро , не образующее циклов с уже выбранными ребрами; этот процесс продолжаем до тех пор, пока не будет выбрано ребер, образующих остовное дерево. Этот процесс известен как жадный алгоритм. Жадный алгоритм может быть выполнен в два этапа. Сначала ребра сортируются по весу и затем строится остовное дерево путем выбора наименьших из имеющихся в распоряжении ребер. Существует другой метод получения минимума остовных деревьев , который не требует ни сортировки ребер, ни проверки на цикличность на каждом шаге, - так называемый алгоритм ближайшего соседа. Мы начинаем с некоторой произвольной вершины в заданном графе. Пусть - ребро с наименьшим весом, инцидентное ; ребро включается в дерево. Затем среди всех ребер, инцидентных либо , либо , выбираем ребро с наименьшим весом и включаем его в частично построенное дерево. В результате этого в дерево добавляется новая вершина, например,. Повторяя процесс, ищем наименьшее ребро, соединяющее , или с некоторой другой вершиной графа. Процесс продолжается до тех пор, пока все вершины из не будут включены в дерево, то есть пока дерево не станет остовным. Наихудшим для этого алгоритма будет случай, когда - полный граф то есть когда каждая пара вершин в графе соединена ребром ; в этом случае для того, чтобы найти ближайшего соседа, на каждом шаге нужно сделать максимальное число сравнений. Чтобы выбрать первое ребро, мы сравниваем веса всех ребер, инцидентных вершине , и выбираем наименьшее; этот шаг требует сравнений. Для выбора второго ребра мы ищем наименьшее среди возможных ребер инцидентных или и делаем для этого сравнений. Таким образом, ясно, что для выбора -го ребра требуется сравнений, и поэтому в сумме потребуется сравнений для построения минимума остовных деревьев. Максимальный полный подграф графа называется кликой графа ; другими словами, клика графа есть подмножество его вершин, такое, что между каждой парой вершин этого подмножества существует ребро и, кроме того, это подмножество не принадлежит никакому большому подмножеству с тем же свойством. Граф G и все его клики. Клики графа представляют "естественные" группировки вершин, и определение клик графа полезно в кластерном анализе в таких областях, как информационный поиск и социология. Два графа называются изоморфными , если существует взаимно однозначное соответствие , такое, что тогда и только тогда, если , то есть существует соответствие между вершинами графа и вершинами графа , сохраняющее отношение смежности. Вообще говоря, между и может быть более чем одно соответствие, и на рис. Изоморфные графы отличаются только метками вершин, в связи с чем задача определения изоморфизма возникает в ряде практических ситуаций, таких, как информационный поиск и определение химических соединений. Заметим, что можно ограничится орграфами. Любой неориентированный граф превращается в орграф заменой каждого ребра двумя противоположно направленными ребрами. Два полученные таким образом орграфа, очевидно, изоморфны тогда и только тогда, если изоморфны исходные графы. Определение планарности графа отличается от других рассмотренных нами задач, поскольку при изображении точек и линий на плоскости приходится больше иметь дело с непрерывными, а не с дискретными величинами. Взаимосвязь между дискретными и непрерывными аспектами планарности заинтересовала математиков и привела к различным характеристикам планарных графов. С точки зрения математики эти характеристики изящны, но эффективных алгоритмов определения планарности они не дают. Наиболее успешный подход к определению планарности состоит просто в том, что граф разбивается на подграфы и затем делается попытка разместить его на плоскости, добавляя подграфы один за другим и сохраняя при размещении планарность. Вначале сделаем несколько простых, но полезных наблюдений. Поскольку орграф планарен тогда и только тогда, если планарен соответствующий неориентированный граф, полученный игнорированием направления ребер, то достаточно рассматривать только неориентированные графы, поскольку неориентированный граф планарен тогда и только тогда, если все его двусвязные компоненты планарны. Поэтому если неориентированный граф является разделимым, мы можем разложить его на двусвязные компоненты и рассматривать их отдельно. Наконец, поскольку параллельные ребра и петли всегда можно добавить к графу или удалить из него без нарушения свойства планарности, нам достаточно рассматривать только простые графы. Поэтому при определении планарности будем предполагать, что граф неориентированный, простой и двусвязный. Наша основная стратегия состоит прежде всего в том, чтобы в графе найти цикл , разместить на плоскости в виде простой замкнутой кривой, разложить оставшуюся часть на непересекающиеся по ребрам пути и затем попытаться разместить каждый из этих путей либо целиком внутри , либо целиком вне. Если нам удалось разместить так весь граф , то он планарен, в противном случае он непланарен. Трудность этого способа заключается в том, что при размещении путей можно выбирать либо внутренность, либо внешность , и мы должны проконтролировать, чтобы неправильный выбор области размещения на ранней стадии не устранял возможности размещения последующих путей, - это могло бы привести нас к неверному заключению, что планарный граф непланарен. Задача поиска является фундаментальной в комбинаторных алгоритмах, так как она формулируется в такой общности, что включает в себя множество задач, представляющих практический интерес. При самой общей постановке "Исследовать множество с тем чтобы найти элемент, удовлетворяющий некоторому условию ", о задаче поиска едва ли можно сказать что-либо стоящее. Удивительно, однако, что достаточно незначительных ограничений на структуру множества , чтобы задача стала интересной: Мы сделаем некоторые предположения о структуре множества , позволяющие исследовать или. Большинство алгоритмов поиска попадает в одну из трех категорий, характеризуемых временем поиска. Любой способ поиска оперирует с элементами, которые будем называть именами , взятыми из множества имен - оно называется пространством имен. Это пространство имен может быть конечным или бесконечным. Самыми распространенными пространствами имен являются множества целых чисел с их числовым порядком нумерацией , и множества последовательностей символов над некоторым конечным алфавитом с их лексикографическим то есть словарным порядком. Каждый из алгоритмов поиска, обсуждаемых в этой лекции, основан на одном из трех следующих предположений о пространстве. Такой порядок имеет следующие свойства. Каждое имя в есть последовательность символов или цифр над конечным линейно упорядоченным алфавитом. Естественным порядком на является лексикографический порядок , индуцированный линейным порядком на. Мы полагаем, что исход , или сравнения двух символов не имен получается за время, не зависящее от или. Имеется функция , которая равномерно отображает пространство имен в множество , то есть все целые , приблизительно с одинаковой частотой являются образами имен из при отображении.
https://gist.github.com/82f81d66db5537387ba7b63a0b8ed7b0
https://gist.github.com/753c6964638a9914b4c6ec5c7853bea5
https://gist.github.com/384ec06ae719e2517cbf55e40a24fd4d