Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Кибернетика и программирование
Правильная ссылка на статью:

О практической реализации некоторых алгоритмов, связанных с проблемой композиции чисел

Бородин Андрей Викторович

кандидат экономических наук

профессор, кафедра информатики и системного программирования, ФГБОУ ВПО «Поволжский государственный технологический университет»

424000, Россия, Республика Марий Эл, г. Йошкар-Ола, пл. Ленина, 3

Borodin Andrey Viktorovich

PhD in Economics

Professor, Department of Computer Science and System Programming, Volga State University of Technology

424000, Russia, respublika Marii El, g. Ioshkar-Ola, pl. Lenina, 3

bor@mari-el.com
Другие публикации этого автора
 

 
Бирюков Евгений Сергеевич

студент, кафедра ИиСП, Поволжский государственный технологический университет

424000, Россия, республика Марий Эл, г. Йошкар-Ола, пл. Ленина, 3

Biryukov Evgeniy Sergeevich

student, Department of Informatics and System Programming, Volga State University of Technology

424000, Rossiya, respublika Mariy El, g. Yoshkar-Ola, pl. Lenina, 3

Eugene.Biryukov@icloud.com

DOI:

10.7256/2306-4196.2015.1.13734

Дата направления статьи в редакцию:

19-11-2014


Дата публикации:

20-01-2015


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


Ключевые слова:

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

УДК:

004.051

Abstract: Among combinatorial algorithms of additive number theory the algorithms of the algorithms for listing compositions of natural numbers have a special place. On the one hand, ideologically, they are among the simplest algorithms in mentioned theory. On the other hand, they play a huge role in all applications somehow connected with the polynomial theorem. In recent years, due to the rapid development of the general theory of risk ideas underlying the polynomial theorem were involved to in the challenges of risk measurement in homogeneous systems of high dimensionality. Solving these problems requires providing mass listing compositions numbers of fixed length and calculating the amount of such compositions for sufficiently large values of both number and the length of composition. In these circumstances, the most urgent task is in effective implementation of these algorithms. The presented article is devoted to the questions related with the synthesis of efficient algorithms for listing the compositions of fixed length and calculating the amount of such compositions. As a methodological base of this study authors use certain facts of set theory, approaches of theory of complex algorithms, as well as some basic results of the theory of numbers. Within this paper, the author propose a new efficient implementation of two algorithms: algorithm for listing all the compositions of fixed length based on the idea of multiset representation of the number partitions and algorithm for calculating the amounts of the compositions of given kind, implemented without involvement of high bitness machine arithmetic. The article shows not only an estimate of the complexity of the proposed algorithms but also presents the results of numerical experiments demonstrating the effectiveness of the implementation of the algorithms discussed in the VBA programming language. 


Keywords:

number composition, number expansion, partition of the number, polynomial theorem, multiset, complexity of the algorithm, risk, risk theory, risk measurement, total cost of ownership

Введение

Пусть `n` – натуральное число. Рассмотрим задачу порождения такого множества целых неотрицательных чисел `{ r_1, quad r_2, quadldots quad, quadr_m }` , что `sum_{k=1}^m quad r_k = n`. В зависимости от ограничений, накладываемых на числа `r_k`, `k=1, quad 2, quad ldots quad, quad m `, постановка этой задачи может несколько видоизменяться. Если порядок чисел `r_k `, `k=1, quad 2, quad ldots quad, quad m `, важен, то последовательность `( r_1, quad r_2, quad ldots quad, quad r_m )` называется композицией или разложением `n `, а число `m` длиной композиции [5, 7]. При этом обычно накладываются следующие дополнительные ограничения: `r_k > 0 `, `k=1, quad 2, quad ldots quad, quad m `. В отдельных случаях число `m` фиксируется, и тогда возможно рассмотрение композиций, содержащих нулевые элементы, `r_k >= 0 `, `k=1, quad 2, quad ldots quad, quadm `. Эти композиции называются композициями числа `n` из `m` частей. Если порядок `r_k` не важен и `r_k > 0 `, `k=1, quad 2, quad ldots quad, quad m `, то `{ r_1, quad r_2, quad ldots quad, quad r_m }` является мультимножеством и называется разбиением числа `n` [7].

