Soi92

Содержание

Берникова О.А., Бояров А.А., Редькин О.И., Сенов А.А. (СПбГУ) Ме­
тоды оптического распознавания текста на арабском языке.....................       3

Иванов Д.В.,Кацюба О.А. (СамГУПС) О состоятельности оценок пара­
метров ARX-систем дробного порядка с помехой в выходном сигна­
ле   ..............................................................................................................     21

Кижаева Н.А. (СПбГУ) Тематическое моделирование и кластеризация
текстов на арабском языке   .......................................................................     33

Мальковский Н.В. (СГТбГУ) Задача распределения ресурсов в контек­
сте мультиагентных систем.......................................................................    41

Макаркин СБ., Мельников Б.Ф. (СамГУ) Геометрические методы ре­
шения псевдогеометрической версии задачи коммивояжера   ..................     54

Мельников Б.Ф., Мельникова Е.А. (СамГУ) Некоторые эвристические
алгоритмы в задаче вершинной минимизации недетерминированных
конечных автоматов ..................................................................................     ТЗ

Нагорнов Ю.С. (Тольятти) Метод Монте-Карло, в котором вероятности переходов определяются межатомным потенциалом взаимодействия    88

Нагорнов Ю.С. (Тольятти) Об одном алгоритме оптимизации расчетов
методом Монте-Карло при моделировании роста кристаллов   ...............     96

Соколов А.В.  (ПетрГУ, ИПМИ КарНЦ РАН, Петрозаводск) Об опти­
мальном кешировании FIFO-очередей.............................................................................................................. 108

Соколов А.В., Барковский Е.А. (ПетрГУ, ИПМИ КарНЦ РАН, Петро­
заводск) Оптимальное разбиение общей памяти для двух параллель­
ных FIFO-очередей   .............................................................................................................. 124

Сысоев С.С. (СПбГУ), Велюхов Ю.Г. (Петромс) Рандомизированное
обобщенное преобразование Хафа в задаче идентификации объектов
на изображениях местности.............................................................................................................. 138

Stoynov P.T. (Sofia, Bulgaria) Sums of a special class of generalized Stoynov
distributions.............................................................................................................. 150

Abstracts   ......................................................................................................................... 154

 

 

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

НИИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

СТОХАСТИЧЕСКАЯ ОПТИМИЗАЦИЯ В ИНФОРМАТИКЕ

Издается с 2005 года

ТОМ 9

Выпуск 2

Издательство С.-Петербургского университета

2 0 1 3

 

УДК 519.712 ВКК 32.811.7

С82

Ответственный редактор д. ф.-м. н., проф. О. Н. Граничин

Редакционная коллегия:         Н. К. Кривулин (С.-Петерб. гос. ун-т),

Г. А. Леонов (С.-Петерб. гос. ун-т),

Б. Т. Поляк (ипу ран),

А. В. Соколов    (ИПМИ КарНЦРАН),

А. П. Терехов (С.-Петерб. гос. ун-т),

М. К. Чирков (С.-Петерб. гос. ун-т),

П. С. Щербаков (ипу ран)

Печатается по постановлению

Редакционно-издателъского совета

математико-механического факультета

С.-Петербургского государственного университета

Стохастическая оптимизация в информатике. Том 9 (Вып. 2) / Под ред. О. Н. Граничина — СПб.: Издательство С.-Петербургского университета, 2013. — 166 с. ISSN 1992-2922

Издание выпускается ежегодно (том 1, ненумерованный, вышел в 2005 г., тома (вып.) 2—8 — в 2006—12 гг.) и содержит научные работы по стохастической оптимизации, особо выделяя приложения в информатике. Второй выпуск девятого тома составлен из поступивших в редколлегию рукописей и материалов одноименной регулярной серии семинаров для студентов, аспирантов и научных работников, проводившихся в 2013 г. на математико-механическом факультете С.-Петербургского университе­та под руководством профессора кафедры системного программирования О. Н. Граничина. Выпуск опубликован при поддержке гранта РФФИ №13-07-00250-а.

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

ББК 32.811.7

©   Авторы статей, 2013

 

 

3-20

Методы оптического распознавания текста на арабском языке

О. А. Берникова, к. фил. н., А. А. Бояров, О. И. Редъкин, д. фил. н., А. А. Сенов

 

Санкт-Петербургский государственный университет "Лаборатория анализа и моделирования социальных процессов: политический ислам / исламизм: теория и практика в сравнительной и исторической перспективе" bernikova@mail.ru, andrei.boiarov@gmail.com, oleg_redkin@mail.ru, alexander_senov@gmail.com

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

Ключевые  слова: оптическое распознавание символов, арабский язык, машинное обучение, кластеризация.

 

1 Работа проведена в рамках проекта СПбГУ "Математическая модель распознавания и процессинга текстов на восточных языках на основе сегментации релевантных составляющих" (Мероприятие 1, Шифр ИАС 0.37.102.2011).

Список литературы

Redkin O.I., Bernikova О.A. Problems of the Arabic OCR: new attitudes // Proceedings of the 2013 International Conference on Artificial Intelligence. Las Vegas, 2013. P. 777-782.

LeCun Y., Botton L., Bengio Y., Haffner P. Gradient-based learning applied to document recognition // Proc. IEEE 1998.

El-Sheikh T. S., Guindi R. M. Computer recognition of arabic cursive script // Pattern Recognition. № 21(4). 1988. P. 293Ц-302

Hussain F., Cowell J. Character recognition of arabic and latin scripts // Proc. IEEE International Conference on Information Visualisation. 2000. P. 51Ц-56.

Шалымов Д. С. Автоматическое распознавание печатных тек­стов арабского языка // Стохастическая оптимизация в информатике. 2007. № 3. С. 124-137

Razak Z., Zulkiflee К. Off-line handwritting textline segmentation: a review // International Journal of Computer Science and Network security. 2006. Vol. 8. № 7.

Papavassiliou V., Stafylakis Т., Katsouros V., Carayannis G. Handwritten document image segmenation into textlines and words // Pattern Recognition. 2010. Vol. 43. No 1.

Li Y., Zheng Y., Doermann D. Detecting text line in handwritten documents // ICPR'06, 2006, P. 1030-1033

