WWW.KONF.X-PDF.RU
БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА - Авторефераты, диссертации, конференции
 

Pages:   || 2 | 3 | 4 | 5 |

«ЕРУСАЛИМСКИЙ ЯКОВ МИХАЙЛОВИЧ РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ РЕШЕНИЯ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ НА ОРИЕНТИРОВАННЫХ ГРАФАХ И СЕТЯХ С ОГРАНИЧЕНИЯМИ НА ДОСТИЖИМОСТЬ Специальность: 05.13.17 – ...»

-- [ Страница 1 ] --

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ

«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

На правах рукописи

ЕРУСАЛИМСКИЙ ЯКОВ МИХАЙЛОВИЧ

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДОВ РЕШЕНИЯ



ЭКСТРЕМАЛЬНЫХ ЗАДАЧ НА ОРИЕНТИРОВАННЫХ

ГРАФАХ И СЕТЯХ С ОГРАНИЧЕНИЯМИ

НА ДОСТИЖИМОСТЬ

Специальность: 05.13.17 – теоретические основы информатики диссертация на соискание ученой степени доктора технических наук

Ростов-на-Дону, 2015

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ.....................

1. ОГРАНИЧЕНИЯ НА ДОСТИЖИМОСТЬ РАЗЛИЧНЫХ

ВИДОВ, КРАТЧАЙШИЕ ПУТИ НА ГРАФАХ С ОГРАНИЧЕНИЯМИ НА ДОСТИЖИМОСТЬ....... 24

1.1. Основные определения.......... 24

1.2. Смешанная достижимость на орграфах..... 27

1.3. Магнитная достижимость на орграфах...... 3

1.4. Барьерная достижимость на графах....... 37

1.5. Обсуждение результатов главы 1....... 42

1.6. Выводы по главе 1............. 45

2. СЛУЧАЙНЫЕ БЛУЖДАНИЯ НА ГРАФАХ С ОГРАНИЧЕНИЯМИ НА ДОСТИЖИМОСТЬ....... 46

2.1. Случайные блуждания на графах со смешанной достижимостью............. 48

2.2. Случайные блуждания на графах с монотонной достижимостью............. 52

2.3. Случайные блуждания по графам с вентильной достижимостью............. 59

2.4. Случайные блуждания по графу-решётке.... 66

2.5.Заключение к главе 2............. 78

2.6. Выводы по главе 2.......... 79

3. ПОТОКИ В СЕТЯХ С ОГРАНИЧЕНИЯМИ НА ДОСТИЖИМОСТЬ.............. 80

3.1. Примеры потоков в сетях с ограничениями на достижимость.............

3.2. Основные определения теории потоков в сетях с ограничениями на достижимость.......... 87

3.3. Вычислительный эксперимент....... 91

3.4. Заключение к главе 3............ 96

3.5. Выводы по главе 3......... 97

4. СМЕШАННАЯ ДОСТИЖИМОСТЬ ПОРЯДКА k. СТУПЕНЧАТАЯ ДОСТИЖИМОСТЬ. ОГРАНИЧЕНИЯ НА

ДОСТИЖИМОСТЬ В ТЕРМИНАХ ВЕРШИН....... 98

4.1. Ступенчатая достижимость смешанная достижимость порядка k............. 99

4.2. Смешанная достижимость порядка k......... 104

4.3. Ограничения на достижимость различных видов, определяемы

–  –  –

ВВЕДЕНИЕ

Настоящая работа посвящена ориентированным графам с ограничениями на достижимость и некоторым смежным вопросам теоретической информатики. Ключевых слов в этом предложении несколько. Во-первых, «ориентированным», поскольку в приложениях чаще встречаются и более естественны для использования именно ориентированные графы. Класс ориентированных графов более широк и интересен, чем класс неориентированных графов. В большинстве случаев неориентированный граф можно считать симметрическим ориентированным графом. Вторым ключевым словом или фразой в первом предложении является «граф с ограничениями на достижимость». Именно эти объекты мы и будем рассматривать в нашей работе.

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





Допустимыми на графе с ограничением на достижимость являются не все пути, а пути, удовлетворяющие определенному условию. Это условие называется типом или видом достижимости. Тип достижимости обычно возникает после того, как задано некоторое разбиение множества дуг (вершин) графа, а ограничения на достижимость формулируются с помощью (в терминах) этого разбиения. Почему мы считаем, что графы с ограничениями на достижимость являются по существу новыми объектами, по сравнению с обычными графами? Обычные графы можно считать графами с тривиальными ограничениями на достижимость, но главное не в этом. Как оказалось [38], для большинства известных видов ограничений на достижимость задача о максимальном целочисленном потоке в такой сети является NP-полной в отличие от классической задачи о максимальном целочисленном потоке в сети.

Графовые методы и алгоритмы на графах в настоящее время активно используются в различных областях науки и техники. Их широкая применимость стала и мощным стимулом для их развития. Новый этап развития теории графов можно назвать алгоритмическим, поскольку широкая применимость всегда связана с алгоритмами, позволяющими решать массовые задачи. Сам термин «теория графов» стали заменять термином «Прикладная теория графов» или «Алгоритмическая теория графов» [96, 171, 195]. Всюду в дальнейшем в нашей работе под теорией графов мы понимаем термин «теория графов» именно в этом смысле.

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

(Ю.В. Покорный, О.М. Пенкин, В.Л. Прядиев, А.В. Боровских, В.В. Провоторов и др.), это позволяет решать задачи распространения тепла и колебательные процессы в таких конструкциях).

