русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Введение


Дата добавления: 2013-12-23; просмотров: 1558; Нарушение авторских прав


Предисловие

УДК 519.682.1

ББК 22.18 (я7)

П 30

 

П 30 Филиппова А.С. Лекции по дисциплине «Комбинаторные алгоритмы»: Учеб. пособие / А.С.Филиппова; Уфимск. гос. авиац. техн. ун-т. – Уфа: УГАТУ, 2010.-85 с. ISBN 0-486-41962-2

 

Пособие соответствует государственному образовательному стандарту дисциплины «Комбинаторные алгоритмы» направления подготовки бакалавров 010300 – «Математика. Компьютерные науки». Дисциплина посвящена алгоритмам решения типовых задач комбинаторной оптимизации. В лекциях основное внимание уделено комбинаторным алгоритмам и задачам исследования операций: кратчайшие расстояния на графах, остовные деревья, сети, сетевое планирование, потоки в сетях, паросочетания, понятие NP-полных задач.

Учебное пособие предназначены для студентов 2-го и 3-го курса общенаучного факультета, изучающих дисциплину «Комбинаторные алгоритмы».

 

Ил. 37. Табл. 13. Библиогр.: 5 назв.

 

Рецензенты: д-р. физ.-мат. наук, проф. С.И. Спивак

 

ISBN

ББК 22.18 (я7)

ISBN 0-486-41962-2 © Уфимский государственный авиационный

технический университет, 2010

© А.С. Филиппова, 2010


Содержание

 

Предисловие………………………………………………………………………………..4

Введение…………………………………………………………………………………….4

Лекция 1. Основные определения комбинаторики……………………………………5

Лекция 2. Сеть. Кратчайшие пути. Алгоритм Дейкстры……………………………..9

Лекция 3. Кратчайшие пути между всеми парами узлов. Алгоритм

с тройственными операциями…………………………………………………………….16

Лекция 4. Поиск остовного дерева в ширину и поиск в глубину. Алгоритмы .

Прима и Краскала (жадный) для поиска минимального остовного дерева…………….21

ЛЕКЦИЯ 5. Проблема коммивояжера. Алгоритмы «ближайшего соседа», «самой близкой вставки»……………………………………………………………………………26

ЛЕКЦИЯ 6. Сетевое планирование. Задача о кратчайшем сроке.



Задача о критическом пути…………………………………………………………………30

ЛЕКЦИЯ 7. Максимальные потоки. Теорема Форда и Фалкерсона……………………..35

Лекция 8. Метод нахождения максимального потока. Теорема о максимальных разрезах………………………………………………………………………………………40

ЛЕКЦИЯ 9. Алгоритмы для нахождения максимального потока и минимального разреза………………………………………………………………………………………..46

ЛЕКЦИЯ 10. Потоки с минимальной стоимостью. Метод анализа и оценки проекта REPT-метод………………………………………………………………………………….51

Лекция 11. Непересекающиеся цепи и разделяющие множества

Теорема Менгера. …………………………………………………………………………...56

ЛЕКЦИЯ 12. Максимальные и наибольшие паросочетания. Алгоритм выбора наибольшего сочетания в двудольном графе с матрицей двудольного графа.…………60

ЛЕКЦИЯ 13 Задачи о назначении. Венгерский алгоритм……………………………….69

ЛЕКЦИЯ 14. Классы задач в зависимости от их трудности. Полиномиальные, недетерминированные алгоритмы. Стандартные NP-полные задачи. Решение NP-полной задачи……………………………………………………………………………….74

Контрольные вопросы… …………………………………………………………………..82

Литература…………………………………………………………………………………..84

 

Учебное пособие содержит в себе курс лекций по дисциплине «Комбинаторные алгоритмы». Оно посвящено некоторым комбинаторным алгоритмам, которые встречаются в информатике, исследовании операций и дискретной математике. Особое внимание уделяется идеям, лежащим в основе алгоритмов, а так же детальному разбору численных примеров для каждого приведенного алгоритма. Каждый пример проиллюстрирован, что упрощает понимание сути изучаемых алгоритмов. Основу для материалов лекций составила книга Ху Т.Ч., Шинга М.Т. «Комбинаторные алгоритмы», перевод и научное редактирование которой выполнены в 2004 году на кафедре математической логики и высшей алгебры Нижегородского государственного университета им. Н.И.Лобачевского. Несмотря на то, что на русском языке имеются разного уровня и объема учебники, отражающие в разной степени рассматриваемую тематику, в основном они изданы в конце прошлого века и поэтому для студентов составляет трудность их изучение. Данное учебное пособие отличает простой стиль изложения с минимумом формализма (но не в ущерб математической строгости), отбор материала, сбалансированный объем.