[9] Kumar, Jayant, et al. Handwritten arabic text line segmentation using affinity propagation // Proc. of the 9th IAPR International Workshop on Document Analysis Systems. ACM. 2010

[10] Hamid A., Haraty R. A neuro-heuristic approach for segmenting handwritten Arabic text // ACS/IEEE International Conference on Computer Systems and Applications. 2001.

[11] Yang Y., Pedersen J. O. A comparative study on feature selection in text categorization // Proc. Fourteenth International Conference on Machine Learning. 1997. P. 412-420.

[12] Khorsheed M. S. Off-line arabic character recognition. A review // Pattern Analysis and Applications, 2002. Vol. 5. P. 31-45.

[13] Canny J. A computational approach to edge detection // IEEE Trans. Pattern Analysis and Machine Intelligence, 1986. Vol. 8. P. 679-714.

[14] Shapiro L. G., Stockman G. G. Computer Vision. — London etc.: Prentice Hall, 2001. P. 326.

[15] Lindeberg T Feature detection with automatic scale selection // International Journal of Computer Vision. 1998. № 30(2), P. 77Ц-116.

[16] Al-Maadeed S. Text-dependent writer identification for arabic handwriting // Journal of Electrical and Computer Engineering. 2012.

[17] El-Hajj R., Likforman-Sulem L, Mokbel C. Arabic handwriting recognition using baseline dependant features and hidden Markov modeling // 8th International Conference on Document Analysis and Recognition. ICDAR 2005. Seoul, Korea, 2005.

[18] Pechwitz M., Margne V. Baseline estimation for arabic handwritten words // Proc. Eighth International Workshop Frontiers in Handwriting Recognition. 2002. P. 479-484.

[19] Coates A., Carpenter В., Case C, Satheesh S., Suresh В., Wang Т., David J. Wu, Andrew Y. Ng Text detection and character recognition in scene images with unsupervised feature learning // ICDAR 2011. P. 440-445

[20] Morozkov M., Granichin О., Volkovich Z., Zhang X. Fast algorithm for finding true number of clusters. Applications to control systems // In: Proc. of the 24th Chinese Control and Decision Conference (CCDC). 2012. P. 2013-2018.

[21] Граничин О.Н., Шалымов Д.С, Аврос Р., Волкович 3. Рандомизированный алгоритм нахождения количества кластеров // Автоматика и телемеханика. 2011. №4. С. 86-98.

[22] Граничин О.Н., Измакова О.А. Рандомизированный алгоритм стохастической аппроксимации в задаче самообучения // Автоматика и телемеханика. 2005. №8. С. 52-63.

[23] Dunn J.C. Well separated clusters and optimal fuzzy partitions // Journal Cybernetics. 1974. Vol. 4. P. 95-104.

[24] Tibshirani R., Walther G., Hastie T. Estimating the number of clusters via the gap statistic // Journals of the Royal Statistical Society: Series B, 2001. Vol. 63. № 2. P. 411-423.

[25] Dudoit S., Frid lyand J. A prediction-based resampling method for estimating the number of clusters in a dataset // Genome Biol. 2002. No. 3. P. 112-129.

[26] Sugar C, James G. Finding the number of clusters in a data set: An information theoretic approach // J. America Statistical Assoc. 2003. No. 98. P. 750-763.

[27] Levine E., Domany E. Resampling method for unsupervised estimation of cluster validity // Neural Computation. 2001. № 13. P. 2573-2593.

[28] Avros R., Granichin O., Shalymov D., Volkovich Z., Weber G.-W. Randomized algorithm of finding the true number of clusters based on Chebychev polynomial approximation (Chapter 6) // Data Mining: Found. & Intell. Paradigms, D.E. Holmes, L.C. Jain (Eds.), Berlin Heidelberg: Springer-Verlag, ISRL 23, 2012. Vol. 1, P. 131-155.

 

21-32 

 

О состоятельности оценок параметров ARX-систем дробного порядка с помехой в выходном сигнале

Д. В. Иванов, к. ф.-м. н.

О. А. Кацюба, д. т. н.

Самарский государственный университет путей сообщения

dvi85@list.ru,   katsyuba.samgups@mail.ru

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

Ключевые слова: состоятельное оценивание, метод наименьших квадратов, разность дробного порядка.

Список литературы

[1] Stiassnie M. On the application of fractional calculus for the formulation of viscoelastic models // Applied Mathematical Modelling. 1979. Vol. 3 P. 300-302.

[2] Bagley R. L. ractional calculus - a different approach to the analysis of viscoelastically damped structuresr // AIAA J. 1983. Vol. 21. P. 741-748.

[3] Le Myehautye A. Fractal Geometries, Theory and Applications.— Penton Press, New York, 1991.

[4] Reyes-Melo M. E., Martinez-Vega J. J., Guerrero-Salazar C. A., Ortiz-Mendez U. Application of fractional calculus to modelling of relaxation phenomena of organic dielectric materials // Proc. Int. Conf. Solid Dielectrics. 2004. Vol. 2. P. 530-533.

[5] Vinagre В. М. Modeling and control of dynamic system using fractional calculus: Application to electrochemical processes and flexible structures // Proc. 41-st IEEE Conf Decision Control. 2002, Las Vegas, NV. 2002. P. 214-239.

[6] Zaborovsky V.,Meylanov R. Informational network traffic model based on fractional calculus// Proc Int Conf Info-tech and Info-net, ICII 2001, Beijing, China. 2001. P. 58-63.

[7] Бутковский А.Г., Постное С.С, Постнова Е.А. Дробное интегро-дифференциальное исчисление и его приложения в теории управления. I. Математические основы и проблема ин­терпретации // Автоматика и телемеханика. 2013. №. 4. С. 3— 42.

[8] Бутковский А.Г., Постное С.С, Постнова Е.А. Дробное интегро-дифференциальное исчисление и его приложения в теории управления. I. Дробные динамические системы: моде­лирование и аппаратная реализация // Автоматика и телеме­ханика. 2013. №. 5. С. 3-34.

[9] Льюнг Л. Идентификация систем. Теория для пользователя. Пер. с англ./ Под ред. Я.З. Цыпкина.— М.: Наука. 1991. 432 с.

