Выпускная работа по «Основам информационных технологий»




Скачать 268.49 Kb.
Дата30.08.2016
Размер268.49 Kb.


БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Выпускная работа по


«Основам информационных технологий»


Магистрант

кафедры информационного и программно-

математического обеспечения

автоматизированных производств

Журак Ирина

Руководители:

доцент Пилипчук Людмила Андреевна,

ст. преподаватель Кожич Павел Павлович


Минск – 2009 г.

Оглавление


Оглавление 3

Список обозначений ко всей выпускной работе 4

Реферат на тему «Применение ИТ при оптимизации мультипотоков в обобщенных сетях» 5

Введение 5

Глава 1 (обзор литературы). 6

Глава 2 (методика исследований) 8

Глава 3 (обсуждение результатов) 17

Заключение 17

Список литературы к реферату. 18

Предметный указатель к реферату. 20

Интернет ресурсы в предметной области исследования. 21

Действующий личный сайт в WWW (гиперссылка). 22

Граф научных интересов 23

Презентация магистерской диссертации 25

Список литературы к выпускной работе. 28

Приложение А 29

Приложение Б 31




Список обозначений ко всей выпускной работе


ИТ – информационные технологии

СЛАУ – система линейных алгебраических уравнений

ЭВМ – электронно-вычислительная машина

Реферат на тему «Применение ИТ при оптимизации мультипотоков в обобщенных сетях»

Введение


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

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

Линейное программирование, открытое в 30-е гг. XX вв., продолжает развиваться благодаря усовершенствованию ЭВМ. Разрабатываются общие методы решения линейных задач большой размерности, которые стали возможны с развитием ИТ. В современном линейном программировании активно развивается направление, в рамках которого исследуются задачи со специальной структурой и создаются методы, способные эффективно учесть особенности структуры конкретных классов задач, часто встречающихся в приложениях. Использование компьютерных математических пакетов позволяет расширить диапазон реальных приложений; рассматривать больше задач, благодаря сокращению количества рутинных преобразований; сочетать научность, системность, наглядность, межпредметные связи при решении экстремальных задач.

Многие СЛАУ с матрицей большой размерности было бы невозможно разрешить без применения численных методов. Успехи в области вычислительной математики, которая развивается в тесной взаимосвязи с ИТ, в значительной степени способствовали повышению интереса к математике вообще и привели к созданию новых разделов и возможностей исследования.



Глава 1 (обзор литературы).

  1. История развития линейного программирования


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

После гибели античной цивилизации научная жизнь в Европе стала возрождаться только в XV веке. Экстремальные задачи оказались среди тех, которыми интересовались лучшие умы того времени. Если в античные времена экстремальные задачи исследовались только геометрическими методами, и каждая задача для своего решения требовала специфического приема, то в XVII веке появились общие методы изучения экстремальных задач, которые привели к созданию дифференциального и интегрального исчислений. Первые элементы математического анализа были созданы И. Кеплером (1615 год). Открытое И. Кеплером основное свойство экстремумов было оформлено в виде теоремы сначала П. Ферма (для многочленов), потом И. Ньютоном и Г. В. Лейбницем для произвольных функций и носит теперь название теоремы Ферма, согласно которой в точке экстремума непрерывной функции производная функции равна нулю.

С конца XVII до середины XX века теория экстремальных задач прошла огромный путь. В ее развитии приняли участие почти все великие математики прошлого. Кроме упомянутых экстремальными задачами занимались Х. Гюйгенс, К.Ф. Гаусс, А.М. Лежандр, П.Г. Дирихле, Б. Риман, У.Р. Гамильтон, К.Г. Якоби, К.Т. Вейерштрасс, Д. Гильберт и др.

После второй мировой войны (1947 год) американский математик Д. Данциг предложил эффективный метод решения экстремальных задач линейного программирования – симплекс-метод. С начала 50-х годов новый раздел экстремальных задач стал называться линейным программированием и явился первым разделом современной теории экстремальных задач, которая отличается от классической теории экстремальных задач наличием в ней методов решения задач с нестрогими неравенствами и порождаемыми последними замкнутыми множествами.

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

Теория экстремальных задач продолжает развиваться и в наши дни. В последние годы возникли и сейчас находятся в центре внимания многих математиков большие экстремальные задачи.

