О выборе орбит для космических аппаратов
Автор: Егорычев Г. П., Ширяева Т. А., Шлепкин А. К., Филиппов К. А., Пашковская О. В.
Журнал: Сибирский аэрокосмический журнал @vestnik-sibsau
Рубрика: Информатика, вычислительная техника и управление
Статья в выпуске: 4 т.22, 2021 года.
Бесплатный доступ
Рассматривается задача распределения заданного числа космических аппаратов по некоторому структурированному множеству орбит, состоящему из n = pk орбит. Решение данной задачи дано при условии, что множество возможных орбит для космических аппаратов совпадает с количеством космических аппаратов. Дополнительно предполагается, что данное множество разбито на непересекающиеся подмножества орбит, причем количество орбит в указанных подмножествах одинаково. В рассматриваемой ситуации оно равно некоторому простому числу p. В настоящее время используется несколько орбит для размещения на них спутников в зависимости от решаемых ими задач. Геостационарная орбита используется для прямого телевещания. Низкие спутниковые орбиты используются для связи между спутниковыми телефонами. Свои орбиты существуют для спутников систем навигации GPS, Navstar, ГЛОНАСС, военных спутников, спутников для различных научных исследований. Естественно, что в этих условиях возникает задача структурирования множества орбит при некоторых ограничениях на нахождение космического аппарата на заданных орбитах в зависимости от назначения космического аппарата. Рассмотрен вопрос сложности вычисления количества орбит при данных ограничениях.
Спутник, орбита, подстановка
Короткий адрес: https://sciup.org/148323922
IDR: 148323922 | DOI: 10.31772/2712-8970-2021-22-4-568-576
Текст научной статьи О выборе орбит для космических аппаратов
Продолжены исследования, начатые в [1] и посвященные решению задачи о выборе наиболее благоприятных орбит для космических аппаратов того или иного класса, а также задача распределения заданного количества спутников по заданному множеству орбит при существующих запретах на нахождение спутника на некоторых орбитах. В статье приведено решение данной задачи при следующих условиях: число спутников n совпадает с числом возможных орбит нахождения на них спутников; каждому спутнику запрещено находиться ровно на одной орбите; два спутника не могут находиться на одной орбите; количество орбит разбивается на непересекающиеся блоки определенной конфигурации ( n = pk ). Приводится формула позволяющая вычислить число возможных комбинаций для распределений спутников по таким орбитам.
Постановка задачи, определения, обозначения
Математическая модель задачи. Под подстановкой будем понимать взаимно однозначное отображение, записанное в виде таблицы размерности 2 х n :
i 2

Подстановка называется регулярной, если k ^ ik, т. е.
i 1 * 1, i 2 ^ 2, "', i n * n .
Напомним, что под порядком подстановки в теоретико-групповом смысле понимается такое минимально возможное натуральное число m, что g
m
' 1 2

i 2