[10] Кацюба О.А. Теория идентификации стохастических динами­ческих систем в условиях неопределенности. — Самара: Сам-ГУПС, 2008. 119 с.

[11] Иванов Д. В. Рекуррентное оценивание параметров динами­ческих систем. — Saarbrucken: LAP LAMBERT Academic Publishing GmbH. 2011. 136 с

[12] Иванов Д. В. Идентификация авторегрессии нецелого поряд­ка с помехой в выходном сигнале // Междисциплинар­ные исследования в области математического моделирова­ния и информатики. Материалы научно-практической internet-конференции. 18-19 июня 2013 г./ отв. ред. Ю.С. Нагорнов — Ульяновск^ГМЛЕТ, 2013. С. 3-34.

[13] Иванов Д.В. Идентификация линейных динамических систем нецелого порядка с помехой в выходном сигнале// Вестник Тамбовского университета. Серия: Естественные и технические науки. 2013. Т. 18. №.5-2. С. 2534-2536.

[14] Ivanov D. V. Identification discrete fractional order linear dynamic systems with output-error// Proceedings International Siberian Conference on Control and Communications (SIBCON'2013). Krasnoyarsk: Siberian Federal University. Russia, Krasnoyarsk, September 12-13, 2013. IEEE Catalog Number: CFP13794-CDR.

[15] Ivanov D. V. Identification discrete fractional order linear dynamic systems with errors-in-variables // Proceedings of IEEE East-West Design & Test Symposium (EWDTS'2013), Rostov-on-Don, Russia, September 27-30, 2013. P. 374-377.

[16] Иванов Д.В., Усков О.В. Рекуррентная идентификация били­нейных ARX-систем с помехой наблюдения в выходном сигнале // Известия высших учебных заведений. Поволжский регион. Технические науки.2012. №. 2(22). С. 96-105.

[17] Иванов Д.В.,Усков О.В. Рекуррентная идентификация били­нейных ARX-систем с помехой наблюдения в выходном сигнале // Известия высших учебных заведений. Поволжский регион. Технические науки. 2012. №. 2(22). С. 96-105.

[18] Авсиевич А.В., Иванов Д.В. Рекуррентная идентификация би­линейных ARX-систем с помехой наблюдения в выходном сиг­нале // Информационные системы и технологии. 2010. №. 5(61). С. 43-50.

[19] Кацюба О.А., Жданов А.И. Особенности применения МНК для оценивания линейных разностных операторов в задачах идентификации объектов управления // Автоматика и телемеханика. 1979. №. 8. С. 86-90.

[20] Кацюба О.А., Жданов А.И. Идентификация методом наименьших квадратов параметров уравнений авторегрессии с аддитивными ошибками измерений // Автоматика и телемеханика. 1982. №. 2. С. 29-38.

[21] Самко С.Г., Килбас А.А., Маричев О.И. — Минск: Наука и техника, 1987. 688   с.

[22] Фихтенголъц Г.М. Курс дифференциального и интегрально­го исчисления. (В 3-х томах )—М.: ФИЗМАТЛИТ, 2001. Т.2. 810 с;

[23] Гантмахер   Ф.Р. Теория матриц. — М.: Наука, 1966. 575   с.

[24] Stoica P.,Soderstrom T. Bias correction in least - squares identification // Int. J. Control. 1982. Vol. 35. No. 3. P. 449-457.

 

 

33-40

Тематическое моделирование и кластеризация текстов на арабском языке

Н. А. Кижаева, аспирант

Санкт-Петербургский государственный университет

"Лаборатория анализа и моделирования социальных процессов:

политический ислам / исламизм: теория и практика

в сравнительной и исторической перспективе"

natalia.kizhaeva@gmail.com

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

Ключевые   слова:   тематическое  моделирование,  арабский язык,   машинное обучение, кластеризация.

Список литературы

[1] Коршунов А., Гомзин А. Тематическое моделирование текстов на естественном языке // Труды ИСП РАН. 2012. С. 215-244.

[2]  Salton   G.,   McGill  M.J.   Introduction  to  Modern  Information Retrieval. 1983.

[3] DeerwesterlS., Dumais G.W., Furnas S.T., Landauer Т.К., Harshman R. Indexing by latent semantic analysis // Journal of the American Society of Information Science. Vol. 41. 1990. P. 391-407.

[4] Arora S., Ge R., Moitra A. Learning topic models-Going beyond SVD // IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS). 2012. P. 1-10.

[5] Hofmann T. Probabilistic latent semantic indexing // Proceedings of he Twenty-Second Annual International SIGIR Conference. 1999.

[6] Blei D.M., Ng A.Y., Jordan M.I. Latent Dirichlet allocation // Journal of Machine Learning Research. Vol. 3. 2003. P. 993-1022.

[7] Dhillon I., Kogan J., Nicholas C. In: A Comprehensive Survey of Text Mining. Springer, Berlin Heildelberg New York. 2003. P.73-100.

[8] Граничин О.Н., Павленко Д.В. Рандомизация получения дан­ных и 1\-оптимизация (опознание со сжатием) (обзор) // Автоматика и телемеханика. 2010. №11. С. 3-28.

[9] Efimov К., Titievsky A., Rave E., Volkovich Z. Style Determination via Random Projection. 2013.

[10]   Templeton C. Topic Modeling in the Humanities: An Overview. Maryland    Institute     for    Technology    in    the     Humanities, http://mith.umd.edu/topic-modeling-in-the-humanities-an-overview/

[11] Nelson        R.        K.   Mining        the       Dispatch.       2010.

http://dsl.richmond.edu/dispatch/

[12] Newman D. J., Block S. Probabilistic topic decomposition of an eighteenth-century American newspaper // Journal of the American Society for Information Science and Technology. Vol. 57. No. 6. 2006. P. 753-767.

[13] Chang J., Boyd-Graber J., Wang C, Gerrish S., Blei D.M. Reading tea leaves: how humans interpret topic models // Neural Information Processing Systems. 2009.

[14] Берникова О.А., Бояров А.А., Редъкин О.И., Сенов А.А. Методы оптического распознавания текста на арабском языке // Стохастическая оптимизация в информатике. Т. 9 (2). 2013. С. 3-20.

[15] Zhu X. J., Blei DM., Lafferty J. TagLDA: Bringing Document Structure Knowledge Into Topic Models. 2006.

