WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

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

Зинин Михаил Владимирович

Символьные алгоритмы и программы

вычисления булевых базисов Грёбнера

05.13.11 – математическое и программное обеспечение вычислительных

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата физико-математических наук

Москва – 2013

Работа выполнена в Лаборатории информационных технологий Объединенного института ядерных исследований.

Научный руководитель: доктор физико-математических наук, профессор Гердт Владимир Петрович

Официальные оппоненты: Абрамов Сергей Александрович доктор физико-математических наук, профессор, Вычислительный центр им. А.А. Дородницына РАН, главный научный сотрудник Зобнин Алексей Игоревич, кандидат физико-математических наук, доцент, МГУ имени М.В. Ломоносова

Ведущая организация: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Российский университет дружбы народов»

Защита состоится 1 марта 2013 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при факультете вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова по адресу: 119991, г.Москва, ГСП-1, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. (495)939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М.В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте ВМК МГУ http://cs.msu.ru в разделе «Наука» – «Работа диссертационных советов» – «Д 501.001.44».

Автореферат разослан 25 января 2013 г.

Ученый секретарь диссертационного совета Д 501.001. профессор Н.П. Трифонов

Общая характеристика работы

Объект исследования и актуальность работы. Базис Грёбнера представляет собой каноническую форму системы алгебраических [1], дифференциальных [2, 3] или разностных [4] многочленов многих переменных.





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

Так, построение базиса Грёбнера для системы алгебраических уравнений полиномиального типа позволяет установить её совместность (т.е. наличие общих корней у многочленов системы), определить число (а в случае бесконечного числа — размерность пространства) решений, привести исходную систему к треугольному виду, либо исключить часть переменных. В целом метод базисов Грёбнера является обобщением метода Гаусса на случай нелинейных систем.

Алгоритмически задача нахождения базиса Грёбнера для заданной системы многочленов в коммутативной алгебре была решена около полувека назад Б.Бухбергером [1], а соответствующий алгоритм [5] получил имя автора. С тех пор усилиями многих исследователей базисы Грёбнера нашли плодотворное применение в различных областях математики и естественных наук и в настоящее время обладают обширным числом практических приложений [6].

Расширение области применения базисов Грёбнера не обошло стороной и специфический случай систем булевых многочленов. Впервые алгоритм вычисления булевых базисов Грёбнера был представлен в [7]. Теоретическим фундаментом идеи использования базисов Грёбнера в булевых кольцах послужила весьма развитая к тому времени теория булевых функций.

Напомним, что nместной булевой функцией называется отображение { 0, 1}n в { 0, 1} [8]. Для булевых функций определено понятие их суперпозиции, и, как следствие, для любого множества булевых функций может быть получено его замыкание — как множество всех функций, получаемых с помощью суперпозиции из функций исходного множества. В таком случае говорят, что множество Q порождает замкнутый класс булевых функций R:

[Q] = R (замкнутый, т.к. очевидно, что [[R]] = [R]). Если [R] совпадает со множеством всех булевых функций, то порождающее множество Q называют полным. Базисом замкнутого класса R в теории булевых функций называют такое множество Q, которое порождает класс R, но при этом ни одно несобственное подмножество Q этого класса не порождает.

Известно, что множество булевых функций {1, x + y, xy} полно [8] (здесь 1 — функция-константа единица, x + y — сложение по модулю 2, xy — конъюнкция). Причем функции x + y и xy являются соответственно сложением и умножением в поле Галуа F2 = {0, 1}. Поэтому, пользуясь коммутативностью сложения и умножения, дистрибутивностью умножения относительно сложения и соотношениями x + x = 0, x · x = x, всякую функцию из замыкания множества {1, x + y, xy} (т.е. любую булеву функцию) можно представить в виде многочлена Жегалкина [8]:

ai1...is · xi1 ·... · xis, (i1,...,is ) где ai1...is F2. В данной работе мы будем называть многочлен Жегалкина булевым многочленом. Все такие многочлены от заданного конечного набора переменных {x1,..., xn } образуют кольцо, которое мы будем называть булевым. Это кольцо является эквивалентом булевой алгебры [9]. Более того, каждая булева функция представима булевым многочленом единственным образом [8]. Как и в случае булевых функций, множество булевых многочленов порождает идеал в булевом кольце, причем булево кольцо является кольцом главных идеалов, т.е. каждый идеал кольца порождается его единственным элементом.





Базисы Грёбнера в целом, как уже было сказано, и булевы в частности, оказываются весьма полезными в случаях, когда решение некоторой задачи связано с исследованием и/или решением соответствующей полиномиальной системы [10–12]. В случае булева кольца наиболее распространенными задачами такого рода являются задачи криптоанализа и булевой выполнимости.

Например, одним из первых ярких применений метода булевых базисов Грёбнера стало решение сложной [13] проблемы — криптосистемы на скрытых отображениях полей (Hidden Fields Equations) в криптографии с открытым ключом. Эта задача описывается системой квадратичных булевых многочленов от 80 переменных, и впервые ее решение было получено именно путем вычисления булева базиса Грёбнера с помощью алгоритма F5, позднее — с помощью алгоритма F4 [14, 15].

