Содержание к диссертации
Перечень сокращений и условных обозначений 6
Введение 7
1. Системы однородных неотрицательных линейных ди-
офантовых уравнений, ассоциированные с контекстно-
свободными грамматиками 21
Основные свойства систем одАНЛДУ 22
Сложность задачи нахождения базиса Гильберта 25
Частные случаи систем одАНЛДУ 27
Преобразования произвольной системы одАНЛДУ 28
Сравнение предложенных преобразований с общим методом последовательного исключения 34
Моделирование сетей ЭВМ на основе систем одАНЛДУ и базисов Гильберта 36
Выводы 39
2. Линейные диофантовы модели сети MPLS 40
Обзор технологии и размерность реальных сетей MPLS ... 41
Задача восстановления соединений в сети MPLS 43
Обзор алгоритмов восстановления соединений 44
Модель топологии 48
Модель с фиксированным соединением 50
Модель с характеристиками линии связи 52
Кумулятивная характеристика маршрута 53
Модель с множественной пересылкой 56
Вопросы применения моделей 59
Выводы 61
3. Алгоритмы нахождения базиса Гильберта и генерации си
стем одАНЛДУ 63
Постановка задач решения и генерации 64
Построение оценок вычислительной сложности 66
Алгоритм TransSol нахождения базиса Гильберта системы одАНЛДУ 68
Алгоритм преобразования к трапециевидной форме . 69
Алгоритм НБГ системы 5(г) 70
Алгоритм подстановки базиса для системы (1.9) ... 71
Модификация алгоритма TransSol для нахождения части базиса 74
Алгоритм JordanGen генерации систем одАНЛДУ с единичным базисом Гильберта 75
Алгоритм GaussGen генерации систем одАНЛДУ с частично единичным базисом Гильберта 77
Алгоритм ExtGaussGen генерации систем одАНЛДУ с частично единичным базисом Гильберта. Общий случай .... 80
Алгоритм SymGen генерации систем содАНЛДУ 84
Алгоритм ExtSymGen генерации систем одАНЛДУ, сводящихся к симметричным 86
Применение алгоритмов НБГ и генерации для моделирования сети MPLS 90
Генерация и реализация модели топологии 90
Генерация и реализация модели с фиксированным соединением 91
Генерация и реализация модели с характеристиками линии связи 92
Генерация и реализация модели с множественной пересылкой 93
3.10 Сводная информация по разработанным алгоритмам .... 94
Выводы 96
4. Комплекс программ и экспериментальное исследование ал
горитмов 98
Постановка задач экспериментального исследования 99
Измерение вычислительных ресурсов 100
Комплекс программ для поддержки экспериментов 102
Реализация алгоритмов НБГ и генерации 102
Программная система alg_analyser 103
Программная система Web-SynDic 105
4.4 Экспериментальное исследование алгоритмов 109
Схема организации экспериментов 109
Тестирование алгоритма Syntactic Ill
Сравнение алгоритмов SlopesSys и Syntactic 112
Сравнение алгоритмов Syntactic и TransSol на М-системах 115
Выводы 119
Заключение 121
Литература 123
Приложения 137
А Системы одАНЛДУ и контекстно-свободные грамматики . . 137
Б Дополнительные факты о системах одНЛДУ и одАНЛДУ . 138
В Примеры, поясняющие работу алгоритмов НБГ и генерации
систем одАНЛДУ 144
Г Дополнения к реализации комплекса программ 150
Д Дополнения к экспериментальному исследованию 156
Перечень сокращений и условных обозначений
ИБГ система — система одАНЛДУ с известным базисом Гильберта.
НБГ — нахождение базиса Гильберта.
одАНЛДУ система — однородная система АНЛДУ.
одНЛДУ — однородное уравнение НЛДУ.
ПО — программное обеспечение.
содАНЛДУ система — симметричная система одАНЛДУ.
ІодАНЛДУ — система одАНЛДУ с одним уравнением.
М-система — модельная система одАНЛДУ, структурно соотвествующая реальной сети MPLS.
MPLS — многопротокольная коммутация по меткам (Multiprotocol label switching).
SLSP алгоритм — алгоритм восстановления соединений в сети MPLS (Short Leap Shared Protection).
О — нулевой вектор, О — (0,0,..., 0).
C„ — кумулятивная характеристика маршрута в орграфе из и в v.
E(In,m) — матрица индексного разбиения /п'т.
е/с — стандартный единичный вектор, е& = (0,..., 0,1,0,..., 0).
jn,m _ индексное разбиение множества Nm, In'm = {Iq, її,..., Іп}.
Lk — индексы неизвестных уравнения к, которые не встречаются в уравнениях системы
% - базис Гильберта системы одНЛДУ, 'К = {№\ hP\..., ИЩ.
Nm — конечный отрезок натурального ряда длины га, Nm = {1,2,..., га}.
g{k) _ система одАНЛДУ, полученная на итерации к преобразования к трапециевидной форме.
Т — временная сложность алгоритма.
Rk — индексы неизвестных системы S^k>, не входящих в левые части ее
fc-i уравнений, Rk = (J Ij.
3=0 к-1
Uk — индексы неизвестных системы S(k\ Uk = Nm \ [J Li.
г=1
V — емкостная сложность алгоритма.
Z+ — множество неотрицательных целых чисел, Z+ = {0,1,2,...}.
Введение к работе
Сложность сетей ЭВМ постоянно возрастает за счет введения новых протоколов, роста числа приложений и их требований к качеству обслуживания. Этот рост приводит к усложнению прикладных технических задач управления сетевыми системами, что, в свою очередь, требует развития соответствующих методов математического моделирования. В моделях сетей ЭВМ необходимо учитывать дискретность как самих сетей (напр., топология и характеристики линии связи), так и возможных управляющих воздействий на них (напр., переключение маршрута или кратное увеличение пропускной способности линии связи), а также большую размерность (число ЭВМ порядка 102-106), см., напр., [32,53,72].
Традиционно решение многих задач управления сетями основано на графовых моделях и их обобщениях (напр., гиперграфы), реализация которых использует базовые алгоритмы на графах (напр., поиск простых контуров, кратчайших путей, оптимальных потоков) и методы целочисленного линейного программирования (ЦЛП) [12,10,13,74]. На практике этот подход может приводить к затруднениям [60,93,82,87].
Так, кратчайшие пути могут порождать перегрузку линий связи, линейность целевой функции не всегда адекватна на практике, оптимизационные задачи дают только одно решение, поиск альтернативных решений и различные обобщения графовых моделей требуют многократного использования базовых алгоритмов. В ряде случаев этих затруднений можно из-
бежать применяя модели на основе систем однородных неотрицательных линейных диофантовых уравнений (одНЛДУ) и базисов Гильберта (линейные диофантовы модели). [17,19,64,56,80].
Системой одНЛДУ называется система, коэффициенты которой — целые числа, а неизвестные — неотрицательные целые. Конечный и единственный базис Гильберта однородной системы НЛДУ (системы одНЛДУ) представляет собой множество всех ее неразложимых решений за исключением нулевого. Традиционно системы НЛДУ исследовались в теории чисел [5] и комбинаторном анализе [70]. Концепция базиса Гильберта появляется в исследованиях ученых D. Hilbert, P. Gordan, J. G. van der Corput, E. B. Elliot и P. A. MacMahon (см. исторические справки в [36,85,39,50]). Термин "базис Гильберта" дан F. Giles и W. Pulleyblank [57] в ходе развития теории вполне двойственной целочисленности и целочисленных полиэдров [10,36,37]. Сложность задачи решения таких систем исследуется в работах В. Н. Шевченко [37], Н. К. Косовского [20], A. Schriever [36], L. Pottier [79], М. Henk [59], L. Juban [50], J.-F. Romeuf [83] и др.
Базис Гильберта используется в самых разнообразных приложениях. Так, при автоматизации дедуктивных построений задача ассоциативно-коммутативной унификации сводится к решению системы одНЛДУ, где базис Гильберта определяет минимальный полный набор унификаторов [88, 52,41,90]. В целочисленном программировании этот базис используется при построении универсального тестового множества для семейства целочисленных задач [36,39]. В задачах управления памятью и распараллеливания программ доступ к данным (кэш-память, массивы) описывается системой НЛДУ, решения которой определяют повторные обращения [80,56].
Базис Гильберта представляется удобным инструментом для описания дискретных свойств сетей ЭВМ. Известно, что базис системы одНЛ-ДУ, построенной по матрице инцидентности графа сети, определяет простые контуры в графе. Они используются при решении задач обеспечения надежности и устойчивости сети к сбоям [67,87]. При идентификации структуры нагрузки канала передачи данных базис Гильберта определяет главные источники нагрузки [17]. В самоорганизующихся и одноранговых сетях этот базис описывает маршруты с заданными свойствами [19,64].
Таким образом, актуальной является проблема развития методов моделирования сетей ЭВМ на основе систем одНЛДУ и их базисов Гильберта. В диссертационной работе эта проблема рассматривается на примере актуальной прикладной технической задачи — восстановления соединений в сети ЭВМ. Ее актуальность вызвана ростом числа чувствительных к задержкам приложений (напр., потоковый звук и видео). Существующие методы восстановления (напр., IP reroute [95,87]) не обеспечивают гарантированного времени восстановления. Кроме поиска возможных маршрутов, необходимо выполнять отбор маршрутов-кандидатов на основе дополнительных критериев. Например, некоторые маршруты могут не подходить из-за загруженности линий связи.
Задача восстановления соединений особенно актуальна для технологии многопротокольной коммутации с использованием меток (Multiprotocol label switching, MPLS) [84,73], позволяющей значительно уменьшать время выбора направления пересылки пакета и выполнять рационализацию (инжиниринг [30, 8, 72]) трафика. Технология MPLS имеет общий механизм восстановления, включающий поиск маршрута [86]. В [60] предложен алго-
ритм Short Leap Shared Protection (SLSP) для поиска маршрута восстановления. Используемая в алгоритме SLSP-модель основана на поиске простых циклов в графе сети по которому отбираются маршруты-кандидаты, а затем выбор оптимального маршрута решается задачей ЦЛП. Трудоемкость последней зависит от числа выбранных простых циклов [71,36].
Таким образом, актуальной является задача разработки линейных диофантовых моделей сетей MPLS для рационального поиска и отбора маршрутов.
В диссертационной работе предлагается иерархия линейных диофантовых моделей сети MPLS в виде систем одАНЛДУ для замены SLSP-модели. Предложенные модели используют базис Гильберта для описания кандидатов на маршрут восстановления, а для их отбора предлагается использовать содержательный нелинейный критерий — кумулятивную характеристику маршрута, которая более адекватно учитывает наличие неэффективных линий связи в маршруте.
Кумулятивная характеристика представляет собой произведение линейных комбинаций характеристик предыдущих частей маршрута. Это соответствует принципу "слабого звена", когда значение одной неэффективной линии связи приводит к существенному ухудшению кумулятивной характеристики всего маршрута. Таким образом, для маршрутов-кандидатов значение кумулятивной характеристики должно быть небольшим. Такой подход позволяет рассматривать как кратчайшие пути, так и более длинные, а также отсеивать маршруты, которые можно упростить (составные маршруты), даже если их длина не превосходит заданную границу.
Линейные диофантовы модели представляют интерес не только для
модификации алгоритма SLSP, но могут быть использованы и при решении других задач, связанных с сетями MPLS. Так, в вычислительных экспериментах с сетью MPLS необходимо определять входную нагрузку. Для каждого входного маршрутизатора указываются сценарии поступления пакетов в сеть, что отражается на загрузке линии связи. В этом случае предложенная иерархия моделей может быть использована для поиска основного маршрута соединения с учетом оптимального распределения нагрузки по всей сети.
Применение предлагаемых моделей возможно при условии наличия эффективных алгоритмов нахождения базиса Гильберта (НБГ) и их протестированных реализаций. Однако в этой области существует серьезный пробел. В настоящее время предложен ряд алгоритмов НБГ для случая произвольных одНЛДУ и их систем на основе различных математических методов: верхние границы компонент базисных решений [62,79,59]; элементарные преобразования матриц [66]; покомпонентное построение решений, начиная с пулевого [45,46]; преобразования производящих функций (метод Elliott — MacMahon) [70,49,77,40]; нахождение базисных решений с минимальным носителем и последующим построением оставшихся базисных решений как рациональных положительных комбинаций [48,91,65]; нахождение базиса Гребпера идеала в кольце полиномов [79,78].
Эти алгоритмы представлены без верхних оценок сложности и реализованы как прототипы, не проверенные массовым тестированием. Автору не удалось найти алгоритмов НБГ со сложностью, позволяющей решать задачи необходимых размерностей, а также протестированные реализации.
Задача НБГ является вычислительно трудоемкой, поскольку число
базисных решений в худшем случае экспоненциально зависит от размерности системы и абсолютных величин ее коэффициентов [36,50]. В этом случае эффективным можно считать псевдополиномиальный алгоритм, сложность которого ограничена полиномиально не только в зависимости от числа уравнений и неизвестных, но и от числа базисных решений [42,17].
Такое положение определяет актуальность исследований частных классов систем одНЛДУ для построения специализированных эффективных алгоритмов НБГ. Например, в случае системы одНЛДУ из двух уравнений, время нахождения базиса Гильберта полиномиально по числу неизвестных и максимальному значению коэффициентов [83].
М. Filgueiras и A. Tomas показали, как систему НЛДУ можно ассоциировать с контекстно-свободной (КС) грамматикой (сокращенно — система АНЛДУ) [54]. Авторы [4], а затем Д. Ж. Корзун в [15,17] развили этот результат, предложив метод построения системы АНЛДУ по произвольной КС-грамматике и по двум цепочкам. При равенстве цепочек строится однородная система АНЛДУ (система одАНЛДУ). В диссертации используется только алгебраическое определение этих систем [15,17].
Известно, что метод последовательного исключения для систем линейных уравнений справедлив, когда и коэффициенты системы и неизвестные рассматриваются, как элементы одного множества, например произвольного поля (варианты метода Гаусса [28,3]) или кольца целых чисел Z (метод Эрмита [13]). В то же время неизвестны аналоги этого метода, когда коэффициенты являются элементами множества Z, а неизвестные — элементами множества неотрицательных целых чисел Z+.
Таким образом, актуальной является задача построения эффективно-
го алгоритма НБГ системы одАНЛДУ на основе метода последовательного исключения уравнений и неизвестных.
Автором предлагается и обосновывается алгоритм — аналог метода исключения, позволяющий решать как задачу НБГ, так и задачу генерации систем одАНЛДУ с известным базисом Гильберта (ИБГ системы). Последние включают тестовые, эталонные и модельные системы одАНЛДУ, структурно соотвествующие реальным сетям MPLS (М-системы). Для практического применения алгоритма необходимы тестирование и экспериментальная оценка эффективности его реализации, в том числе по сравнению с реализациями других алгоритмов.
Таким образом, актуальной является задача программной реализации алгоритмов НБГ и разработки программных средств для их тестирования, экспериментального и сравнительного анализа, оценки эффективности предлагаемых моделей на М-системах и представления результатов исследований в Web-пространстве.
Эти задачи решаются с помощью разработанного автором комплекса программ. Тестирование позволяет проверить корректность реализации алгоритма на наборе тестовых систем [35]. При этом необходимы разработка и реализация ПО измерения эффективности и автоматической генерации и проверки тестов.
При экспериментальном анализе оценка эффективности алгоритма выполняется на выборке из некоторого класса систем. Соответствующее программное обеспечение (ПО) разработано автором путем дополнения ПО автоматизированного тестирования функциями вычисления статистических параметров. Включение в ПО возможностей использования pea-
лизаций других исследуемых алгоритмов позволяет провести сравнительный анализ эффективности. В практических, демонстрационных и научно-образовательных целях представляется целесообразной интеграция ПО тестирования и экспериментального анализа в Web-ориентированиый комплекс программ.
Цель исследования формулируется следующим образом.
Развитие метода последовательного исключения для частного класса — систем одАНЛДУ, коэффициенты которых принадлежат Z, а неизвестные — Z+. Разработка, обоснование, реализация, тестирование и экспериментальное исследование алгоритмов НБГ и генерации этих систем.
Разработка, обоснование и реализация линейных диофантовых моделей сетей MPLS для использования в алгоритме SLSP, а также проверка эффективности алгоритмов НБГ на сгенерированных М-системах.
В диссертационной работе используются методы линейной алгебры, математического моделирования, дискретной и вычислительной математики, теории сложности алгоритмов, технологии программного обеспечения и прикладной статистики.
Научная новизна работы отражена в следующих положениях.
Для решения задачи восстановления соединений в сетях MPLS впервые предложено использовать линейные диофантовы модели на основе систем одАНЛДУ и базисов Гильберта.
Впервые предложены и обоснованы преобразования систем одАНЛДУ к трапециевидной форме и обратной подстановки базиса Гильберта для случая, когда коэффициенты системы принадлежат Z, а неизвестные
Разработан, обоснован и протестирован новый алгоритм НБГ произвольной системы одАНЛДУ, имеющий лучшие теоретические и экспериментальные оценки по сравнению с известными алгоритмами.
Разработаны и обоснованы пять алгоритмов генерации частных классов ИБГ систем одАНЛДУ. Ранее задача построения тестовых примеров решалась с помощью полученных вручную малых наборов систем или непосредственной (без построения базиса Гильберта) генерацией.
Объектами исследования в работе являются сети MPLS, системы одАНЛДУ и базисы Гильберта, а предметом исследования — линейные ди-офантовы модели сетей ЭВМ, алгоритмы НБГ и генерации систем одАНЛДУ, сложность алгоритмов, программные реализации алгоритмов и средства их экспериментального исследования.
Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка использованной литературы (98 наименований), пяти приложений, имеет объем 136 машинописных страниц и 34 страницы приложений, содержит 25 рисунков и 12 таблиц.
Структура работы соответствует методологии математического моделирования, сформулированной академиком А. А. Самарским в [33]. Обосновывается выбор систем одАНЛДУ и их базиса Гильберта как "эквивалента" сетей MPLS, отражающего их важные свойства, разрабатываются линейные диофаптовы модели этих сетей, предлагается и обосновывается эффективный алгоритм НБГ на ЭВМ и алгоритмы генерации тестовых, эталонных и модельных систем. Затем алгоритмы реализуются в виде комплекса программ, выполняются тестирование и экспериментальное исследование потребления этими реализациям ресурсов в типичных случаях.
В первой главе системы одАНЛДУ исследованы как математический объект моделирования сетей ЭВМ. Автором обоснована целесообразность использования систем одАНЛДУ для построения линейных диофантовых моделей сети MPLS. Выделены два частных случая: системы с одним уравнением (ІодАНЛДУ) и симметричные системы (системы сод АН Л ДУ). Для нахождения базиса Гильберта системы одАНЛДУ предложены и обоснованы преобразования к трапециевидной форме и обратной подстановки базиса Гильберта, развивающие метод последовательного исключения.
Во второй главе автором предложена иерархия линейных диофантовых моделей в виде систем одАНЛДУ. Модели предназначены для использования в алгоритме SLSP [60,61]. В иерархию входят модели топологии, с фиксированным соединением, с характеристиками линии связи и с множественной пересылкой. Эффективность реализаций таких моделей подтверждена автором экспериментально в гл. 4 на основе алгоритма генерации ExtGaussGen (для систем с ограничением 2000 на число неизвестных, уравнений и базисных решений среднее время нахождения базиса Гильберта составляет 17 с на ЭВМ Intel Хеоп 2.8ГГц).
В третьей главе автором сформулирована задача НБГ и задачи генерации тестовых, эталонных и М-систем. Предложены алгоритм НБГ TransSol и пять алгоритмов генерации систем одАНЛДУ, основанных на преобразованиях к трапециевидной форме и обратной подстановке, полученных в гл. 1. Для всех алгоритмов автором в виде теорем получены оценки сложности наихудшего случая.
Четвертая глава содержит описание комплекса программ для тестирования, экспериментального и сравнительного анализа алгоритмов НБГ.
В состав комплекса входят системы alg_analyser и Web-SynDic. Описаны результаты выполненных автором вычислительных экспериментов с алгоритмами НБГ SlopesSys [92], Syntactic [16,17] и разработанным автором алгоритмом TransSol (всего было решено более 1.5 106 систем).
В заключении приведена общая характеристика выполненного научного исследования и основные выводы по полученным результатам.
В приложениях представлены связь систем одАНЛДУ с грамматиками, дополнительные сведения о системах одНЛДУ и одАНЛДУ, примеры, поясняющие работу алгоритмов, дополнения в виде таблиц и графиков по реализации алгоритмов и программных средств, а также по результатам выполненного экспериментального исследования.
Результаты, выносимые автором на защиту.
Предложена иерархия линейных диофантовых моделей сетей MPLS для известного алгоритма SLSP восстановления соединений. Использование базиса Гильберта позволяет единообразно учитывать топологию, характеристики линий связи и множественную пересылку, а также строить кумулятивную характеристику для рационального отбора маршрутов-кандидатов.
Предложены преобразования системы одАНЛДУ к трапециевидной форме и обратной подстановки базиса Гильберта. Они развивают метод последовательного исключения для класса систем одАНЛДУ, позволяя разрабатывать эффективные алгоритмы НБГ и генерации ИБГ систем.
3. Разработан, обоснован, реализован и протестирован псевдополи-
номиальиый алгоритм НБГ произвольной системы одАНЛДУ TransSol.
Сложность алгоритма позволяет реализовать с его помощью линейные ди-
офантовы модели сетей MPLS реальных размерностей.
Разработаны и обоснованы пять алгоритмов генерации ИБГ систем, четыре из которых программно реализованы.
Разработан комплекс программ, содержащий реализации предложенных алгоритмов НБГ и генерации ИБГ систем, реализации алгоритмов НБГ других авторов, ПС alg_analyser для измерения потребляемых ресурсов и ПС Web-SynDic для доступа к исследуемым алгоритмам через Интернет.
Результаты тестирования и экспериментального исследования программных реализаций алгоритмов НБГ TransSol, Syntactic и SlopesSys показывают эффективность предложенного алгоритма TransSol при реализации линейных диофантовых моделей сетей MPLS.
Практическая ценность полученных результатов отражена в следующих положениях.
Предложенная иерархия моделей может быть использована при решении задачи восстановления соединений в сети MPLS. По сравнению с моделью, применяемой в алгоритме SLSP, разработанные модели учитывают больше важнейших свойств сетей MPLS и поэтому более удобны для практического использования.
Разработанные алгоритмы НБГ и генерации ИБГ систем могут быть использованы в прикладных задачах с дискретными переменными. Результаты выполненного экспериментального исследования позволяют оценить практическую эффективность реализаций таких алгоритмов.
Разработанный комплекс программ может быть использован для решения прикладных задач путем доступа через Интернет, а также, для те-
стирования и экспериментального исследования алгоритмов НБГ.
Результаты диссертационной работы докладывались и обсуждались на международном научном семинаре FDPW03, на конкурсе-конференции студентов и молодых ученых Северо-Запада "Технологии Microsoft в теории и практике программирования" (2004 г.), на всероссийской научной конференции "Научный сервис в сети Интернет" (2004 г.), на второй международной научно-практической конференции "Исследование, разработка и применение высоких технологий в промышленности" (2006 г.), па международной конференции "Развитие вычислительной техники в России и странах бывшего СССР: история и перспективы (SORUCOM'06)", на международном семинаре "Распределенные компьютерные и телекоммуникационные сети: теория и приложения (DCCN-2007)", на XIV Всероссийской научно-методической конференции "Телематика'2007", на научном семинаре "Проблемы современных информационно-вычислительных систем" механико-математического факультета МГУ им. М. В. Ломоносова под руководством д.ф.-м.н., профессора В. А. Васенина (2007 г.), на научном семинаре кафедры информатики математико-механического факультета СПбГУ под руководством д.ф.-м.н., профессора Н. К. Косовского (2008 г.), на семинаре Института прикладных математических исследований Карельского НЦ РАН под руководством д.ф.-м.н., профессора В. В. Мазалова (2008 г.), на семинаре кафедры вычислительной математики механико-математического факультета МГУ им. М. В. Ломоносова под руководством д.ф.-м.н., профессора Г. М. Кобелькова (2008 г.), а также на научных семинарах кафедры информатики и математического обеспечения ПетрГУ. По результатам работы опубликованы тезисы [24,96,34,26] и статьи [25,22,21,23,27,31].
В работе использованы следующие соглашения и обозначения. Основные понятия и определения выделены курсивом. Примеры оканчиваются символом . Доказательства теорем и свойств оканчиваются символом П.
Автор выражает искреннюю признательность своему научному руководителю доценту Ю. А. Богоявленскому, сформулировавшему направление исследований и оказавшему сильное влияние на структуру и стиль изложения этой работы, которая не состоялась бы без его постоянного внимания. Автор крайне признателен доценту Д. Ж. Корзуну, некоторые из результатов которого развиты в диссертационном исследовании. Этому в значительной мере способствовали наша совместная работа и постоянные и плодотворные обсуждения. Автор благодарен профессорам В. А. Васенину и Н. К. Косовскому за помощь, оказанную при работе над диссертацией. Автор также благодарит системного администратора В. А. Пономарева за неоценимую помощь в организации проведения вычислительных экспериментов на серверах кафедры информатики и математического обеспечения
ПетрГУ. Автор благодарен профессорам В. И. Чернецкому , В. В. Мазало-ву, Е. В. Морозову, Ю. В. Заике, Г. М. Кобелькову и его коллегам, доцентам В. Т. Вдовицыну, А. А. Печникову, преподавателю С. А. Афонину, критические замечания которых, бесспорно, способствовали повышению качества данной работы.
