Оценка количества латинских прямоугольников методом ускоренного моделирования

Запропоновано метод прискореного моделювання для обчислення кiлькостi латинських прямокутникiв та квадратiв. Численнi приклади демонструють високу точнiсть методу. Наведено оцiнку кiлькостi латинських квадратiв порядку n = 20 з вiдносною похибкою 5 % та достовiрнiстю 0,99. Побудовано статистичнi ниж...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2009
Автор:	Кузнецов, Н.Ю.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2009
Назва видання:	Кибернетика и системный анализ
Теми:	Системный анализ
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/44306
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Оценка количества латинских прямоугольников методом ускоренного моделирования / Н.Ю. Кузнецов // Кибернетика и системный анализ. — 2009. — № 1. — С. 76-84. — Бібліогр.: 12 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-44306
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-443062025-02-23T17:43:57Z Оценка количества латинских прямоугольников методом ускоренного моделирования Оцiнка кiлькостi латинських прямокутникiв методом прискореного моделювання Evaluation of the number of Latin rectangles by a fast simulation method Кузнецов, Н.Ю. Системный анализ Запропоновано метод прискореного моделювання для обчислення кiлькостi латинських прямокутникiв та квадратiв. Численнi приклади демонструють високу точнiсть методу. Наведено оцiнку кiлькостi латинських квадратiв порядку n = 20 з вiдносною похибкою 5 % та достовiрнiстю 0,99. Побудовано статистичнi нижнi оцiнки максимальної кiлькостi трансверсалей у латинських квадратах порядку n ≤ 20. A fast simulation method is proposed for the evaluation of the number of Latin rectangles and squares. Numerous examples demonstrate a high accuracy of the method. An estimate of the number of Latin squares of order n = 20 is given with the relative error equal to 5% and confidence level equal to 0.99. Statistical lower bounds are constructed for maximum numbers of transversals of Latin squares of order n ≤ 20. 2009 Article Оценка количества латинских прямоугольников методом ускоренного моделирования / Н.Ю. Кузнецов // Кибернетика и системный анализ. — 2009. — № 1. — С. 76-84. — Бібліогр.: 12 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44306 519.21 ru Кибернетика и системный анализ application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Системный анализ Системный анализ
spellingShingle	Системный анализ Системный анализ Кузнецов, Н.Ю. Оценка количества латинских прямоугольников методом ускоренного моделирования Кибернетика и системный анализ
description	Запропоновано метод прискореного моделювання для обчислення кiлькостi латинських прямокутникiв та квадратiв. Численнi приклади демонструють високу точнiсть методу. Наведено оцiнку кiлькостi латинських квадратiв порядку n = 20 з вiдносною похибкою 5 % та достовiрнiстю 0,99. Побудовано статистичнi нижнi оцiнки максимальної кiлькостi трансверсалей у латинських квадратах порядку n ≤ 20.
format	Article
author	Кузнецов, Н.Ю.
author_facet	Кузнецов, Н.Ю.
author_sort	Кузнецов, Н.Ю.
title	Оценка количества латинских прямоугольников методом ускоренного моделирования
title_short	Оценка количества латинских прямоугольников методом ускоренного моделирования
title_full	Оценка количества латинских прямоугольников методом ускоренного моделирования
title_fullStr	Оценка количества латинских прямоугольников методом ускоренного моделирования
title_full_unstemmed	Оценка количества латинских прямоугольников методом ускоренного моделирования
title_sort	оценка количества латинских прямоугольников методом ускоренного моделирования
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2009
topic_facet	Системный анализ
url	https://nasplib.isofts.kiev.ua/handle/123456789/44306
citation_txt	Оценка количества латинских прямоугольников методом ускоренного моделирования / Н.Ю. Кузнецов // Кибернетика и системный анализ. — 2009. — № 1. — С. 76-84. — Бібліогр.: 12 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT kuznecovnû ocenkakoličestvalatinskihprâmougolʹnikovmetodomuskorennogomodelirovaniâ AT kuznecovnû ocinkakilʹkostilatinsʹkihprâmokutnikivmetodompriskorenogomodelûvannâ AT kuznecovnû evaluationofthenumberoflatinrectanglesbyafastsimulationmethod
first_indexed	2025-11-24T05:32:29Z
last_indexed	2025-11-24T05:32:29Z
_version_	1849648584565194752
fulltext	ÓÄÊ 519.21 Í.Þ. ÊÓÇÍÅÖÎÂ ÎÖÅÍÊÀ ÊÎËÈ×ÅÑÒÂÀ ËÀÒÈÍÑÊÈÕ ÏÐßÌÎÓÃÎËÜÍÈÊÎÂ ÌÅÒÎÄÎÌ ÓÑÊÎÐÅÍÍÎÃÎ ÌÎÄÅËÈÐÎÂÀÍÈß Êëþ÷åâûå ñëîâà: ëàòèíñêèé ïðÿìîóãîëüíèê, ëàòèíñêèé êâàäðàò, òðàíñâåðñàëü, ìåòîä óñêîðåííîãî ìîäåëèðîâàíèÿ, íåñìåùåííàÿ îöåíêà, âûáîðî÷íàÿ äèñïåðñèÿ, îòíîñèòåëüíàÿ ïîãðåøíîñòü. Ëàòèíñêèì ïðÿìîóãîëüíèêîì íàçûâàåòñÿ ïðÿìîóãîëüíàÿ ìàòðèöà ðàçìåðà n m� , m n� , êàæäûé ñòîëáåö êîòîðîé ÿâëÿåòñÿ ïåðåñòàíîâêîé (áåç ïîâòîðåíèé) ýëåìåí- òîâ ìíîæåñòâà S a an� { , , }1 � , ïðè÷åì â êàæäîé ñòðîêå ýëåìåíòû íå ïîâòîðÿþò- ñÿ. Åñëè m n� , òî ïîëó÷èì êâàäðàòíóþ ìàòðèöó ïîðÿäêà n n� , êàæäàÿ ñòðîêà è êàæäûé ñòîëáåö êîòîðîé ÿâëÿþòñÿ ïåðåñòàíîâêîé ýëåìåíòîâ ìíîæåñòâà S . Êâàä- ðàòíàÿ ìàòðèöà, îáëàäàþùàÿ óêàçàííûì ñâîéñòâîì, íàçûâàåòñÿ ëàòèíñêèì êâàä- ðàòîì. Òåðìèí «ëàòèíñêèé» âîñõîäèò åùå ê Ýéëåðó, êîòîðûé â êà÷åñòâå ýëåìåí- òîâ ìíîæåñòâà S èñïîëüçîâàë áóêâû ëàòèíñêîãî àëôàâèòà. Â íàñòîÿùåå âðåìÿ â êà÷åñòâå S ïðèíÿòî èñïîëüçîâàòü ìíîæåñòâî S n� { , , }1� . Ïðîáëåìà ïåðå÷èñëåíèÿ âñåõ ëàòèíñêèõ ïðÿìîóãîëüíèêîâ ÿâëÿåòñÿ NP-ïîëíîé è â îáùåì ñëó÷àå íå ðåøåíà. Çàäà÷à îïðåäåëåíèÿ, ìîæåò ëè ÷àñòè÷íî çàïîëíåí- íûé êâàäðàò áûòü äîïîëíåííûì äî ëàòèíñêîãî êâàäðàòà, òàêæå ÿâëÿåòñÿ NP-ïîë- íîé [1]. ßâíûå àíàëèòè÷åñêèå ôîðìóëû äëÿ îïðåäåëåíèÿ êîëè÷åñòâà ëàòèíñêèõ ïðÿìîóãîëüíèêîâ èçâåñòíû ëèøü äëÿ m � 2 (çàäà÷à î ÷èñëå áåñïîðÿäêîâ) è m � 3 (çàäà÷à î ÷èñëå ðàçìåùåíèé n ñóïðóæåñêèõ ïàð çà êðóãëûì ñòîëîì ñ óñëîâèåì, ÷òîáû íè îäíà èç ïàð íå ñèäåëà âìåñòå) [2, 3]. Îáîçíà÷èì: L n m( , ) — êîëè÷åñòâî ëà- òèíñêèõ ïðÿìîóãîëüíèêîâ ðàçìåðà n m� , m n� ; N n m( , ) — êîëè÷åñòâî ëàòèíñêèõ ïðÿìîóãîëüíèêîâ ñ ôèêñèðîâàííûì ïåðâûì ñòîëáöîì ( , , , )1 2 � n T (íîðìàëèçîâàí- íûå ïðÿìîóãîëüíèêè); M n m( , ) — êîëè÷åñòâî ëàòèíñêèõ ïðÿìîóãîëüíèêîâ ñ ôèêñè- ðîâàííûì ïåðâûì ñòîëáöîì ( , , , )1 2 � n T è ïåðâîé ñòðî÷êîé ( , , , )1 2 � m (ðåäóöèðî- âàííûé ïðÿìîóãîëüíèê èëè ïðÿìîóãîëüíèê ñòàíäàðòíîãî âèäà). Èìåþò ìåñòî î÷åâèäíûå ñîîòíîøåíèÿ: L n m n N n m n A M n m n n n m M n n m( , ) ! ( , ) ! ( , ) !( )! ( )! ( ,� � � � �� 1 1 1 m). (1) Ïðîáëåìà íàõîæäåíèÿ òî÷íîãî êîëè÷åñòâà ëàòèíñêèõ êâàäðàòîâ òðåáóåò îã- ðîìíûõ âû÷èñëèòåëüíûõ çàòðàò, êîòîðûå ýêñïîíåíöèàëüíî âîçðàñòàþò ñ ðîñòîì n. Èñïîëüçîâàíèå ñàìîé ñîâðåìåííîé âû÷èñëèòåëüíîé òåõíèêè ïîçâîëèëî îïðåäåëèòü L n n( , ) ëèøü äëÿ n � 11[4]. Ïîýòîìó îñíîâíîé àêöåíò â èññëåäîâàíèÿõ ñëåäóåò ñäå- ëàòü íà ðàçâèòèå ïðèáëèæåííûõ ìåòîäîâ ðàñ÷åòà êîëè÷åñòâà ëàòèíñêèõ êâàäðàòîâ è ëàòèíñêèõ ïðÿìîóãîëüíèêîâ. Â íàñòîÿùåé ñòàòüå ïðåäëàãàåòñÿ àëüòåðíàòèâíûé ïîäõîä, îñíîâàííûé íà èñ- ïîëüçîâàíèè ñïåöèàëüíûõ ïðèåìîâ ìîäåëèðîâàíèÿ, ïîçâîëÿþùèõ íàïðàâëåííûì îáðàçîì ñòðîèòü ëàòèíñêèé ïðÿìîóãîëüíèê, àíàëèòè÷åñêè âû÷èñëÿÿ ïðè ýòîì ñîîò- âåòñòâóþùèå íîðìèðóþùèå ìíîæèòåëè, ïðîèçâåäåíèå êîòîðûõ è ñëóæèò îöåíêîé. Ïðè çàäàííûõ îòíîñèòåëüíîé ïîãðåøíîñòè � è äîâåðèòåëüíîé âåðîÿòíîñòè � ñòðî- ÿòñÿ îöåíêà � ( , , , )L n m � � è ñîîòâåòñòâóþùèé äîâåðèòåëüíûé èíòåðâàë � ( , , , )� n m � � . Çà ñ÷åò âûáîðà ïàðàìåòðîâ � è � óäàåòñÿ ñóùåñòâåííî ðàñøèðèòü îáëàñòü çíà÷åíèé n è m, äëÿ êîòîðûõ ïðè ñðàâíèòåëüíî íåáîëüøèõ çàòðàòàõ âðåìåíè ìîãóò áûòü ïî- ñòðîåíû îöåíêè äëÿ L n m( , ). Íàïðèìåð, ñîîòâåòñòâóþùèå îöåíêè ïîñòðîåíû äëÿ L n n( , ) ïðè n � 20, � � 5 %, � � 0 99, è äëÿ L n m( , ) ïðè n � 1000, m � 10, � � 1%, � � 0 99, . Åñëè íå òðåáóåòñÿ ñòîëü âûñîêàÿ òî÷íîñòü âû÷èñëåíèé, òî ñîîòâåòñòâóþùèå îöåí- êè ìîãóò áûòü ïîñòðîåíû äëÿ çíà÷èòåëüíî á�ëüøèõ çíà÷åíèé n è m. 76 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 © Í.Þ. Êóçíåöîâ, 2009 Ïðîâåäåíî ïîäðîáíîå èññëåäîâàíèå òî÷íîñòè ïðåäëàãàåìîãî ìåòîäà. Ïðîâå- ðÿåòñÿ, ïîïàäàþò ëè òî÷íûå çíà÷åíèÿ L n m( , ) â ñîîòâåòñòâóþùèå äîâåðèòåëüíûå èíòåðâàëû. Êðîìå òîãî, èññëåäóåòñÿ âçàèìíîå ïîâåäåíèå ñòàòèñòè÷åñêèõ è àñèì- ïòîòè÷åñêèõ îöåíîê. Â ïîñëåäíåì ðàçäåëå ñòàòüè ñòðîèòñÿ ñòàòèñòè÷åñêàÿ íèæíÿÿ îöåíêà ìàêñè- ìàëüíîãî êîëè÷åñòâà òðàíñâåðñàëåé â ëàòèíñêèõ êâàäðàòàõ, êîòîðàÿ ñðàâíèâàåòñÿ ñ ïîñëåäíèìè ðåçóëüòàòàìè â äàííîì íàïðàâëåíèè [5]. ÎÖÅÍÊÀ M n m( , ) ÌÅÒÎÄÎÌ ÓÑÊÎÐÅÍÍÎÃÎ ÌÎÄÅËÈÐÎÂÀÍÈß Îñíîâíîå âíèìàíèå ñîñðåäîòî÷èì íà îöåíêå M n m( , ) (êîëè÷åñòâî ðåäóöèðîâàí- íûõ ëàòèíñêèõ ïðÿìîóãîëüíèêîâ). Îáùåå êîëè÷åñòâî ëàòèíñêèõ ïðÿìîóãîëüíè- êîâ L n m( , ) è êîëè÷åñòâî íîðìàëèçîâàííûõ ïðÿìîóãîëüíèêîâ N n m( , ) îïðåäåëÿ- þòñÿ ñîãëàñíî (1). Ïîñêîëüêó ïåðâûé ñòîëáåö è ïåðâàÿ ñòðî÷êà çàïîëíåíû, îñòà- åòñÿ çàïîëíèòü åùå ( )( )m n� �1 1 ïîçèöèé â îñòàëüíûõ m�1 ñòîëáöàõ, ïðè÷åì â ñòîëáöå j ( )2 � �j m ìîãóò ðàçìåùàòüñÿ ëèøü ñèìâîëû { , , , , , }1 1 1� �j j n� � . Ïðåäïîëîæèì, ÷òî îíè ðàñïîëîæåíû ñëó÷àéíûì îáðàçîì (( )!n �1 âàðèàíòîâ äëÿ êàæäîãî ñòîëáöà). Îáîçíà÷èì P n m( , ) âåðîÿòíîñòü ïîñòðîåíèÿ ëàòèíñêîãî ïðÿìî- óãîëüíèêà. Î÷åâèäíî, ÷òî P n m M n m n m ( , ) ( , ) [( )!] � � �1 1 . (2) Êàê îòìå÷àëîñü, íå ñóùåñòâóåò àíàëèòè÷åñêèõ ìåòîäîâ íàõîæäåíèÿ P n m( , ) (åäèíñòâåííûì èñêëþ÷åíèåì ÿâëÿåòñÿ ñëó÷àé m � 3). Àëüòåðíàòèâíûé ïîäõîä îñíîâàí íà èñïîëüçîâàíèè ìåòîäà Ìîíòå-Êàðëî, ïîçâîëÿþùåãî ñòðîèòü ïðèáëè- æåííûå îöåíêè äëÿ P n m( , ). Â òî æå âðåìÿ ñ ðîñòîì n è m ( )m n� âåðîÿòíîñòü P n m( , ) ñòðåìèòåëüíî óáûâàåò, ÷òî äåëàåò ìåòîä Ìîíòå-Êàðëî ïðàêòè÷åñêè íåïðè- ãîäíûì äëÿ èñïîëüçîâàíèÿ äàæå ïðè âåñüìà óìåðåííûõ çíà÷åíèÿõ n è m. Â íàñòîÿùåì ðàçäåëå ïðåäëàãàåòñÿ ìåòîä óñêîðåííîãî ìîäåëèðîâàíèÿ (âàðèàíò ìåòîäà âçâåøåííîãî ìîäåëèðîâàíèÿ), ïîçâîëÿþùèé íàïðàâëåííî âûáèðàòü ïîçèöèè, íà êîòîðûõ ìîæåò áûòü ðàçìåùåí òîò èëè èíîé ñèìâîë. Íåñìåùåííîñòü îöåíêè äîñòè- ãàåòñÿ çà ñ÷åò ïîäõîäÿùåãî âûáîðà âåñîâûõ ìíîæèòåëåé. «Óñêîðåíèå» ïðîèñõîäèò áëàãîäàðÿ ðåçêîìó âîçðàñòàíèþ êîëè÷åñòâà ðåàëèçàöèé, â êîòîðûõ óäàåòñÿ ïîñòðîèòü ëàòèíñêèé ïðÿìîóãîëüíèê. Ïðè ýòîì ñîîòâåòñòâóþùèå âåñîâûå ìíîæèòåëè ïî ñâîåìó ïîðÿäêó ñðàâíèìû ñ P n m( , ). Çà ñ÷åò ýòîãî ñóùåñòâåííî óìåíüøàåòñÿ äèñïåðñèÿ îöåí- êè, à ñëåäîâàòåëüíî, è êîëè÷åñòâî ðåàëèçàöèé, íåîáõîäèìûõ äëÿ äîñòèæåíèÿ òðåáóå- ìîé òî÷íîñòè îöåíêè. Ââåäåì âñïîìîãàòåëüíûå èíäèêàòîðû îïðåäåëÿþùèå ðàñïîëîæåíèå ñèìâîëîâ ïî ñòðîêàì è ñòîëáöàì. Ìåòîä óñêîðåí- íîãî ìîäåëèðîâàíèÿ ñôîðìóëèðóåì â âèäå àëãîðèòìà ïîñòðîåíèÿ îöåíêè � ( , )P n m1 â îäíîé ðåàëèçàöèè äëÿ P n m( , ). 1. Ïîëàãàåì q � 1(íà÷àëüíîå çíà÷åíèå íîðìèðóþùåãî ìíîæèòåëÿ) è çàäàåì íà- ÷àëüíîå ñîñòîÿíèå çàïîëíÿåìîé ìàòðèöû A aij i j n m� � � ( ) , , 1 1 : ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 77 � � ,ñëó÷àåïðîòèâíîìâ0 ,íîìåðîìññòðîêåâðàñïîëîæåíñèìâîëåñëè,1 )( ik ki� � � ,ñëó÷àåïðîòèâíîìâ0 ,íîìåðîìññòîëáöåâðàñïîëîæåíñèìâîëåñëè,1 )( jk kj� � � � � � � .ñëó÷àåïðîòèâíîìâ0 ,1åñëè, ,1åñëè, ij ji aij Â ïîñëåäóþùèõ øàãàõ 2–8 àëãîðèòìà ðàçìåùàåì ñèìâîëû ìíîæåñòâà C � � �{ , , }2 1� n . Ïîëîæèì k � 2. 2. Çàäàåì íà÷àëüíûå çíà÷åíèÿ âñïîìîãàòåëüíûõ èíäèêàòîðîâ: 3. Ñòðîèì ìíîæåñòâî D j j m kk j� � � �{ : , ( ) }2 0� íîìåðîâ ñòîëáöîâ, â êîòî- ðûõ äîëæåí áûòü ðàñïîëîæåí ñèìâîë k . 4. Äëÿ êàæäîãî ñòîëáöà îïðåäåëÿåì êîëè÷åñòâî ïîçèöèé, â êîòîðûõ äîïóñêàåò- ñÿ ðàñïîëîæåíèå ñèìâîëà k : r j D j rj i k a k j D j i ij k � � � � � � : ( ) , , , arg min � 0 0 01 . 5. Åñëè rj0 0� , òî â äàííîé ðåàëèçàöèè ëàòèíñêèé ïðÿìîóãîëüíèê íå ìîæåò áûòü ïîñòðîåí. Àëãîðèòì îêîí÷åí, â êà÷åñòâå îöåíêè âûáèðàåì � ( , )P n m1 0� . 6. Ïóñòü rj0 0� . Îáîçíà÷èì l j0 êîëè÷åñòâî ñâîáîäíûõ ïîçèöèé â ñòîëáöå j0 , ò.å. l j i aij 0 0 0 1� � : . Ïîëîæèì q q r l j j :� 0 0 (çäåñü è â äàëüíåéøåì ñèìâîë «: �» óêàçûâàåò, ÷òî íîâîå çíà÷åíèå íåêîòîðîé âåëè÷èíû âû÷èñëÿåòñÿ êàê ñîîòâåòñòâóþùàÿ ôóíêöèÿ åå ñòàðîãî çíà÷åíèÿ). 7. Ðàâíîâåðîÿòíûì îáðàçîì âûáèðàåì îäíó èç rj0 ñòðî÷åê, â êîòîðûõ ìîæåò áûòü ðàçìåùåí ñèìâîë k . Ïóñòü ýòî áóäåò ñòðî÷êà i 0 . 8. Ïîëàãàåì a ki j0 0 � , � i k 0 1( ) � , � j k 0 1( ) � è ñòðîèì ìíîæåñòâî Dk � � � � �{ : , ( ) }j j m kj2 0� . Åñëè D k � �, òî ïåðåõîäèì íà øàã 4 àëãîðèòìà. Åñëè Dk � � è k n� �1, òî ïîëàãàåì k k: � � 1 è ïåðåõîäèì íà øàã 2 àëãîðèòìà. Â ñëó÷àå Dk � � è k n� �1 ïåðåõîäèì íà øàã 9. 9. Â ïðÿìîóãîëüíîé ìàòðèöå A ðàçìåùåíû âñå ñèìâîëû ìíîæåñòâà C � � �{ , , }2 1� n . Íà îñòàâøèõñÿ ñâîáîäíûõ ïîçèöèÿõ îñòàëîñü ðàçìåñòèòü ñèìâîëû 1 è n. Åñëè â ñòðî÷êå n èìåþòñÿ õîòÿ áû äâå ñâîáîäíûå ïîçèöèè èëè â îäíîé èç ñòðî- ÷åê 2 1, ,� n � ñóùåñòâóþò òðè íåçàíÿòûå ïîçèöèè, òî ëàòèíñêèé ïðÿìîóãîëüíèê ïî- ñòðîåí áûòü íå ìîæåò. Â ýòîì ñëó÷àå àëãîðèòì îêîí÷åí, â êà÷åñòâå îöåíêè âûáèðà- åì � ( , )P n m1 0� . Åñëè óêàçàííîå óñëîâèå íå âûïîëíåíî, òî ëàòèíñêèé ïðÿìîóãîëü- íèê ìîæåò áûòü ïîñòðîåí. Ïðè ýòîì ìàòðèöà A èìååò ñëåäóþùóþ ñòðóêòóðó. Åñëè m n� , òî êàæäàÿ ñòðî÷êà i ( )2 1� � �i n è êàæäûé ñòîëáåö j ( )2 1� � �j n ñîäåðæàò ïî äâå ñâîáîäíûõ ïîçèöèè, â òî âðåìÿ êàê ñòðî÷êà n è ñòîëáåö n — ïî îäíîé ñâîáîäíîé ïîçèöèè. Åñëè m n� , òî âñå ñòîëáöû (êðîìå ïåðâîãî) ñîäåðæàò ïî äâå ñâîáîäíûõ ïîçèöèè, à êàæäàÿ ñòðî÷êà i ( )2 1� � �i n — íå áîëåå äâóõ ñâîáîäíûõ ïîçèöèé. Ïîñëåäíÿÿ ñòðî÷êà ñîäåðæèò íå áîëåå îäíîé ñâîáîäíîé ïîçèöèè. 10. Ó÷èòûâàÿ êîëè÷åñòâî íåçàïîëíåííûõ ïîçèöèé â êàæäîì ñòîëáöå, ïîëàãàåì q q m n q m n n m : , , , . � � � �� 1 2 1 2 2 1 åñëè åñëè 11. Åñëè â ñòðî÷êå n åñòü ñâîáîäíàÿ ïîçèöèÿ, òî ðàçìåùàåì íà íåé ñèìâîë 1, çàòåì ñèìâîë n â ñîîòâåòñòâóþùåì ñòîëáöå, çàòåì ñèìâîë 1 â ñòðî÷êå è ò.ä. Òàêîé 78 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 � � � � � � .ñëó÷àåïðîòèâíîìâ0 ,åñëè,1 )( ,ñëó÷àåïðîòèâíîìâ0 ,åñëè,1 )( kj k ki k ji �� öèêëè÷åñêèé àëãîðèòì ïîçâîëÿåò èíîãäà çàïîëíèòü âñå ñâîáîäíûå ïîçèöèè ìàòðè- öû (ëàòèíñêèé ïðÿìîóãîëüíèê ïîñòðîåí). Â ýòîì ñëó÷àå â êà÷åñòâå îöåíêè âûáèðà- åì � ( , )P n m q1 � . 12. Ïðåäïîëîæèì, ÷òî â ñòðî÷êå n íå áûëî ñâîáîäíûõ ïîçèöèé èëè óêàçàííûé öèêëè÷åñêèé àëãîðèòì ïîçâîëèë ëèøü ÷àñòè÷íî çàïîëíèòü ìàòðèöó. Â ýòîì ñëó÷àå âûáåðåì ïðîèçâîëüíóþ ñòðî÷êó, ñîäåðæàùóþ õîòÿ áû îäíó ñâîáîäíóþ ïîçèöèþ. Íà ýòîé ïîçèöèè ñ âåðîÿòíîñòüþ 0,5 ðàçìåñòèì ñèìâîë 1 ëèáî ñèìâîë n. Äàëåå çà- ïîëíÿåì ìàòðèöó öèêëè÷åñêèì îáðàçîì (ñì. øàã 11). Ïðè ýòîì ïîëàãàåì q q: � 2 . Óêàçàííàÿ ïðîöåäóðà ïîâòîðÿåòñÿ äî òåõ ïîð, ïîêà íå áóäóò çàïîëíåíû âñå ïîçèöèè ìàòðèöû A . Â êà÷åñòâå îöåíêè âûáèðàåì � ( , )P n m q1 � . Çàìå÷àíèÿ. 1. Íåñìåùåííîñòü îöåíêè � ( , )P n m1 î÷åâèäíûì îáðàçîì ñîõðàíÿåòñÿ çà ñ÷åò íàïðàâëåííîãî ìîäåëèðîâàíèÿ ïîçèöèé, íà êîòîðûõ ìîãóò áûòü ðàçìåùåíû ñîîò- âåòñòâóþùèå ñèìâîëû, à òàêæå ïîäõîäÿùåãî âûáîðà íîðìèðóþùèõ ìíîæèòåëåé. 2. Äëÿ óïðîùåíèÿ èçëîæåíèÿ â àëãîðèòìå îïóùåí âàæíûé ýòàï, ïîçâîëÿþùèé ñóùåñòâåííî óâåëè÷èòü ïðîöåíò ðåàëèçàöèé, â êîòîðûõ óäàåòñÿ ïîñòðîèòü ëàòèíñêèé ïðÿìîóãîëüíèê. Àíàëèçèðóÿ ïðè÷èíû, ïðåïÿòñòâóþùèå ïîñòðîåíèþ ëàòèíñêîãî ïðÿ- ìîóãîëüíèêà, îòìåòèì, ÷òî íàèáîëüøóþ ñëîæíîñòü âûçûâàåò ðàçìåùåíèå ñèìâîëîâ â íåñêîëüêèõ ïîñëåäíèõ ñòîëáöàõ (íàïðèìåð, â ñëó÷àå ëàòèíñêîãî êâàäðàòà â ïîñëåä- íåì ñòîëáöå äëÿ ðàçìåùåíèÿ îñòàåòñÿ ëèøü îäíà ïîçèöèÿ, êîòîðàÿ óæå ìîæåò áûòü çàíÿòîé). Äîïîëíèòåëüíûé ýòàï ïîçâîëÿåò íàéòè âñå äîïóñòèìûå âàðèàíòû ðàçìåùå- íèÿ ñèìâîëà â ÷åòûðåõ ïîñëåäíèõ ñòîëáöàõ è âûáðàòü îäèí èç íèõ. 3. Ïðè çàäàííûõ îòíîñèòåëüíîé ïîãðåøíîñòè � è äîâåðèòåëüíîé âåðîÿòíîñòè � îáû÷íûìè ñòàòèñòè÷åñêèìè ìåòîäàìè [6] ñòðîÿòñÿ îöåíêà � ( , , , )P n m � � äëÿ P n m( , ) è äîâåðèòåëüíûé èíòåðâàë. Ñîãëàñíî (2) è (1) ñ ñîîòâåòñòâóþùåé òî÷íîñòüþ ñòðî- ÿòñÿ îöåíêè è äîâåðèòåëüíûå èíòåðâàëû äëÿ M n m( , ), N n m( , ) è L n m( , ). ÀÍÀËÈÒÈ×ÅÑÊÈÅ È ÀÑÈÌÏÒÎÒÈ×ÅÑÊÈÅ ÔÎÐÌÓËÛ ÄËß L n m( , ) Â äàííîì ðàçäåëå ïðèâåäåíû àíàëèòè÷åñêèå è àñèìïòîòè÷åñêèå ôîðìóëû [2] äëÿ âû÷èñëåíèÿ êîëè÷åñòâà ëàòèíñêèõ ïðÿìîóãîëüíèêîâ, èçâåñòíûå ê íàñòîÿùåìó âðåìåíè: L n n Dn( , ) !2 � , (3) L n L n n e n as( , ) ~ ( , ) ( !)2 2 2 1 �� , (4) L n n C D D Un k n k k n k k n ( , ) ! [ / ] 3 2 0 2 � � � � , (5) L n L n n e n as( , ) ~ ( , ) ( !)3 3 3 3 �� , (6) ãäå D r r r r � � � � � � �� ! ! ! ! ( ) ! 1 1 1 1 2 1 3 1 � , r n� 2, ,� , D0 1� , D1 0� , U r r r r r k C r kr k r k k r� � � � � � � � � � � � ! ( )! ( ) ( )! ( )2 1 1 2 2 1 2 2 � � , r n U U U� � � � �3 1 1 00 1 2, , , , ,� . Êðîìå òîãî, â [7] äîêàçàíî, ÷òî ïðè m n3� L n m L n m n eas m Cm( , ) ~ ( , ) ( !)� � 2 . (7) Âîñïîëüçóåìñÿ óêàçàííûìè ôîðìóëàìè äëÿ òåñòèðîâàíèÿ òî÷íîñòè îöåíîê, ïîëó÷àåìûõ ïðåäëîæåííûì âûøå ìåòîäîì óñêîðåííîãî ìîäåëèðîâàíèÿ. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 79 ×ÈÑËÅÍÍÛÅ ÐÅÇÓËÜÒÀÒÛ Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ: � — îòíîñèòåëüíàÿ ïîãðåøíîñòü îöåíêè; � — äîâåðèòåëüíàÿ âåðîÿòíîñòü (â äàëüíåéøåì âî âñåõ ðàñ÷åòàõ ïðåäïîëàãàåò- ñÿ, ÷òî � � 0 99, ); �( , , , )L n m � � — îöåíêà, ïîñòðîåííàÿ äëÿ L n m( , ) ñ îòíîñèòåëüíîé ïîãðåøíîñòüþ � è äîâåðèòåëüíîé âåðîÿòíîñòüþ �; � ( , , , )S n m � � — êîëè÷åñòâî ðåàëèçàöèé, èñïîëüçîâàííûõ äëÿ ïîñòðîåíèÿ îöåí- êè �( , , , )L n m � � ; � � � � � � � as as n m L n m L n m L n m ( , , , ) ( , ) �( , , , ) �( , , , ) %� � �100 — îòíîñèòåëüíîå îòêëîíåíèå àñèìïòîòè÷åñêîé îöåíêè îò îöåíêè, ïîëó÷åííîé óñêîðåííûì ìîäåëèðîâàíèåì; �( , , , )n m � � — äîâåðèòåëüíûé èíòåðâàë äëÿ L n m( , ), ïîñòðîåííûé ñ îòíîñè- òåëüíîé ïîãðåøíîñòüþ � è äîâåðèòåëüíîé âåðîÿòíîñòüþ �; T n m( , , , )� � — âðåìÿ (â ñåêóíäàõ), ïîòðà÷åííîå íà ïîñòðîåíèå îöåíêè �( , , , )L n m � � ; � ( , , , )K n m � � — îöåíêà îòíîñèòåëüíîãî êîëè÷åñòâà ðåàëèçàöèé, â êîòîðûõ àëãî- ðèòì ñòðîèò ëàòèíñêèé ïðÿìîóãîëüíèê. Âñå ïðèâåäåííûå äàëåå âû÷èñëåíèÿ ïðîèçâîäèëèñü íà êîìïüþòåðå ñ ïðîöåññî- ðîì Pentium IV, 3.2 GHz. Ïðîâåäåì ñðàâíåíèå îöåíîê �( , , , )L n m � � , ïîñòðîåííûõ ñ îòíîñèòåëüíîé ïî- ãðåøíîñòüþ � � 1%, ñ òî÷íûìè çíà÷åíèÿìè L n m( , ) è àñèìïòîòè÷åñêèìè îöåíêàìè L n mas ( , ) äëÿ m � 2 â òàáë. 1 (ôîðìóëû (3), (4)) è m � 3 â òàáë. 2 (ôîðìóëû (5), (6)) ñîîòâåòñòâåííî. Ïðèâåäåííûå ÷èñëåííûå äàííûå ñâèäåòåëüñòâóþò î âûñîêîé òî÷íîñòè îöåíîê (âñå òî÷íûå çíà÷åíèÿ ïîïàäàþò â îäíîïðîöåíòíûé äîâåðèòåëüíûé èíòåðâàë). Îòìåòèì, ÷òî ñ âîçðàñòàíèåì n óáûâàåò êîëè÷åñòâî ðåàëèçàöèé (îöåíèâàåìîå âåëè- ÷èíîé � ( , , , )S n m � � ), òðåáóåìûõ äëÿ äîñòèæåíèÿ çàäàííîé òî÷íîñòè. Ýòî îçíà÷àåò, ÷òî ñîîòâåòñòâóþùèì îáðàçîì óáûâàåò è äèñïåðñèÿ îöåíêè. Åñëè ïðè m � 2 àñèì- ïòîòè÷åñêàÿ ôîðìóëà óæå ïðè n � 6 îáåñïå÷èâàåò âûñîêóþ òî÷íîñòü, òî ïðè m � 3 ñõîäèìîñòü ê òî÷íîìó çíà÷åíèþ íåñêîëüêî çàìåäëÿåòñÿ. Â òàáë. 3 äëÿ m � 5 èññëåäóåòñÿ òî÷íîñòü àñèìïòîòè÷åñêîé ôîðìóëû (7). Ïîñ- êîëüêó òî÷íûå çíà÷åíèÿ L n( , )5 íåèçâåñòíû, ñðàâíåíèå âåäåòñÿ ñ îöåíêàìè, ïîñòðî- åííûìè ñ îäíîïðîöåíòíîé îòíîñèòåëüíîé ïîãðåøíîñòüþ. Êàê è ðàíåå, íàáëþäàåòñÿ óáûâàíèå êîëè÷åñòâà ðåàëèçàöèé � ( , , , )S n 5 � � ñ âîç- ðàñòàíèåì n. Åñëè ïðè n � 10 ïîãðåøíîñòü àñèìïòîòè÷åñêîé ôîðìóëû ñîñòàâëÿåò 246 % (ñ òî÷íîñòüþ äî 1 % ïîãðåøíîñòè îöåíêè), òî ñ âîçðàñòàíèåì n ýòà ïîãðåø- íîñòü óáûâàåò. Ëèøü ïðè n � 500 îòíîñèòåëüíàÿ ïîãðåøíîñòü àñèìïòîòè÷åñêîé îöåíêè ñîñòàâëÿåò îêîëî 1 %. 80 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 Ò à á ë è ö à 1 n L n( , )2 L nas ( , )2 � ( , , , )L n 2 � � � ( , , , )S n 2 � � 3 12 13,24 12,00 1 6 1,908 �105 1,907 � 105 1,907 � 105 6 067 10 4,844 �1012 4,844 � 1012 4,842 � 1012 5 365 50 3,403 �10128 3,403 � 10128 3,404 � 10128 2 611 100 3,204 �10315 3,204 � 10315 3,200 � 10315 1 643 500 5,477 �102267 5,477 � 102267 5,487 � 102267 425 1 000 5,956 �105134 5,956 � 105134 5,965 � 105134 349 Â ðàáîòå [7] ôîðìóëà (7) äîêàçàíà ïðè m n3 � . Âîçíèêàåò åñòåñòâåííûé âîïðîñ, êàê áóäåò èçìåíÿòüñÿ òî÷íîñòü ýòîé àñèìïòîòè÷åñêîé ôîðìóëû ïðè n m� 3 ñ ðîñ- òîì n. Ñîîòâåòñòâóþùèå îöåíêè (� � 1 %), ïîñòðîåííûå âïëîòü äî m � 10, ïðèâåäå- íû â òàáë. 4. ×èñëåííûå äàííûå ïîêàçûâàþò, ÷òî ïðè n m� 3 êîëè÷åñòâî òðåáóåìûõ ðåàëè- çàöèé âåñüìà ñëàáî çàâèñèò îò m. Â òî æå âðåìÿ ñ ðîñòîì m òî÷íîñòü àñèìïòîòè÷åñ- êîé ôîðìóëû ïàäàåò. Â òàáë. 5 äëÿ n m� èññëåäóåòñÿ òî÷íîñòü ìåòîäà óñêîðåííîãî ìîäåëèðîâàíèÿ ïðè âû÷èñëåíèè êîëè÷åñòâà ëàòèíñêèõ êâàäðàòîâ âïëîòü äî n � 20. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 81 Ò à á ë è ö à 2 n L n( , )3 L nas ( , )3 � � �as n( , , , )3 , % � ( , , , )L n 3 � � � ( , , , )S n 3 � � 3 12 10,75 10,4 12,00 1 6 1,532 �107 1,858 �107 18,6 1,535 �107 18 911 10 2,131 �1018 2,379 �1018 12,0 2,124 �1018 19 128 50 1,372 �10192 1,401�10192 1,2 1,384 �10192 8 051 100 4,006 �10472 4,047 �10472 0,50 4,027 �10472 5 227 500 9,026 �103400 9,044 �103400 0,54 9,093 �103400 1 567 1 000 3,241 �107701 3,244 �107701 0,37 3,256 �107701 884 Ò à á ë è ö à 3 n L nas ( , )5 � ( , , , )L n 5 � � � ( , , , )S n 5 � � � � �as n( , , , )5 , % 10 28,567 �1027 8,253 �1027 97 886 246 25 4,076 �10121 2,653 �10121 57 841 53,6 50 11,815 �10317 9,644 �10317 34 761 22,5 75 4,267 �10542 3,720 �10542 25 200 14,7 100 3,214 �10785 2,897 �10785 20 686 10,9 125 10,738 �101041 9,865 �101041 17 256 8,85 150 2,763 �101309 2,590 �101309 14 687 6,68 200 1,385 �101870 1,312 �101870 11 953 5,56 500 1,228 �105666 1,212 �105666 5 673 1,32 1 000 4,789 �1012833 4,734 �1012833 3 244 1,16 Ò à á ë è ö à 4 m L m mas ( , )3 � ( , , , )L m m 3 � � � ( , , , )S m m 3 � � � � ��as m m( , , ,3 , % 4 6,425 �10353 6,031 �10353 15 916 6,53 5 10,738 �101041 9,865 �101041 17 256 8,85 6 3,097 �102465 2,827 �102465 17 778 9,55 7 1,116 �105047 1,007 �105047 17 611 10,8 8 1,478 �109320 1,315 �109320 17 310 12,4 9 6,154 �1015933 5,443 �1015933 16 881 13,1 10 3,186 �1025656 2,819 �1025656 16 789 13,0 Èç ïðèâåäåííûõ ðåçóëüòàòîâ âèäíî, ÷òî âñå èçâåñòíûå äî ñèõ ïîð çíà÷åíèÿ L n n( , ) (âïëîòü äî n � 11) ïîïàäàþò â ïîñòðîåííûå îäíîïðîöåíòíûå äîâåðèòåëüíûå èíòåðâàëû. Çàìåòèì, ÷òî äëÿ ïîñòðîåíèÿ îöåíêè ïðè n � 11 ñ òî÷íîñòüþ � � 1 % òðåáóåòñÿ âñåãî 61 ñ. Âàæíîé õàðàêòåðèñòèêîé ìåòîäà ÿâëÿþòñÿ çíà÷åíèÿ � ( , , , )K n n � � . Àëãîðèòì óñòðîåí òàêèì îáðàçîì, ÷òî ïðè n � 9 áîëåå 90 % ðåàëèçà- öèé îêàí÷èâàþòñÿ ïîñòðîåíèåì ëàòèíñêîãî êâàäðàòà. Ñ ðîñòîì n ÷èñëî «óñïåø- íûõ» ðåàëèçàöèé ïàäàåò, õîòÿ è ïðè n � 20 îíî ÿâëÿåòñÿ âåñüìà çíà÷èòåëüíûì ( %36 ). Òàáëèöà ñîäåðæèò òàêæå äàííûå î âðåìåíè �( , , , )T n n � � , çàòðà÷åííîì íà ïîñòðîåíèå îöåíêè ñ óêàçàííîé òî÷íîñòüþ. Îòìåòèì íåîæèäàííî áîëüøèå çàòðà- òû âðåìåíè ïðè n � 16. Ýòî ïðîèçîøëî çà ñ÷åò òàê íàçûâàåìûõ «âûáðîñîâ» (áîëü- øîå çíà÷åíèå îöåíêè â êîíêðåòíîé ðåàëèçàöèè). Â ñëó÷àå î÷åðåäíîãî «âûáðîñà» ðåçêî óâåëè÷èâàåòñÿ êîëè÷åñòâî ðåàëèçàöèé, òðåáóåìûõ äëÿ äîñòèæåíèÿ îòíîñè- 82 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 Ò à á ë è ö à 5 n �, % L n n( , ) � ( , , , )L n n � � , � ( , , , )n n � � � ( , , , )T n n � � , c � ( , , , )K n n � � , % 4 1 576 5,747 �102 (5,689 �102, 5,804 �102) 0,06 100,0 5 1 161 280 1,609 �105 (1,593 �105, 1,625 �105) 0,14 97,9 6 1 8,129 �108 8,135 �108 (8,054 �108, 8,217 �108) 0,41 100,0 7 1 6,148 �1013 6,149 �1013 (6,087 �1013, 6,210 �1013) 1,2 97,9 8 1 1,088 �1020 1,095 �1020 (1,084 �1020, 1,106 �1020) 3,8 95,0 9 1 5,525 �1027 5,531 �1027 (5,475 �1027, 5,586 �1027) 9,8 90,9 10 1 9,982 �1036 9,991 �1036 (9,891 �1036, 10,091 �1036) 26,5 86,3 11 1 7,770 �1047 7,777 �1047 (7,700 �1047, 7,855 �1047) 61,4 81,3 12 1 — 3,083 �1060 (3,053 �1060, 3,114 �1060) 159,3 76,1 13 1 — 7,427 �1074 (7,353 �1074, 7,502 �1074) 401,3 70,8 14 1 — 1,261 �1091 (1,249 �1091, 1,274 �1091) 1 080 65,3 15 1 — 1,728 �10109 (1,710 �10109, 1,745 �10109) 2 845 59,8 16 2 — 2,211 �10129 (2,167 �10129, 2,255 �10129) 16 262 54,6 17 2 — 2,766 �10151 (2,711 �10151, 2,821 �10151) 3 113 49,6 18 3 — 4,163 �10175 (4,038 �10175, 4,288 �10175) 3 618 44,8 19 4 — 8,594 �10201 (8,250 �10201, 8,937 �10201) 14 271 40,3 20 5 — 2,263 �10230 (2,150 �10230, 2,376 �10230) 10 448 36,1 òåëüíîé ïîãðåøíîñòè �. Ïðîöåññ âû- ÷èñëåíèÿ èëëþñòðèðóåò òàáë. 6. Èç ïðèâåäåííûõ äàííûõ ñëåäó- åò, ÷òî áûëî òðè ñóùåñòâåííûõ «âûáðîñà». Ïåðâûé èç íèõ ïðîèçî- øåë ìåæäó ðåàëèçàöèÿìè 400 000 è 500 000. Ïðè ýòîì êîëè÷åñòâî òðå- áóåìûõ ðåàëèçàöèé âîçðîñëî â 33 ðàçà, íî ñàìà îöåíêà óâåëè÷è- ëàñü ëèøü íà 25 %. Ïîñëåäóþùèå äâà âûáðîñà õîòÿ çàìåòíî óâåëè÷èëè ÷èñ- ëî òðåáóåìûõ ðåàëèçàöèé, îäíàêî âåñüìà ñëàáî ïîâëèÿëè íà óâåëè÷å- íèå îöåíêè. Ýòî îáúÿñíÿåòñÿ ñãëàæè- âàþùèì ýôôåêòîì áîëüøîãî êîëè- ÷åñòâà ïðîâåäåííûõ ðåàëèçàöèé. Îêîí÷àòåëüíàÿ îöåíêà ëèøü íåçíà÷è- òåëüíî îòëè÷àåòñÿ îò îöåíêè, ïîñòðî- åííîé ïî 100 000 ðåàëèçàöèé. ÍÈÆÍßß ÎÖÅÍÊÀ ÌÀÊÑÈÌÀËÜÍÎÃÎ ÊÎËÈ×ÅÑÒÂÀ ÒÐÀÍÑÂÅÐÑÀËÅÉ Áîëüøîé èíòåðåñ ïðåäñòàâëÿåò îöåíêà ìàêñèìàëüíîãî êîëè÷åñòâà òðàíñâåðñàëåé â ëàòèíñêèõ êâàäðàòàõ. Íàáîð ðàçëè÷íûõ ñèìâîëîâ (ïåðåñòàíîâêà) ( , , )i in1 � íàçû- âàåòñÿ òðàíñâåðñàëåì, åñëè íèêàêèå äâà ýëåìåíòà ýòîãî íàáîðà íå ðàñïîëîæåíû â îäíîì è òîì æå ñòîëáöå èëè îäíîé è òîé æå ñòðî÷êå ëàòèíñêîãî êâàäðàòà. Îáîç- íà÷èì: �n — ìíîæåñòâî âñåõ ëàòèíñêèõ êâàäðàòîâ ðàçìåðíîñòè n n� ; T Ln( ) — êî- ëè÷åñòâî òðàíñâåðñàëåé â ëàòèíñêîì êâàäðàòå Ln n� � ; T n T L L n n n ( ) max ( )� �� . Íàõîæäåíèå êîëè÷åñòâà òðàíñâåðñàëåé òåñíî ñâÿçàíî ñ èññëåäîâàíèåì êîëè- ÷åñòâà «õîðîøèõ» ïåðåñòàíîâîê, ïðîâåäåííûì â [8–12]. Â ðàáîòå [5] ïîñòðîåíû âåðõíÿÿ è íèæíÿÿ îöåíêè: åñëè n � 5, òî E b T n c n n En L n n n U� � � �( ) ! , (8) ãäå b � 1719, , c � 0 614, . Ñôîðìóëèðîâàííûé ìåòîä óñêîðåííîãî ìîäåëèðîâàíèÿ íå ïîçâîëÿåò ñòðîèòü âåðõíþþ îöåíêó äëÿ T n( ). Â òî æå âðåìÿ äëÿ êàæäîãî ïîñòðîåííîãî ëàòèíñêîãî êâàäðàòà ìîæíî ïðèìåíèòü óñêîðåííîå ìîäåëèðîâàíèå äëÿ îöåíêè êîëè÷åñòâà òðàíñâåðñàëåé. Òàêèì îáðàçîì, ìîæíî ñòðîèòü íèæíþþ îöåíêó äëÿ T n( ), óêàçûâàÿ ïðè ýòîì ëàòèíñêèé êâàäðàò Ln , íà êîòîðîì ýòîò ìèíèìóì äîñòèãàåòñÿ. Â òàáë. 7 ñðàâíèâàþòñÿ âåðõíÿÿ è íèæíÿÿ îöåíêè (8) ñ íèæíåé îöåíêîé �Vn L , ïîñòðîåííîé óñêîðåííûì ìîäåëèðîâàíèåì (â êà÷åñòâå ýòîé îöåíêè âûáèðàåòñÿ íèæíÿÿ ãðàíèöà ñîîòâåòñòâóþùåãî äîâåðèòåëüíîãî èíòåðâàëà). Â òàáëèöå óêàçàíî òàêæå òî÷íîå çíà÷åíèå T n( ), èçâåñòíîå ïðè n � 9. Ïðèâåäåííûå ÷èñëåííûå äàííûå ïîêàçûâàþò, ÷òî ïðè n � 7 óñêîðåííîå ìîäå- ëèðîâàíèå ïîçâîëÿåò ïðàêòè÷åñêè òî÷íî îöåíèòü ìàêñèìàëüíîå êîëè÷åñòâî òðàíñ- âåðñàëåé. Ñ óâåëè÷åíèåì n òî÷íîñòü óõóäøàåòñÿ. Â òî æå âðåìÿ ïðè áîëüøèõ çíà- ÷åíèÿõ n íèæíÿÿ îöåíêà �Vn L íà íåñêîëüêî ïîðÿäêîâ ëó÷øå òåîðåòè÷åñêîé îöåíêè En L (â 6 8 105, � ðàç ïðè n � 20). ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 83 Ò à á ë è ö à 6 Êîëè÷åñòâî ïðîâåäåííûõ ðåàëèçàöèé Îöåíêà âåðîÿòíîñòè � ( , , , )P n m � � Òðåáóåìîå êîëè÷åñòâî ðåàëèçàöèé 100 000 1,508 � �10 78 12 113 670 � � � 400 000 1,468 � �10 78 11 409 208 500 000 1,837 � �10 78 380 007 803 � � � 13 500 000 1,445 � �10 78 29 016 668 13 600 000 1,458 � �10 78 50 087 023 � � � 26 700 000 1,444 � �10 78 29 205 035 26 800 000 1,451 � �10 78 39 996 382 � � � 33 308 643 1,446 � �10 78 33 308 642 Òàêèì îáðàçîì, ïðåäëîæåííûé ìåòîä óñêîðåííîãî ìîäåëèðîâàíèÿ ÿâëÿåòñÿ ðåàëüíûì èíñòðóìåíòîì, ïîçâîëÿþùèì ïðè îòíîñèòåëüíî íåáîëüøèõ çàòðàòàõ âðå- ìåíè ñ âûñîêîé òî÷íîñòüþ îöåíèâàòü êîëè÷åñòâî ëàòèíñêèõ ïðÿìîóãîëüíèêîâ ïðè äîñòàòî÷íî áîëüøèõ çíà÷åíèÿõ n è m, à òàêæå ñòðîèòü íèæíþþ îöåíêó ìàêñèìàëü- íîãî êîëè÷åñòâà òðàíñâåðñàëåé, ñóùåñòâåííî ëó÷øóþ ïî ñðàâíåíèþ ñ èçâåñòíûìè äî ñèõ ïîð. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. C o l b o u r n C . The complexity of completing partial Latin squares // Discrete Appl. Math. — 1984. — 8. — P. 25–30. 2. Ð û á í è ê î â Ê . À . Ââåäåíèå â êîìáèíàòîðíûé àíàëèç. — Ì.: Èçä-âî Ìîñê. óí-òà, 1985. — 308 ñ. 3. Ñ à ÷ ê î â Â . Í . Ââåäåíèå â êîìáèíàòîðíûå ìåòîäû äèñêðåòíîé ìàòåìàòèêè. — Ì.: Íàóêà, 1982. — 384 ñ. 4. http://en.wikipedia.org/wiki/Latin_square. 5. M c K a y B . D . , M c L e o d J . C . , W a n l e s s I . M . The number of transversals in a Latin square // Des. Codes Crypt. — 2006. — 40. — P. 269–284. 6. Å ð ì à ê î â Ñ . Ì . Ìåòîä Ìîíòå-Êàðëî è ñìåæíûå âîïðîñû. — Ì.: Íàóêà, 1975. — 471 ñ. 7. Y a m a m o t o K . On the asymptotic number of Latin rectangles // Jap. J. Math. — 1951. — 21. — P. 113–119. 8. C o o p e r C . , K o v a l e n k o I . N . An upper bound for the number of complete mappings // Òåîðèÿ âåðîÿòíîñòåé è ìàò. ñòàòèñòèêà. — 1995. — 53. — Ñ. 69–75. 9. K o v a l e n k o I . N . On an upper bound for the number of complete mappings // Êèáåðíåòèêà è ñèñòåì- íûé àíàëèç. — 1996. — ¹ 1. — C. 81–85. 10. Ë å â è ò ñ ê à ÿ À . À . Îäíà êîìáèíàòîðíàÿ çàäà÷à â êëàññå ïåðåñòàíîâîê íàä êîëüöîì Zn âû÷åòîâ ïî íå÷åòíîìó ìîäóëþ n // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 1996. — ¹ 5. — C. 99–108. 11. C o o p e r C . , G i l c h r i s t R . , K o v a l e n k o I . N . , N o v a k o v i c D . Deriving the number of «good» permutations, with application to cryptography // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1999. — ¹ 5. — Ñ. 10–16. 12. Ê ó ç í å ö î â Í . Þ . Îöåíêà êîëè÷åñòâà «õîðîøèõ» ïåðåñòàíîâîê ìîäèôèöèðîâàííûì ìåòîäîì óñêîðåííîãî ìîäåëèðîâàíèÿ // Òàì æå. — 2008. — ¹ 4. — Ñ. 101–109. Ïîñòóïèëà 20.03.2008 84 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 Ò à á ë è ö à 7 n T n( ) En L �Vn L En U 4 8 — 8 — 5 15 15,01 15 23,42 6 32 25,80 31,69 94,50 7 133 44,35 131,53 438,69 8 384 76,24 142,11 2 303,64 9 2 241 1,31 �102 2,60 �102 1,35 �104 10 — 2,25 �102 8,58 �102 8,74 �104 11 — 3,87 �102 3,43 �103 6,19 �105 12 — 6,66 �102 1,61�104 4,76 �106 13 — 1,14 �103 7,90 �104 3,96 �107 14 — 1,97 �103 4,20 �105 3,53 �108 15 — 3,38 �103 2,39 �106 3,37 �109 16 — 5,81 �103 1,47 �107 3,41 �1010 17 — 9,99 �103 9,32 �107 3,67 �1011 18 — 1,72 �104 6,36 �108 4,18 �1012 19 — 2,95 �104 4,56 �109 5,01 �1013 20 — 5,08 �104 3,46 �1010 6,31 �1014

Оценка количества латинских прямоугольников методом ускоренного моделирования

Репозитарії

Схожі ресурси