» » по истории математики Научный ру

Реферат на тему по истории математики Научный ру


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


Московский государственный университет им М.В. Ломоносова

Мехманико - математический факультет

Кафедра математической логики и теории алгоритмов

Наливайко Павел Владимирович

«История изучения теории потоков в сетях»

Реферат по истории математики

Научный руководитель: проф. Верещагин Н.К.

____________________

Ведущий семинары: к.ф.н. Катречко С.Л.

____________________

Москва, 2008

Оглавление

Введение.

3

Для чего нужны быстрые алгоритмы?

4

Глава 1. История изучения теории потоков

· Начало исследований

· Эвристика Болдырева

· Отчет Харриса-Росса

· Метод Форда-Фалекрсона

· Алгоритм Эдмондса-Карпа

· Дальнейшие улучшения алгоритма построения максимального потока

· Хронологическая таблица результатов

6

Глава 2. Теория паросочетаний

· Паросочетание в двудольном графе

· Теорема Фробениуса

· Теоремы Менгера и Кёнига

· Связь между потоками и паросочетаниями

13

Глава 3. Задача о назначениях: «взвешенный» вариант задачи о паросочетаниях

· Монж: оптимальное назначение

· Теорема Эгервари

· 1940е годы

· Ранние 1950е

· Вычислительные результаты начала 1950х

· Венгерский метод Куна-Манкреша

16

Глава 4. Дальнейшие исследования в теории потоков

· Потоки минимальной стоимости

· Динамические потоки. Задача транспортировки

· Универсально-максимальные динамические потоки

· Наибыстрейшие потоки

21

Заключение

25

Библиография

26

Введение

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

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

Наглядно сеть можно представить себе как разветвленный трубопровод. Вершинами будут начала (источники) и концы (стоки) трубопровода, а также промежуточные узловые точки. Ребрами – трубы. Поток в сети соответствует жидкости, перемещаемой по трубопроводу.

Рис. 1. Поток в сети. Иллюстрация из Wikipedia.

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


Другие рефераты


  • Рейтинг@Mail.ru
  • Яндекс.Метрика