Важным инструментом тестирования, анализа программ и автоматического распараллеливания является управляющий граф программы (В.В. Воеводин, В.А. Евстигнеев, В.Н. Касьянов, С.В. Огородов, Л. Лампорт, Р. Аллэн, К. Кэннеди, М. Вольф и др.) Среди алгоритмов на графах следует особо выделить алгоритм Е.Дейкстры [178] нахождения кратчайших путей на графах, фактически первый динамический алгоритм, и алгоритм Д. Краскала [205] нахождения легчайшего покрывающего дерева.

Ещё одним выдающимся достижением алгоритмической теории графов стала теория потоков в сетях, созданная Л. Фордом и Д. Фалкерсоном (см. [159] и [185,186]). В настоящий момент теория потоков в сетях находит все большее применение в связи с развитием телекоммуникаций (Internet, мобильная связь, глобальные компьютерные сети, облачные вычислительные системы и т.п. [143–145]), логистики, теории нейронных сетей, биоинформатики (см. напр.[45]). Вот что говорится во введении в книгу М.Ньюмана «Сети: введение» [209]: «Современная теория сетей стала прототипом междисциплинарных исследований: социология, компьютерные науки, химия, экономика, энергетика, транспорт, управление бизнесом и, сравнительно недавно, социальные сети и биоинформатика. Целям и задачам все этих наук служит эта теория». Современное состояние теории сетей изложено в книге Т.

Левиса «Сетевая наука: теория и приложения» [207]. Следует отметить, что с точки зрения общих подходов к теории сетей, то они мало изменились по сравнению с подходом основоположников этой теории Л.Форда и Д.Фалкерсона (см. [159] и [185,186]). В основном её развитие связано с разработкой и совершенствованием алгоритмов решения потоковых задач в сетях (см.[167–170], [179, 180], [187–193], [202–204]). Среди учёных внесших основной вклад в развитие этого направления необходимо назвать Г.Данцига, Е.Диница,Дж. Эдмонтса, Х. Габова, А. Гольдберга, Р. Карпа, В. Кинга, Р.

Тарьяна. Если говорить о развитии общих подходов к теории сетей, то следует особо выделить работу А.Гольдберга и С.Рао [194] и работы О.П. Кузнецова и Л.Ю. Жиляковой по ресурсным сетям [64-72], [97-106].

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

Настоящая работа посвящена, в основном ориентированным графам и сетям с ограничениями на достижимость. Необходимость в рассмотрении ориентированных графов и сетей возникает обычно при рассмотрении прикладных задач. Ограничения на достижимость также характерны для прикладных задач.

Рассмотрим телекоммуникационную сеть. Будем интерпретировать её как граф, вершины которого соответствуют пунктам приема и передачи информации. Дуги соответствуют каналам связи, по которым передается информация между пунктами. В процессе передачи сигнала несущего информацию по каналу связи с ним могут происходить изменения – сигнал может затухать, это может привести к его «потере» в естественном шуме. Имеется два типа основных средств борьбы с этим: пассивные и активные. Первые предполагают улучшение физических характеристик каналов. Это обеспечивает более низкий уровень затухания сигнала и снижение уровня естественного шума в канале. Оптоволоконные каналы, получившие в настоящее время достаточно широкое распространение, являются последним достижением в этой области. Активные средства предполагают использование специальных устройств – усилителей, которые комбинируются со средствами фильтрации. Это позволяет отфильтровать сигнал от шума и поднять его уровень.

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

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

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

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

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

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

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

Главной особенностью задач на графах с ограничениями на достижимость является неприменимость напрямую классических алгоритмов, поскольку они предполагают, что все пути на графе являются допустимыми.

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

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

Для достижения поставленной цели в диссертационной работе решаются следующие задачи:

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

2. Разработать методы решения задач нахождения кратчайших путей на графах при различных ограничениях на достижимость на основе перехода к задаче отыскания кратчайшего пути на развертке из вершины в подмножество вершин.

3. Найти преобразование задачи о случайных блужданиях по вершинам графа с ограничениями на достижимость, которая в исходной постановке не является Марковским процессом к Марковскому процессу на развертке. Предложенное преобразование должно позволить находить вероятность попадания из вершины в вершину на исходном графе как вероятность попадания из вершины в подмножество вершин на развертке.

4. Синтезировать алгоритм нахождения максимального потока в сетях с ограничениями на достижимость в случае, когда поток является функцией на множестве допустимых путей из источника в сток, а развертка интерпретируется как сеть со связанными дугами, для которых определена только суммарная пропускная способность.

5. Найти балансовые соотношения, построить разложение потока в сумму фронтальных потоков, а также его разложение в сумму потоков специального вида для динамических потоков тождественно равных нулю при t 0 и дать оценку сверху средней величины динамического потока на временном промежутке.

6. Исследовать эффект всплеска динамического потока в сети, найти условия на топологию сети, при которых возможно возникновение всплесков, получить оценки величины возможных всплесков.

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

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

В работе использованы методы дискретной математики, в том числе теории графов, комбинаторного анализа, дискретной оптимизации, а также методы алгебры и математического анализа.

Изучение графов с ограничениями на достижимость началось сравнительно недавно. Первые результаты в этой области принадлежат Я.М.Ерусалимскому и Е.О.Басанговой ([12 – 16]). В работах [12, 13, 15] рассматривались частично-ориентированные графы, т.е. такие, которые содержат ориентированные дуги и неориентированные ребра. В качестве допустимых путей на таких графах мы рассматривали смешанные пути двух типов.

Первый тип – смешанная Допустимыми при ОO-достижимость.