Комбинаторика раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Поэтому можно сказать, что целью комбинаторного анализа является изучение комбинаторных конфигураций. Это изучение включает в себя вопросы существования комбинаторных конфигураций, алгоритмы их построения, оптимизацию таких алгоритмов, а также решение задач перечисления, в частности определение числа конфигураций данного класса. Простейшим примером комбинаторных конфигураций являются перестановки, сочетания и размещения. Большой вклад в систематическое развитие комбинаторных методов был сделан Г. Лейбницем (диссертация Комбинаторное искусство), Я. Бернулли (работа Искусство предположений), Л. Эйлером. Можно считать, что с появлением работ Я. Бернулли и Г. Лейбница комбинаторные методы выделились в самостоятельную часть математики. В работах Л.Эйлера по разбиениям и композициям натуральных чисел на слагаемые было положено начало одному из основных методов перечисления комбинаторных конфигураций методу производящих функций. Возвращение интереса к комбинаторному анализу относится к 50-м годам ХХ в. в связи с бурным развитием кибернетики и дискретной математики и широким использованием электронно-вычислительной техники. В этот период активизировался интерес к классическим комбинаторным задачам. Классические комбинаторные задачи это задачи выбора и расположения элементов конечного множества, имеющие в качестве исходной некоторую формулировку развлекательного содержания типа головоломок. Например, в 1859 г. У. Гамильтон придумал игру Кругосветное путешествие, состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа. Это одна из самых известных задач комбинаторики - задача коммивояжера.

 

Лекция 1. Основные определения комбинаторики

Бытуетмнение, что комбинаторные задачи элементарны. Конечно, это не так. Число комбинаторных задач и их разнообразие быстро растет. К их решению прямо или косвенно приводят многие практические задачи. При этом оказывается, что несмотря на заманчивую простоту постановки, комбинаторные задачи в большинстве очень трудны; многие из них не поддаются решению до сих пор. К числу современных задач, решаемых комбинаторными методами, относятся:

1) задачи на размещения. Это задачи о расположении, например, на плоскости предметов, обладающих свойствами дальнодействия;

2) задачи о покрытиях и заполнениях. Это задачи, например, о заполнении заданных пространственных фигур меньшими телами заданных форм и размеров;

3) задачи о маршрутах. К ним относятся задачи на отыскание кратчайшего пути и тому подобное. Это задачи оптимального плана;

4) комбинаторные задачи теории графов. Это задачи сетевого планирования, например, задачи транспортных и электрических сетей, задачи об окрашивании графов, задачи о перечислении вершин и тому подобные задачи;

5) перечислительные задачи. В таких задачах речь идет о числе предметов, составляемых из данного набора элементов при соблюдении определенных правил.

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

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

Пример 1.1. Пусть некоторое агентство недвижимости располагает базой данных из n записей, причём каждая запись содержит одно предложение (что имеется) и один запрос (что требуется) относительно объектов недвижимости. Требуется найти все такие пары записей, в которых предложение первой записи совпадает с запросом второй и одновременно предложение второй записи совпадает с запросом первой. (На бытовом языке это называется подбором вариантов обмена.) Допустим, что используемая СУБД позволяет проверить вариант за одну миллисекунду. Нетрудно сообразить, что при «лобовом» алгоритме поиска вариантов (каждая запись сравнивается с каждой) потребуется п(п — 1)/2 сравнений. Если n = 100, то все в порядке — ответ будет получен за 4,95 секунды. Но если n = 100 000 (более реальный случай), то ответ будет получен за 4 999 950 секунд, что составляет без малого 1389 часов и вряд ли может считаться приемлемым. Обратите внимание на то, что мы оценили только трудоёмкость подбора прямых вариантов, а существуют ещё варианты, когда число участников сделки больше двух.

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

- сложность по времени (или временную сложность), то есть количество необходимых шагов алгоритма,

- сложность по памяти (или емкостную сложность), то есть объём памяти, необходимый для работы алгоритма.

Во всех случаях основным инструментом такого анализа оказываются формулы и методы.

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

Для формулировки и решения комбинаторных задач используются различные модели комбинаторных конфигураций. Рассмотрим следующие две наиболее по­пулярные (изложение на “языке ящиков» и «языке функций»):

а) Дано n предметов. Их нужно разместить по m ящикам так, чтобы выполнялись заданные ограничения. Сколькими способами это можно сделать?

б) Рассмотрим множество функций , где , . Не ограничивая общности, можно считать, что Х = {1,...,п}, Y = {1,...,т}, F= (F(1),...,F(n)), . Сколько существует функций F, удовлетворяющих заданным ограничениям?

1) Размещения. Число всех функций (при отсутствии ограничений), или число всех возможных способов разместить п предметов по m ящикам, называется числом размещений и обозначается U(m,n).

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

Теорема.U (m,n) = .

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

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