Задача перечисления всех композиций фиксированной длины чрезвычайно тесно связана с полиномиальной теоремой [4]. При этом последняя занимает центральное место в ряде приложений современной теории риска [8].

Такими приложениями являются:

1) оценка риска однородных финансовых инструментов [13], в том числе розничных кредитных портфелей [11];

2) расчет случайной величины совокупной стоимости владения технической системой за период времени при известной дневной статистике отказов [3];

3) расчет случайной величины совокупной стоимости владения технической системой за период времени при имеющихся оценках вероятностей успеха реализации атак злоумышленником в течение некоторого интервала (кванта) времени [9, 12];

4) оценка эффективности системы массового обслуживания клиентов в условиях риска ошибок и злоупотреблений со стороны персонала, а также задачи управления такими системами [1, 2].

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

Задача перечисления композиций фиксированной длины

Простейший алгоритм перечисления всех композиций числа `n` фиксированной длины `m` может быть построен на основе того факта, что все эти композиции содержатся в множестве всех возможных образов некоторого упорядоченного множества `A` , мощности `m` , в кольце вычетов по модулю `n+1` :

`forall A quad ( | A | = m ) quad [ { ( r_1, quad r_2, quad ldots quad, quad r_m) } sub { ( f(A)) quad : quad fin Map(A, quadmathbb{Z}_{n+1}}] ` ,

где `( f(A) )` – упорядоченное множество образов элементов множества `A` под действием `f` , это множество упорядочено в порядке следования элементов множества `A` ;

`Map(A, quad mathbb{Z}_{n+1}) = ( mathbb{Z}_{n+1} ) ^ A` – множество всех отображений из `A` в `mathbb{Z}_{n+1}` ;

`mathbb{Z}_{n+1} = {0, quad 1, quad ldots quad, quad n}` – кольцо вычетов по модулю `n+1` .

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

`forall A quad ( | A | = m ) quad [ { (r_1, quad r_2, quad ldots quad, quad r_m) } = { (f(A)) quad : quad f in Map(A, mathbb{Z}_{n+1}), quad sum_{x in A} f(x) = n} ]` .

Листинг 1 представляет практическую реализацию этого принципа на языке программирования VBA. Идея построения вариантов упорядоченного множества образов элементов множества `A` под действием отображения `f` заключается в интерпретации образа множества как представления порядкового номера варианта отображения в виде последовательности цифр в системе счисления с основанием `n+1` .

Листинг 1

gensplit1

Для оценки временной сложности предложенного алгоритма используем подход, основанный на оценке временной стоимости каждого оператора языка программирования и подсчете количеств исполнений каждого оператора [6]. Временную стоимость каждой операции примем за 1, а стоимость связки операторов "For i=j to k" и "Next i" оценим как `1 + ( k - j + 1) xx ( 3 + y )` , где `y` – временная стоимость тела цикла.

В результате для функции временной сложности алгоритма имеем:

`f(n, m)=3+1+ (n+1)^m xx quad (3+1+1+m xx (3+2+2)+1+1+m xx (3+1)+1+{[x+1],["0"]}) +1 =`

`=(n+1)^m xx quad (11 m + {[x+9],["8"]} ) + 5` ,

где `x` временная стоимость процедуры утилизации композиции UtilSplit,

`{[a],[b]}` – возможный выбор из двух альтернатив `a` или `b` .

Таким образом, оценкой сложности [14] предложенного алгоритма является

`Theta ( m(n+1)^m )`. (1)

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

Воспользуемся идеей, положенной в основу доказательства того факта, что общее количество композиций числа `n` длины `m` равно `([n+m-1], [m-1]) = ([n+m-1], [n])` ` ` , где `([n], [m])` – число сочетаний (биномиальный коэффициент) из `n` по `m quad`[7].