[16] Redkin O.I., Bernikova O.A. Problems of the Arabic OCR: new attitudes // Proceedings of the 2013 International Conference on Artificial Intelligence. Las Vegas, 2013. P. 777-782.

[17] Said D. A. et al. A study of text preprocessing tools for Arabic text categorization // The Second International Conference on Arabic Language. 2009. P. 230-236.

[18] Brahmi A., Ech-Cherif A., Benyettou A. An arabic lemma-based stemmer for latent topic modeling // Int. Arab J. Inf. Technol. Vol. 10. No. 2. 2013. P. 160-168.

[19] Griffits Т., Steyvers M. Finding Scientific topics // Proceedings of the National Academy of Sciences. 101. 2004. P. 5228-5235.

[20] Граничин О.Н., Измакова О.А. Рандомизированный алгоритм стохастической аппроксимации в задаче самообучения // Автоматика и телемеханика. 2005. №8. С. 52-63.

[21] Граничин О.Н., Шалымов Д.С, Аврос Р., Волкович 3. Рандомизированный алгоритм нахождения количества кластеров // Автоматика и телемеханика. 2011. №4. С. 86-98.

 

41-53

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

Н. В. Мальковский, аспирант

Санкт-Петербургский государственный университет

malkovskynv@gmail.com

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

Ключевые слова: распределение ресурсов, оптимизация, мультиагентные системы.

Список литературы

Граничина Н.О. Мультиагентная система для распределения заказов //Управление большими системами: сборник трудов. 2010. №30-1. С. 549-566.

Kuhn H. W. The Hungarian method for the assignment problem // Naval Research Logistics Quarterly. 1955. Vol. 2. No. 1-2. C. 83-97.

Schaerf A. A survey of automated timetabling // Artificial Intelligence Review. 1999. Vol. 13. No. 2. С 87-127.

Pinedo M. Scheduling: Theory, Algorithms, and Systems. — Springer, 2012.

Поляк Б. Т. Введение в оптимизацию. — Наука. Гл.ред. физ.-мат. лит., 1983.

Граничин О.Н. Рандомизированные алгоритмы стохастической аппроксимации при произвольных помехах // Автоматика и телемеханика. 2002. №2. С. 44-55.

Boyd S.P., Vandenberghe L. Convex optimization. — Cambridge university press, 2004.

Юдин Д.Б., Голъштейн Е.Г. Линейное программирование. Теория, методы и приложения.М.: Наука, гл. ред. физ.-мат. лит. 1969.

[9] Поляк Б. Т., Щербаков П.С. Рандомизированный метод реше­ния задач полуопределенного программирования // Стохастическая оптимизация в информатике. 2006. Т. 2. С. 38-70.

[10] Nesterov Y., Nemirovskii A.S., Ye Y. Interior-point polynomial algorithms in convex programming. Philadelphia : Society for Industrial and Applied Mathematics, 1994. Vol. 13.

[11] Calafiore G.C., Campi M.C. The scenario approach to robust control design // IEEE Trans. Automat. Control. Vol. 51. No. 5. May 2006. PP. 742-753.

[12] Лопатин А. Метод отжига // Стохастическая оптимизация в информатике. 2005. Т. 1. С. 133-149.

[13] Mitchell M. An Introduction to Genetic Algorithms (Complex Adaptive Systems). - 1998.

[14] Симонова Е.В., Скобелев П. О. Мультиагентная система реше­ния задачи о расстановке восьми ферзей. Методические указа­ния. - ПГУТИ. 2010. - 33 с.

[15] Амелина Н.О. Применение протокола локального голосования для децентрализованной балансировки загрузки сети с переменной топологией и помехами в измерениях // Вест­ник Санкт-Петербургского университета. Серия 1: Математика. Механика. Астрономия. 2013. №3. С. 12-20.

[16] Amelina N., Granichin О., Kornivetc A. Local voting protocol in decentralized load balancing problem with switched topology, noise, and delays // In: Proc. of the 52nd IEEE Conference on Decision and Control, December 10-13, 2013, Firenze, Italy. P. 4613-4618.

[17] Olfati-Saber R., Fax J. A., Murray R.M. Consensus and cooperation in networked multi-agent systems // Proceedings of the IEEE. 2007. Vol. 95. No. 1. PP. 215-233.

 

 

54-72

Геометрические методы решения псевдогеометрической версии задачи коммивояжера

С. Б. Макаркин, аспирант Б. Ф. Мельников, д. ф.-м. н.

Самарский государственный университет

 s.makarkin@gmail.com, bormel@rambler.ru

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

Ключевые слово,: математическая модель, задача коммивояжера, геометри­ческая версия, псевдогеометрическая версия, геометрический подход, эвристические алгоритмы.

1 Работа      частично      поддержана      грантом      РФФИ      №      13-01-97003 (р_поволжье-а).

Список литературы

[1] Гэри М., Джонсон М. Вычислительные машины и труднорешаемые задачи. - Пер. с англ. - М.: Мир. 1982. 416 с.

[2] Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптогра­фию. - Пер. с нем. - СПб.: Изд-во БХВ-Петербург. 2010. 326 с.

[3] Hromkovic J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer. 2003. 538 p.

[4] Melnikov B. Multiheuristic approach to discrete optimization problems // Cybernetics and Systems Analysis. 2006. Vol. 42. No. 3. Sept. P. 335-341.

[5] Melnikov В., Radionov A., Gumayunov V. Some special heuristics for discrete optimization problems // Proc. of 8th International Conference on Enterprise Information Systems, ICEIS-2006. P. 360-364.

[6] Мельников В., Романов Н. Еще раз об эвристиках для задачи коммивояжера // Теоретические проблемы информатики и ее приложений. 2001. № 4. С. 81-92.

[7]   Gutin G., Punnen A. (editors) The Traveling Salesman problem.

-  Boston, Kluwer Academic Publishers. 856 p.

[8] http://arxiv.org/ftp/arxiv/papers/1204/1204.2350.pdf. -Liew Sing. Introducing convex layers to the Traveling Salesman Problem // Preprint: arXiv:1204.2348. - 2012. - Режим доступа

-  свободный. - [Интернет-ресурс].