достижимости являются только такие пути, которые не проходят подряд по дугам, т.е. дуги такого пути должны «прореживаться» ребрами. При Nдостижимости допустимыми являются только такие пути, которые не проходят подряд по рёбрам частично-ориентированного графа. Рёбра допустимого пути в этом случае должны «прореживаться» дугами.

Рассмотрение частично-ориентированных графов в этих работах было вызвано задачей, связанной с теорией базисов в пространствах Кёте [11].

Существенным моментом в этих работах стали ограничения на множество допустимых путей, а не то, что рассматривались частично-ориентированные графы. В работах [14, 62] впервые было сформулировано понятие «ориентированный граф со смешанной достижимостью», состоящее в следующем – множество дуг такого графа представляет собой объединение попарно непересекающихся множеств U N и U Z. Смешанным путем на таком графе называется путь, на котором по дугам из множества U Z нельзя проходить более одного раза подряд. Граф, на котором рассматриваются только смешанные пути, мы назвали графом со смешанной достижимостью. Основным методом для решения задач на таких графах оказалось построение вспомогательного графа, путям на котором соответствуют допустимые пути на графе со смешанной достижимостью. Это позволило свести задачу о кратчайших путях на графе со смешанной достижимостью к задаче о кратчайших путях на вспомогательном графе, который мы назвали развёрткой. Развертка в случае смешанной достижимости содержит в два раза больше вершин, чем исходный граф, а количество её дуг определяется формулой U 2U N U Z. (0.1) Это означает, что трудоемкость решения задачи о кратчайших путях на графах со смешанной достижимостью такая же, как и на обычных графах.

Для графов со смешанной достижимостью были рассмотрены классические задачи о кратчайших путях, случайных блужданиях, получен критерий эйлеровости таких графов. Наиболее сложной оказалась задача о максимальном потоке в таких сетях. Возникшие трудности связаны с появлением на вспомогательном графе новых дуг (одной дуге из множества U N на вспомогательном графе соответствует две дуги). Если полагать, что новая дуга имеет такую же пропускную способность, как и дуга её породившая, мы можем получить на вспомогательном графе поток, который нельзя будет интерпретировать, как поток на исходном графе.

Загрузка...

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

Во всех рассмотренных случаях «идеология» остаётся прежней – построение вспомогательного графа – развёртки и замена исходной задачи на графе с ограничениями на достижимость соответствующей задачей на развертке (без ограничений на достижимость). Это позволяет применять известные или соответствующим образом модифицированные алгоритмы для решения таких задач как задача о кратчайшем пути или задача о случайных блужданиях частицы по графу. Заметим, что последняя задача, в нашем случае, не является Марковской.

Наиболее сложными оказались потоковые задачи. Они потребовали существенного пересмотра даже исходной постановки. Пришлось пересмотреть базовое понятие потока, поскольку определение Форда-Фалкерсона [185] учитывает только локальную структуру графа, и никак не учитывает – по каким путям транспортируется поток. Важной для нашего понимания стала работа [10], в которой приведена теорема о декомпозиции потока в виде набора потоков по путям.

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

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

1. Предложен метод построения разверток, представляющих собой вспомогательные графы, для которых имеет место соответствие между множеством допустимых путей на графе с ограничениями на достижимость и множеством путей на развертке. Метод характеризуется общностью для различных типов ограничений на достижимость в ориентированных графах и сетях – смешанной, магнитной, монотонной, вентильной, барьерной, ступенчатой – и отличается от известных аналогов, в частности от метода временной развертки динамического потока, учетом видов ограничений на достижимость, что позволяет эффективно решать оптимизационные задачи на графах широкого класса (стр. 28–29, 33–34, 53–55, 60–62, 100–103, 105– 106, 121–122).

2. Разработан метод решения задач нахождения кратчайших путей на графах при различных ограничениях на достижимость на основе перехода к задаче отыскания кратчайшего пути на развертке из вершины в подмножество вершин, что позволяет применять известный алгоритм Дейкстры, который непосредственно, без перехода к развертке, неприменим для решения задач в исходной постановке (стр.

27–39, 42–44).

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

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

5. Дан конструктивный вывод балансового соотношения, доказана разложимость потока в сумму фронтальных потоков, а также его разложимость в сумму двух потоков специального вида для случая динамических потоков тождественно равных нулю при t 0, что позволяет дать оценку сверху средней величины динамического потока на временном промежутке величиной максимального стационарного потока (стр. 126–140).

6. Исследован эффект всплеска динамического потока в сети, даны необходимые и достаточные условия для топологии сети, при которых возможно возникновение всплесков, при этом максимальная величина всплеска в случае динамических потоков является, наряду с величиной максимального стационарного потока, параметром сети (стр. 149–163).

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

166–180).

8. Даны необходимые и достаточные условия существования функции Гранди графа, отличные от известных условий достаточности; для неориентированных графов доказано существование бесконтурной ориентации, сохраняющей функцию Гранди, что в совокупности позволяет обосновать и синтезировать алгоритм нахождения семейства функций Гранди графа в ориентированном и неориентированном случаях (стр. 184–192).

Все результаты, изложенные в диссертации, получены автором либо самостоятельно, либо при его непосредственном активном творческом участии. В совместных работах, опубликованных со своими учениками, автору принадлежит общая постановка задач и осуществление непосредственного руководства. Диссертационные работы учеников (Басангова Е.О., Логвинов С.Ю., Скороходов В.А., Петросян А.Г., Кузьминова М.В., Водолазов Н.Н.) посвящены в основном алгоритмам решения задач о кратчайших путях, случайных блужданиях, потоках в сетях на графах и сетях с конкретными видами ограничений на достижимость и их реализации. В настоящей работе рассмотрены наиболее общие вопросы теории графов и сетей с ограничениями на достижимость, а также их возможные приложения.

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