Задача булевой выполнимости SAT (Boolean Satisability) — очень распространенная и, в общем случае, N Pполная [16] задача, которая возникает, в частности, при проверке корректности работы оборудования и программ, в робототехнике, при создании экспертных систем и т.п. Для решения этой задачи разработан ряд успешных и широко применяемых специализированных алгоритмов. В настоящее время уже известен ряд примеров [17] успешного применения техники булевых базисов Грёбнера к решению задачи булевой выполнимости. Через 12 лет после теоретического обоснования [18] применимости таких базисов для решения задач SAT был создан программный пакет PolyBoRi [19], использующий метод базисов Грёбнера и способный конкурировать с лучшими современными программами решения задач булевой выполнимости (SAT-solvers).

Приведем простой пример задачи булевой выполнимости, иллюстрирующий применение метода базисов Грёбнера для её решения, т.е. для ответа на вопрос: существует ли для заданной булевой функции такой набор значений переменных, на котором функция принимает значение 1 (истина)? В терминах базисов Грёбнера данный вопрос формулируется следующим образом:

состоит ли соответствующий базис Грёбнера из одного многочлена, который, в свою очередь, является единичным булевым мономом {1}) или нет? В последнем случае рассматриваемая задача является выполнимой.

Пусть булева функция, заданная в своей конъюнктивой нормальной форме, имеет вид:

Приведем функцию к полиномиальному виду, используя следующие формулы:

Тогда булева выполнимость рассматриваемой задачи сводится к существованию решения в F3 у системы булевых многочленов Вычисление базиса Грёбнера для данной системы многочленов показывает, что этот базис равен {1}, т.е. полиномиальная система не имеет решений (несовместна), и задача невыполнима.

Ещё одним интересным применением булевых базисов Грёбнера может стать моделирование квантовых вычислений, т.е. построение унитарной матрицы квантовой цепи на классическом компьютере. Как показано в [20], для квантовой цепи с помощью вентилей Тоффоли и Адамара (они образуют универсальный базис вентилей) её цепная матрица однозначно определяется числом общих корней (когда все переменные принимают значения в F2 ) системы булевых многочленов. В работе [21] описан пакет для системы Mathematica [22], позволяющий пользователю по введенной квантовой цепи строить её цепную унитарную матрицу стандартными методами линейной алгебры, а также автоматически создавать систему определяющих её булевых многочленов. На практике, в силу ограниченности памяти компьютера, методами линейной алгебры удается промоделировать лишь 20–25 кубитные схемы. И хотя задача построения базисов Грёбнера в булевых кольцах имеет экспоненциальную сложность [23], уже сейчас эта задача решается для некоторых систем многочленов от 100 и более переменных [17], что дает реальную надежду на то, что базисы Грёбнера, по крайне мере в отдельных случаях, позволят сильно продвинуться в моделировании квантовых вычислений.

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

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

Таким образом, можно утверждать, что в настоящее время существует практическая потребность в быстрых и высокоэффективных алгоритмах для вычисления булевых базисов Грёбнера и их реализациях, что заставляет исследователей искать и находить новые, более эффективные алгоритмы для их построения. К таковым можно отнести уже упоминавшиеся алгоритмы F и F5 французского математика Фожера, целый ряд модификаций алгоритма F5, например, алгоритмы G2V и GVW [25] — результат работы китайских и американских исследователей, а также инволютивный алгоритм [26, 27] Блинкова и Гердта. Булевой версии последнего и посвящена данная работа.

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

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

• Исследование современных алгоритмов построения базисов Грёбнера в полиномиальных кольцах и условий их применимости для вычисления булевых базисов Грёбнера.

• Разработка специализированного алгоритма, способного строить булев базис Грёбнера путем вычислений непосредственно в булевом кольце.

• Реализация разработанного алгоритма на языке С++ и ее оптимизация на основе эмпирических данных, полученных с помощью компьютерных экспериментов.

• Разработка программных пакетов, реализующих предложенный алгоритм в среде систем компьютерной алгебры с открытым исходным кодом.

Научная новизна. В диссертационной работе получен ряд результатов, обладающих научной новизной:

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

• Впервые получена точная верхняя оценка на число элементов редуцированного булева базиса Грёбнера, что важно для оценки возможных затрат памяти на вычисление данного базиса.

• В системы компьютерной алгебры с открытым кодом REDUCE (версия 3.8) и Macaulay2 (версия 1.4.1) встроены новые пакеты, которые предназначены для построения булевых базисов Грёбнера и значительно превосходят по своей вычислительной эффективности имевшиеся в этих системах возможности для указанного построения.

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

Реализация алгоритма в виде пакета BIBasis встроена в открытые системы компьютерной алгебры Macaulay2 и REDUCE. Это существенно расширяет применимость указанных систем для решения задач, сводящихся к булевой логике. При этом Macaulay2 является одной из наиболее широко используемых программных систем специального назначения, ориентированных на задачи вычислительной коммутативной алгебры и алгебраической геометрии, а REDUCE является системой компьютерной алгебры общематематического назначения и находит применение в различных областях науки и техники.