Каждая конечномерная экстремальная задача имеет два размера: количество ограничений и количество переменных. Если эти размеры большие, то задача называется большой. Для решения больших экстремальных задач используются два подхода: а) совершенствование общих методов решения, б) разработка реализаций общих методов для специальных подклассов задач, имеющих ярко выраженную особую структуру математических моделей. Подход а) в последние годы обогатился новыми методами, основанными как на идеях симплекс-метода, так и на других идеях. Типичным примером реализации подхода б) являются методы решения широко распространенных в приложениях транспортных задач. Математические модели этих задач являются частным случаем задачи (1), и поэтому их можно решить симплекс-методом. Однако если реализовать симплекс-метод с учетом специфики новой модели, то получается метод, который намного эффективнее симплекс-метода. Успехи, достигнутые в решении больших задач, позволяют с помощью современных ЭВМ решать специальные задачи линейного программирования, имеющие миллионы переменных и сотни тысяч основных ограничений. Однако проблема решения больших экстремальных задач не может считаться закрытой, ибо практика постоянно поставляет все новые и новые задачи, которые пока не под силу современным методам и ЭВМ.

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


  1. Обзор литературы


Экстремальные задачи – это один из наиболее часто встречающихся математических объектов. Умение их применять и решать – это то, что нужно практически любому математику в той или иной форме для эффективной научной деятельности. В работах Габасов Р., Кириллова Ф. М. [3] и Альсевич В.В., Габасов Р., Глушенков В. С. [4] рассматриваются задачи линейного программирования и их методы решения.

При рассмотрении сетевых моделей важную роль играют структуры данных, которые наиболее детально описаны в работе Йенсен П., Барнес Д.[7].

Книга Б. Страуструпа "Принципы и практика использования С++" дает описание языка, его ключевых понятий и основных приемов программирования на нем. Это завершенное руководство, написанное создателем языка, которое содержит описание всех средств С++, в том числе управление исключительными ситуациями, шаблоны типа (параметризованные типы данных) и множественное наследование.

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


Глава 2 (методика исследований)

  1. Постановка задачи


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




(2.1.1)






(2.1.2)






(2.1.3)




,

(2.1.4)






(2.1.5)






(2.1.6)

где. Вектор - план (поток), , (- множество планов), если на нем выполняются ограничения (2.1.2)-(2.1.6) задачи. План оптимален, если , .
  1. Технологии исследования с применением ИТ


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

Используя форматы системы Tex, удобно генерировать математические модели (прямые и двойственные неоднородные задачи) с взаимосвязью потоков различных видов. Применение системы Tex дает возможность получать экстремальные неоднородные задачи больших размеров, с большим количеством ограничений. Математическая модель может быть представлена как в форматах системы Tex (dvi, tex), так и в формате PDF документов. Сгенерированные математические модели экстремальных неоднородных задач используются для проверки правильности работы алгоритмов решения и для построения сетевых структур.

При построении решения экстремальной задачи потокового программирования значительную роль играет визуализация данных на компьтере. Наглядное представление сети позволяет указать последовательность действий необходимых для построения решения. Использование графовых структур дает возможность более эффективно решать СЛАУ с большими разреженными матрицами системы. Если иметь представление о компонентах связности и опоре, то можно строить характеристические вектора и вектор псевдопотоков с меньшими затратами памяти и времени выполнения.

Сетевая модель задачи (для случая обобщенной сети):




Рисунок 2.2.1 – Сетевая модель

Важным для сетевых моделей является понятие опоры.






(2.2.1)



(2.2.2)



(2.2.3)

где ; – параметры системы; - вектор неизвестных.



Определение 2.2.1. Опора сети для системы (2.2.1) - (2.2.3) есть множество дуг , такое что система



(2.2.4)

имеет только тривиальное решение для множества и имеет нетривиальное решение для множества , .



Рисунок 2.2.2 – Опора для первого типа потока



Рисунок 2.2.3 – Опора для второго типа потока



Рисунок 2.2.4 – Опора для третьего типа потока



Рисунок 2.2.5 – Опора для четвертого типа потока



Рисунок 2.2.6 – Опора для пятого типа потока

Для решения задач потокового программирования широко используется пакет Mathematica. Пакет Mathematica, разработанный компанией Wolfram Reseach Inc., объединяет возможности аналитических и численных вычислений, визуализации и документирования в единой среде. Система предлагает средства для линейного программирования, статистики, решения задач оптимизации, комбинаторики и теории графов. КТС Mathematica применяется при расчетах в современных научных исследованиях.