Идея заключается в представлении числа `k` мультимножеством `k` единиц. В таком случае композицию числа `n` длины `m` удобно представить в виде упорядоченного мультимножества (массива) длины `n+m-1`, где кроме `n` единиц присутствуют `m-1` нулей, выполняющих функцию разделителей упорядоченного мультимножества на `m` частей (мультимножеств), пустых или состоящих из одних единиц. Перечисление всех таких упорядоченных мультимножеств эквивалентно перечислению композиций числа `n` длины `m`.

Эта идея воплощена в алгоритме, представленном на листинге 2 в виде функции, реализованной на языке программирования VBA. За основу реализации был взят фрагмент кода процедуры возведения в степень полинома, описывающего риск, входящей в пакет прикладных программ "МультиМИР" версии 1.0 [8, 11] (речь идет о процедуре RP).

Листинг 2

gensplit21

gensplit22

Оценим временную сложность нового алгоритма. Разбор алгоритма позволяет записать:

`f(n, m)=8+1+(n+m-1) xx (3+1) + 3+`

`+C xx ([n+m-1],[n]) xx (1+1+{[1+{["1"],["3"]}],[1+1+{[2+1+(n+m-1) xx (3+1+{["3"],["1"]})+1+x+1+2],["4"]}]})=`

`=4(n+m-1)+12+C xx ([n+m-1], [n]) xx {["4"],["6"],["8"],[{["5"],["7"]} xx (n+m-1) +x +11]}` ,

где `C` – константа, учитывающая в среднем выбор в цикле "While" ветви формирования разбиения мультимножества наряду с ветвью подсчета мощностей мультимножеств и вызова процедуры утилизации очередной сформированной композиции;

`([n+m-1], [n])` – количество композиций числа `n` длины `m`, иначе - это количество повторений ветви подсчета мощностей мультимножеств и утилизации очередной композиции.

Таким образом, оценкой сложности этого алгоритма является

`Theta((n+m-1)xx([n+m-1], [n]))` . (2)

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

t480gensplit12

Рис. 1. Результаты численного эксперимента по сравнению временной сложности алгоритмов GenSplit1 и GenSplit2.

Рис. 1 наглядно демонстрирует преимущество второго алгоритма GenSplit2. Однако остается ряд вопросов. Каков характер роста временных затрат алгоритма GenSplit2 с ростом значений параметров? Алгоритм GenSplit2 принципиально лучше алгоритма GenSplit1 или это просто более совершенная реализация того же класса сложности алгоритмов?

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

t480gensplit2

Рис. 2. Результаты численного эксперимента по изучению зависимости временных затрат алгоритма GenSplit2 при перечислении композиций натуральных чисел в диапазоне от 20 до 100 для ряда значений длины композиций.

Сравнивая рисунки 1 и 2, можно выдвинуть гипотезу о совпадении (или существенной близости) классов сложности обоих предложенных алгоритмов. Эта гипотеза находит косвенное подтверждение в монографии [8]. Действительно, в этой работе на стр. 81 приведена иллюстрация, которая показывает, что количество композиций числа `n` длины `m` при `n->oo` асимптотически изменяется как `n^{m-1}` , по крайней мере, если `m/n -> 0` . Иначе говоря, имеет место соотношение

`lim_(n->oo, quad m/n->0) ([n+m-1], [n]) quad = quad c n^{m-1}` , (3)

где `c` – некоторая константа.

Таким образом, оценку (2) с учетом соотношения (3) при условии `m/n-> 0` можно переписать следующим образом:

`Theta((n+m-1)n^{m-1})`. (4)

Хотя обе оценки, (1) и (4), относят оба предложенных алгоритма к классу EXPTIME [14], тем не менее при малых значениях `m` алгоритм с оценкой сложности (4) заметно эффективнее алгоритма с оценкой сложности (1). Это последнее замечание подтверждается в том числе проведенными численными экспериментами.