Основные положения, выносимые на защиту

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

2. Методы решения задач о кратчайших путях и случайных блужданиях на графах с ограничениями на достижимость на основе перехода к задачам отыскания кратчайшего пути и случайных блужданий из вершины в подмножество вершин на развертке графа.

3. Теория потоков в сетях с ограничениями на достижимость и на ее основе эвристический алгоритм нахождения максимального потока, использующий развертку сети, в которой имеются связанные дуги.

4. Конструктивный вывод балансового соотношения, методы декомпозиции динамического потока с оценкой его средней величины, а также необходимые и достаточные условия для существования всплесков динамического потока.

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

6. Методы нахождения семейства функций Гранди графа в ориентированном и неориентированном случаях на основе связи этой функции на ориентированном графе и на его бесконтурных частичных графах, а также на основе существования бесконтурной ориентации, сохраняющей функцию Гранди неориентированного графа.

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

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

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

Теоретические и практические результаты использованы при выполнении следующих научно-исследовательских работ:

- Внедрены в ФГАНУ «Спецвузавтоматика» при выполнении НИР по госконтракту №2/Бр-13 от 20.042013 и в целом приняты к использованию в основной деятельности данной научно-исследовательской организации.

- Использованы в Институте математики, механики и компьютерных наук имени И.И. Воровича ЮФУ в работах по Проекту Е02-01-231 «Нестандартная достижимость на ориентированных графах». Грант конкурсного центра Минобразования РФ по разделу естественные науки.

- Использованы в Институте математики, механики и компьютерных наук имени И.И. Воровича ЮФУ в работах по проекту 7857 «Графы и сети с нестандартной достижимостью». Ведомственная программа Минобрнауки РФ «Развитие научного потенциала высшей школы», подпрограмма № 3, раздел 3.3.

- Использованы в учебном процессе кафедры алгебры и дискретной математики ЮФУ в лекционных курсах «Конечные графы и сети», «Алгоритмы на графах», «Дискретная математика», читаемых на факультете математики, механики и компьютерных наук ЮФУ, включены в учебное пособие, имеющее гриф Минобразования РФ «Допущено в качестве учебного пособия для студентов высших учебных заведений по направлениям подготовки и специальностям «Прикладная математика и информатика» и «Математика»».

Основные результаты апробированы на ряде научных конференций и семинаров различного уровня, в том числе: Всероссийского: III всероссийской школе-семинаре «Математическое моделирование и биомеханика в современном университете» (Ростов н/Д, 2007), на весенней Воронежской математической школе «Понтрягинские чтения – ХХI (Воронеж, 2010), на весенней Воронежской математической школе «Понтрягинские чтения – ХХII (Воронеж, 2011), на весенней Воронежской математической школе «Понтрягинские чтения – ХХV (Воронеж, 2014), международного: международном конгрессе математиков (Мадрид, 2006), на IV-й Международной конференции «Современные проблемы прикладной математики, теории управления и математического моделирования» (Воронеж, 2011), на Кишинёвском и Одесском семинарах по графам и гиперграфам проф. А.А.Зыкова, на семинаре в Бранденбургском техническом университете (Коттбус, Германия, 2014, рук.

проф. С. Пикенхайм), на VI международной конференции «Современные методы прикладной математики, теории управления и компьютерных технологий» (Воронеж, 2013), на VII международной конференции «Современные методы прикладной математики, теории управления и компьютерных технологий» (Воронеж, 2014), на международных конференциях «Современные методы и проблемы теории операторов и гармонического анализа и их приложения III, IV и V» (Ростов-на-Дону 2013, 2014, 2015), а также на семинаре кафедры алгебры и дискретной математики Южного федерального университета, на семинаре кафедры математического моделирования Южного федерального университета, на семинаре кафедры математической кибернетики ВМК МГУ (2012), на НТС в Самарском государственном аэрокосмическом университете им. акад. С.П. Королева (Самара, 2015, рук. проф. Сергеев В.В.), на семинаре в ИПУ РАН (Москва, 2015, рук. проф. Кузнецов О.П.) Публикации по теме исследования. Результаты диссертационной работы отражены в 46 печатных работах, из них в изданиях из списка ВАК, рекомендованных для опубликования результатов диссертационных исследований – 12, реферируемых международных изданиях – 2, в тематических выпусках журналов из списка ВАК, монографий – 1, учебных пособий – 2.

Работа состоит из введения, семи глав и трех приложений на 253 стр., список литературы содержит 226 наименований.

В главе 1 мы определили несколько видов ограничений на достижимость, описали построение развёрток графов со смешанной и барьерной достижимостью, позволяющих решать задачу о кратчайших путях на графах с ограничениями на достижимость.

Заметим, что «геометрия» графа с ограничениями на достижимость существенно отличается от «геометрии» этого графа без ограничения на достижимость.

В главе 2 мы определяем ещё несколько видов ограничений на достижимость и рассматриваем задачу о случайных блужданиях по вершинам таких графов. Специфика решенных задач состоит в том, что на исходном графе с ограничениями на достижимость они не являются Марковскими. Переход к вспомогательным графам – разверткам позволяет сводить процесс, не являющийся Марковским, к Марковскому. Роль памяти о предыстории блуждания выполняет сама развёртка.

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

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

В главе 3 изучены потоки в сетях с ограничениями на достижимость.

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