На защиту выносятся следующие основные результаты и положения:

1. Проведено исследование применимости инволютивного алгоритма к задаче построения базисов Грёбнера и базисов Жане в булевом кольце.

В результате показано, что инволютивный алгоритм на основе деления Жане, равно как и алгоритм Бухбергера, может быть использован для этой цели только в том случае, когда исходное множество булевых многочленов дополняется множеством всех полевых биномов. После этого вычисление базиса Грёбнера производится в кольце многочленов над полем F2, а искомый булев базис является мультилинейным подмножеством найденного базиса Грёбнера.

2. Разработана версия инволютивного алгоритма на основе деления Поммаре для построения редуцированных булевых базисов Грёбнера и базисов Поммаре непосредственно в булевом кольце, т.е. без использования полевых мономов. Доказаны корректность и завершаемость данного алгоритма. Показано, что он позволяет эффективно использовать представление булевых многочленов в памяти ЭВМ и простоту их арифметики. Получена точная верхняя оценка на число элементов редуцированного булева базиса Грёбнера.

3. Разработанный булев инволютивный алгоритм на основе деления Поммаре, а также алгоритм на основе деления Жане реализованы на языке программирования C++ в виде отдельных утилит. Дальнейшие изучение и сравнение быстродействия этих утилит между собой и с другими программными пакетами позволили отказаться от некоторых шагов алгоритма и найти компромисс между производительностью и функциональностью. Итоговая версия алгоритма, использующего деление Поммаре, реализована в виде пакета BIBasis, встроенного в системы компьютерной алгебры с открытым исходных кодом Macaulay2 и REDUCE.

Пакет доступен под лицензией GPL v2.

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях и семинарах:

• Международная конференция по компьютерной алгебре и дифференциальным уравнениям. Доклад «О вычислении базисов Грёбнера над F2 », Финляндия, Турку, 20 — 23 февраля 2007 г.

• 11-ое международное совещание по компьютерной алгебре. Доклад «Инволютивный метод вычисления базисов Грёбнера над F2 », Россия, Дубна, 24 — 25 мая 2007 г.

• 4-ое международное совещание «Квантовая физика и информация». Доклад «Алгоритмический подход к решению полиномиальных уравнений, описывающих квантовые схемы», Россия, Дубна, 15 — 19 октября • 12-ое международное совещание по компьютерной алгебре. Доклад «О роли инволютивных критериев при вычислении булевых базисов Грёбнера», Россия, Дубна, 14 — 15 мая 2008 г.

• Международная конференция «Математическое моделирование и вычислительная физика», MMCP 2009. Доклад «О вычислении булевых инволютивных базисов», Россия, Дубна, 7 — 11 июля 2009 г.

• Международная конференция «Полиномиальная компьютерная алгебра», PCA 2010. Доклад «Булевы инволютивные базисы и решение задач булевой выполнимости», Россия, Санкт-Петербург, 2 — 7 апреля 2010 г.

• 14-ое международное совещание по компьютерной алгебре. Доклад «Пакет BIBasis для вычисления булевых инволютивных базисов и базисов Грёбнера в системах компьютерной алгебры REDUCE и Macaulay2», Россия, Дубна, 2 — 3 июня 2011 г.

Публикации. По материалам диссертации опубликовано 8 печатных работ: 5 статей в рецензируемых журналах, рекомендованных ВАК [A1, A2, A3, A4, A5], и 3 статьи в сборниках трудов конференций [A6, A7, A8].

Личный вклад автора. Основные положения и выводы диссертации являются результатом самостоятельных исследований автора, выполненных под руководством д.ф.-м.н., профессора В.П. Гердта. Постановка и формализация задачи, разработка математических моделей и алгоритмов выполнены соискателем совместно с научным руководителем и соавторами. Практическая реализация, исследование форм представления данных, численные расчеты и анализ результатов проводились соискателем самостоятельно. Также соискателем самостоятельно создан и встроен в системы компьютерной алгебры REDUCE и Macaulay2 специализированный пакет для построения булевых базисов Грёбнера, и опубликована работа [A5], описывающая данный пакет.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Общий объем диссертации составляет 114 страниц, включая 34 рисунка и 4 таблицы. Список литературы содержит 63 наименования.

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

В первой главе приводятся обозначения и определения, используемые в дальнейшем во всей работе:

F2 = {0, 1} — поле Галуа характеристики 2;

X = {x1,..., xn } — множество независимых переменных;

F2 [X] — кольцо многочленов от переменных X над полем F2 ;

B [X] — кольцо булевых многочленов от переменных X;

MB [X] — множество всех булевых мономов от переменных X;

F — идеал, порожденный конечным множеством многочленов F ;

degi (u) — степень переменной xi в мономе u;

deg(u) = n degi (u) — полная степень монома u;

— мономиальное упорядочение, такое, что x1 x2 · · · xn 1;

lm(f ) — старший моном многочлена f ;