Главным достоинством КТС Mathematica является выполнение арифметических действий в символьном виде, то есть так, как это делает человек. При работе с дробями и корнями программа не приводит их в процессе вычислений к десятичному виду, а производит необходимые сокращения и преобразования в столбик, что позволяет избежать ошибок при округлении. Кроме того, КТС Mathematica cодержит библиотеки и для численных вычислений. Например, функция Solve[] ищет решение в символьном виде, а NSolve[] в численном. Любое решение, представленное в символьном виде, можно приближенно представить в виде десятичной дроби: если это возможно исходя из введенных данных, КТС Mathematica выполнит такое приближение (функция N[]).

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

В пакете Mathematica можно создавать собственные программы и библиотеки. Mathematica обладает очень большими графическими возможностями. Результаты можно отображать в виде диаграмм и графиков, 3D-графиков, контурных графиков, плотностных графиков, параметрических графиков, полярных графиков, графиков неявных функций.

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

В интегрированной символьной системы Mathematica с использованием встроенных функций Minimize и Maximize строятся решения сгенерированных задач для проверки правильности теоретически разработанных алгоритмов решения экстремальных неоднородных задач. Проводятся необходимые расчеты, чтобы установить параметры и размеры исследуемых неоднородных задач, которые можно решить с использованием встроенных функций КТС Mathematica. Определяются параметры, при которых экстремальные задачи имеют единственное решение. Сравниваются результаты решения специальных систем линейных алгебраических уравнений построенными численными методами, теоретически разработанными в работе, с решениями полученными с использованием встроенных функций Solve и FindRoot КТС Mathematica.





Для реализации теоретически построенного алгоритма решения на ЭВМ разрабатываются численные методы решения СЛАУ и структуры данных для описания графовой структуры. Двойственные алгоритмы неоднородных экстремальных задач потокового программирования с взаимосвязью потоков различных видов (обобщенная сеть) программируются на языке С/С++ с использованием современных технологий численного решения неоднородных задач указанного класса. Для того чтобы запрограммировать методы решения, основанные на графовых структурах, необходимо разработать структуры данных, наиболее оптимально описывающие свойства сети.

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

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

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

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

При программной реализации алгоритма использовались современные инструменты написания программ (Microsoft Visual Studio .Net 2005) . Широко использовались возможности отладочной (debug) версии программы, позволяющей ускорить процесс поиска ошибок в тексте.

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

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

Для представления полученных результатов использовались такие средства как Microsoft Word, Microsoft Power Point и TEX. Системы TEX и LATEX создавались изначально как средство для набора и печати математических текстов. В связи с этим системы предоставляют обширнейшие возможности для набора формул любой сложности.

Например, СЛАУ

в системе LATEX выглядит следующим образом:

\begin{equation}\label{eq1}

\sum_{j\in I^{+}_{i}(U^{k})}x^{k}_{ij}-

\sum_{j\in I^{-}_{i}(U^{k})}\mu^{k}_{ji}x^{k}_{ji}=a^{k}_{i}, \quad i\in I^{k},\,k\in K,

\end{equation}

\begin{equation}\label{eq2}

\sum_{(i,j)\in U} \sum_{k\in K(i,j)}\lambda_{ij}^{kp}x^{k}_{ij}=\alpha_{p},\,p=\overline{1,q},

\end{equation}

\begin{equation}\label{eq3}

\sum_{k\in K_{0}(i,j)}x_{ij}^{k}=z_{ij},\quad(i,j)\in U_{0},

\end{equation}

Использование системы ТЕХ, если сравнивать с MS Equation 3.0, значительно упрощает ввод математических формул

  1. Технологии построения численных решений разреженных систем вычисления псевдопотоков. Структуры данных


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

Определение 2.3.1. Совокупность чисел , называется псевдопотоком прямой неоднородной экстремальной задачи потокового программирования в случае обобщенной сети [1,5], если эта совокупность чисел удовлетворяет недоопределенной системе линейных алгебраических уравнений:

,



.

(2.3.1)

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

Для коллекции корневых деревьев введем следующие списки (структуры данных):

t[i], – обратный список вершин династического обхода;

p[i], – список предков для каждой вершины;

d[i], – список направлений для дуг, входящих в опору, где – число узлов дерева коллекции.

Следует отметить, что для циклических дуг используются те же элементы списков кроме списка t[i], .

Введем список вершин цикла g[i], – список вершин цикла и порядок его обхода.