[9] Somhom S., Modares A., Enkawa T. Competition-based neural network for the multiple travelling salesmen problem with minimax objective // Computers & Operations Research. 1999. Vol. 26. No. 4. Sept. P. 395-407.

[10] Korostensky C, Gonnet G. Near optimal multiple sequence alignments fffusing a travelling salesman problem approach // String Processing and Information Retrieval Symposium & International Workshop on Groupware. l999. P. 105-114.

[11] Мельников В., Панин А. Параллельная реализация мультиэв-ристического подхода в задаче сравнения генетических после­довательностей // Вектор науки Тольяттинского государствен­ного университета. 2012.№. 4. С. 83-86.

[12] Makarkin S., Melnikov В., Panin A. On the metaheuristics approach to the problem of genetic sequence comparison and its parallel implementation // Applied Mathematics. 2013. Vol. 4. No 10A. Sept. P. 35-39.

[13] Korostensky C, Gonnet G. Using traveling salesman problem algorithms for evolutionary tree construction // Bioinformatics. 2000. Vol. 16. P. 619-627.

[14] Melnikov В., Kashlakova E. Some grammatical structures of programming languages as simple bracketed languages // Informatica (Lithuania). 2000. Vol. 11. No 4. P. 441-453.

[15] Алексеева А., Мельников Б. Итерации конечных и бесконеч­ных языков и недетерминированные конечные автоматы // Вектор науки Тольяттинского государственного университета. 2011. № 3. С. 30-33.

[16] Мельников Б. Алгоритм проверки равенства бесконечных итераций конечных языков // Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика. 1996. № 4. С. 49-53.

[17] Gurevich Y., Veanes M., Wallace С. Can abstract state machines be useful in language theory? // Theoretical Computer Science (Developments in Language Theory). 2007. Vol. 376. No. 1-2. Sept. P. 17-29.

[18] Мельников В., Пивнева С, Рогова О. Репрезентативность случайно сгенерированных недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов // Стохастическая оптимизация в информатике. 2010. Т. 6. № 1. С. 74-82.

[19] Watson G. Goodness-of-fit tests on a circle // Biometrika. 1961. Vol. 48. No 1-2. P. 109-114; 1962. Vol. 49. No 1-2. P. 57-63.

[20] Лагутин М. Наглядная математическая статистика. - M.: Бином. 2012. 472 с.

[21] Хайкин С. Нейронные сети: полный курс. - Пер. с англ. - М.: Вильяме. 2008. 1104 с.

[22] Melnikov B. Heuristics in programming of nondeterministic games // Programming and Computer Software. 2001. Vol. 27. No 5. P. 277-288.

[23] Макаркин С. Еще об одном подходе к решению псевдогеометрической задачи коммивояжера // Вектор науки Тольяттин-ского государственного университета. 2012. № 4. С. 79-83.

[24] Макконнел Дж. Основы современных алгоритмов. - М.: Техносфера. 2004. 368 с.

[25] Штовба С. Муравьиные алгоритмы. - Exponenta Pro. Математика в приложениях. 2004. №. 4.

[26] Кузюрин Н.,Фомин С. Эффективные алгоритмы. - М.: МФТИ. 2007. 313 с.

[27] Мельников Б., Эйрих С. Подход к комбинированию незавер­шенного метода ветвей и границ и алгоритма имитационной нормализации // Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. 2010. № 1. С. 35-38.

[28] Эйрих С. Применение имитационной нормализации в гибридных алгоритмах. - Дисс.... канд. физ.-мат. наук: 05.13.18, Тольяттинский государственный университет, Д 212.264.03, защищена 21.02.2012. 124 с.

 

 

73-87

Некоторые эвристические алгоритмы в задаче вершинной минимизации недетерминированных конечных автоматов

Мельников Б. Ф., д. ф.-м. н. Мельникова Е. А., к. ф.-м. н.

Самарский государственный университет

bormel@rambler.ru, elenamel@rambler.ru

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

Ключевые слово,: недетерминированный конечный автомат, универсальный автомат, вершинная минимизация, эвристический алгоритм, итерационный алгоритм.

1 Работа      частично      поддержана      грантом      РФФИ      №      13-01-97003 (р_поволжье-а).

 

Список литературы

[1] Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1. - Пер. с англ. - М.: Мир. 1978. 613 с.

[2] Jiang Т., Ravikumar В. Minimal NFA problems are hard // SIAM J. Comput. 1993. Vol. 22. No 6. P. 1117-1141.

[3] Melnikov B. Multiheuristic approach to discrete optimization problems // Cybernetics and Systems Analysis. 2006. Vol. 42. No 3. P. 335-341.

[4] Melnikov В., Radionov A., Gumayunov V. Some special heuristics for discrete optimization problems // Proc. of 8th International Conference on Enterprise Information Systems, ICEIS-2006. P. 360-364.

[5] Geldenhuys J., van der Merwe В., van Zijl L. Reducing nondeterministic finite automata with SAT solvers // Springer. Finite-State Methods and Natural Language Processing. Lecture Notes in Computer Science. 2010. Vol. 6062. P. 81-92.

[6] Алексеева А., Мельников Б. Итерации конечных и бесконеч­ных языков и недетерминированные конечные автоматы // Вектор науки Тольяттинского государственного университета. 2011. № 3. С. 30-33.

[7] Melnikov B. The equality condition for infinite catenations of two sets of finite words // International Journal of Foundations of Computer Science. 1993. Vol. 4. No 3. P. 267-273.

[8] Мельников Б. Алгоритм проверки равенства бесконечных ите­раций конечных языков // Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика. 1996. № 4. С. 49-53.

[9] Дубасова О., Мельников Б. Об одном расширении класса контекстно-свободных языков // Программирование (РАН). 1995. № 6. С. 46-58.

[10]  Melnikov   В.,    Kashlakova   E.    Some   grammatical   structures of programming  languages  as   simple   bracketed  languages   //

Informatica   (Lithuanian  Acad. Sci.Ed.).   2000.  Vol.   11.   No  4. P. 441-454.

[11] Мельников Б. Описание специальных подмоноидов глобально­го надмоноида свободного моноида // Известия высших учебных заведений. Математика. 2004. № 3. С. 46-56.