Булево кольцо B [X] определяется как кольцо многочленов Жегалкина [8], которое является коммутативным факторкольцом Легко видеть, что умножение в булевом кольце идемпотентно, а сложение — нильпотентно:

Здесь же вводится определение частного от деления булевых мономов:

Определение 1.3.5. Булев моном m MB [X] будем называть частным от деления монома b на моном a в булевом кольце B [X], если m · a = b и deg(m) = min{deg(mi ) | mi a = b}.

Доказано следующее Утверждение 1.3.1. Частное от деления булевых мономов единственно.

Далее вводится понятие базиса Грёбнера и нормальной формы многочлена f по модулю заданного конечного полиномиального множества F :

Определение 1.3.7. Пусть даны идеал I B [X] и упорядочение. Конечное подмножество G I называется базисом Грёбнера идеала I (относительно упорядочения ), если Нормальная форма f по модулю F определяется как остаток от деления f на элементы из F.

Далее в первой главе приводятся основные, необходимые для понимания работы инволютивного алгоритма в дальнейшем, определения из теории инволютивных базисов, восходящей к работе [28] и основанной на теории инволютивных делений [26]. Полностью все эти определения даются в работе [27].

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

Определение 1.4.10. Для монома u = xd1 · · · xk1 xdk, где dk 0 переменные k называются мультипликативными (по Поммаре), все остальные, xj, j соответственно, — немультиплипкативными. Для u = 1 все переменные считаются мультипликативными. Моном u является инволютивным делителем Поммаре монома v (обозначение u |P v) если v = u · w и все переменные положительной степени в мономе w являются мультипликативными для этого монома.

Также в первой главе описываются особенности булева кольца, не позволяющие использовать существующие алгоритмы построения базисов Грёбнера непосредственно в этом кольце. Этими особенностями являются: (1) нарушение свойства совместимости мономиального упорядочения с операцией умножения в булевом кольце; (2) минимальный базис Грёбнера идеала, не обязательно совпадаем с порождающим его многочленом. Напомним, что булево кольцо является кольцом главных идеалов. Мы иллюстрируем указанные особенности простыми примерами:

Основные результаты первой главы опубликованы в [A6, A1] и состоят в следующем:

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

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

Во второй главе рассматриваются теоретические аспекты вычисления булевых базисов Грёбнера.

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

Поскольку, как уже было выяснено в первой главе, ни один из существующих алгоритмов не может работать непосредственно в булевом кольце, в данном разделе описана возможность построения булева базиса Грёбнера с помощью вычислений в кольце F2 [X]. Для этого исходный набор булевых многочленов {f1,..., fm } дополняется множеством всех полевых биномов и для полученного набора {f1,..., fm, } (где fi F2 [X] — прообраз fi относительно гомоморфизма факторизации F2 [X] B [X]), вычисляется базис Грёбнера в кольце F2 [X]. Полученный базис имеет вид {g1,..., gk, }, где gi F2 [X], gi,, причем многочлены gi не содержат переменных в степени выше 1.

Утверждение 2.2.1. Набор булевых многочленов {g1,..., gk } является искомым базисом Грёбнера идеала f1,..., fm.

Доказательство этого утверждения можно найти в [6].

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

Во втором разделе главы подробно описаны инволютивный алгоритм на основе деления Жане [26, 27] и его ключевые подалгоритмы, работающие в кольце F2 [X]. Сами алгоритмы представлены в виде псевдокода, исходный же код утилиты на языке программирования C++ доступен по адресу в Интернете http://bpb.googlecode.com. Реализация этого алгоритма используется для сравнения с новой разработкой — инволютивным алгоритмом на основе деления Поммаре (описан ниже) и для иллюстрации недостатков работы в кольце F2 [X].

Третий раздел посвящен инволютивному алгоритму на основе деления Поммаре. Как и в случае любого другого инволютивного деления [26], его отличие от обычного мономиального деления состоит в том, что в этом делении и, соответственно, при полиномиальной редукции допускается умножение только на мультипликативные переменные.

Деление Поммаре обладает важным свойством, а именно: свойство делимости по Поммаре сохраняется каноническим гомоморфизмом кольца F2 [X] по идеалу, порождённому полевыми биномами.

Доказано Утверждение 2.3.1. Разделение переменных монома на мультипликативные и немультипликативные по Поммаре и, следовательно, свойство делимости по Поммаре сохраняются гомоморфизмом кольца F2 [X] в кольцо B [X].

Представлена разработанная версия инволютивного алгоритма на основе деления Поммаре.

Algorithm 1 PommaretBasis(F, ) Вход: F F2 [X] \ {0}, — мономиальное упорядочение;

Выход: P F2 [X] — базис Поммаре идеала F ;

1: выбрать f F с наименьшим lm(f ) относительно 2: P := {f } 4: while Q = do выбрать q Q с наименьшим lm(q) относительно 10:

11:

12:

13:

14:

15:

16:

17:

18:

19: od 20: P := AutoreduceT ailsP (P ) 21: return P В силу особенностей деления Поммаре инволютивный алгоритм на его основе в других полиномиальных кольцах, отличных от булева, в общем случае не завершается. В булевом же кольце он всегда закачивается за конечное число шагов. Этот факт доказан и является одним из результатов диссертационной работы.