В работе Я.М.Ерусалимского и А.Г.Петросяна [50] был предложен эвристический алгоритм «прорыва», который в большинстве случаев позволяет определить – как должны быть розданы пропускные способности по связанным дугам, чтобы возникал максимальный поток и находит его. Этот алгоритм состоит в следующем: на развёртке мы находим простой путь из источника в сток. Этот путь насыщается потоком, после чего пропускные способности обычных дуг, принадлежащих этому пути, уменьшаются на величину найденного потока, также уменьшаются суммарные пропускные способности связанных дуг, по которым проходит найденный путь. Затем дуги нулевой пропускной способности удаляются из графа, и всё повторяется заново.

Ещё более ярко особенности графов с ограничениями на достижимость проявляются на графах с барьерной достижимостью. Рассмотренные в § 3.1 примеры показали, что необходимо четко разобраться с понятием поток на графе с ограничениями на достижимость. Классическое определение потока как функции, определенной на множестве дуг, не содержит в себе никаких требований на пути, по которым транспортируется поток и, значит, не учитывает ограничения на достижимость. Определение потока на сети с ограничениями на достижимость как потока на развертке в силу наличия на ней связанных дуг тоже не совсем корректно. Мы определяли в этом случае поток, как функцию, заданную на допустимых путях и удовлетворяющую естественным ограничениям, при которых он является потоком в смысле ФордаФалкерсона.

В главе 4 мы определили ещё два вида ограничений на достижимость:

смешанную порядка k и ступенчатую. Первая при k = 1 совпадает с обычной смешанной достижимостью, определенной в первой главе. Для этих видов достижимости построены развертки, это позволяет перенести на графы со ступенчатой и смешанной достижимостью порядка k результаты глав I–III.

В третьем параграфе введены аналоги всех видов ограничений на достижимость в терминах вершин графов. Для каждого вершинного типа ограничений на достижимость описано его сведение к соответствующему типу ограничений на достижимость, заданных в терминах дуг графа. Это делает справедливыми для таких графов результаты глав 1–3.

В четвертом параграфе рассмотрена задача о маршрутизации в информационной сети, в которой имеются дуги, на которых происходит затухание сигнала и вершины, в которых происходит усиление сигнала. В связи с этой задачей определен новый тип ограничений на достижимость – с затуханием на дугах и усилением в вершинах. Для таких графов построена развертка, решение задачи о маршрутизации в таких информационных сетях равносильно нахождению кратчайшего пути между вершинами на графе с затуханием на дугах и усилением в вершинах. Построение развертки делает справедливыми для таких графов результаты глав 1–3.

В главе 5 мы рассматриваем задачи о динамических потоках, т.е.

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

Теорема 5.3.

Пусть (u, t ) динамический поток в сети G( X,U, f, c), равный нулю на всех дугах сети при t 0, тогда для произвольного T N, существуют такие потоки 1 (u, t ), 2 (u, t ), для которых выполнены следующие условия:

1. Потоки 1 (u, t ), 2 (u, t ) равны нулю на всех дугах сети при t 0 ;

2. Поток 1 (u, t ) равен нулю на всех дугах графа при t T ;

3. V, t V 1, t, t [0;T ] ;

4. V 2, t 0, t [0;T ] ; 5. (u, t ) 1 (u, t ) 2 (u, t ), t Z.

Доказана оценка величины динамического потока и рассмотрена задача о максимальном всплеске потока в динамической сети.

Обозначим через vmax величину максимального стационарного потока, сети, тогда справедливо:

V,[0;T ] vmax T.

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

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

В приложении 1 Приведены новые доказательства известных комбинаторных тождеств для степеней натуральных чисел и факториала, доказаны их полиномиальные обобщения.

В приложении 2 подробно рассмотрены конкретные примеры решения задачи о случайных блужданиях и максимальном потоке.

В приложении 3 описано задание графов с ограничениями на достижимость различных типов и сетей со связанными дугами.

В приложении 4 содержится акты использования результатов работы.

1. ОГРАНИЧЕНИЯ НА ДОСТИЖИМОСТЬ РАЗЛИЧНЫХ ВИДОВ.

КРАТЧАЙШИЕ ПУТИ НА ГРАФАХ С ОГРАНИЧЕНИЯМИ НА ДОСТИЖИМОСТЬ

В §1.1 этой главы мы приводим основные понятия и определения необходимые в дальнейшем. Далее мы определяем несколько видов ограничений на достижимость: смешанную, магнитную и барьерную достижимости.

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

1.1. Основные определения В этом небольшом параграфе мы приведем основные определения необходимые в дальнейшем. Будем пользоваться определениями из [46].

Определение 1.1. Ориентированным графом (далее графом) будем X ( ) – множество, называемое множеназывать тройку G( X,U, f ), где ством вершин, U – множество, называемое множеством дуг графа, f : U X X – отображение, называемое отображением инцидентности.

Будем рассматривать конечные графы, т.е. такие, у которых множества X и U - конечны, т.е. X, U.1

–  –  –

взвешенный, будем считать, что веса всех дуг равны единице. Ясно, что в этом случае длина пути из n (n N ) дуг равна n.

Существуют и другие определения графа. Приведем их и поясним, почему мы выбрали приведенное выше определение.

Определение графа по К. Бержу (Berge C.)[173]. Ориентированным графом называется двойка G( X, ), где X ( ) – множество вершин, – многозначное отображение из множества X во множество X, т.е. правило сопоставляющее каждому x из множества X некоторое подмножество (x) множества X. Дугами графа Бержа называют упорядоченные пары вершин ( x; y), где y (x).

Чем нам «не нравится» это определение? Это определение не допускает наличия на графе кратных дуг, т.е. нескольких дуг, соединяющих данную упорядоченную пару вершин. Как будет видно в дальнейшем, это определение существенно сузит класс рассматриваемых задач, да и с точки зрения приложений оно недостаточно, поскольку кратность дуг в приложениях существенна (кратные дуги могут иметь разные длины (стоимость, пропускную способность и т.п.)). Однако в главе VII мы будем использовать именно это определение, поскольку функция Гранди, которую мы рассматриваем, определена для графа Бержа.