[12] Senizergues G. L(A)=L(B)? decidability results from complete formal systems // Theor. Comput. Sci. 2001. Vol. 251. No 1-2. P. 1-166.

[13] Зубова Т., Мельников Б. Использование сетей петри для мо­делирования процесса принятия управленческих решений // Вектор науки Тольяттинского государственного университета. 2011. № 3. С. 33-37.

[14] Ханова А. Концептуальная структура системы управления предприятием на основе интегрированных моделей (на примере грузового порта) // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Информатика. Телекоммуникации. Управление. 2012. Т. 3. № 150. С. 99-105.

[15] Вылиток А., Зубова М., Мельников Б. Об одном расширении класса конечных автоматов для задания контекстно-свободных языков // Вестник Московского университета. Серия 15: Вы­числительная математика и кибернетика. 2013. № 1. С. 39-45.

[16] Polak L. Minimizations of NFA using the universal automaton // International Journal of Foundations of Computer Science. 2005. Vol. 16. No 5. P. 999-1010.

[17] Kameda Т., Weiner P. On the state minimization of nondeterministic finite automata // IEEE Transactions on Computers. 1970. Vol. C-19. P. 617-627.

[18] Lombardy S., Sakarovitch J. The universal automaton // Logic and Automata. 2008. P. 457-504.

[19] Melnikov B. A new algorithm of the state-minimization for the nondeterministic finite automata // The Korean Journal of Computational and Applied Mathematics. 1999. Vol. 6. No 2. P. 277-290.

[20] Melnikov B. Once more about the state-minimization of the nondeterministic finite automata // The Korean Journal of Computational and Applied Mathematics. 2000. Vol. 7. No 3. P. 655-662.

[21] Melnikov B. Once more on the edge-minimization of nondeterministic finite automata and the connected problems // Fundamenta Informaticae. 2010. Vol. 104. No 3. P. 267-283.

[22] Yo-Sub Han. State elimination heuristics for short regular expressions // Fundamenta Informaticae. 2013. Vol. 128. P. 445-462.

[23] Мельников В., Мельникова Е. Кластеризация ситуаций в алгоритмах реального времени в некоторых задачах дискретной оптимизации // Известия высших учебных заведений. Поволжский регион. Естественные науки. 2007. № 2. С. 3-11.

[24] Мельникова Е. Применение алгоритмов кластеризации подза­дач для вершинной минимизации недетерминированных конечных автоматов // Вектор науки Тольяттинского государ­ственного университета. 2012. № 4. С. 86-89.

[25] Мельников В., Пивнева С, Рогова О. Репрезентативность случайно сгенерированных недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов // Стохастическая оптимизация в информатике. 2010. Т. 6. № 1. С. 74-82.

[26] Hromkovic J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer. 2003. 538 p.

[27] Мельников В., Эйрих С. Подход к комбинированию незавершенного метода ветвей и границ и алгоритма имитационной нормализации // Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. 2010. № 1. С. 35-38.

 

88-95

Метод Монте-Карло, в котором вероятности переходов определяются межатомным потенциалом взаимодействия

Ю. С. Нагорнов, к. ф.-м. н.

Толъяттинский государственный университет

nagornovy s ©yandex. ru

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

Ключевые слова: метод Монте-Карло, метод молекулярной динамики, мо­делирование роста нанокристаллов, моделирование перестройки структуры кристалла.

1Работа выполнена при поддержке гранта РФФИ №11-01-00311-а.

Список литературы

[1] Нагорнов Ю.С., Мельников Б.Ф., Золотое А.В. Подходу моделирования формирования нанокристаллов в процессе карбонизации пористого кремния // Вектор науки Тольяттинского го­сударственного университета. 2012. № 4. С. 89-93.

[2] Костишко Б.М., Золотое А.В., Нагорное Ю.С. Моделирование деградации рельефа нанопористого кремния в процессе отжига в неоднородном температурном поле // Физика и техника полупроводников. 2009. Т. 43. № 3. С. 372-375.

[3] Ясников И. С, Денисова Д. А. Формоизменение габитуса микрокристаллов меди электролитического происхождения при инги-бировании роста низкоэнергетических граней // Письма в Журнал Экспериментальной и Теоретической Физики. 2012. Т. 95. №5. С. 270-272.

[4] Нагорнов Ю.С, Махмуд-Ахунов Р.Ю., Костишко Б.М., Голованов В.Н., Светухин В.В., Кац А.В. О температурной зависимости межатомного потенциала при молекулярно-динамическом моделировании свойств диоксида урана // Вопросы атомной науки и техники. Серия: Математическое моделирование физических процессов. 2010. № 4. С. 27-34.

 

96-107

Об одном алгоритме оптимизации расчетов методом Монте-Карло

при моделировании роста кристаллов

Ю. С. Нагорнов, к. ф.-м. н.

Тольяттипский государственный университет

nagornovys@yandex.ru

Предложен метод Монте-Карло для моделирования роста кристалла в условиях, когда параметры физических величин могут в процессе модели­рования существенно меняться, что на порядки увеличивает число событий. Для оптимизации расчетов предложен алгоритм, в котором предлагается про­вести группировку событий по различным критериям. В этом случае вероят­ность каждого события записывается как вектор, у которого первая коорди­ната собственно вероятность наступления события, а вторая и последующая координаты — это номера групп, к которым это событие отнесено. При ини­циализации определяются вероятности наступления групп событий, а при моделировании выбор конкретного события происходит последовательно — сначала выбор группы, потом выбор события внутри группы, причем группы могут быть вложены друг в друга. В конце алгоритма определяется факт, произойдет событие или нет. Алгоритм позволяет ускорять расчеты в 40 и более раз.

Ключевые слова: метод Монте-Карло, моделирование роста кристаллов, век­тор вероятности для групп событий.

1Работа выполнена при поддержке гранта РФФИ №11-01-00311-а.

Список литературы

[1] Abraham F.F., White G.M. Computer Simulation of Vapor Deposition on Two-Dimensional Lattices // J. Appl. Phys. 1969. Vol. 41. No 4. P. 1841-1849.

[2] Gilmer G.H., Bennema P. Simulation of crystal growth with surface diffusion // J. Appl. Phys. 1972. Vol. 43. No 4. P. 1347-1360.