Доказаны следующие теоремы:

Теорема 2.3.1. Алгоритм PommaretBasis корректен и завершается за конечное число шагов для любого набора многочленов B F2 [X].

Следствие 2.3.1. Базис Поммаре, получаемый в результате работы алгоритма PommaretBasis, применённого к набору B, может содержать только булевы многочлены и произведения полевых многочленов на немультипликативные переменные их старших мономов.

Следствие 2.3.2. Мощность базиса Поммаре идеала в F2 [X], порожденного набором булевых многочленов от n переменных и дополненного множеством полевых многочленов, ограничена 2n 1.

Теорема 2.3.2. Для данного набора B булевых многочленов идеал B в булевом кольце B [X] имеет единственный базис Грёбнера.

Теорема 2.3.3. Алгоритм PommaretBasis корректен и завершается за конечное число шагов для любого набора многочленов F B [X].

Теорема 2.3.3. Мощность приведенного базиса Грёбнера G в булевом кольце И в заключительной части третьего раздела подробно описываются инволютивный алгоритм на основе деления Поммаре и его основные подалгоритмы в том виде, в каком они были реализованы в утилите BPB. Как и в предыдущем разделе, алгоритмы представлены в виде псевдокода, а исходный код можно найти по тому же адресу http://bpb.googlecode.com.

Основные результаты второй главы опубликованы в [A1, A8, A2] и состоят в следующем:

• Показана применимость инволютивного алгоритма, выполняющего вычисления в коммутативной алгебре, для построения булевых базисов Грёбнера путем проведения вычислений в кольце F2 [X] и дополнения исходной системы булевых многочленов полевыми биномами.

• Разработана версия инволютивного алгоритма, применимого к построению булевых базисов Грёбнера непосредственно в булевом кольце и основанного на делении Поммаре. Доказаны корректность и завершаемость данного алгоритма.

• Получена точная верхняя оценка на число элементов редуцированного булева базиса Грёбнера.

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

В первом разделе рассматриваются способы представления монома в памяти ЭВМ, и обосновывается выбор односвязных списков для хранения мономов в реализациях алгоритмов Жане (т.е. для работы в кольце F2 [X]) и Поммаре (для работы в B [X]). В реализации алгоритма Поммаре список хранит только номера переменных, входящих в моном в степени 1, а в реализации алгоритма Жане — и номера, и показатели степеней переменных, входящих в моном в положительной степени. Приводятся оценки вычислительной сложности для основных операций над мономами в таком представлении.

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

Приводится оценка сложности для каждой их этих операций.

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

Во втором и третьем разделах главы описывается пакет BIBasis, реализующий инволютивный алгоритм на основе деления Поммаре, для открытых систем компьютерной алгебры Macaulay2 и REDUCE. Macaulay2 — это система, специализированная для вычислений в аналитической геометрии и коммутативной алгебры. Её ядро и основные алгоритмы написаны на языке программирования С++. Пакет BIBasis в этой системе также реализован на языке C++. REDUCE — система общего назначения, написана на Standard LISP — диалекте языка LISP. На этом же языке написан и пакет BIBasis для системы REDUCE.

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

Для каждой упомянутой системы приводятся примеры использования пакета BIBasis, иллюстрирующие его возможности. Пример использования BIBasis в системе REDUCE:

1: load_package bibasis;

2: variables := {x0,x1,x2,x3,x4}$ 3: polynomials := {x0*x3+x1*x2,x2*x4+x0}$ 4: bibasis(polynomials, variables, deglex, t);

{x1*x2*(x3 + 1), x1*(x0 + x2), x0*(x2 + 1), x0*x3 + x1*x2, x0*(x4 + 1), x2*x4 + x0} Основные результаты третьей главы опубликованы в [A4, A5] и состоят в следующем:

• Обоснован выбор внутреннего представления данных: мономы и многочлены — односвязные упорядоченные списки.

• Инволютивный алгоритм, основанный на делении Поммаре, реализован на языке C++ в виде отдельной программы, на языке С++ — в виде пакета BIBasis для системы Macaulay2, и на языке Standard LISP — в виде пакета BIBasis для системы REDUCE.

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

В этой главе выбираются тестовые серии примеров из набора стандартных бенчмарков [29, 30] и из коллекции SAT-02 Challenge Set [31]. Используются серии cyclic, eco, redcyc(lic), redeco, ezfact, xor-chains и серия life, полученная из анализа [32] известной игры «Жизнь» Дж. Конуэя.

Далее в главе приводятся результаты сравнения времен счета выбранных примеров. Сравниваются утилиты BJB и BPB, реализующие булевы инволютивные алгоритмы Жане и Поммаре соответственно, утилита BPB сравнивается с библиотекой PolyBoRi [19] и системой компьютерной алгебры Singular [33], пакет BIBasis в системе Macaulay2 — со стандартным алгоритмом gb из этой системы, и пакет BIBasis в системе REDUCE сравнивается с пакетом Groebner. Результаты сравнений представлены в виде графиков, два из которых приводятся ниже.