Приведем ещё одно определение ориентированного графа, которое неприемлемо для нас по той же самой причине.

Определение ориентированного графа по А.А.Зыкову [90]. Ориентированным графом называется двойка G( X,U ), где X ( ) – множество вершин графа, U ( X X ) – множество дуг графа.

В этом определении дуги графа – это упорядоченные пары вершин.

Значит, это определение, как и определение Бержа, не допускает наличия на графе кратных дуг.

Ясно, что определение 1.1 ориентированного графа допускает наличие на графе кратных дуг, при этом, если нам потребуется, мы можем перейти от определения 1.1 к определению К. Бержа или А.А. Зыкова.

Действительно, если нам задан граф G( X,U, f ),определим многозначное отображение f, действующее их множества X во множество X, пра

–  –  –

нятно, что кратность дуг (если она имела место) при этом переходе исчезнет.

Аналогично, чтобы перейти от графа G( X,U, f ) к графу А.А. Зыкова положим U f { f (u)} и рассмотрим граф G( X,U f ). Ясно, что при таком u U переходе кратность дуг, если она имела место, исчезает.

1.2. Смешанная достижимость на орграфах Пусть G( X,U, f ) – орграф. Множество дуг графа U U R U Z, U R, U Z. Дуги множества U R будем называть нейтральными, а множества U Z - запрещенными.

Определение 1.3. Смешанным путем на графе G( X,U U R U Z, f ) будем называть путь : [1; n] N U, удовлетворяющий дополнительному условию:

i ([1; n 1]N )( (i) U Z (i 1) U R ).

Пример 1.1.

Рассмотрим граф, изображенный на рис. 1.1.

Рис. 1.1.

На рисунке запрещенные дуги обозначены пунктиром. Ясно, что путь, проходящий через вершины 1–7–5–6, не является смешанным, также не является смешанным путь 1–2–3–4–5–6. Единственный смешанный путь, соединяющий вершину 1 с вершиной 6, проходит через вершины1–8–4–5–6.

Определение 1.4. Графом со смешанной достижимостью будем называть граф G( X,U U R U Z, f ), на котором допустимыми являются только смешанные пути (см. определение 1.3).

Приведенный пример 1.1 показывает, что на графах со смешанной достижимостью нарушается основное свойство путей на обычных графах, которое мы называем аддитивным: «Если существует путь xy, соединяющий вершину x с вершиной y, и существует путь yz, соединяющий вершину y с вершиной z, то существует путь xz, соединяющий вершину x с вершиной z, проходящий через вершину y, получаемый склейкой имеющихся путей». Действительно на рис. 1.1 путь 1 2 3 является смешанным путем, путь также является смешанным путем, а путь 1 2 3 4 5 6 на графе со смешанной достижимостью не существует.

Заметим, что «геометрия» графа со смешанной достижимостью существенно отличается от «геометрии» этого графа без ограничения на достижимость. Действительно, если граф рис. 1.1 считать обычным графом, то кратчайший путь из первой вершины в шестую вершину – 1 7 5 6 имеет длину 3 (мы считаем, что длина любой дуги на этом графе равна единице), а кратчайший смешанный (и единственный) путь на этом графе из первой вершины в шестую 1 8 4 5 6 имеет длину равную 4.

Построение развёртки - вспомогательного графа для графа со смешанной достижимостью В этом пункте мы опишем построение развёртки – вспомогательного графа для графа со смешанной достижимостью G( X,U U R U Z, f ). Множеством вершин этого графа является множество X X, где X – дубликат множества X, т.е. каждой вершине x X соответствует x X. Если u U R, f (u) ( x, y), то на вспомогательном графе ей соответствует две дуги, первая соединяет вершину x с вершиной y, а вторая дуга начинается в вершине x и заканчивается в вершине y. Если u U z, f (u) ( x, y), то на вспомогательном графе её соответствует дуга, которая соединяет вершину x с вершиной y.

На рис. 1.2 приведена развёртка G для графа рис.1.1:

Рис. 1.2.

Очевидно, что из построения развёртки G следует:

Утверждение 1.1. Вершина y достижима из вершины x на графе со смешанной достижимостью G( X,U U R U Z, f ) тогда и только тогда, когда на развёртке G существует путь из вершины x хотя бы в одну из вершин множества { y, y }. Между множеством допустимых путей из вершины x в вершину y на графе со смешанной достижимостью G( X,U U R U Z, f ) и множеством путей из вершины x во множество вершин { y, y } на развёртке существует взаимно однозначное соответствие.

Справедливость этого утверждения следует из конструкции развертки.

Если на исходном графе заданы длины дуг, то развертку тоже считаем взвешенным графом, полагая длины его дуг равными длинам породивших их дуг исходного графа.

Утверждение 1.2. Длина кратчайшего пути из вершины x в вершину y на графе со смешанной достижимостью G( X,U U R U Z, f ) равна длине кратчайшего пути из вершины x в вершины множества { y, y } на развёртке G. Этот кратчайший смешанный путь может быть восстановлен по кратчайшему пути из вершины x во множество вершин { y, y } на развёртке G.

Ясно, что этот кратчайший путь на графе G может быть найден с помощью алгоритма Дейкстры [178]. Из сделанных ранее замечаний следует, что никакая модернизация алгоритма Дейкстры без перехода к развёртке невозможна.