Вначале находим значения псевдопотоков, соответствующие древесные дугам опоры. Для этого, двигаясь по списку t, решаем уравнения соответствующие вершинам t[i]. В зависимости от направления d[t[i]] находим значения неизвестных, относящихся к дуге (p[t[i]],t[i]), если d[t[i]]=1, или (t[i],p[t[i]]), если d[t[i]]= -1. Таким образом, мы поднимаемся к корню дерева, решая на каждом шаге уравнение с одной неизвестной. Процесс продолжаем до тех пор, пока не рассмотрим все узлы корневого дерева из коллекции корневых деревьев.

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

Список g[i], , где - число узлов цикла компоненты связности опоры, вершин цикла представим следующим образом. Выберем произвольную вершину цикла. Запишем ее в список g[i], . Далее, двигаясь вдоль цикла в одном направлении, записываем каждую новую вершину в список g[i], пока не дойдем до первой вершины. В итоге, получаем упорядоченный список вершин цикла.

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

Выбираем произвольную вершину в качестве начала обхода цикла.


  1. положить псевдопоток по начальной дуге цикла =0;

  2. решить последовательно уравнения системы в том порядке, в котором записаны вершины цикла в список g[i], . То есть, двигаясь по списку g[i], , решаем уравнения для каждой вершины g[i], в котором неизвестной является компонента вектора псевдопотока, соответствующая дуге (g[i],g[i+1]), если направление дуги совпадает с выбранным, или (g[i+1],g[i]), если направление дуги не совпадает с выбранным направлением обхода цикла. На последнем шаге находим новое значение ;

  3. вычислить невязку 0, по формуле 0=x0-;

  4. положив =1, вычислить аналогичным способом невязку 1;

  5. по формуле

,




вычислить истинное значение x1, которое соответствует значению псевдопотока начальной дуги цикла;

  1. решая последовательно n-1 первых уравнений системы, вычислить значения остальных переменных.

Описан алгоритм, использующий разработанные структуры данных, описывающие сеть. Данный алгоритм позволяет на ЭВМ решать СЛАУ специального вида за линейное время.

Глава 3 (обсуждение результатов)

Заключение


В данной работе рассмотрено применение ИТ при решении неоднородной задачи потокового программирования с взаимосвязью потоков различных типов на обобщенной сети, приведены примеры применения различных средств ИТ, используемых при исследовании и построении решения экстремальной задачи потокового программирования. Описаны структуры данных, которые применяются для численного решения больших разреженных СЛАУ, рассмотрен алгоритм применения структур для нахождения вектора псевдопотоков., который основан на использовании современных достижений в технике построения численных решений неоднородных экстремальных задач потокового программирования при введении сетевых структур данных.

Была рассмотрена одна из популярных систем компьютерной алгебры – система Mathematica: были описаны некоторые возможности этого пакета, дающие возможность решать экстремальные задачи и СЛАУ. Пакет Mathematica позволяет комбинировать лучшие характеристики: точные числовые результаты и глубокое понимание, обеспеченное символьными вычислениями. Можно сделать вывод, что использование системы компьютерной алгебры значительно упрощает расчеты, дает возможность быстро и эффективно решать экстремальные задачи с любой точностью, позволяет визуализировать полученное решение в виде графиков.

Двойственный алгоритм решения экстремальной неоднородной задачи потокового программирования реализован с помощью языка программирования С++. В результате изучения возможностей разнообразных программ для реализации алгоритмов, был выбран пакета Microsoft Visual Studio.NET 2005 и язык программирования С/C++. Этот выбор обусловлен тем, что данный пакет является очень удобными инструментом для разработки сложных Windows-приложений. Во первых, язык программирования С++ совместим с языком СИ, который сравним по скорости выполнения с программами, написанными на языке ассемблера, что очень важно при построении алгоритмов численных решений СЛАУ, так как особое внимание уделено сокращению времени исполнения и затрат памяти компьютера. Во-вторых, компилятор данного инструмента имеет много различных настроек (оптимизация программы для максимальной быстроты выполнения, минимизация размера и так далее), и позволяет формировать несколько версий программы – отладочную (Debug) и финальную (Release). В-третьих, созданная программа будет полностью совместима с одной из самых распространенных операционных систем – MS Windows. В-четвертых, объектно-ориентированный язык высокого уровня C++ является очень удобным инструментом для создания различных программ в силу его богатых возможностей по реализации классов.