Рис. 1. Зависимость времени работы системы Macaulay2 от числа переменных для серии eco.

Рис. 2. Зависимость времени работы системы REDUCE от числа переменных для серии eco.

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

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

• на большинстве тестовых примеров BPB быстрее Singular;

• существуют SAT примеры, на которых BPB быстрее PolyBoRi;

• на подавляющем большинстве тестовых примеров BIBasis быстрее gb и Groebner;

• производительность процессора важнее объема оперативной памяти;

• высокая скорость работы разработанного алгоритма экспериментально подтверждена путем сравнения его реализации с существующими пакетами и библиотеками, способными вычислять булевы базисы Грёбнера.

В Заключении сформулированы основные результаты диссертационной работы.

Список публикаций A1. Гердт В. П., Зинин М. В. Инволютивный метод вычисления базисов Грёбнера над F2 // Программирование. 2008. Т. 34, № 4. С. 191–203.

A2. Гердт В. П., Зинин М. В. О роли инволютивных критериев при вычислении булевых базисов Грёбнера // Программирование. 2009. Т. 35, № 2.

С. 90–97.

A3. Gerdt V. P., Zinin M. V. An algorithmic approach to solving polynomial equations associated with quantum circuits // Physics of Particles and Nuclei Letters. 2009. Vol. 6, no. 7. Pp. 521–525.

A4. Гердт В. П., Зинин М. В., Блинков Ю. А. О вычислении булевых инволютивных базисов // Программирование. 2010. Т. 36, № 2. С. 117–125.

A5. Зинин М. В. Пакет BIBasis для вычисления булевых инволютивных базисов и базисов Грёбнера в системах компьютерной алгебры REDUCE и Macaulay2 // Программирование. 2012. Т. 38, № 2. С. 55–67.

A6. Gerdt V. P., Zinin M. V. Grbner bases over F2 // Computer Algebra and Dierential Equations. Vol. 67. 2007. Pp. 59–68.

A7. Gerdt V., Zinin M., Blinkov Y. On computation of Boolean involutive bases // Proceedings of International Conference Polynomial Computer Algebra. 2009. Pp. 17–24.

A8. Gerdt V. P., Zinin M. V. A Pommaret Division Algorithm for Computing Grbner Bases in Boolean Rings // Proceedings of ISSAC 2008. ISSAC’08.

New York: ACM Press, 2008. Pp. 95–102.

Цитированная литература 1. Buchberger B. Ein Algorithmus zum Aunden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal (An Algorithm for Finding the Basis Elements in the Residue Class Ring Modulo a Zero Dimensional Polynomial Ideal): Ph. D. thesis / Mathematical Institute, University of Innsbruck, Austria. 1965.

2. Kandri-Rody A., Weispfenning V. Non-commutative Grbner bases in algeo bras of solvable type // Journal of Symbolic Computation. 1990. Vol. 9.

Pp. 1–26.

3. Carra’Ferro G. Grbner bases and dierential algebra // Proceedings of the 5th international conference, AAECC-5 on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes / Ed. by L. Huguet, A. Poli. Springer-Verlag New York, Inc. New York, NY, USA, 1987. Pp. 129 – 140.

4. Gerdt V. P. On Computation of Grbner Bases for Linear Dierence Syso tems. // Nuclear Instruments and Methods in Physics Research. 2006. Vol.

559(1). Pp. 211 – 214. URL: arXiv.org:math-ph/0509050.

5. Buchberger B. Grbner Bases: An Algorithmic Method in Polynomial Ideal Theory // Multidimensional Systems Theory - Progress, Directions and Open Problems in Multidimensional Systems. Copyright: Reidel Publishing Company, Dordrecht - Boston - Lancaster, The Netherlands, 1985. Pp. 184–232.

6. Brickenstein M. Boolean Grbner bases — Theory, Algorithms and Applicao tions: Ph. D. thesis / Technischen Universitat Kaiserslautern. 2010.

7. Sakai K., Sato Y. Boolean Grbner Bases, 1988.

8. Марченков.. Замкнутые классы булевых функций. Москва: Физматлит, 2000. ISBN: 5-9221-0066-1.

9. Hsiang J., Huang G. Some Fundamental Properties of Boolean Ring Normal Forms // DIMACS series on Discrete Mathematics and Computer Science:

The Satisability Problem. 1997. Vol. 35. Pp. 587–602.

10. Sato Y., Inoue S., Suzuki A. et al. Boolean Grbner bases // J. Symb. Comput.

2011. Vol. 46, no. 5. Pp. 622–632.

11. Kalorkoti K. Model checking in the modal µ-calculus and generic solutions // J. Symb. Comput. 2011. Vol. 46, no. 5. Pp. 584–594.

12. Bernasconi A., Codenotti B., Crespi V., Resta G. Computing Grbner Bases in the Boolean Setting with Applications to Counting.