Задача вычисления количества композиций фиксированной длины

Рассмотрим теперь задачу вычисления количества композиций числа `n` длины `m`. Количество таких композиций определяется соотношением [4, 7]:

`([n+m-1], [n]) = {(n+m-1)(n+m-2) quad ldots quad m}/{n!}` . (5)

Реализация "в лоб" алгоритма вычисления количества композиций по формуле (5) на языке программирования VBA приведена на листинге 3.

Листинг 3

getnmonom01

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

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

Листинг 4

getnmonom02

Данная модификация алгоритма позволяет отодвинуть границы применимости алгоритма вычисления количества композиций в сторону несколько больших значений параметров `n` и `m`, но этого все еще не достаточно для потребностей практики.

Прежде чем построить новую вычислительную схему, оптимизирующую вычисление правой части соотношения (5), введем ряд обозначений. Пусть `vec p` – вектор, компонентами которого являются первые `l` простых чисел:

`vec p = (p_i)_{i=1}^{l} quad = (2, quad 3, quad 5, quad 7, quad 11, quad ldots quad), quad p_i in mathbb P, quad i=1, quad 2, quad ldots quad, quad l,`

здесь `mathbb P` – множество простых чисел.

Пусть, далее, `vec f` – вектор-функция частичной факторизации:

`(e_i)_{i=1}^l quad = vec {f} (vec p, n) quad hArr_{Def} quad n = mprod_{i=1}^l p_i^{e_i}, `

`e_i in ZZ_0^{+}, quad m != 0 (mod quad p_i), quad i=1, quad 2, quad ldots quad, quad l,`

`g` – функция, возвращающая остаточный член, возникающий при частичной факторизации:

`m=g(vec p, n) quad hArr_{Def} quad n = m prod_{i=1}^l p_i^{e_i},`

`e_i in ZZ_0^{+}, quad m!=0(mod quad p_i), quad i=1, quad 2, quad ldots quad, quad l,`

где `ZZ_0^{+}` – множество неотрицательных целых чисел.

И, наконец, пусть `pi` – функция, формирующая число из результатов его частичной факторизации:

`pi(vec p, quad vec e, quad m) =_{Def} m prod_{i=1}^l p_i^{e_i}.`

Пользуясь введенными обозначениями, соотношение (5) можно переписать следующим образом:

`([n+m-1], [n]) = pi (vec p, quad sum_(i=0)^{n-1} vec{f}(vec p, quad m+i) - sum_(i=1)^n vec{f}(vec p, quad i), quad {prod_(i=0)^{n-1} g(vec p, quad m+i)}/{prod_(i=1)^n g(vec p, quad i)}) . (6)`

На основе соотношения (6) можно построить новый алгоритм вычисления количества разбиений. Так на листинге 5 представлена часть реализации этого алгоритма, связанная с описанием структур данных и инициализации массива простых чискл. Реализация самого алгоритма приведена на листинге 6.

Листинг 5

getnmonom2init

Листинг 6

getnmonom2main

На листинге 7 приведен код вспомогательных процедур, используемых основным алгоритмом.

Листинг 7

getnmonom2sub

Тестирование функции GetNMonom2 продемонстрировало ее способность вычислять количества композиций, исчисляющиеся величинами в пределах числа `2^31 - 1` .

Заключение

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

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

Дальнейшим развитием исследований, описанных в данной статье, представляется работа по совершенствованию алгоритма, реализованного в рамках функции GenSplit2, в направлении снижения коэффициента перед выражением `(n+m-1)([n+m-1], [n])` в функции временной трудоемкости алгоритма.