При программной реализации алгоритма особое внимание уделено структурам данных, позволяющим построить каждый характеристический вектор с вычислительной сложностью О(n), n - число узлов сети, построить частное решение системы линейных уравнений специального вида за О(n) операций. Использование ЭВМ дало возможность решать СЛАУ с большими матрицами системы.

Для представлений результатов исследования наиболее удобной является системы ТЕХ и LATEX.

   

Список литературы к реферату.

Библиографический список


  1. Pilipchuk L.A., Algorithms of Solving Large Sparse Underdeterminated Linear Systems with Embedded Network Structure / L.A. Pilipchuk, Y.V. Malakhouskaya, D.R. Kincaid /   East West Journal of Mathematics, Vol. 4, No 2 (2002) pp. 191-201.

  2. Ravindra K. Ahuja Network Flows: Theory, Algorithms, and Applications / Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin.   Prentice Hall, Englewood Cliffs, New Jersey, 1993.   840 p.

  3. Габасов, Р. Методы линейного программирования. Ч. 2. Транспортные задачи / Р. Габасов, Ф. М. Кириллова – Мн.: Изд-во БГУ, 1978.

  4. Габасов, Р. Методы линейного программирования. Ч. 3. Специальные задачи / Р. Габасов, Ф. М. Кириллова – Мн.: Изд-во БГУ, 1980.

  5. Pilipchuk, L. A. Network optimization problems. Applications of Mathematics in Engineering and Economics '27 , eds. D. Ivanchev and M.D.Todorov, Heron Press, Sofia, 2002.

  6. Альсевич, В.В. Оптимизация линейных экономических моделей: Статические задачи / В.В. Альсевич, Р. Габасов, В.С. Глушенков - Минск, БГУ, 2000.

  7. Йенсен, П. Потоковое программирование / Йенсен П., Барнес Д. - Радио и связь, 1984, – 390 с.

Список публикаций


  1. Пилипчук, Л.А. Алгоритмы вычисления псевдопотока в одной двойственной неоднородной задаче потокового программирования / Л.А. Пилипчук, И.К. Журак – Интеграция информационных и педагогических технологий: материалы международной научной конференции «Информатизация образования – 2008». Минск, 2008. С. 329-335.

  2. Вишневецкая, Т.С. Алгоритмы декомпозиции псевдопотока в двойственных задачах оптимизации неоднородного потока в обобщенной мульти сети / Т.С. Вишневецкая, Л.А. Пилипчук, И.К. Журак – Материалы международной научной конференции «Информационные системы и технологии» (IST’2009). Минск, 2009. С. 87-92.

  3. Pilipchuk, L.A. Algorithms and data structures for construction of the vector of variation of co-flow for a dual generalized non-homogeneous network flow programming problem / L.A. Pilipchuk, T.S. Vishnevetskaya, I.K. Zhurak – Materials of the international scientific conference “Informational systems and technologies”. Minsk, 2009. P.189-190.

Предметный указатель к реферату.


Д

Двойственные алгоритмы 13

Л

Линейное программирование 5



О

Опора сети 10

п

пакет Mathematica 12



потокового программирования 5

псевдопотоком 15

С

Сетевые модели 5



СЛАУ с большими разреженными матрицами системы 9

с

структуры данных 15



Э

Экстремальные задачи 7

Я

Язык Си 14





Интернет ресурсы в предметной области исследования.


  1. http://wolfram.com/

Сайт системы компьютерной алгебры Mathematica. Информация о системе, справка.

  1. http://mathnet.ru

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

  1. http://math.ru

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

  1. http://www.emis.de/ELibM.html

Научная электронная библиотека. Обширная библиотека математических журналов и монографий.

  1. Google Scholar [Electronic resource] // Google – Mode of access : http://scholar.google.com.

  2. Поисковая система научных изданий, раздел поисковой системы Google.

  3. e-Print archive [Electronic resource] // Cornell University Library – Mode of access : http://arxiv.org

Современные статьи в области методов оптимизации.

  1. http://planetmath.org

Математическая энциклопедия.

  1. http://msdn.microsoft.com/en-us/vstudio/default.aspx

Microsoft Visual Studio 2005.

  1. http://elibrary.ru

Научная электронная библиотека. Большое количество журналов по математике и ее приложениям.

Действующий личный сайт в WWW (гиперссылка).


Ссылка на действующий личный сайт [Электрон. ресурс] – 2009. – Режим доступа: www.izhurak.narod.ru

Граф научных интересов