Вернёмся к примеру 1.1 и найдем кратчайший смешанный путь из вершины 1 в вершину 6. На развёртке этого графа (рис. 1.2) кратчайший путь из вершины 1 во множество вершин {6, 6} имеет длину 4:

1 8 4 5 6. Этот путь «восстанавливается» в смешанный путь длины 4 на исходном графе: 1 8 4 5 6.



Pages:   || 2 | 3 | 4 | 5 |
 
Похожие работы:

«САВОСТЬЯНОВА ИРИНА ЛЕОНИДОВНА МЕТОДИЧЕСКАЯ СИСТЕМА ФОРМИРОВАНИЯ ПРОФЕССИОНАЛЬНОЙ ИНФОРМАЦИОННОЙ КОМПЕТЕНТНОСТИ БУДУЩИХ БАКАЛАВРОВ-ЭКОНОМИСТОВ В ДИСЦИПЛИНАХ ИНФОРМАЦИОННОГО ЦИКЛА 13.00.02 – Теория и методика обучения и воспитания (информатика, уровень высшего профессионального образования) Диссертация на соискание ученой степени кандидата...»

«Баженова Ирина Васильевна МЕТОДИКА ПРОЕКТИВНО-РЕКУРСИВНОГО ОБУЧЕНИЯ ПРОГРАММИРОВАНИЮ СТУДЕНТОВ МАТЕМАТИЧЕСКИХ НАПРАВЛЕНИЙ ПОДГОТОВКИ 13.00.02 – Теория и методика обучения и воспитания (информатика, уровень профессионального образования) Диссертация на соискание учёной степени кандидата педагогических наук Научный руководитель: доктор...»

«Федосеева Марина Васильевна СЕТЕВЫЕ СООБЩЕСТВА КАК СРЕДСТВО ОРГАНИЗАЦИИ УЧЕНИЧЕСКОГО САМОУПРАВЛЕНИЯ 13.00.02 — теория и методика обучения и воспитания (информатизация образования) Диссертация на соискание ученой степени кандидата педагогических наук Научный руководитель академик РАО, доктор педагогических наук, профессор Кузнецов А.А. МОСКВА 201...»

«Егоров Алексей Юрьевич ФОРМИРОВАНИЕ И РАЗВИТИЕ РЫНКА ОРГАНИЧЕСКОЙ АГРОПРОДОВОЛЬСТВЕННОЙ ПРОДУКЦИИ (НА ПРИМЕРЕ ЦФО) Специальность 08.00.05 Экономика и управление народным хозяйством (экономика, организация и управление предприятиями, отраслями, комплексами – АПК и сельское хозяйство) ДИССЕРТАЦИЯ на соискание ученой степени кандидата экономических наук...»

«МИНИСТЕРСТВО ЗДРАВООХРАНЕНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ФГБУ «ЦЕНТРАЛЬНЫЙ НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ ОРГАНИЗАЦИИ И ИНФОРМАТИЗАЦИИ ЗДРАВООХРАНЕНИЯ» _ СТЕРЛИКОВ СЕРГЕЙ АЛЕКСАНДРОВИЧ ОПТИМИЗАЦИЯ СИСТЕМЫ ОКАЗАНИЯ ПРОТИВОТУБЕРКУЛЕЗНОЙ ПОМОЩИ НАСЕЛЕНИЮ РОССИЙСКОЙ ФЕДЕРАЦИИ 14.02.03 – Общественное здоровье и здравоохранение Диссертация на соискание ученой степени доктора медицинских наук Научный консультант: доктор медицинских наук, профессор Нечаева Ольга Брониславовна Москва,...»

«НИКОНОРОВ Артем Владимирович ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ВОССТАНОВЛЕНИЯ ЦВЕТНЫХ И...»

«ВОЙТКО ДМИТРИЙ АЛЕКСЕЕВИЧ КОМПЛЕКСНЫЙ ПОДХОД К СОВЕРШЕНСТВОВАНИЮ ОРГАНИЗАЦИИ ЛЕЧЕБНО-ДИАГНОСТИЧЕСКОЙ ПОМОЩИ ПРИ РАКЕ ПРЕДСТАТЕЛЬНОЙ ЖЕЛЕЗЫ 14.02.03 Общественное здоровье и здравоохранение Диссертация на соискание ученой степени кандидата медицинских наук НАУЧНЫЕ РУКОВОДИТЕЛИ: доктор...»

«Рафикова Юлия Юрьевна ГЕОИНФОРМАЦИОННОЕ КАРТОГРАФИРОВАНИЕ РЕСУРСОВ ВОЗОБНОВЛЯЕМЫХ ИСТОЧНИКОВ ЭНЕРГИИ (на примере Юга России) Диссертация на соискание ученой степени кандидата географических наук Специальность 25.00.33 «Картография» Научный руководитель Доктор географических наук, профессор Б.А. Новаковский Москва 201 Содержание Введение.. Глава 1....»

«Денисов Дмитрий Вадимович АНТЕННЫЕ И ДИФРАКЦИОННЫЕ ХАРАКТЕРИСТИКИ ЛИНЗ ЛЮНЕБЕРГА ПРИ ОБЛУЧЕНИИ ПОЛЕМ КРУГОВОЙ ПОЛЯРИЗАЦИИ Специальность 05.12.07 – Антенны, СВЧ устройства и их технологии Диссертация на соискание ученой степени кандидата технических наук Научный руководитель – доктор технических наук, профессор Панченко Б.А. Екатеринбург – 2015...»