13. Bardet M., Faug`re J.-C., Salvy B., Spaenlehauer P.-J. On the Complexity of Solving Quadratic Boolean Systems. 2011. URL: arXiv.org:1112.6263v1.

14. Faug`re J.-C. A new ecient algorithm for computing Grbner bases (F4 ) // Journal of Pure and Applied Algebra. 1999. Vol. 139, no. 1–3. Pp. 61–88.

URL: http://www-salsa.lip6.fr/~jcf/Papers/F99a.pdf.

15. Faug`re J.-C. A new ecient algorithm for computing Grbner bases without reduction to zero (F5 ) // Proceedings of the 2002 international symposium on Symbolic and algebraic computation. ISSAC ’02. New York, NY, USA:

ACM, 2002. Pp. 75–83. URL: http://www-salsa.lip6.fr/~jcf/Papers/ F02a.pdf.

16. Garey M. R., Johnson D. S. Computers and Intractability: a Guide to the Theory of N Pcompleteness. New York: Freeman, 1978.

17. Brickenstein M., Dreyer A., Greuel G. et al. New developments in the theory of Grbner bases and applications to formal verication // Journal of Pure and Applied Algebra, Special issue on Theoretical Eectivity and Practical Eectivity of Grbner Bases. 2009. Vol. 213, no. 8. Pp. 1612––1635.

18. Clegg M., Edmonds J., Impagliazzo R. Using the Grbner Basis algorithm to nd proofs of unsatisability // Proc. 28th Annual ACM Symposium on Theory of Computing. 1996. Pp. 174–183.

19. Brickenstein M., Dreyer A. PolyBoRi: A framework for Grbner -basis compuo tations with Boolean polynomials // Journal of Symbolic Computation. 2009.

Vol. 44, no. 9. Pp. 1326 – 1345. Eective Methods in Algebraic Geometry.

URL: http://dx.doi.org/10.1016/j.jsc.2008.02.017.

20. Dawson C. M., Haselgrove H. L., Hines A. P. et al. Quantum computing and polynomial equations over the nite eld Z2 // Quantum Information and Computation. 2005. Vol. 5, no. 2. Pp. 102–112. URL: arXiv.org:

quant-ph/0408129v1.

21. Gerdt V. P., Kragler R., Prokopenya A. N. Computer Algebra Application to Simulation of Quantum Computation // Proceedings of the DST-UNISA-JINR symposium, Ed. by S. Soanos. Models and Methods in Few-and Many-Body Systems. University of South Africa, Pretoria, 2007. Pp. 219–232.

22. Mathematica 6.0. Champaign, Illinois, USA: Wolfram Research, Inc., 2007.

URL: http://www.wolfram.com/.

putation of semi-regular overdetermined algebraic equations // International Conference on Polynomial System Solving - ICPSS. 2004. Pp. 71–75. URL:

http://www-salsa.lip6.fr/~jcf/Papers/43BF.pdf.

24. Arithmetic of Finite Fields. Vol. 5130 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2008.

25. Volny IV F. New Algorithms for Computing Grbner Bases: Ph. D. theo sis / Clemson University. 2011. URL: http://etd.lib.clemson.edu/ documents/1306872881/Volny_clemson_0050D_11180.pdf.

26. Gerdt V. P., Blinkov Y. A. Involutive Bases of Polynomial Ideals // Mathematics and Computers in Simulation. 1998. Vol. 45. Pp. 519–542. URL:

arXiv.org:math.AC/9912027.

27. Gerdt V. P. Involutive Algorithms for Computing Grbner Bases // Como putational Commutative and Non-Commutative Algebraic Geometry, Ed. by S. Cojocaru, G. Pster, V. Ufnarovski. NATO Science Series. NATO Science Series, IOS Press, 2005. Pp. 199–225. URL: arXiv.org:math.AC/0501111.

28. Жарков.., Блинков.. Инволютивные системы алгебраических уравнений // Программирование. 1994. Pp. 53–56.

29. Bini D., Mourrain B. Polynomial test suite. 2006. URL: http://www-sop.

inria.fr/saga/POL.

30. Verschelde J. The database of polynomial systems. 2011. URL: http://www.

math.uic.edu/~jan/demo.html.

31. Hoos H. H., Sttzle T. SATLIB: An Online Resource for Research on SAT // SAT 2000, Ed. by I. P. Gent, H. V. Maaren, T. Walsh. IOS Press, 2000. 32. Kornyak V. V. On Compatibility of Discrete Relations // CASC-2005 proceedings. LNCS 3718. Springer-Verlag, 2005. 272–284 pp. URL: arXiv.org:

math-ph/0504048.

33. Decker W., Greuel G.-M., Pster G., Schnemann H. Singular 3-1-3 – A computer algebra system for polynomial computations. 2011. URL: http:

//www.singular.uni-kl.de.



 
Похожие работы:

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

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

«Трифонов Сергей Владимирович ОПТИМИЗАЦИЯ РАБОТЫ МАЛОМОЩНОЙ БЕСПРОВОДНОЙ СЕНСОРНОЙ СЕТИ НА БАЗЕ ЕЁ ИМИТАЦИОННОЙ МОДЕЛИ Специальность 05.13.18 – Математическое моделирование, численные методы и комплексы программ. АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук Москва – 2013 2 Работа выполнена на кафедре вычислительной математики Московского физико-технического института (государственного университета) Научный руководитель : кандидат...»

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

«ПЫХАЛОВ АЛЕКСАНДР ВЛАДИМИРОВИЧ МЕТОДЫ И СРЕДСТВА ИНТЕГРАЦИИ НЕЗАВИСИМЫХ БАЗ ДАННЫХ В РАСПРЕДЕЛЕННЫХ СЕТЯХ TCP/IP 05.13.11 – Программное и математическое обеспечение вычислительных машин, комплексов и компьютерных сетей Автореферат диссертации на соискание ученой степени кандидата технических наук Ростов-на-Дону 2012 г. Работа выполнена в Южно-Российском региональном центре информатизации Южного Федерального университета. Научный руководитель : Букатов Александр Алексеевич,...»

«Гончар Дмитрий Русланович МЕТОДЫ ПЛАНИРОВАНИЯ ВЫЧИСЛЕНИЙ В САПР СИСТЕМ РЕАЛЬНОГО ВРЕМЕНИ Специальность 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук Москва – 2008 Работа выполнена в отделе Математического моделирования систем проектирования Вычислительного центра им. А.А.Дородницына Российской академии наук кандидат физико-математических...»

«УДК 517.94, 519.6 Эйалло Корней Оксанс ЧИСЛЕННОЕ МОДЕЛИРОВАНИЕ СТАЦИОНАРНЫХ ПЛОСКИХ ТЕЧЕНИЙ СО СВОБОДНЫМИ ГРАНИЦАМИ Специальность 05.13.18 – математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Тверь 2011 Работа выполнена на кафедре функционального анализа и геометрии Тверского государственного университета. Научный руководитель кандидат физико-математических наук, доцент...»

«Суров Максим Олегович Планирование и стабилизация траекторий неполноприводных динамических систем 05.13.01 – Системный анализ, управление и обработка информации (в технических системах) АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург – 2013 Работа выполнена в Национальном исследовательском университете информационных технологий, механики и...»

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

«КНЯЗЬКОВ Дмитрий Юрьевич МОДЕЛИРОВАНИЕ И ОПТИМИЗАЦИЯ ПРОЦЕССА ФОРМИРОВАНИЯ ГОЛОГРАФИЧЕСКИХ ИЗОБРАЖЕНИЙ НА ОСНОВЕ ЭФФЕКТИВНЫХ МЕТОДОВ РАСЧЕТА ЭЛЕКТРОМАГНИТНЫХ ПОЛЕЙ специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание учёной степени кандидата физико-математических наук Москва — 2013 Работа выполнена в лаборатории механики управляемых систем Федерального государственного бюджетного учреждении науки...»

«ПЛЕШКОВА ЮЛИЯ АЛЕКСАНДРОВНА МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЭФФЕКТИВНЫХ СИСТЕМ ПЕРЕДАЧИ ОПТИЧЕСКОГО СИГНАЛА НАСЕКОМЫМ Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени кандидата технических наук Тамбов – 2014 2 Работа выполнена на кафедре прикладной математики и информатики Федерального государственного бюджетного образовательного учреждения высшего профессионального образования...»

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

«УДК 517.96; 537.87 ЧЕРНОКОЖИН Евгений Владимирович ИССЛЕДОВАНИЕ ЗАДАЧИ СИНТЕЗА НЕРАССЕИВАЮЩИХ ТЕЛ 05.13.18 – математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук Москва 2007 Работа выполнена в лаборатории вычислительной электродинамики факультета вычислительной...»

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

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

«Ефимов Александр Александрович МОДЕЛИ И ОРГАНИЗАЦИОННЫЕ МЕХАНИЗМЫ ПРОДВИЖЕНИЯ ПРИКЛАДНЫХ ПРОГРАММНЫХ ПРОДУКТОВ Специальность 05.13.10 — Управление в социальных и экономических системах (технические наук и) Автореферат диссертации на соискание ученой степени кандидата технических наук Новосибирск – 2011 Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Томский государственный университет систем управления...»

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

«Муравьева-Витковская Людмила Александровна МЕТОДЫ ИССЛЕДОВАНИЯ ПРОЦЕССОВ УПРАВЛЕНИЯ НЕОДНОРОДНЫМ ТРАФИКОМ В ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМАХ Специальность 05.13.13 - Телекоммуникационные системы и компьютерные сети АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук Санкт-Петербург - 2007 2 Работа выполнена в Государственном образовательном учреждении высшего профессионального образования Санкт-Петербургский государственный университет информационных...»

«Логинов Константин Константинович Имитационное моделирование динамики популяций, развивающихся в нестационарной среде 05.13.18 — Математическое моделирование, численные методы и комплексы программ Автореферат диссертации на соискание ученой степени кандидата физико-математических наук Омск – 2012 Работа выполнена в Омском филиале Учреждения Российской академии наук Института математики им. С. Л. Соболева СО РАН Научный руководитель : доктор физико-математических наук,...»

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






 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

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