Реферат по истории математики Научный проф. Верещагин Н. К

Московский государственный университет им М.В. Ломоносова Мехманико - математический факультет Кафедра математической логики и теории алгоритмов Наливайко Павел Владимирович «История изучения теории потоков в сетях» Реферат по истории математики Научный руководитель: проф. Верещагин Н.К. ____________________ Ведущий семинары: к.ф.н. Катречко С.Л. ____________________ Москва, 2008 Оглавление Введение. 3 Для чего нужны быстрые алгоритмы? 4 Глава 1. История изучения теории потоков Начало исследований Эвристика Болдырева Отчет Харриса-Росса Метод Форда-Фалекрсона Алгоритм Эдмондса-Карпа Дальнейшие улучшения алгоритма построения максимального потока Хронологическая таблица результатов 6 Глава 2. Теория паросочетаний Паросочетание в двудольном графе Теорема Фробениуса Теоремы Менгера и Кёнига Связь между потоками и паросочетаниями 13 Глава 3. Задача о назначениях: «взвешенный» вариант задачи о паросочетаниях Монж: оптимальное назначение Теорема Эгервари 1940е годы Ранние 1950е Вычислительные результаты начала 1950х Венгерский метод Куна-Манкреша 16 Глава 4. Дальнейшие исследования в теории потоков Потоки минимальной стоимости Динамические потоки. Задача транспортировки Универсально-максимальные динамические потоки Наибыстрейшие потоки 21 Заключение 25 Библиография 26 Введение Теория потоков в сетях – одно из современных направлений развития компьютерных наук в целом, и теории графов в частности. Многие комбинаторные задачи и линейные программы могут быть сформулированы и эффективно решены в терминах потоков. Сеть представляет собой специальный вид графа. Сеть состоит из вершин и ребер. В практических задачах каждая вершина сети соответствует фабрике, складу, компьютеру, географическому или какому-либо другому объекту. Ребро соединяет пару вершин, в соответствии с дорогами, кабелями или другими каналами связи. В теории потоков, каждое ребро имеет пропускную способность, которая ограничивает количество информации (грузов, товаров...) которое может быть одновременно переправлено по этому ребру. В сети также выделены терминальные вершины. Они могут быть двух типов – источники и стоки. Наглядно сеть можно представить себе как разветвленный трубопровод. Вершинами будут начала (источники) и концы (стоки) трубопровода, а также промежуточные узловые точки. Ребрами – трубы. Поток в сети соответствует жидкости, перемещаемой по трубопроводу. Рис. 1. Поток в сети. Иллюстрация из Wikipedia. Поток в сети, с формальной точки зрения, это неотрицательная вещественнозначная функция, определенная на ребрах сети, обладающая дополнительными условиями консервативности (для каждой нетерминальной вершины сумма потока по входящим ребрам равна сумме потока по исходящим) и подчиненности пропускным способностей (поток по ребру не превышает его пропускной способности). Первая, и самая естественная задача теории потоков – это организовать поток так, чтобы доставлять наибольшее количество потока из источника в сток. Эта задача получила название задачи о максимальном потоке. С потоками в сетях тесно связана задача о паросочетании в двудольном графе. Эта задача возникла раньше, однако, является частным случаем задачи о максимальном потоке. Далее в данной работе мы проследим за развитием исследований в этих областях. Мы постараемся понять, какие были мотивы у ученых для поиска решений этих задач. Основные источники данной работы являются англоязычными. Более того, для многих терминов в русскоязычной литературе даже нет устоявшегося перевода. В таких случаях мы будем в скобках указывать англоязычный термин.

Похожие:

	Программа по формированию навыков безопасного поведения на дорогах... Авторский коллектив: В. Г. Антонов, д э н., проф., О. Н. Громова д э н., проф., Г. Р. Латфуллин, д э н., проф., А. В. Райченко, д...		Реферат по методике преподавания математики Научный Решение уравнений содержащих переменную под знаком модуля
	Реферат по истории науки на тему: «Периодизация истории математики... Методические указания для подготовки к экзамену кандидатского минимума по истории и философии науки		Программа по формированию навыков безопасного поведения на дорогах... Проф. В. М. Гаврилов, проф. В. А. Голиченков, проф. Л. П. Корзун, проф. А. М. Рубцов, проф. Е. С. Лобакова, доц., к б н
	Реферат сдается в приемную комиссию вместе с необходимыми для поступления... К вступительному испытанию по специальности поступающий готовит научный реферат. Научный реферат по специальности должен носить исследовательский...		Тематика научных рефератов для поступающих в аспирантуру по направлению... К вступительному испытанию по специальности поступающий готовит научный реферат. Научный реферат по специальности должен носить исследовательский...
	Рабочая программа по истории 8 класс Программа предназначена для изучения курса истории России XIX века на базовом уровне в его традиционном варианте в объеме 40 ч (2...		Учебно-методический комплекс дисциплины опд. В 1 дополнительные главы... ...
	Рабочая программа учебной дисциплины Российского государственного медицинского университета (ака­демик ран и рамн, проф. В. С. Савельев, проф. Ю. А. Нестеренко, проф....		Гематологический научный центр Заместитель генерального директора по научной работе и инновациям проф., д м н. Менделеева Л. П
	Гематологический научный центр Заместитель генерального директора по научной работе и инновациям проф., д м н. Менделеева Л. П		Гематологический научный центр Заместитель генерального директора по научной работе и инновациям проф., д м н. Менделеева Л. П
	Имитационно-подражательные танцы эвенков Работа учащейся моши «Токкинская... Реферат должен быть написан по истории науки, в соответствии со специальностью, по которой обучается аспирант или соискатель (история...		А. А. Арефьева Научный Среди основных видов можно выделить: научный туризм; туры истории природы; приключенческий туризм; путешествия в природные заповедники...
	Программа дисциплины История экономических учений для специальности... «Экономическая теория» экономическая методологии и истории Председатель проф. О. И. Ананьин Зав кафедрой проф. О. И. Ананьин		Программа дисциплины История экономических учений для специальности... «Экономическая теория» экономическая методологии и истории Председатель проф. О. И. Ананьин Зав кафедрой проф. О. И. Ананьин