«Конфектов Михаил Николаевич Картографирование типов застройки Подмосковья по космическим снимкам Диссертация на соискание ученой степени кандидата географических наук по специальности 25.00.33 картография Научный руководитель: в. н. с., д. г. н. Кравцова В. И. Москва, 2015 Содержание ВВЕДЕНИЕ 1. ГЕОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ УСЛОВИЯ ФОРМИРОВАНИЯ ЗАСТРОЙКИ...»

«ФИРСОВА Екатерина Валериевна ОБУЧЕНИЕ ДИСКРЕТНОЙ МАТЕМАТИКЕ СТУДЕНТОВ ВУЗА С ИСПОЛЬЗОВАНИЕМ ДИСТАНЦИОННЫХ ОБРАЗОВАТЕЛЬНЫХ ТЕХНОЛОГИЙ (на примере специальности/профиля «прикладная информатика (в экономике)») 13.00.02 – теория и методика обучения и воспитания (математика) ДИССЕРТАЦИЯ на соискание ученой степени...»

«Зайцев Владислав Вячеславович РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДИКИ ПРОЕКТИРОВАНИЯ БАЗЫ МЕТАДАННЫХ ХРАНИЛИЩА ГЕОДАННЫХ Специальность 25.00.35 – «Геоинформатика» ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук Научный руководитель д-р техн. наук, проф. А.А. Майоров Москва 2015   ОГЛАВЛЕНИЕ...»

«ВАЙСМАН ДАВИД ШУНЕВИЧ СОВЕРШЕНСТВОВАНИЕ СИСТЕМЫ ИНФОРМАЦИОННОГО ОБЕСПЕЧЕНИЯ ОЦЕНКИ И АНАЛИЗА СМЕРТНОСТИ НАСЕЛЕНИЯ НА УРОВНЕ СУБЪЕКТА РОССИЙСКОЙ ФЕДЕРАЦИИ 14.02.03 – Общественное здоровье и здравоохранение Диссертация на соискание ученой степени доктора медицинских наук Научный консультант: доктор медицинских наук, профессор И.М....»

«Морозов Роман Викторович МОДЕЛЬ И МЕТОДЫ ИНТЕЛЛЕКТУАЛЬНОЙ ПОДДЕРЖКИ ПРИНЯТИЯ УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ ПО ПОЖАРНОЙ БЕЗОПАСНОСТИ ЗДАНИЙ СФЕРЫ ОБРАЗОВАНИЯ 05.13.01 – Системный анализ, управление и обработка информации (информатика, вычислительная техника и управление) Диссертация на соискание ученой степени кандидата технических наук Научный...»

«ВОРОБЬЕВ МИХАИЛ ВИКТОРОВИЧ НАУЧНОЕ ОБОСНОВАНИЕ СИСТЕМЫ ОБЕСПЕЧЕНИЯ ИНФЕКЦИОННОЙ БЕЗОПАСНОСТИ МЕДИЦИНСКОГО ПЕРСОНАЛА И ПАЦИЕНТОВ ПРИ ОКАЗАНИИ СТОМАТОЛОГИЧЕСКОЙ ПОМОЩИ 14.02.03 – Общественное здоровье и здравоохранение Диссертация на соискание ученой степени доктора медицинских наук Научный консультант: Доктор медицинских наук, профессор...»

«ЖЕЛЕЗНЯКОВ ВЛАДИМИР АНДРЕЕВИЧ Разработка методики геоинформационного обеспечения оперативного обновления электронных карт большого объёма с использованием банка пространственных данных Специальность 25.00.35 – Геоинформатика Диссертация на соискание учёной степени кандидата технических наук Научный руководитель: доктор...»

«Шаталов Павел Сергеевич СИСТЕМА ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ ПО УПРАВЛЕНИЮ ПРИРОДНЫМИ ПОЖАРАМИ С ИСПОЛЬЗОВАНИЕМ ВЫСОКОПРОИЗВОДИТЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ И ДАННЫХ КОСМИЧЕСКОГО МОНИТОРИНГА 05.13.01 Системный анализ, управление и обработка информации (информатика, вычислительная техника, управление) Диссертация на соискание ученой степени...»

«УДК 316.32 АБДУЛЛАЕВ Ильхом Заирович «ИНФОРМАТИЗАЦИЯ ОБЩЕСТВЕННО-ПОЛИТИЧЕСКОЙ ЖИЗНИ В УСЛОВИЯХ ГЛОБАЛИЗАЦИИ РАЗВИТИЯ» Специальность – 23.00.04 – Политические проблемы мировых систем и глобального развития Диссертация на соискание ученой степени доктора политических наук Ташкент – 2007 ОГЛАВЛЕНИЕ с. 3 – 15 ВВЕДЕНИЕ Глава 1. Понятийно-категориальные основы теории информационного...»

«Родионова Татьяна Васильевна Исследование динамики термокарстовых озер в различных районах криолитозоны России по космическим снимкам Диссертация на соискание ученой степени кандидата географических наук по специальности 25.00.33 картография Научный руководитель: в. н. с., д. г. н. Кравцова В. И. Москва 2013 Оглавление Введение...3 1. Термокарстовые озера...»

«Андреева Надежда Михайловна МЕТОДИКА ИСПОЛЬЗОВАНИЯ ДОРОЖНЫХ КАРТ ПРИ ЭЛЕКТРОННОМ ОБУЧЕНИИ СТУДЕНТОВ ИНФОРМАТИКЕ (на примере экономических и биологических направлений подготовки) 13.00.02 – Теория и методика обучения и воспитания (математика, уровень профессионального образования) ДИССЕРТАЦИЯ на соискание учёной степени кандидата...»









 
2016 www.konf.x-pdf.ru - «Бесплатная электронная библиотека - Авторефераты, диссертации, конференции»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.