[3] Van Leeuwen C, Van Rosmalen R., Bennema P. Simulation of step motion on crystal surfaces // Surf. Sci. 1974. Vol. 44. P. 213-236.

[4] Levi А.С, Kotra M. Theory and simulation of Crystal growth // J. Phys.: Condens. Matter 1997. Vol. 9. P. 299-344.

[5] Heyn Ch., Franke Т., Anton R. et. al. Correlation between island-formation kinetics, surface roughening and RHEED oscillation damping during GaAs homoepitaxy // Phys. Rev. В. 1997-П. Vol. 56. No 20. P. 13483-13489.

[6] McCoy J. M., Maksym P. A. Monte Carlo simulation of III-V MBE growth: incorporating of electron-counting constraints // Semicond. Sci. Technol. 1991. Vol. 6. P. 141-144.

[7] Maksym P. A. Monte Carlo simulation of III-V MBE growth // Semicond. Sci. Technol. 1998. No 3. P. 594-599.

[8] Kersulis S., Mitin V. Molecular beam epitaxial growth of Si (001): Monte Carlo study // Semicond. Sci. Technol. 1995. Vol. 10. P. 653-659.

[9] Костишко Б.М., Золотое А.В., Нагорное Ю.С. Моделирова­ние деградации рельефа нанопористого кремния в процессе от­жита в неоднородном температурном поле // Физика и техника полупроводников. 2009. Т. 43. № 3. С. 372-375.

[10] Золотое А.В. Моделирование процессов термического отжига и высокотемпературной карбонизации пористого кремния. Диссертация на соискание степени кандидата физико-математических наук по специальности 01.04.10 - физика полупроводников. Ульяновск. УлГУ. 2007г. 139 с.

[11] Боргардт А.А., Нагорное Ю.С. Многопоточный алгоритм Монте-Карло моделирования роста нанокристаллов // Вектор науки ТГУ. 2012. № 4(22). С. 32-36.

 

108-123

Об оптимальном хешировании FIFO-очередей

А. В. Соколов д. ф.-м. н.

ПетрГУ,

ИПМИ КарНЦ РАН,

Петрозаводск

avs@krc.karelia.ru

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

Ключевые слова: FIFO-очереди, динамические структуры данных, матема­тическое моделирование, кеширование.

1 Работа выполнена при финансовой поддержке РФФИ (грант №12-01-00253-а) и Программы стратегического развития ПетрГУ в рамках реализации ком­плекса мероприятий по развитию научно-исследовательской деятельности.

Список литературы

[1] Кнут Д. Искусство программирования для ЭВМ. Т. 1. М.: Вильямс, 2001. 736 с.

[2] Седжвик Р. Фундаментальные алгоритмы на C++. К.: Диасофт, 2001. 688 с.

[3] Баранов СИ. Язык Форт в СССР и России. Вирту­альный компьютерный музей URL: http://www. computer-museum. ru/histsoft/fortran_sorucom_2011

[4] Баранов С.Н., Ноздрунов Н.Р. Язык Форт и его реализации. — Л.: Машиностроение, Ленинградское отделение, 1988. 156 с.

[5] Бураго А.Ю., Кириллин В.А., Романовский И.В. ФОРТ — язык для микропроцессоров. Л.: Знание, 1989. 36 с.

[6] Коортап P. Stack Computers. Ellis Horwood, 1989. URL: http://www.cs.cmu.edu/ koopman/stackcomputers/

[7] Катеванис М.Г.Х., Секуин К.Х., Паттерсон Д.А., Шер-бурн Р.У. RISC: Эффективные архитектуры для СБИС-компьютеров. Электроника СБИС. Проектирование микроструктур. — М.:Мир, 1989.

[8] Hasegava M., Shigei Y. High-speed top-of-stack scheme for VLSI processor: a management algorithm and its analysis // Proceedings of 12th Symposium on Computer Architecture. June. 1985. P. 48-54.

[9] Stanley Т., Wedig R. A performance analysis of automatically managed top of stack buffers // Proceeding of 14th Symposuim on Computer Architecture. June. 1987. P. 272-281.

[10] Аксенова Е.А., Лазутина А.А., Соколов А.В. Исследование немарковской модели управления стеком в двухуровневой па­мяти // Программирование. № 1. 2004. С. 37-46.

[11] Аксенова Е.А., Соколов А.В. Оптимальное управление двумя параллельными стеками в двухуровневой памяти // Дискретная математика. Том 19, выпуск 1. М. 2007. С. 67-75.

[12] Гюнтер М. (Wind River) Оптимизированное ПО для многоядерных процессоров обеспечивает прорыв в пропускной способности сетей // МКА: ВКС. № 4. 2012. С. 38-47. www.mka.ru

[13] Егоров В. Многоядерные интегрированные сетевые процессоры высокой пропускной способности // Электронные компоненты. № 7. 2009. С. 29-33. http://www.russianelectronics.ru/leader-r/review/2192/doc/46335/

[14] Михновский С.Д., Шор Н.З. Оценка минимального числа пе­ресылок при динамическом распределении страничной памяти // Кибернетика. 1965. № 5. С. 18-21.

[15] Драц А.В., Соколов А.В. Оптимальное размещение в памяти одного уровня п стеков и/или очередей // Стохастическая оптимизация в информатике. Вып.4. 2008. С. 72-89.

[16] Феллер В. Введение в теорию вероятностей и ее приложения. — М.: Мир. 1964.

 

124-137

Оптимальное разбиение общей памяти для двух параллельных FIFO-очередей

А. В. Соколов д. ф.-м. н., Е. А. Барковскии

ПетрГУ, ИПМИ КарНЦ РАН,

Петрозаводск

avs@krc.karelia.ru, barkevgen@gmail.com

В работе предлагается математическая модель и решается задача оптимального разбиения общей памяти для двух FIFO-очередей в случае их последовательного циклического представления, в предположении, что на нечетном шаге допускаются операции включения элементов в одну из очередей с заданными вероятностями, а на четном шаге — операции исключения элементов из очередей. Наряду с последовательным, возможно и параллельное выполнение операций с очередями с заданными вероятностями.

Ключевые слова: FIFO-очереди, динамические структуры данных, матема­тическое моделирование.