Магистранта Журак И.К., факультета прикладной математики и информатики

Специальность - прикладная математика



Смежные специальности

01.01.01 - математический анализ

  1. Вариационное исчисление и общая теория экстремальных задач.

  2. Теория приближений и методы численного анализа.




01.01.02 - дифференциальные уравнения

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







01.01.05 - теория вероятностей и математическая статистика

  1. Статистические выводы и анализ данных




01.01.07 — вычислительная математика

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

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




Основная специальность

01.01.09 - дискретная математика и математическая кибернетика

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

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

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



Сопутствующие специальности

05.13.01 — системный анализ, управление и обработка информации

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

  2. Формализация и постановка задач системного анализа, оптимизации, управления, принятия решений и обработки информации.

  3. Разработка критериев, моделей описания и оценки эффективности решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации.

  4. Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации.

  5. Разработка специального математического и программного обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации.




05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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




05.13.17 — теоретические основы информатики

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




08.00.13 — математические и инструментальные методы экономики

  1. Методы принятия оптимальных решений.

  2. Оптимизация поддержки принятия решений, включая информационную инфраструктуру экономических систем.



Презентация магистерской диссертации


http://izhurak.narod.ru/ZhurakIK_FinalWork.ppt




Список литературы к выпускной работе.


  1. Bjarne Stroustrup “Programming: Principles and Practice Using C++” 2009, 1272 pages.

  2. [Электрон. ресурс – \\Serv314\subfaculty\ …] Таранчук В.Б. Графический сервис вычислительного эксперимента. БГУ, ФПМИ. 1_ZapuskUst-ki_v*.nb, 3_Grafika_v*.nb

  3. Articles of educational journal [Electronic resource] //– Mode of access: http://www.pereplet.ru/obrazovanie/stsoros/352.html – Date of access : 1.12.2009.

Приложение А


Листинг программы

//Структура сети:

class Graph // класс описывающий сеть

{

int N,M,K,q, n0; // параметры сети



double* al; // правая часть системы

double *al_wave;

struct node; // узел

double** D; // матрица для декомпозиции псевдопотоков

double* Ap; // массив для расчета правой части системы

double* betta; // правая часть для нахождения псевдопотоков

//соответствующих бициклическим дугам

node ** threads;

int* alpha; // правая часть сетевых ограничений

struct karc // дуга к-ого типа потока

{

int c,*lambda,d;



int looked; // просмотрена ли дуга

double *la_wave;

bool k0,k1,crit; // Множества К0 и К1

double x_kr,X; // план задачи

double x; //план

int direction; // направление обхода цикла

bool La; // показатель является ли дуга бициклической

int Cyc; // показатель входит ли дуга в цикл

int teta_inf; // оценки

double *b; // характеристический вектор

double teta; // оценки

double delta; // копоток

double delta_ijk, hi_ijk, hi_ijk_partitial; // псевдопоток

double nu; // коэффициенты преобразования дуговых потоков

int index; // индекс в массиве характеристического вектора

};

struct arc //дуга



{

arc *nextin,*nextout; // входящая и исходящая дуги

node *begin,*end; // узел начала и конца дуги

int k0; // показатель множества К0

karc** karcs; // к-ый тип потока

double v_ij; // вспомогательный вектор для условия согласования

int d0; // ограничение для множества К0

};

struct knode // узел к-ого типа потока



{

double a,a_wave; // основные ограничения

double u_ik; // потенциалы

arc* parentarc; // родительская дуга

arc* parentarcCyc; // родительская дуга по отношению к циклу

int level,levelCyc; // уровень/ глубина узла

node* thread;

node* threadr;

int looked; // показатель, что узел просмотрен

int component;

int count;

double u;

};

struct node // узел



{

node *next,*prev; // следующий/предыдущий узел

arc *in,*out; // входящая/исходящая дуга

knode** knodes; // узел принадлежащий к-ому типу потока

int num; // номер узла

int temp;



};

};

Приложение Б




Можно ли с помощью XML записать структуру различных баз данных?



нет, только базы данных dBase

можно

только базы данных Access

только базы данных Oracle








Какое XML-приложение разработано для обмена данными приложений?



Simple Object Access Protocol

XML Court Interface

Vector Markup Language

Extensible Stylesheet Language








База данных защищена авторским правом ©infoeto.ru 2016
обратиться к администрации
Как написать курсовую работу | Как написать хороший реферат
    Главная страница