Библиография
1. Бородин, А. В. Архитектура информационной системы поддержки принятия решений по управлению персоналом розничной подсистемы коммерческого банка // Программные системы и вычислительные методы. – 2014. – №2. – С. 174–190. – DOI: 10.7256/2305–6061.2014.2.12331.
2. Бородин, А. В. Модели управления персоналом в розничной подсистеме коммерческого банка / А. В. Бородин // Экономика и социум: современные модели развития общества в аспекте глобализации: материалы III международной научно-практической конференции (12 февраля 2014 г.). – Саратов: Издательство ЦПМ «Академия Бизнеса», 2014. – С. 26–30.
3. Бородин, А. В. Стохастическое моделирование в задачах синтеза оптимальных топологий сетей дистрибуции точного времени / А. В. Бородин, Д. Р. Зубьяк // Технические науки – от теории к практике. Сборник статей по материалам XXXIV международной научно-практической конференции. № 5 (30). – Новосибирск: Издательство «СибАК», 2014. – С. 7–15.
4. Виленкин, Н. Я. Комбинаторика / Н. Я. Виленкин. – М.: Наука, 1969. – 328 с.
5. Композиция числа // Википедия. Свободная энциклопедия. – URL: https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D1%8F_%D1%87%D0%B8%D1%81%D0%BB%D0%B0. Дата обращения: 17.11.2014.
6. Кормен, Т. Х. Алгоритмы: построение и анализ / Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн. – М.: ООО «И. Д. Вильямс», 2013. – 1328 с.
7. Рейнгольд, Э. Комбинаторные алгоритмы: теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. – М.: Мир, 1980. – 477 с.
8. Уразаева, Т. А. Алгебра рисков / Т. А. Уразаева. – Йошкар-Ола: Поволжский государственный технологический университет, 2013. – 209 с.
9. Уразаева, Т. А. Инструментальные методы анализа риска в экономике безопасности вычислительных сетей / Т. А. Уразаева // Материалы III Международной научно-практической конференции «Инновационное развитие российской экономики». Часть 1. – М.: МЭСИ, 2010. – С. 246-250.
10. Уразаева, Т. А. Пакет прикладных программ «МультиМИР»: архитектура и применение / Т. А. Уразаева // NB: Кибернетика и программирование. – 2014. – № 5. – С.34-61. – DOI: 10.7256/2306-4196.2014.5.12962. – URL: http://e-notabene.ru/kp/article_12962.html.
11. Уразаева, Т. А. Пакет прикладных программ «МультиМИР» в практике анализа кредитного риска / Т. А. Уразаева // VIII Международная научно-методическая конференция «Совершенствование подготовки IT-специалистов по направлению «Прикладная информатика» для инновационной экономики»: Сборник научных трудов. – М.: Московский государственный университет экономики, статистики и информатики, 2012. – С. 182-186.
12. Уразаева, Т. А. Стоимостной анализ риска нарушения одной политики безопасности в вычислительных сетях / Т. А. Уразаева // Моделирование и анализ безопасности и риска в сложных системах: Труды Международной научной школы МА БР – 2010 (Санкт-Петербург, 6-10 июля, 2010 г.). – СПб.: ГУАП, СПб., 2010. – С. 193-199.
13. Уразаева, Т. А. Финансовые риски: алгебраическая модель исчисления / Т. А. Уразаева // Региональная экономика: теория и практика. – 2010. – № 2(137). – С. 33-35.
14. Arora, S. Computational Complexity: A Modern Approach / S. Arora, B. Barak. – New York: Cambridge University Press, 2009. – 594 p.
References
1. Borodin, A. V. Arkhitektura informatsionnoi sistemy podderzhki prinyatiya reshenii po upravleniyu personalom roznichnoi podsistemy kommercheskogo banka // Programmnye sistemy i vychislitel'nye metody. – 2014. – №2. – S. 174–190. – DOI: 10.7256/2305–6061.2014.2.12331.
2. Borodin, A. V. Modeli upravleniya personalom v roznichnoi podsisteme kommercheskogo banka / A. V. Borodin // Ekonomika i sotsium: sovremennye modeli razvitiya obshchestva v aspekte globalizatsii: materialy III mezhdunarodnoi nauchno-prakticheskoi konferentsii (12 fevralya 2014 g.). – Saratov: Izdatel'stvo TsPM «Akademiya Biznesa», 2014. – S. 26–30.
3. Borodin, A. V. Stokhasticheskoe modelirovanie v zadachakh sinteza optimal'nykh topologii setei distributsii tochnogo vremeni / A. V. Borodin, D. R. Zub'yak // Tekhnicheskie nauki – ot teorii k praktike. Sbornik statei po materialam XXXIV mezhdunarodnoi nauchno-prakticheskoi konferentsii. № 5 (30). – Novosibirsk: Izdatel'stvo «SibAK», 2014. – S. 7–15.
4. Vilenkin, N. Ya. Kombinatorika / N. Ya. Vilenkin. – M.: Nauka, 1969. – 328 s.
5. Kompozitsiya chisla // Vikipediya. Svobodnaya entsiklopediya. – URL: https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D1%8F_%D1%87%D0%B8%D1%81%D0%BB%D0%B0. Data obrashcheniya: 17.11.2014.
6. Kormen, T. Kh. Algoritmy: postroenie i analiz / T. Kh. Kormen, Ch. I. Leizerson, R. L. Rivest, K. Shtain. – M.: OOO «I. D. Vil'yams», 2013. – 1328 s.
7. Reingol'd, E. Kombinatornye algoritmy: teoriya i praktika / E. Reingol'd, Yu. Nivergel't, N. Deo. – M.: Mir, 1980. – 477 s.
8. Urazaeva, T. A. Algebra riskov / T. A. Urazaeva. – Ioshkar-Ola: Povolzhskii gosudarstvennyi tekhnologicheskii universitet, 2013. – 209 s.
9. Urazaeva, T. A. Instrumental'nye metody analiza riska v ekonomike bezopasnosti vychislitel'nykh setei / T. A. Urazaeva // Materialy III Mezhdunarodnoi nauchno-prakticheskoi konferentsii «Innovatsionnoe razvitie rossiiskoi ekonomiki». Chast' 1. – M.: MESI, 2010. – S. 246-250.
10. Urazaeva, T. A. Paket prikladnykh programm «Mul'tiMIR»: arkhitektura i primenenie / T. A. Urazaeva // NB: Kibernetika i programmirovanie. – 2014. – № 5. – S.34-61. – DOI: 10.7256/2306-4196.2014.5.12962. – URL: http://e-notabene.ru/kp/article_12962.html.
11. Urazaeva, T. A. Paket prikladnykh programm «Mul'tiMIR» v praktike analiza kreditnogo riska / T. A. Urazaeva // VIII Mezhdunarodnaya nauchno-metodicheskaya konferentsiya «Sovershenstvovanie podgotovki IT-spetsialistov po napravleniyu «Prikladnaya informatika» dlya innovatsionnoi ekonomiki»: Sbornik nauchnykh trudov. – M.: Moskovskii gosudarstvennyi universitet ekonomiki, statistiki i informatiki, 2012. – S. 182-186.
12. Urazaeva, T. A. Stoimostnoi analiz riska narusheniya odnoi politiki bezopasnosti v vychislitel'nykh setyakh / T. A. Urazaeva // Modelirovanie i analiz bezopasnosti i riska v slozhnykh sistemakh: Trudy Mezhdunarodnoi nauchnoi shkoly MA BR – 2010 (Sankt-Peterburg, 6-10 iyulya, 2010 g.). – SPb.: GUAP, SPb., 2010. – S. 193-199.
13. Urazaeva, T. A. Finansovye riski: algebraicheskaya model' ischisleniya / T. A. Urazaeva // Regional'naya ekonomika: teoriya i praktika. – 2010. – № 2(137). – S. 33-35.
14. Arora, S. Computational Complexity: A Modern Approach / S. Arora, B. Barak. – New York: Cambridge University Press, 2009. – 594 p.