Пример 1.1. При игре в кости бросаются две кости и выпавшие на верхних гранях очки складываются. Какова вероятность выбросить 12 очков? Каждый возмож­ный исход соответствует функции F: {1,2} —> {1,2,3,4,5,6} (аргумент — номер кости, результат — очки на верхней грани). Таким образом, всего возможно U(6,2) = 62 = 36 различных исходов. Из них только один (6 + 6) даёт двенадцать очков. Вероятность 1/36.

2) Размещения без повторений. Число инъективных функций, или число способов разместить n предметов по m ящикам, не более чем по одному в ящик, называется числом размещений без повторений и обозначается А(m,n), или .

Теорема. .

Доказательство. Ящик дляпервого предмета можно выбрать m способами, для второго — m- 1 способами и т. д. Таким образом

. (1.1)

По определению считают, что A(m,n)=0 при n > m и А(т, 0) = 1.

Замечание. Формула (1.1) слева выглядит сложной и незавершённой, формула справа — изящной и «математичной». Но формула — это частный случай алгоритма. При практическом вычислении левая формула оказывается намного предпочтительнее правой. Во-первых, для вычисления по левой формуле потребуется (т- 1) умножение, а по правой — (2т- п - 2) умножений и одно деление. Поскольку п < т, левая формула вычисляется существенно быстрее. Во- вторых, число А(m,n) растёт довольно быстро и при больших m и n может не поместиться в разрядную сетку. Левая формула работает правильно, если результат помещается в разрядную сетку. При вычислении же по правой формуле переполнение может наступить «раньше времени» (то есть промежуточные результаты не помещаются в разрядную сетку, в то время как окончательный результат мог бы поместиться), поскольку факториал — очень быстро растущая функция.

Пример 1.2. В некоторых видах спортивных соревнований исходом является опре­деление участников, занявших первое, второе и третье места. Сколько возможно различных исходов, если в соревновании участвуют п участников? Каждый возможный исход соответствует функции F: {1,2,3} {1 ..п} (аргумент — номер призового места, результат — номер участника). Таким образом, всего возможно А(п, 3) = п(п - 1)(n- 2) различных исходов.

3)Перестановки. Если |Х| = |Y| = n, то существуют взаимно-однозначные функции . Число взаимно-однозначных функций, или число перестановок п предметов, обозначается Р(п).

Теорема Р(п) = п!.

Доказательство:

Пример 1.3. Последовательность непустых подмножеств множе­ства называется цепочкой в Е, если

&.

Цепочка называется полной цепочкой в Е, если || =|E|. Сколько существует полных цепочек? Очевидно, что в полной цепочке каждое следующее подмножество Ei+1 получено из предыдущего подмножества Ei добавлением ровно одного элемента из Е и таким образом, |E1|=1, |E2|= 2, ..., |Ет|= т. Следовательно, полная цепочка определяется порядком, в котором элементы Е добавляются для образования очередного элемента полной цепочки. Отсюда количество полных цепочек — это количество перестановок элементов множества Е, равное т!.

4) Сочетания. Число строго монотонно возрастающих функций, или число размещений n неразличимых предметов по m ящикам не более чем по одному в ящик, то есть число способов выбрать из т ящиков n ящиков с предметами, называется числом сочетаний и обозначается С(т,п), или , или .

Теорема.

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

.

(Сведение моделей) Число сочетаний является числом строго монотонно воз­растающих функций, потому что любая строго монотонно возрастающая функция определяется набором своих значений, причём . Другими словами, каждая строго монотонно возрастающая функция определяется выбором п чисел из диапазона 1..т. Таким образом, число строго монотонно возрастающих функций равно числу n-элементных подмножеств m-элементного множества, которое, в свою очередь, равно числу способов выбрать n ящиков с предметами из m ящиков. □

По определению при п> т.

Пример 1.4. В начале игры в домино каждому играющему выдаётся 7 костей из имеющихся 28 различных костей. Сколько существует различных комбинаций костей, которые игрок может получить в начале игры? Очевидно, что искомое число равно числу 7-элементных подмножеств 28-элементпого множества. Имеем:

.

5) Сочетания с повторениями. Число монотонно возрастающих функций, или число размещений n неразличимых предметов по т ящикам, называется числом сочетаний с повторениями и обозначается V(m, п).

Теорема. V(m,n) = C(n + m - 1, n).

Доказательство. Монотонно возрастающей функции однозначно соответствует строго монотонно возрастающая функция . Это соответствие устанавливается следующей формулой: .

Пример 1.5. Сколькими способами можно рассадить n вновь прибывших гостей среди m гостей, уже сидящих за круглым столом? Очевидно, что между m сидящими за круглым столом гостями имеется m промежутков, в которые можно рассаживать вновь прибывших. Таким образом, число способов равно

.



<== предыдущая лекция | следующая лекция ==>
Лекции по дисциплине | Кратчайший путь


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.007 сек.