Реферат по истории математики Научный проф. Верещагин Н. К
Скачать 272.28 Kb.
|
Для чего нужны быстрые алгоритмы?Эффективность алгоритма принято измерять асимптотической оценкой времени работы алгоритма в зависимости от параметров исходной сети. (Употребляется также термин «сложность алгоритма» - «complexity» в англоязычной литературе.) Основным параметром является число вершин исходной сети (так как число ребер в большинстве практических задач не превосходит квадрата числа вершин). Алгоритмы, время работы которых не превосходит некоторого полинома от размера исходной сети (числа вершин), называются полиномиальными. Как правило, полиномиальные алгоритмы возможно эффективно реализовать на практике. Напротив, алгоритмы, так или иначе использующие перебор большого числа вариантов, по своей сложности обычно бывают экспоненциальными. Начнем с рассмотрения простого примера, наглядно иллюстрирующего пользу теоретических исследований в области компьютерных наук. Пусть в памяти компьютера имеется N целых чисел, и необходимо расположить их в порядке возрастания. (Данная задача называется задачей сортировки). Рассмотрим следующий алгоритм: выберем среди данных чисел наименьшее, поставим его на первое место. Затем из оставшихся чисел снова выберем наименьшее, и поставим его на второе место. И так далее. Очевидно, что данный алгоритм решает задачу сортировки. Но насколько он эффективен? Несложно показать, что данному алгоритму требуется порядка N^2 действий. (Данная оценка называется асимптотикой работы алгоритма, и с помощью O-символики данный факт записывается так: сложность алгоритма есть O(N^2) ). Предположим что N = 10^8. Современный однопроцессорный компьютер способен выполнять порядка ста миллионов элементарных операций (присваивание, сложение, вычитание...) в секунду. Таким образом, для сортировки данного набора чисел потребуется порядка (10^8)^2 / 10^8 = 100 миллионов секунд, или около трех лет. В то же время, известны алгоритмы решения задачи сортировки со сложность O(NlogN). Самые известные из них – это алгоритм пирамидальной сортировки (heap sort) и «быстрая» (quick sort) сортировка Хоара (последняя, впрочем, имеет лишь время работы O(NlogN) «в среднем»). При N = 10^8 время работы таких алгоритмов получается около 30 секунд! На примере данной задачи видно, что дополнительные исследования в алгоритмической области могут сократить объемы вычислений на порядки, за считанные секунды решить задачу, которая ранее с практической точки зрения казалась неразрешимой. Глава 1. История изучения теории потоков §1.1. Начало исследований Впервые проблемы связанные с пересылкой потоков в сетях были рассмотрены Канторовичем в 1933 году. (Более того – он рассматривал более общую задачу с движением потока жидкостей различных типов (multicommodity flows)). Основы теории потоков были заложены в период с ноября 1954 по декабрь 1955 года исследователями корпорации RAND (Санта-Моника, Калифорния). Проследим за развитием теории потоков в хронологическом порядке по отчетам RAND. Первый отчет «Максимальный поток в сети» датируется 19м ноября 1954 года. Авторы отчета – Форд (Ford) и Фалкерсон (Fulkerson), доказали теорему о максимальном потоке и минимальном разрезе для неориентированных графов: значение максимального потока в сети равно минимальной пропускной способности разреза. (Разрезом в сети называется разбиение множества ее вершин на два непересекающихся класса, таких что источник и сток лежат в разных классах. Пропускной способностью разреза называется сумма пропускных способностей ребер, концы которых лежат в разных классах.) В 1955 году в работе Робахера (Robacher) было упомянуто, что впервые эту теорему доказал Фалкерсон. Работа Форда и Фалкерсона о потоках и разрезах была мотивирована изучением транспортных сетей железных дорог (см. далее). В том же отчета они также описали простой алгоритм нахождения максимального потока для планарных графов, обладающих следующим дополнительным свойством: после добавления дуги из источника в сток граф остается планарным. Более того, авторы заметили, что задача о максимальном потоке является частным случаем задачи линейного программирования, а стало быть, может быть решена симплекс-методом Данцига (Danzig). В отчете от 1 января 1955 года, Данциг и Фалекрсон показали, что теорема о максимальном потоке и минимальном разрезе может быть выведена из теоремы о сильной двойственности для задач линейного программирования (в работе упоминалось, что этот факт установлен Хоффманом (Hoffman)). Более того, было доказано существование максимального целочисленного потока, для сетей пропускные способности которых являются целочисленными. Следствием этого факта является известная теорема Менгера (Menger) о непересекающихся путях. 1 апреля 1955 года Данциг и Фалкерсон описали простой способ вычисления максимального потока основанный на симплекс-методе. 26 мая 1955 года Робахер независимо доказал теорему о максимальном потоке и минимальном разрезе, сведя ее к теореме Менгера. §1.2. Эвристика Болдырева До тех пор пока существующие алгоритмы вычисления максимального потока основывались на симплекс-методе, одной из важнейших задач в теории потоков было построение комбинаторного алгоритма решения этой задачи. 3 июня 1955 года в Нью-Йорке на встрече Американского Общества Исследования Операций Болдырев сделал доклад (опубликованный затем как отчет RAND от 5 августа 1955 года) об эвристическом алгоритме нахождения максимального потока. Метод Болдырева является так называемым «жадным алгоритмом»: он пытается послать как можно больше потока из источника, до тех пор, пока не обнаружится критическая вершина (т.е. такая вершина из которой невозможно передать поток далее). Такая ситуация устраняется путем возвращения избыточного потока в источник. По словам Болдырева, основные достоинства его метода заключались в том, что:
«Техника решения формулируется как простая игра, которой можно обучить десятилетнего ребенка», утверждал Болдырев. Однако, данный метод является эмпирическим, не использует технику перебора с возвратом, и не гарантирует нахождения оптимального решения. Однако, это не смущало Болдырева, поскольку основным применением своего алгоритма он видел транспортные сети. В своей статье 1955 года он привел пример транспортной сети с 41 вершиной и 85 дугами, для которой его алгоритм посчитал верное решение менее чем за тридцать минут. В заключении статьи Болдырев пишет: «Возникает вопрос о систематическом, формальном обосновании; всесторонней математической базе для эмпирицизма и интуиции, и о связи данной техники с другими процессами, такими как многошаговые решающие процессы (multistage decision process), предложенные Беллманом. Все это остается для будущих исследований». §1.3. Отчет Харриса-Росса В своем первом отчете о максимальных потоках, Форд и Фалкерсон упомянули, что задача о максимальном потоке была сформулирована Харрисом следующим образом: Рассмотрим транспортную сеть железных дорог, соединяющих два города через некоторое число промежуточных городов. Пусть также каждая дорога, соединяющая два города, имеет некоторую пропускную способность. Найти максимальный поток в данной сети, учитывая условие консервативности (т.е. для любого промежуточного города величина потока, пришедшая в город равна величине потока вышедшего из города). Позднее в своей книге «Потоки в сетях» (1962), Форд и Фалкерсон дали более точную ссылку: в 1955 году Харрис, в соавторстве с Россом, сформулировали простую модель для трафика в транспортных сетях, и рассматривали эту задачу (прим. – задачу о минимальном разрезе). Речь идет о секретном отчете Харриса и Росса «Фундаментальный метод оценки пропускных способностей транспортных сетей», датированном 24 октября 1955, и предназначенном для ВВС США. В отличие от Форда и Фалкерсона, центральной задачей для Харриса и Росса была задача о минимальном разрезе. А ее применением: нахождение слабых мест в системе железных дорог СССР. (А именно, минимальному разрезу здесь соответствует минимальный набор транспортных путей, уничтожение которого нанесет критический ущерб транспортному сообщению СССР).  Рис. 2. Сеть железных дорог СССР. Иллюстрация из книги [1] §1.4. Метод Форда-Фалкерсона Теорема Форда и Фалкерсона о связи минимального потока и максимального разреза позволяет обосновать следующий общий метод решения задачи о максимальном потоке. Идея состоит в том, что произвольный поток в сети можно дополнить до максимального. По произвольному потоку f рассмотрим «остаточную сеть» этого потока. Ребрами сети будут исходные ребра графа с пропускной способностью cf(uv) = c(uv) – f(uv), а также обратные ребра с пропускной способностью cf(uv) = f(vu). Метод Форда и Фалкерсона состоит в нахождении в остаточной сети произвольного пути из источника в сток, и дополнении существующего потока (изначально нулевого) вдоль этого пути. Теорема о максимальном потоке и минимальном разрезе позволяет обосновать тот факт, что в случае если такого пути не существует, то поток является максимальным. В оригинале этот метод был сформулирован в 1956 без использования «остаточной сети», однако его описание в терминах обычной сети очень громоздко, поэтому мы его здесь не приводим. Термин «остаточная сеть» появился позднее, и в настоящее время является одним из основных инструментов исследователей в области потоков. §1.5. Алгоритм Эдмондса-Карпа Однако, в общем случае метод Форда и Фалкерсона не является корректным. Существует пример сети с иррациональными пропускными способностями, для которой алгоритм Форда и Фалкерсона не остановится (будет работать «бесконечное время»). Для сетей с целочисленными пропускными способностями время работы составляется O(UVE), где U – максимальная пропускная способность, V – количество вершин и E количество ребер в сети. Сети с рациональными пропускными способностями могут быть сведены к целочисленному случаю путем домножения на наибольший общий делитель знаменателей всех дробей. В 1969 году Эдмондсом и Карпом была предложена модификация этого алгоритма, позволяющая получить гарантированное время O(VE^2) работы алгоритма следующим способом: на каждом шаге путь из источника в сток нужно выбирать не произвольный, а кратчайший. В этом случае удается доказать оценку O(VE) на число фаз работы алгоритма. Искомая оценка следует из того, что в неориентированном графе возможно найти расстояние между двумя вершинами за время O(E). §1.6. Дальнейшие улучшения алгоритма построения максимального потока В 1970 году Дициц опубликовал принципиально новый алгоритм нахождения максимального потока, основанный на поиске псевдомаксимального ("блокирующего") потока во вспомогательной сети. Блокирующий поток – это поток, величину которого невозможно улучшить путем лишь увеличения потока вдоль отдельных ребер. Строить такой поток Диниц предлагал при помощи классического алгоритма поиска «в ширину». Другое направление исследований – улучшенные алгоритмы для нахождения максимального потока в сети с целочисленными пропускными способностями. Метод, предложенный Эдмондсом и Карпом в 1972 году (и независимо Диницом в 1973) получил название метода масштабирования пропускных способностей (capacity scaling). Идея метода проста: поток в сети с пропускными способностями, равными половине пропускных способностей исходной сети, мы легко можем получить поток в исходной сети путем умножения его значения на 2. Отдельно нужно обрабатывать ребра с нечетными пропускными способностями. Полученный алгоритм имеет время работы O(nm log U), где n – число вершин сети, m – число ребер, U – максимальная пропускная способность. Карзанову в 1974г удалось, с помощью модификации алгоритма Диница, добиться оценки быстродействия O(n^3). Им также впервые было введено понятие “предпотока”. В 1978г Малхотри, Кумару м Махешвари (Malhotra, Kumar, Maheshwari) удалось повторить этот результат, однако их алгоритм отличался от алгоритма Карзанова. Лучший из известных на сегодняшний день алгоритмов был предложен в 1997 году Гольдбергом и Рао (Goldberg, Rao). В качестве вспомогательной процедуры алгоритм использует структуру данных, полученную Гольдбергом и Тарьяном (Tarjan). В заключение приведем сводную хронологическую таблицу результатов, полученных для задачи о максимальном потоке (везде далее n – число вершин сети, m – число ребер, U – максимальная пропускная способность ребер сети)  Глава 2. Теория паросочетаний §2.1. Паросочетание в двудольном графе Основы теории паросочетаний в двудольных графах были заложены Фробениусом (сформулировавшим их в терминах матриц и детерминантов) и Кёнигом. В статье Кёнига (1915г), представленной ранее в Венгерской Академии Наук он описал способ построение двудольного графа по произвольной матрице (a_ij): вершины графа соответствуют строкам и столбцам матрицы, при этом ребро между строкой i и столбцом j существует в том и только том случае, когда a_ij не равно нулю. Ранее, в апреле 1914 года на Конгрессе Философии Математики в Париже, Кёниг представил теорему о том, что любой регулярный граф без циклов нечетной длины является двудольным. Впервые, задача близкая к задаче о паросочетании была рассмотрена Кёнигом в 1916 году. Он доказал, что если требуется расположить на квадратной доске размера n*n (при этом часть клеток доски может отсутствовать) фишки в количестве k*n (при этом на одной клетке может лежать более одной фишки), таким образом что в каждой строке и в каждом столбце находится ровно по k фишек, то такую конфигурацию можно получить путем объединения k конфигураций, для каждой из которой в каждом столбце и каждой строке находится ровно одна фишка. §2.2.Теорема Фробениуса В 1917 году Фробениус доказал следующую теорему: пусть в матрице A = (a_ij) размера n*n выполнено следующее условие: для любой перестановки p выполнено условие a_1p(1)*..*a_np(n) = 0, то для некоторого числа k найдутся k строк и n – k + 1 столбцов матрице А, такие что любой элемент, лежащий на пересечении этих строк и столбцов, равен нулю. Используя построение Кёнига, этот результат можно переформулировать в терминах двудольных графов: для любого двудольного графа G = (V, E), множество вершин которого разбито на доли V1 и V2, такие, что |V1| = |V2| = n, существует совершенное паросочетение в том и только том случае, когда невозможно выбрать k вершин из V1 и n – k + 1 вершин из V2, таких что между этими вершинами не существует ни одного ребра. Что особенно ценно, Фробениус представил простое комбинаторное доказательство этой теоремы. §2.3.Теорема Менгера о непересекающихся путях и теорема Кёнига о паросочетании В 1927 году тополог Карл Менгер сформулировал и доказал следующую теорему. Пусть в неориентированном графе G = (V, E) заданы подмножества P, Q множества вершин V. Тогда максимальное число непересекающихся путей из P в Q равно минимальному размеру множества W вершин, такого что каждый путь из P в Q пересекает W. Интересно, что первоначально теорема была сформулирована в топологических терминах: компактах и регулярных кривых. Позднее, в 1932 году Кёниг обнаружил в доказательстве Менгера неточность. В марте 1931 года на встрече Математического общества Lorand Eotvos в Будапеште, Кёниг представил новый результат, послуживший основой для доказательства теоремы Менгера: мощность максимального паросочетания в двудольном графе равняется минимальному количеству вершин, необходимых для покрытия всех ребер. (По определению, вершина покрывает все ребра, соседние с данной вершиной, и только их). Кёниг ссылался на результаты, полученные Фробениусом, однако не отметил, что его теорема может быть получена из теоремы Фробениуса. Напротив, в основе доказательства полученного Кёнигом лежит принцип дополнения вдоль чередующихся путей (ставший затем фундаментальным в теории паросочетаний). Опубликованы эти результаты были в 1932 году. §2.4. Связь между потоками и паросочетаниями Следующее простое построение позволяет установить связь между потоками в сетях и Паросочетаниями в двудольном графе. Рассмотрим произвольный двудольный граф с множеством вершин V разбитым на доли X и Y. Добавим две дополнительные вершины – источник s и сток t. Добавим ребро sx из источника в каждую вершину доли x и аналогично ребро yt из каждой вершины доли Y в сток. Все пропускные способности положим единичными. Оказывается, что между потоками в построенной сети и паросочетаниями в исходном графе существует взаимнооднозначное соответствие. А потому мощность максимального Паросочетания в исходном графе равняется величине максимального потока. Таким образом, задача о паросочетании является частным случаем задачи о нахождении максимального потока в сети. А потому любой алгоритм нахождения максимального потока можно применить к решению задачи о паросочетании. Однако стоит заметить, что частная задача о паросочетании может быть решена более эффективно, поскольку алгоритм нахождения максимального потока является общим и не использует двудольную природу исходной сети. |
Похожие:
 | Программа по формированию навыков безопасного поведения на дорогах... Авторский коллектив: В. Г. Антонов, д э н., проф., О. Н. Громова д э н., проф., Г. Р. Латфуллин, д э н., проф., А. В. Райченко, д... | | Реферат по методике преподавания математики Научный Решение уравнений содержащих переменную под знаком модуля |