' 1 2
< i 1 i 2
n LP 2
1 = e n )
m раз
– единичная подстановка. При этом произведение подстановок – это последовательное выполнение отображений-множителей. В данной работе мы будем рассматривать случай n = pk, где p – простое число. Будет рассмотрена задача перечисления всех регулярных подстановок степени n , имеющих порядок p . Под циклической формой записи подстановки g , степени n и имеющей порядок p будем понимать следующее:
' 1 2
к i i i 2
' n 7
=(> (') /Ок •[/ p k "') ,l p k 'H ( i ' "• i p ) "• i n - p + ' "• i n
.
Приведенные выше понятия из теории подстановок можно найти в [2]. Таким образом, каждому варианту расположения спутников на орбитах, указанному выше, будет соответствовать в точности одна регулярная подстановка вида (3). Дополнительно приведена оценка сложности вычисления числа указанных орбит.
Основные результаты
Число регулярных подстановок степени n = p k и имеющих порядок p будем обозначать через R ( n , p , k ) .
Теорема 1.
( p k ) !
R ( n , p , k )=, a ■-. (4)
pP • ( p k - ' ) !
С учетом того, что цикл при «круговом» сдвиге элементов не меняется как подстановка, имеем:
p
Число возможных комбинаций для второго цикла ( i' 2). . i p 2)) равно
(pk -p)•(pk -(p + '))•.•(pk -(2p-')).
С учетом того, что цикл при «круговом» сдвиге элементов не меняется, как подстановка, имеем
p
Действуя подобным образом для последнего цикла с номером ( pk - ' ) , получаем ( p k -( p k - p ) ) • ( p k -( p k - ( p - ' ) ) ) •.• ( p k -( p k - ( p - ( p - ' ) ) ) )
p
Произведение числа комбинаций для всех циклов есть p k • ( p k - ' ) •.• ( p k - p + ' )
p
p
(pk -(pk -p))•(pk -(pk -(p -')))•.•(pk -(pk -(p-(p -')))) p pk!
( p k - ' ) . p
Для завершения доказательства достаточно разделить указанную величину на рк 1 !. Получаем
, p- !
R ( n , Р , к ) = -р-й• p ( p )• p - - 1 !
Теорема доказана.
Оценка сложности оптимального алгоритма для вычисления числа R ( n , p , k )
Приведём несколько полезных свойства чисел R (n, p, к), из которых наибольшую важность представляет второе из них, где приведена оценка сложности оптимального алгоритма для вычисления числа R (n, p, к).
Определение. Пусть A(n), B(n) - числовые функции, зависящие от натурального n. Выраже-х A(n) , ние A (n) ~B (n) означает, что lim —= 1.
v ! v ! n ^» B (n)
Теорема 2. При n ^ да
1 к - -1/„ п
R ( П , p , к ) ~ p 2 ( Рк / e )
.
Доказательство. Ввиду классической асимптотической формулы Стирлинга для факториала n! при n ^да : n! ~ V2пn •( n / e)"
получаем:
R ( n , p , к ) =
Р - !
p ( Р - - 1 ) • Р - - 1 !
kp
,к p e
k
p p
Рр ■\[2Пр
к А р-
e
k
Р г
---f n к-1 Y , к-1 p___ pi Арк e
i
Р p
р- - 1 а р к e )
p p
---( п к - 1 Y , к - 1 p
p p p
к - 1
k
Р г
k p p
1 Г Р‘ = p 2 -
p
p i а р к e .
к - 1 Г
p
i
Р 2
Г Р
.к А р к
к e )
р - - 1 ) p e .
, 2 Г p
к - 1 А р к
e
p p
k
. к - 1 А p - Р
e
p p
k p p
( и к - 1 Y
p- к e )
, к - 1
• p p p
, к - 1
Г Р - - 1 А Р
e
1 Р p р - - 1 p p
i
= р 2
Г .
Р
к А р- - 1 ( р - 1 )
, к - 1
.
p k
• Р
Теорема доказана.
Формула (5) показывает, что число R ( n , p , k ) с ростом к растёт очень быстро, как

Вместе с тем В. В. Кочергин в 1994 г. в [3] привёл оптимальный алгоритм,
позволяющий находить значение 2 n (исходя из 2) за O ( log n )
арифметических операций умножения. В свою очередь Р. В. Borwein в 1985 г. в [4] привёл быстрый алгоритм для вычисления факториала n !, сложность которого равна
O ( n ( log n ( log ( log n ) ) ) 2 )
(см. также [5; 6]). Оценки сложности (6) и (7) применительно к формуле (4) для числа
R ( n , p , к ) , содержащей два факториале ( p k ) ! и ( p k 1 ) !, дают следующий результат.
Теорема 3. Быстрые алгоритмы Кочергина и Borwein при n = p k и n = p k 1 соответственно, порождают оптимальный алгоритм для вычисления числа R ( n , p , k ) , сложность которого
равна
O Г p k ■ ( log p k ■ log ( log p k ) )
Производящие функции различного типа, как и интегральные представления функций одного и нескольких комплексных переменных, являются основными инструментами современного перечислительного комбинаторного анализа [7–15]. Используя следующие хорошо известные интегральные формулы для факториала n ! и 1/ n !, например [6],
n ! = J s n e - s ds , 0
— = —— I" exx n 1 dx , 0 <у<да , n ! 2 n L r
| x =Y
мы получаем
Теорема 4. Число R ( n , p , k ) имеет следующее интегральное представление:
R ( n , p , k )
да
J s n e s ds ■
2п1 1 r
| x =Y
e x x’ n - 1 dx ,
Заключительные выкладки мы проведём с помощью метода коэффициентов Егорычева интегрального представления и вычисления комбинаторных сумм [14; 15].
Определение. Введём в рассмотрение интегралы вида да
H p ( 5 ) = J e-s +5 s p ds , (12)
где p - простое число; 8 - действительное число, не зависящее от s .
Пусть S ( z ) - производящая функция степенного типа для последовательности R ( n , p , k ) , k = 1, 2, …,
№ № k
.
S (z ) = ZR (n, p, k) zn =ZR (n, p, k) zp k=1 k=1
Теорема 5 (интегральное представление для функции S ( z )). Производящая функция S ( z ) допускает следующее представление:
S ( z ) = — J № e" s + tz p s p t -1 A ( t , k ) dsdt , 2 n i\t\ = u 0
где функция (ряд) A ( t , k ) – ядро интегрального представления функции S ( z ) имеет следующий вид:
№
A (t,k )=Z( pt)
k = 1
—
■ pk —1 I 1
, | pt > 1 при любом p
или с учетом (12)
S ( z ) = 2 n_ J t -1 H p ( tz p ) A ( t , k ) dt .
Доказательство. Используя формулу (11) для чисел R ( n , p , k ) , имеем
№k k=1
Pk —1 p p
Pk —1 p p
p p — 1
№
Zzp k=1
Z z p —1 ) p k =1' '
№
№
p
№
№ №
Z]Z(zm) p J( sm)
k = 1 m = 0 о
e s ds •—— f e x x 1 p dx =
2n i, r | x |=Y
— f exx — 2n i । r
I x |=Y
1 — p k — 1 dx =
I p e — s
ds • — [ e x x "1— p 2n i , r
| x |=Y
dx •§ ( m
p —
Здесь б ( m — p k 1 ) - дельта-функция:
5( m — p k — ) = 2П, J
e — 1 + m — p k 1 dt , (0 < u <№ )..
Тогда формула (16) примет вид
№
№
№
Pk —1 p p
£Ш--") p-J(sp)
k = 1
1 r 1 1 r k —1
e- s ds • — e x x" m — 1 dx • — e m — p dt
2n i, r 2n i .r
(перегруппировка членов в последней сумме с выделением в квадратных скобках тех из них, которые содержат индекс m )
Pk — 1 p p
№ 1 № № _
Z ]^ J J Z ( tz-s- ) • k = 1 [ 2 K i t |= u 0 L m = 0
№
№
— f e x x" m — 1 dx 2n i, r
| x |=Y ,
• e — s t — 1 — p k 1 dsdt
(суммирование в квадратных скобках по индексу m , правило подстановки, замена x = tzpsp )
pk — 1 p p
№№
Z _L J J e zx e- s t p k — 1 dsdt = k = 1 2 n i |t |= u 0
(занесение знака суммы за знак интеграла). При этом, поскольку выбор параметра u ничем не ограничен, 0 < и < да , то мы выбираем и > 1/2, чтобы неравенство \pt\ > 1 выполнялось при любом простом p,
w
— Г - , + ,z p sP
2”| , |. и 0
Л w
Г1 К pt)
.- p k - 1
dsdt,
V к = 1
что завершает доказательство теоремы 5.
Заключение
Таким образом, решена задача распределения спутников по заданному множеству орбит при определенных условиях: количество всевозможных комбинаций определяется числом регулярных подстановок R ( n, p, к ) . Приведена оценка сложности оптимального алгоритма для вычисления этого числа.
Заметим, что преобразование (16) несколько парадоксально, поскольку вводит дополнительную сумму по индексу m и тем самым на порядок усложняет исходное выражение. Однако это преобразование совместно с введением дельта-функции позволило получить для числа R ( n , p , k ) интегральное представление нового типа. Отметим также, что преобразование (16) встретилось в практике метода коэффициентов впервые, что предоставляет новые возможности для эффективного применения этого метода.
В связи с вышеизложенным имеет смысл постановка следующей проблемы: изучить свойст- w ва (новой) специальной функции Hp (8) = je-s+5sPds - части ядра интегрального представле-0
ния (15) производящей функции S ( z ).
Список литературы О выборе орбит для космических аппаратов
- О распределении космических аппаратов по заданному числу орбит / Г. П. Егорычев, Т. А. Ширяева, А. К. Шлепкин и др. // Сибирский журнал науки и технологий. 2020. Т. 21, № 2. С. 170-175. Doi: 10.31772/2587-6066-2020-21-2-170-175.
- Глухов М. М., Елизаров В. П., Нечаев А. А. Алгебра. СПб. : Лань, 2015. 606 с.
- Kochergin V. V. About complexity of computation one-terms of powers // Discrete Analysis, IM SO RAN. 1994. Vol. 27. P. 84-107.
- Borwein P. B. On the Complexity of Calculating Factorials // Journal of Algorithms. 1985. Vol. 6. P. 376-380.
- Boiten E. A. Factorisation of the factorials an example of inverting the flow of computation // Periodica Polytechnika, Ser. EL. ENG. 1991. Vol. 35, № 2. Р. 77-99.
- Ficret Cihan, Fatix Audin, Advan Fatih A Kocamaz. A new method for fast computation of factorials of numbers // Balcan Journal of Mathematics. 2013. P. 16-27.
- Стенли Р. Перечислительная комбинаторика / пер. с англ. M. : Мир, 1990. 440 с.
- Kuzmin O. V. Introduction to combinatorial methods of discrete mathematics. Irkutsk: ISU Publishing House, 2012. 113 p.
- Aigner M. Combinatorial theory. Springer-Verlag, New York, 1979.
- Touchard J. Sur unproble'me de permutations / ed. C. R. Acad, Sci. Paris. 1934.
- Kaplansky I. Solution of the "proble'me des me'nages" // Bull. Amer. Math. Soc. 1943. Vol. 49. P. 784-785.
- Riordan J. An introductions to combinatorial analysis. John Wiley & Sons, Inc., New York, 1982.288 p.
- Mine H. Permanents // Encyclopedia of Mathematics and Its Applications. 1978. Vol. 6.
- Egorychev G. P. Integral Representation and the Computation of Combinatorial Sums // Math. Monographs. Vol. 59. Novosibirsk, Nauka, 1984. 300 p.
- Егорычев Г. П. Дискретная математика. Перманенты. Красноярск : Изд-во СФУ, 2007. 272 с.