1 Работа выполнена при финансовой поддержке РФФИ (грант №12-01-00253) и Программы стратегического развития ПетрГУ в рамках реализации комплек­са мероприятий по развитию научно-исследовательской деятельности.

Список литературы

[1] Nikologiannis A., Katevenis M. Multi Queue Management for Advanced QoS in High-Speed Communication Systems Computer Architecture and VLSI Systems Lab, Institute of Computer Science (ICS) Head, http://archvlsi.ics.forth.gr/muqpro/queueMgt.html

[2] Седжвик P. Фундаментальные алгоритмы на C++. К.: Диа­софт, 2001. 688 с.

[3] Боллапрагада В., Мэрфи К., Расе У. Структура операционной системы Cisco IOS. М.: Вильяме, 2002. 208 с.

[4] Кнут Д. Искусство программирования для ЭВМ. T.l. M.: Ви­льяме, 2001. 736 с.

[5] Аксенова Е.А., Драц А.В., Соколов А.В. Оптимальное управление п FIFO-очередями на бесконечном времени // Информационно-управляющие системы. 2009. № 1 С. 46-54.

[6] Aksenova E.A., Sokolov A.V. The optimal implementation of two FIFO-queues in single-level memory // Applied Mathematics. 2011. Vol. 2, № 10. P. 1297-1302.

[7] Sokolov A.V., Drac A.V. The linked list representation of n LIFO-stacks and/or FIFO-queues in the single-level memory // Information Processing Letters. Elsevier Science Publishing Company Inc. 2013. Vol. 13. № 19-21. P. 832-835.

[8] Драц А.В., Соколов А.В. Математический анализ процесса работы с М FIFO-очередями // Стохастическая оптимизация в информатике. 2012. Т. 8, № 2. С. 75-82.

[9] Каблукова И.В., Соколов А.В. Оптимальное разбиение об­щей памяти для двух последовательных циклических FIFO-очередей // Прикладная информатика. 2012. № 40. С. 113-125.

[10] Каблукова Н.В., Соколов А.В. Математический анализ одного способа представления двух FIFO-очередей в общей памяти // Труды Карельского научного центра РАН. 2013. № 1. С. 46-54.

[11] Соколов А.В. Математические модели и алгоритмы оптимального управления динамическими структурами данных. Петрозаводск: Петр-ГУ, 2002. 216 с.

[12] Herlihy M., Shavit N. The Art of Multiprocessor Programming. Morgan Kaufmann. 2008. 528 p.

[13] Кемени Дж., Снелл Дж. Конечные цепи Маркова. М.: Наука, 1960. 272 с.

[14] Lee I.A. Memory Abstractions for Parallel Programming. Massachusetts Institute of Technology, 2012. 163 p.

[15] Hendler D., Lev Y., Moir M., Shavit N. A Dynamic-Sized Nonblocking Work Stealing Deque // Distributed Computing. Special issue: DISC 04, 2006. V. 18, № 3. P. 189-207.

[16] Chase D., Lev Y. Dynamic Circular Work-Stealing Deque // SPAA'05. Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures. 2005. P. 21-28.

 

138-149

Рандомизированное обобщенное преобразование Хафа в задаче идентификации объектов на изображениях местности

С. С Сысоев, к. ф.-м. н.,   Ю. Г. Велюхов,

С. С Сысоев,   Ю. Г. Велюхов

Санкт-Петербургский государственный университет

sysoev@petroms.ru

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

Ключевые слова: преобразование Хафа, рандомизация, идентификация, рас­познавание, контур, прицеливание.

Список литературы

[1] Szeliski R. Computer Vision: Algorithms and Applications. — Springer. 2010.

[2] Абдрашитов Р.Г., Мартынов А.В. Посадка беспилотного ле­тательного аппарата на неподготовленную ВПП // Вестник ГГТУ имени П.О.Сухого. № 2. 2002. С. 55-58.

[3] Граничин О.И. Оценивание параметров линейной регрессии при произвольных помехах // Автоматика и телемеханика, 2002. №1. С. 30-41.

[4] Вахитов А.Т., Граничин О.Н., Сысоев С.С. Точность оценивания рандомизированного алгоритма стохастической оптимизации // Автоматика и телемеханика. 2006. №4. С. 86-96.

[5] Граничин О.И. Неминимаксная фильтрация при неизвестных ограниченных помехах в наблюдениях // Автоматика и телемеханика. 2002. №9. С. 125-133.

[6] Richard О. Duda, Peter E. Hart Use of the Hough Transform to Detect Lines and Curves in Pictures. Technical note, Artificial Intelligence Center, 1971.

 

150-153

Sums of a special class Generalized  Stoynov distributions

P. T. Stoynov,

Sofia University "St. Kliment Ohridski"

Sofia, Bulgaria

todorov@feb.uni-sofia.bg

Generalized Stoynov distributions are weighted versions of generalized Laplace distributions. By analogy with generalized Laplace distributions two kinds generalized Stoynov distributions are considered: one-side and two-side. Formulas for sum of a special class generalized Stoynov distributions are presented.

Key   words:   Laplace   distribution,   Stoynov   distribution,   generalized   Laplace distribution, generalized Stoynov distribution.

Список литературы

[1] Stoynov, P. Negative binomial distribution and applications. Proceedings of the Third International Conference Financial and Actuarial Mathematics — FAM 2010. Perun-Sprint Publishing, Sofia, 2010, 2-20.

 

 

 

 

 

Научное    издание

Стохастическая оптимизация в информатике

Том 9

Выпуск 2

Печатается без издательского редактирования

Обложка художника Е. А. Соловьевой

Оригинал-макет О. Н. Граничина

Подписано в печать 21.12.13. Формат 60 х 84/1 Бумага офсетная. Печать офсетная. Усл. печ. л. 10,0. Тираж 100 экз. Заказ №

Издательство СПбГУ. 199004, С.-Петербург, В.О., 6-я линия, 11/21

Тел. (812) 328-96-17; факс (812) 328-44-22

E-mail: editor@unipress.ru

www.unipress.ru

По вопросам реализации обращаться по адресу:

С.-Петербург, В.О., 6-я линия, д. 11/21, к. 21

Телефоны: 328-77-63, 325-31-76

E-mail: post@unipress.ru

Типография Издательства СПбГУ 199061, С.-Петербург, Средний пр., 41