| Реферат по истории науки на тему: «Периодизация истории математики... Методические указания для подготовки к экзамену кандидатского минимума по истории и философии науки | | Программа по формированию навыков безопасного поведения на дорогах... Проф. В. М. Гаврилов, проф. В. А. Голиченков, проф. Л. П. Корзун, проф. А. М. Рубцов, проф. Е. С. Лобакова, доц., к б н |
| Реферат сдается в приемную комиссию вместе с необходимыми для поступления... К вступительному испытанию по специальности поступающий готовит научный реферат. Научный реферат по специальности должен носить исследовательский... |  | Тематика научных рефератов для поступающих в аспирантуру по направлению... К вступительному испытанию по специальности поступающий готовит научный реферат. Научный реферат по специальности должен носить исследовательский... |
| Рабочая программа по истории 8 класс Программа предназначена для изучения курса истории России XIX века на базовом уровне в его традиционном варианте в объеме 40 ч (2... | | Учебно-методический комплекс дисциплины опд. В 1 дополнительные главы... ... |
| Рабочая программа учебной дисциплины Российского государственного медицинского университета (академик ран и рамн, проф. В. С. Савельев, проф. Ю. А. Нестеренко, проф.... | | Гематологический научный центр Заместитель генерального директора по научной работе и инновациям проф., д м н. Менделеева Л. П |
| Гематологический научный центр Заместитель генерального директора по научной работе и инновациям проф., д м н. Менделеева Л. П | | Гематологический научный центр Заместитель генерального директора по научной работе и инновациям проф., д м н. Менделеева Л. П |
| Имитационно-подражательные танцы эвенков Работа учащейся моши «Токкинская... Реферат должен быть написан по истории науки, в соответствии со специальностью, по которой обучается аспирант или соискатель (история... | | А. А. Арефьева Научный Среди основных видов можно выделить: научный туризм; туры истории природы; приключенческий туризм; путешествия в природные заповедники... |
| Программа дисциплины История экономических учений для специальности... «Экономическая теория» экономическая методологии и истории Председатель проф. О. И. Ананьин Зав кафедрой проф. О. И. Ананьин | | Программа дисциплины История экономических учений для специальности... «Экономическая теория» экономическая методологии и истории Председатель проф. О. И. Ананьин Зав кафедрой проф. О. И. Ананьин |
