microsoft word 13.doc mathematical problems of computer science 37, 102--107, 2012. 102 necessary conditions for optimal permissible placement by the height of the transitive directed tree with one root (part second) armen khachaturyan yerevan state university e-mail: khachaturyanarmen@gmail.com abstract the present paper is the second part of the paper [1]. here we have introduced a couple of additional concepts and have obtained some additional necessary conditions for the solution of the problem formulated in paper [1]. keywords: transitive directed graph, optimal placement. references 1. a.h. khachaturyan, “necessary conditions for optimal permissible placement by the height of the transitive directed tree with one root”, mathematical problems of computer science, vol. 36, pp. 104-114, 2012. 2. a.h. khachaturyan, “the optimal permissible placement by the height of the transitive oriented tree containing one vertex of branching”, mathematical problems of computer science, vol. 30, pp. 71-75, 2008. 3. m.r. garey, d.s. johnson, computers and intractability: a guide to the theory of npcompleteness. san francisco, ca: w.h. freeman, 1979. 4. f. gavril, “some np-complete problems on graphs,” proc.11th conf. on information sciences and systems, johns hopkins university, baltimore, md, pp. 91-95, 1977. 5. m.r. garey, r.l. graham, d.s. johnson and d.e. knuth, “complexity results for bandwidth minimization”, siam j. appl. math., vol. 34, pp. 477–495. 1978. 6. m.r. garey, d.s. johnson and l. stockmeyer, “some simplified np-complete graph problems”, theor. comput. sci., vol. 1, pp. 237–267. 1976. 7. ch.h. papadimitriou, “the np-copleteness of the bandwidth minimization problem”, computing, v. 16, pp. 263–270. 1976. 8. a.v. petrosyan, s.e. markosyan, yu.g. shukuryan, mathematical problems of automation and projection of calculating-machine. yer., (in russian). 1977. 9. g.g. geoletsyan, “flat placement of the vertices of tree with minimization of width”, dan arm. ssr, issue 56, no. 4, pp. 202–207 (in russian). 1973. a. khachaturyan 103 10. l. m. goldberg and i. a. klipker, “minimum placement of trees on a line,” technical report, physico-technical institute of low termeperatures, academy of sciences of ukraina ssr, ussr. 1976. 11. y. shiloach, “a minimum linear arrangement algorithm for undirected trees” report, dept. of applied mathematics, weizmann institute, rehovot, israel. 1976. 12. d. adolphson and t.c. hu, “optimal linear ordering”, siam j. appl. math., vol. 25, no. 3, pp. 403–423. 1973. 13. c. berge, the theory of graphs and its applications. new york: wiley, 1962. ø»ï ³ñù³ïáí ïñ³ý½çïçí ûñç»ýï³óí³í í³éç áëï µ³ñóñáõãû³ý ûåïçù³é ãáõûé³ïñ»éç ï»õ³¹ñù³ý ³ýññ³å»ßï å³ûù³ýý»ñ (ù³ë »ñïñáñ¹) ². ê³ã³ïáõñû³ý ²ù÷á÷áõù êáõûý ñá¹í³íá ñ³ý¹çë³ýáõù ¿ [1] ñá¹í³íç ß³ñáõý³ïáõãûáõýá: ²ûëï»õ ù»ýù ý»ñùáõí»é »ýù áñáß ýáñ ñ³ëï³óáõãûáõýý»ñ ¨ ëï³ó»é [1] ñá¹í³íáõù ó¨³ï»ñåí³í ëý¹ñç éáõíù³ý ñ³ù³ñ ¨ë ùç ù³ýç ³ýññ³å»ßï å³ûù³ýý»ñ: íåîáõîäèìûå óñëîâèÿ îïòèìàëüíîé äîïóñòèìîé ðàññòàíîâêè ïî âûñîòå òðàíçèòèâíî îðèåíòèðîâàííîãî äåðåâà ñ îäíèì êîðíåì (÷àñòü âòîðàÿ) à. õà÷àòóðÿí аннотация íàñòîÿùàÿ ñòàòüÿ ÿâëÿåòñÿ ïðîäîëæåíèåì ñòàòüè [1]. çäåñü ìû ïðèâåëè íåêîòîðûå íîâûå êîíöåïèè è ïîëó÷èëè åùå íåñêîëüêî íåîáõîäèìûõ óñëîâèé äëÿ ðåøåíèÿ çàäà÷è ñôîðìóëóðîâàííîé â ñòàòüå [1]. microsoft word w7.doc mathematical problems of computer science 37, 53--63, 2012. 53 least squares fitting with cubic splines mane khachatryan state engineering university of armenia e-mail: mane.khachatrian@gmail.com abstract in the paper cubic spline approximation of experimental data by least squares method is considered. an algorithm to construct a cubic spline with mixed-type boundary constraints is derived. references [1] ø. ¶. ê³ã³ïñû³ý, «ê³éá ïçåç »½ñ³ûçý ë³ñù³ý³÷³ïáõùý»ñáí ëáñ³ý³ñ¹³ûçý ë÷é³ûýç ï³éáõóáõùá», вестник гиуа. моделирование, оптимизация, управление. вып. 14, том 2. сс.33-40, 2011. [2] ф. р. гантмахер, теория матриц . москва, наука, 1967. [3] ю. с. завьялов, б. и. квасов, в. л. мирошниченко, методы сплайн-функций. москва, наука, 1980. [4] б. и. квасов. методы изогеометрической аппроксимации сплайнами. москва, физматлит, 2006. [5] дж. г. мэтьюз, к. д. финк. численные методы: использование matlab. м.: издательский дом “вильямс”, 2001. [6] р. хорн, ч. джонсон. матричный анализ. м.: мир, 1989. [7] d. kincaid and w. cheney. numerical analysis. brooks/cole, pacific grove, ca, 1991. [8] j. w. lewis. “inversion of tridiagonal matrices”, numer. math., vol. 38, pp. 333–345, 1982. êáñ³ý³ñ¹³ûçý ëåé³ûýý»ñáí ùáï³ñïáõùá ÷áùñ³·áõûý ù³é³ïáõëçý»ñç ù»ãá¹áí ø. ê³ã³ïñû³ý ²ù÷á÷áõù ðá¹í³íáõù ¹çï³ñïíáõù է ÷áñó³ñ³ñ³ï³ý ïíû³éý»ñç ùáï³ñïáõùá ëáñ³ý³ñ¹³ûçý ëåé³ûýý»ñáí` ÷áùñ³·áõûý ù³é³ïáõëçý»ñç ù»ãá¹áí: ²ñï³ííáõù ¿ ë³éá ïçåç »½ñ³ûçý ë³ñù³ý³÷³ïáõùý»ñáí ëáñ³ý³ñ¹³ûçý ëåé³ûýý»ñç ï³éáõóù³ý ³é·áñçãùá: least squares fitting with cubic splines 54 аппроксимация кубическими сплайнами по методу наименьших квадратов м. хачатрян аннотация в статье рассматривается аппроксимация экспериментальных данных методом наименьших квадратов с помощью кубических сплайнов. выводится алгоритм построения интерполяционных кубических сплайнов с краевыми ограничениями смешанного типа. . microsoft word title-template_sbornik36.doc mathematical problems of computer science 36, 41--50, 2012. 41 digital mammogram segmentation and abnormal masses detection system armen sahakyan institute for informatics and automation problems of nas of ra e-mail: armensahakyan@gmail.com abstract digital mammogram has emerged as the most popular screening technique for early detection of breast cancer and other abnormalities. raw digital mammograms are medical images that are difficult to interpret so we need to develop computer aided diagnosis (cad) systems that will improve detection of abnormalities in mammogram images. extraction of the breast region by delineation of the breast contour allows the search for abnormalities to be limited to the region of the breast. we need to perform essential pre-processing steps to suppress artifacts, enhance the breast region and then extract breast region by the process of segmentation. in this paper we present an automated system for detection of abnormal masses by anatomical segmentation of breast region of interest (roi). references [1] l.-m. wun, r. m. merrill, and e. j. feuer, "estimating lifetime and age-conditional probabilities of developing cancer," lifetime data analysis, vol. 4, pp. 169-186, 1998. [2] "who cancer facts," http://www.who.int/cancer/en/, 2009. [3] l. shen, r. rangayyan, and j. desaultels, “detection and classification mammographic calcifications”, international journal of pattern recognition and artificial intelligence. singapore: world scientific, pp. 1403–1416, 1994. [4] f. aghdasi, r.ward, and b. palcic, “restoration of mammographic images in the presence of signal-dependent noise”, in state of the art in digital mammographic image analysis. singapore: world scientific, vol. 7, pp. 42–63, 1994. [5] y. chitre, a. dhawan, and m. moskowtz, “artificial neural network based classification of mammographic microcalcifications using image structure features”, in state of the art of digital mammographic image analysis. singapore: world scientific, vol. 7, pp. 167–197, 1994. [6] pisano and f. shtern,“image processing and computer-aided diagnosis in digital mammography,” in state of the art of digital mammographic image analysis. singapore: world scientific, vol. 7, pp. 280–291, 1994. digital mammogram segmentation and abnormal masses detection system 42 [7] a. sahakyan, h. sarukhanyan, "automatic segmentation of the breast region in digital mammograms", computer science and information technologies, proceedings of the conference, pp. 386 389, yerevan, armenia, september 26-30, 2011. [8] indra kanta maitra ; sanjay nag and prof. samir k. bandyopadhyay, "automated digital mammogram segmentation for detection of abnormal masses using binary homogeneity enhancement algorithm", indian journal of computer science and engineering, issue 3, vol. 2, pp. 416-427, 2011. [9] j. suckling et al., “the mammographic image analysis society digital mammogram database”, exerpta medica., vol. 1069, pp. 375– 378, 1994. âí³ûçý ù³ùá·ñ³ùý»ñç ë»·ù»ýï³íáñù³ý ¨ ³ýýáñù³é ½³ý·í³íý»ñç ñ³ûï³µ»ñù³ý ñ³ù³ï³ñ· ². ê³ñ³ïû³ý ²ù÷á÷áõù îñíù³·»õóç ù³õóï»õç ¨ ³ûé ³ýýáñù³é ½³ý·í³íý»ñç í³õ ñ³ûïý³µ»ñù³ý ù»ãá¹ý»ñçó ¿ ãí³ûçý ù³ùá·ñ³ýç³ý։ âí³ûçý ù³ùá·ñ³ùý»ñá µåßï³ï³ý å³ïï»ñý»ñ »ý, áñáýó í»ñ³ùß³ïù³ý ¨ í»ñéáõíáõãû³ý ñ³ù³ñ ³ýññ³å»ßï ¿ ùß³ï»é ñ³ù³ï³ñ·ã³ûçý ³ëïáñáßù³ý ¹ç³·ýáëïçï (cad) ñ³ù³ï³ñ·, áñá ïû·ýç ³ýýáñù³é ½³ý·í³íý»ñç ñ³ûïý³µ»ñù³ýá։ îñíùç »½ñ³·í»ñç ßñç³·íù³ý û·ýáõãû³ùµ, ïñíù³ûçý ßñç³ýç ³é³ýóý³óáõùá ãáõûé ¿ ï³éçë, áñ ³ýýáñù³é ½³ý·í³íý»ñç áñáýáõùá ë³ñù³ý³÷³ïíç ùç³ûý ïñíùç ßñç³·íáí։ ²ýññ³å»ßï ¿ çñ³ï³ý³óý»é ³õùáõïý»ñç ñ»é³óù³ý ý³ë³ùß³ïù³ý ù³ûé»ñ, µ³ñ»é³í»é ïñíù³·»õóç å³ïï»ñá ¨ ³ûýáõñ»ï¨ ë»·ù»ýï³íáñ»é։ ²ûë ñá¹í³íáõù ý»ñï³û³óí³í ¿ ³ýýáñù³é ½³ý·í³íý»ñç ñ³ûïý³µ»ñù³ý íñ³·ñ³ûçý ñ³ù³ï³ñ·, áñá çñ³ï³ý³óýáõù ¿ å³ïï»ñç ñ»ï³ùñùçñ ïçñáõûãý»ñç (roi) ë»·ù»ýï³íáñáõùá։ ñèñòåìà öèôðîâîé ñåãìåíòàöèè ìàììîãðàì è îáíàðóæåíèÿ àíîìàëüíûõ ìàññ à. ñààêÿí àííîòàöèÿ öèôðîâàÿ ìàììîãðàôèÿ ÿâëÿåòñÿ ñàìîé ïîïóëÿðíîé òåõíèêîé ñêðèíèíãà äëÿ ðàííåãî âûÿâëåíèÿ ðàêà ìîëî÷íîé æåëåçû è äðóãèõ íàðóøåíèé. öèôðîâûå ìàììîãðàìû ÿâëÿþòñÿ ìåäèöèíñêèìè èçîáðàæåíèÿìè è äëÿ èõ îáðàáîòêè íûæíî ðàçàðàáîòàòü âñïîìîãàòåëüíûå äèàãíîñòè÷åñêèå êîìïüþòåðíûå (cad) ñèñòåìû, êîòîðûå áóäóò ñïîñîáñòâîâàòü âûÿâëåíèþ íàðóøåíèé. îòìå÷åíèå îáëàñòè ãðóäè êîíòóðîì ïîçâîëÿåò ïîèñêû àíîìàëèè áûòü îðãàíèÿåííûì òîëüêî îáëàñòüþ ãðóäè. ìû äîëæíû âûïîëíèòü øàãè ïðåâàðèòåëüíîé îáðàáîòêè, ÷òîáû ïîäàâèòü øóìû, óëóòøèòü èçîáðàæåíèå îáëàñòè ãðóäè è çàòåì îòìåòèòü îáëàñòü ãðóäè ïðîöåññîì ñåôìåíòàöèè. â ýòîé ñòàòüå ìû ïðåäñòàâëÿåì àâòîìàòèçèðîâàííóþ ñèñòåìû äëÿ îáíàðóæåíèÿ àíîìàëüíûõ ìàññ àíàòîìè÷åñêîé ñåôìåíòàöèåé îáëàñòè èíòåðåñà (roi) ãðóäè. microsoft word w10.doc mathematical problems of computer science 37, 83--87, 2012. 83 overview of methods of biometric based key protection gurgen khachatrian and narek malkhasyan american university of armenia, institute for informatics and automation problems of nas of ra abstract the security of any modern cryptosystem relies on the assumption that secret keys used for the system such as secret keys for message encryption and authentication as well as private keys of public key cryptosystem are unknown. this assumption is not easy to satisfy in most practical applications. the most widely applicable method uses conventional passwords to encrypt secure keys stored on the computer device. however passwords are vulnerable against many kinds of attacks since they can be either guessed or stolen. another basic problem is the user authentication. it is well known that when using a traditional and widely used cryptographic methods the user authentication is achieved by challenge response protocols, the essence of which consists in verifying that the party which wants to confirm his authentication possesses a secret key. in this paper an overview of methods of password generation from biometric data is presented along with the discussion of the remaining challenges and possible directions of future research. references 1. m. maslennikov, practical cryptography, saint petersburg, 2003. 2. g. khachatrian and h. khasikyan “correlation based password generation from fingerprints”, proc. ita-2012 conference “classification, forecasting, data mining “. 3. a. juels and m. wattenberg, “a fuzzy commitment scheme”, in sixth acm conference computer and communication security”, pp. 28-36, 1999. 4. a. juels and m. sudan, “a fuzzy vault scheme” , proc. ieee international symposium on information theory” , pp.408, 2002. 5. u. uludag, s. pankanti and a. jein. “fuzzy vault for fingerprints”, lecture notes on computer science, pp. 55-71, 2005. overview of methods of biometric based key protection 84 բանալիների պաշտպանության բիոմետրիկ (կենսաչափական) մեթոդների դիտարկում գ. խաչատրյան և ն. մալխասյան ամփոփում ցանկացած ժամանակակից կրիպտոհամակարգի անվտանգությունը հիմնվում է այն ենթադրության վրա, որ համակարգում օրտագործվող բանալիները, ինչպես օրինակ՝ հաղորդագրությունների գաղտնագրման, նույնականացման և բաց բանալիով կրիպտոհամակարգերի բանալիները, անհայտ են: կիրառական համակարգերի մեծամասնությունում այս ենթադրությունը բավարարելը հեշտ չէ: ամենատարածված մեթոդը ավանդական գաղտնաբառերի օգտագործումն է համակարգչային սարքի վրա պահվող բանալին գաղտնագրելու համար: սակայն գաղտնաբառերը խոցելի են տարատեսակ հարձակումների նկատմամբ, քանի որ դրանք կարող են գուշակվել և գողացվել: մեկ այլ կարևոր խնդիր է օգտագործողների նույնականացման խնդիրը: հայտնի է, որ ավանդական և տարածված ծածկագրաբանական մեթոդներ օգտագործելիս օգտագործողի նույնականացումը իրականացվում է <<մարտահրավեր-պատասխան>> արձանագրությունների միջոցով, որոնց օգնությամբ օգտագործողը կարող է ապացուցել որևէ բանալու պատկանելությունը իրեն: սույն հոդվածում ներկայացված են բիոմետրիկ (կենսաչափական) տվյալներից գաղտնաբառերի ստացման մեթոդների, ինչպես նաև ոլորտի այլ մարտահրավերների և աշխատանքի ապագա հնարավոր ուղղությունների դիտարկումները: обзор биометрических методов защиты ключей г. хачатрян и н. малхасян аннотация безопасность всех современных криптосистем базируется на предположении, что секретные ключи используемые в системе, такие как ключи для шифрования сообщений, ключи аутентикации и ключи криптосистем с открытым ключом, неизвестны. в большинстве практических приложений удовлетворять это предположение непросто. самый распространенный метод это использование традиционных паролей для шифрования ключей хранящихся на некоторых компютерных устройствах. но пароли уязвимы множеством атак, так как они могут быть разгаданы и украдены. другая основная проблема заключается в аутентикации пользователей. хорошо известно, что при использовании традиционных и широко известных криптографических методов, аутентикация пользователей достигается при помощи протоколов “вызов-ответ”, при помощи которых пользователь может доказать принадлежность некоторого ключа ему. в этой статье представляется обзор методов генерирования паролей из биометрических данных, а также рассматриваются вызовы в этой сфере и возможные будущие пути исследования. d:\sbornik\...\02\article.dvi mathematical problems of computer science 37, 17{24, 2012. on the shannon cipher system with cor r elated sour ce outputs and guessing wir etapper e avesdr oping thr ough a n oisy channel tig r a n ma r g a r ya n institute for informatics and automation problems of nas of ra e-mail: martigranm@gmail.com abstract in this paper the shannon cipher system with discrete memoryless correlated sources is considered. the wiretapper gains the noisy version of the cryptogram through the memoryless noisy channel and tries to guess the secret information which is related to the encrypted plaintext. the security level of the encryption system is measured by the expected number of wiretapper's guesses. the upper and lower bounds are obtained for the guessing rate. refer ences [1 ] j. l . ma s s e y, \ gu e s s in g a n d e n t r o p y" , p roceedings of the 1994 ie e e international symp. inform. theory ( tr o n d h e im , n o r wa y, 1 9 9 4 ) , p . 2 0 4 . [2 ] e . a r ika n , \ on t h e a ve r a g e n u b e r o f g u e s s e s r e qu ir e d t o d e t e r m in e t h e va lu e o f a r a n d o m va r ia b le " , transactions of the 12th p rague conference on information theory, statistical d ecision f unction and r andom p rocesses, p p . 2 0 -2 3 , 1 9 9 4 . [3 ] e . a r ika n , \ a n in e qu a lit y o n g u e s s in g a n d it s a p p lic a t io n t o s e qu e n t ia l d e c o d in g " , ie e e trans. inform. theory, vo l. 4 2 , n o . 1 , p p . 9 9 -1 0 5 , 1 9 9 6 . [4 ] e . a r ika n a n d n . me r h a v, \ gu e s s in g s u b je c t t o d is t o r t io n " , ie e e trans. inform. theory, vo l. 4 4 , n o . 3 , p p . 1 0 4 1 -1 0 5 6 , 1 9 9 8 . [5 ] e . a r ika n a n d n . me r h a v,\ jo in t s o u r c e -c h a n n e l c o d in g a n d g u e s s in g wit h a p p lic a t io n t o s e qu e n t ia l d e c o d in g " , ie e e trans. inform. theory, vo l. 4 4 , n o . 5 , p p . 1 7 5 6 -1 7 6 9 , 1 9 9 8 . [6 ] n . me r h a v a n d e . a r ika n , \ th e s h a n n o n c ip h e r s ys t e m wit h a g u e s s in g wir e t a p p e r " , ie e e trans. inform. theory, vo l. 4 5 , n o . 6 , p p . 1 8 6 0 -1 8 6 6 , 1 9 9 9 . [7 ] e . a r ika n , \ gu e s s in g a n d c r yp t o lo g y" , in \ a s p e c t s o f n e t wo r k a n d in fo r m a t io n s e c u r it y" , n a to s c ie n c e fo r p e a c e a n d s e c u r it y, s e r ie s d : in fo r m a t io n a n d co m m u n ic a t io n s e c u r it y, ios p r e s s , vo l. 1 7 , p p . 2 1 1 { 2 1 7 , 2 0 0 8 [8 ] e . a . h a r o u t u n ia n a n d a . r . gh a z a r ya n , \ on t h e s h a n n o n c ip h e r s ys t e m wit h a wir e t a p p e r g u e s s in g s u b je c t t o d is t o r t io n a n d r e lia b ilit y r e qu ir e m e n t s " , p roceedings of the 2002 ie e e int. symp. inform. theory ( l a u s a n n a , s wit z e r la n d ) , p . 3 2 4 . 1 7 1 8 on the shannon cipher system with correlated source outputs and guessing wiretapper [9 ] e . a . h a r o u t u n ia n , \ r e a lib ilit y a p p r o a c h in wir e t a p p e r g u e s s in g t h e o r y" , in \ a s p e c t s o f n e t wo r k a n d in fo r m a t io n s e c u r it y" , n a to s c ie n c e fo r p e a c e a n d s e c u r it y, s e r ie s d : in fo r m a t io n a n d co m m u n ic a t io n s e c u r it y, ios p r e s s , vo l. 1 7 , p p . 2 4 8 { 2 6 0 , 2 0 0 8 . [1 0 ] y . h a ya s h i a n d h . y a m a m o t o , \ co d in g t h e o r e m s fo r t h e s h a n n o n c ip h e r wit h a g u e s s in g wir e t a p p e r a n d c o r r e la t e d s o u r c e o u t p u t s " , ie e e trans. inform. theory, vo l. 5 4 , n o . 6 , p p . 2 8 0 8 -2 8 1 7 , ju n e 2 0 0 8 . [1 1 ] d . ma lo n e a n d w . g. s u lliva n , \ gu e s s wo r k a n d e n t r o p y" , ie e e trans. inform. theory, vo l. 5 0 , n o . 3 , p p . 5 2 5 -5 2 6 , 2 0 0 4 . [1 2 ] e . a . h a r o u t u n ia n a n d t. m. ma r g a r ya n , \ th e s h a n n o n c ip h e r s ys t e m wit h a g u e s s in g wir e t a p p e r e a ve s d r o p in g t h r o u g h a n o is y c h a n n e l" , transactions of iiap of nas of r a , m athematical p roblems of computer science, vo l. 3 5 , p p . 7 0 -7 6 , 2 0 1 1 . [1 3 ] e . a . h a r o u t u n ia n a n d t. m. ma r g a r ya n , \ w ir e t a p p e r g u e s s in g b y n o is y c h a n n e l fo r t h e s h a n n o n c ip h e r s ys t e m wit h c o r r e la t e d s o u r c e o u t p u t s " , p roceedings of international conference csit 2011, p p . 1 2 5 { 1 2 8 , y e r e va n 2 0 1 1 . [1 4 ] i. cs is z ¶a r a n d j. k äo r n e r , information theory: coding theorems for d iscrete m emoryless systems, n e w y o r k: a c a d e m ic , 1 9 8 1 . [1 5 ] t. m. co ve r a n d j. a . th o m a s , e lements of information theory, n e w y o r k: w ile y, 2 0 0 6 . ¶áõß³ïáõ ·³õïý³·áõç ³éï³ûáõãû³ùµ ³õùïáï ï³åáõõáí ¨ ³õµûáõñç ñ³ñ³µ»ñ³ïóí³í ñ³õáñ¹³·ñáõãûáõýý»ñáí þ»ýáýû³ý í³íï³·ñù³ý ñ³ù³ï³ñ·ç ù³ëçý î. ø³ñ·³ñû³ý ²ù÷á÷áõù ðá¹í³íáõù ¹çï³ñïí»é ¿ áý¹ñ³ï, ³é³ýó ñçßáõáõãû³ý ñ³ñ³µ»ñ³ïóí³í ³õµûáõñý»ñáí þ»ýáýû³ý í³íï³·ñù³ý ñ³ù³ï³ñ·á: ¶³õïý³·áõá ëï³ýáõù ¿ ·³õïý³·ñç ³õ³í³õí³í ï³ñµ»ñ³ïá ¨ ó·ïáõù ·áõß³ï»é ·³õïýç ï»õ»ïáõãûáõýá, áñá ï³åí³í ¿ í³íï³·ñí³í ³ûé ñ³õáñ¹³·ñáõãû³ý ñ»ï: ì³íï³·ñù³ý ñ³ù³ï³ñ·ç ·³õïýçáõãû³ý ³ëïç׳ýá ã³÷íáõù ¿ ·³õïý³·áõç ·áõß³ïáõùý»ñç ùý³ï³ç ëå³ë»éçáí: êï³óí»é »ý í»ñçý ¨ ëïáñçý ·ý³ñ³ï³ï³ýý»ñ ïé³ñù³ý ³ñ³·áõãû³ý ñ³ù³ñ: î øåííîíîâñêîé ñåêðåòíîé ñèñòåìå ñ êîððåëèðîâàííûìè ñîîáùåíèÿìè èñòî÷íèêà è óãàäûâàþùèì íàðóøèòåëåì ïîäñëóøèâàþùèì ÷åðåç êàíàë ñ øóìîì ò. ìàðãàðÿí àííîòàöèÿ â ñòàòüå ðàññìàòðèâàåòñÿ øåííîíîâñêàÿ ñåêðåòíàÿ ñèñòåìà ñ äèñêðåòíûìè èñòî÷íèêàìè áåç ïàìåòè. íàðóøèòåëü ïîëó÷àåò çàøóìëåííóþ âåðñèþ êðèïòîãðàììû ÷åðåç êàíàë áåç ïàìÿòè è ñòðåìèòñÿ óãàäàòü t. margaryan 1 9 ñåêðåòíóþ èíôîðìàöèþ, ñâÿçàííóþ ñ çàøèôðîâàíûì ñîîáùåíèåì. óðîâåíü ñåêðåòíîñòè êðèïòîãðàôè÷åñêîé ñèñòåìû èçìåðÿåòñÿ ñðåäíèì ÷èñëîì óãàäûâàíèé íàðóøèòåëÿ. ïîëó÷åíû âåðõíÿÿ è íèæíÿÿ ãðàíèöû ñêîðîñòè óãàäûâàíèÿ. d:\sbornik\...\tpel.dvi mathematical problems of computer science 36, 13-16, 2012. a n ote on i nter val e dge-color ings of gr aphs r a fa ye l r . k a m a lia n yz a n d p e t r o s a . p e t r o s ya n yx yinstitute for informatics and automation problems of nas of ra, zdepartment of applied mathematics and informatics, rau xdepartment of informatics and applied mathematics, ysu e-mail: rrkamalian@yahoo.com, pet petros@ipia.sci.am abstract an edge-coloring of a graph g with colors 1; : : : ; t is called an interval t-coloring if for all colors are used, and the colors of edges incident to each vertex of g are distinct and form an interval of integers. in this note we prove that if a connected graph g with n vertices admits an interval t-coloring, then t · 2n ¡ 3. we also show that if g is a connected r-regular graph with n vertices that has an interval t-coloring and n ¸ 2r + 2, then this upper bound can be improved to 2n ¡ 5. refer ences [1 ] a .s . a s r a t ia n , c.j. ca s s e lg r e n , \ on in t e r va l e d g e c o lo r in g s o f ( ®; ¯ ) -b ir e g u la r b ip a r t it e g r a p h s " , d iscrete m ath. 307, p p . 1 9 5 1 -1 9 5 6 , 2 0 0 6 . [2 ] a .s . a s r a t ia n , r .r . k a m a lia n , \ in t e r va l c o lo r in g s o f e d g e s o f a m u lt ig r a p h " , appl. m ath. 5, p p . 2 5 -3 4 , 1 9 8 7 . [3 ] a .s . a s r a t ia n , r .r . k a m a lia n , \ in ve s t ig a t io n o n in t e r va l e d g e -c o lo r in g s o f g r a p h s " , j . combin. theory ser. b 62, p p . 3 4 -4 3 , 1 9 9 4 . [4 ] m.a . a xe n o vic h , \ on in t e r va l c o lo r in g s o f p la n a r g r a p h s " , congr. numer. 159, p p . 7 7 -9 4 , 2 0 0 2 . [5 ] k . gia r o , m. k u b a le , m. ma la ¯ e js ki, \ co n s e c u t ive c o lo r in g s o f t h e e d g e s o f g e n e r a l g r a p h s " , d iscrete m ath. 236, p p . 1 3 1 -1 4 3 , 2 0 0 1 . [6 ] r .r . k a m a lia n , in t e r va l e d g e -c o lo r in g s o f g r a p h s , d o c t o r a l th e s is , n o vo s ib ir s k, 1 9 9 0 . [7 ] r .r . k a m a lia n , p .a . p e t r o s ya n , \ a n o t e o n u p p e r b o u n d s fo r t h e m a xim u m s p a n in in t e r va l e d g e -c o lo r in g s o f g r a p h s " , d iscrete m ath. 312, p p . 1 3 9 3 -1 3 9 9 , 2 0 1 2 . [8 ] p .a . p e t r o s ya n , \ in t e r va l e d g e -c o lo r in g s o f c o m p le t e g r a p h s a n d n-d im e n s io n a l c u b e s " , d iscrete m ath. 310, p p . 1 5 8 0 -1 5 8 7 , 2 0 1 0 . 1 3 1 4 a note on interval edge-colorings of graphs ¶ñ³éáõù ·ñ³ýý»ñç ùçç³ï³ûù³ûçý ïáõ³ûçý ý»ñïáõùý»ñç ù³ëçý è. ø³ù³éû³ý ¨ ä. ä»ïñáëû³ý ²ù÷á÷áõù g ·ñ³ýç ïáõ³ûçý ýñïáõùá 1 ; : : : ; t ·áõûýñáí ï³ýí³ý»ýù ùçç³ï³ûù³ûçý t–ý»ñïáõù, »ã» µáéáñ ·áõûý»ñá û·ï³·áñíí»é »ý ¨ ûáõñ³ù³ýãûáõñ ·³·³ãçý ïçó ïáõ»ñá ý»ñïí³í »ý ½áõû· ³é ½áõû· ï³ñµ»ñ ¨ ñ³çáñ¹³ï³ý ·áõûý»ñáí: ²ûë ³ßë³ï³ýùáõù ³å³óáõóíáõù ¿, áñ »ã» ·³·³ã³ýç g ï³å³ïóí³í ·ñ³ýá áõýç ùçç³ï³ûù³ûçý t–ý»ñïáõù, ³å³ t · 2 n¡ 3 : ü³¨ ³ßë³ï³ýùáõù óáõûó ¿ ïñíáõù, áñ »ã» n ·³·³ã³ýç g ï³å³ïóí³í r–ñ³ù³ë»é ·ñ³ýá áõýç ùçç³ï³ûù³ûçý t-ý»ñïáõù ¨ n ¸ 2 r + 2 , ³å³ t · 2 n ¡ 5 : çàìåòêà î èíòåðâàëüíûx ðåáåðíûx ðàñêðàñêàx ãðàôîâ ð. êàìàëÿí è ï. ïåòðîñÿí àííîòàöèÿ èíòåðâàëüíîé t-ðàñêðàñêîé ãðàôà g íàçîâåì ïðàâèëüíóþ ðàñêðàñêó ðåáåð g â öâåòà 1 ; :::; t ïðè êîòîðîé â êàæäûé öâåò i, 1 · i · t îêðàøåíî xîòÿ áû îäíî ðåáðî ãðàôà g, è ðåáðà, èíöèäåíòíûå êàæäîé âåðøèíå g, îêðàøåíû â ïîñëåäîâàòåëüíûå öâåòà. â íàñòîÿùåé ðàáîòå äîêàçàíî, ÷òî åñëè ñâÿçíûé ãðàô g ñ n âåðøèíàìè èìååò èíòåðâàëüíóþ t–ðàñêðàñêó, òî t · 2 n ¡ 3 . òàêæå â äàííîé ðàáîòå ïîêàçàíî, ÷òî åñëè ñâÿçíûé r-ðåãóëÿðíûé ãðàô g ñ n âåðøèíàìè èìååò èíòåðâàëüíóþ t-ðàñêðàñêó è n ¸ 2 r + 2 , òî t · 2 n ¡ 5 microsoft word tpel.doc mathematical problems of computer science 36, 104--114, 2012. 104 necessary conditions for optimal permissible placement by the height of the transitive directed tree with one root armen khachaturyan yerevan state university e-mail: khachaturyanarmen@gmail.com abstract in the graph theory the problem of the minimum placement of graph by the height, which is similarly formulated in [2] (the problem of minimum cut arrangement of graph), is known. the problem is np-complete [3]. in the present paper a partial case of this problem, i.e. the problem of optimal permissible placement by the height of the transitive directed tree with one root (which is a such transitive directed graph, the arc base of which forms a directed tree with one root), is formulated. in this paper some new concepts are introduced and necessary conditions for optimal solving of the new formulated problem are given. keywords: transitive directed graph, optimal placement. r e f e r e n c e s 1. a. h. khachaturyan, “the optimal permissible placement by the height of the transitive oriented tree containing one vertex of branching”, mathematical problems of computer science, vol. 33, pp183-186, 2010. 2. m.r. garey, d.s. johnson, computers and intractability: a guide to the theory of npcompleteness. san francisco, ca: w.h. freeman, 1979. 3. f. gavril, “some np-complete problems on graphs,” proc.11th conf. on information sciences and systems, johns hopkins university, baltimore, md, pp. 91-95, 1977. 4. m. r. garey, r. l. graham, d. s. johnson and d. e. knuth, “complexity results for bandwidth minimization”, siam j. appl. math., vol. 34, pp. 477–495. 1978. 5. m. r. garey, d. s. johnson and l. stockmeyer, “some simplified np-complete graph problems”, theor. comput. sci., vol. 1, pp. 237–267. 1976. 6. ch. h. papadimitriou, “the np-completeness of the bandwidth minimization problem”, computing, v. 16, pp. 263–270. 1976. 7. a.v. petrosyan, s. e. markosyan, yu. h. shukuryan, mathematical problems of automation and projection of calculating-machine. yer., (in russian). 1977. 8. g.g. geoletsyan, “flat placement of the vertices of tree with minimization of width”, dan arm. ssr, issue 56, no. 4, pp. 202–207 (in russian). 1973. 9. l. m. goldberg and i. a. klipker, “minimum placement of trees on a line,” technical report, physico-technical institute of low temperatures, academy of sciences of ukraine ssr, 1976. a. khachaturyan 105 10. y. shiloach, “a minimum linear arrangement algorithm for undirected trees” report, dept. of applied mathematics, weizmann institute, rehovot, israel. 1976. 11. d. adolphson and t.c. hu, “optimal linear ordering”, siam j. appl. math., vol. 25, no. 3, pp. 403–423. 1973. 12. c. berge, the theory of graphs and its applications. new york: wiley, 1962. ø»ï ³ñù³ïáí փոխանցական կողմնորոշ í³éç áëï µ³ñóñáõãû³ý ûåïçù³é ãáõûé³ïñ»éç ï»õ³¹ñáõãû³ý ³ýññ³å»ßï å³ûù³ýý»ñ ². ê³ã³ïáõñû³ý ²ù÷á÷áõù ¶ñ³ýý»ñç ï»ëáõãû³ý ù»ç ñ³ûïýç ¿ ·ñ³ýç áëï µ³ñóñáõãû³ý ûåïçù³é ï»õ³¹ñù³ý ëý¹çñá, áñá ñ³ù³ñå»ù ï»ñåáí ó¨³ï»ñåí³í ¿ [2]-áõù (·ñ³ýç ùçýçù³é ïïñí³íùáí ï³ñ·³íáñù³ý ëý¹çñá): êý¹çñá np-¹åí³ñ ¿: êáõûý ³ßë³ï³ýùáõù ó¨³ï»ñåí³í ¿ ³ûë ëý¹ñç ù³ëý³ïç ¹»åùá` ù»ï ³ñù³ïáí փոխանցական կողմնորոշ í³éç (¹³ ³ûý փոխանցական կողմնորոշ ·ñ³ýý ¿, áñç ³õ»õý»ñç µ³½³ý ï³½ùáõù ¿ ù»ï ³ñù³ïáí կողմնորոշ í³é) áëï µ³ñóñáõãû³ý ûåïçù³é ãáõûé³ïñ»éç ï»õ³¹ñù³ý ëý¹çñá: ²ûë ³ßë³ï³ýùáõù ý»ñï³û³óí»é »ý áñáß³ïç ýáñ ñ³ëï³óáõãûáõýý»ñ ¨ ïñí»é ó¨³ï»ñåí³í ëý¹ñç ûåïçù³é éáõíù³ý ³ýññ³í»ßï å³ûù³ýý»ñ: íåîáõîäèìûå óñëîâèÿ îïòèìàëüíîé äîïóñòèìîé ðàññòàíîâêè ïî âûñîòå òðàíçèòèâíî îðèåíòèðîâàííîãî äåðåâà ñ îäíèì êîðíåì à. õà÷àòóðÿí аннотация â òåîðèè ãðàôîâ èçâåñòíà ïðîáëåìà ìèíèìàëüíîé ðàññòàíîâêè ãðàôà ïî âûñîòå, êîòîðàÿ àíàëîãè÷íî ñôîðìóëèðîâàíà â [2] (ïðîáëåìà óïîðÿäî÷èâàíèÿ ãðàôà ñ ìèíèìàëüíûì ðàçðåçîì). ïðîáëåìà np-ïîëíà 3. â íàñòîÿùåé ñòàòüå ôîðìóëèðîâàí ÷àñòíûé ñëó÷àé ýòîé ïðîáëåìû: ïðîáëåìà îïòèìàëüíî äîíóñòèìîé ðàññòàíîâêè ïî âûñîòå òðàíçèòèâíî îðèåíòèðîâàííîãî äåðåâà ñ îäíèì êîðíåì (ýòî òàêîé òðàíçèòèâíî îðèåíòèðîâàííûé ãðàô, áàçà äóã êîòîðîãî ñîñòàâëÿåò îðèåíòèðîâàííîå äåðåâî ñ îäíèì êîðíåì). â ðàáîòå ââåäåíû íåêîòîðûå íîâûå ïîíÿòèÿ è äàíû íåîáõîäèìûå óñëîâèÿ äëÿ îïòèìàëüíîãî ðåøåíèÿ ñôîðìóëèðîâàííîé çàäà÷è. mathematical problems of computer science 53, 63--66, 2020. udc 004 development of multi-eap radius configuration for eduroam service arthur s. petrosyan, gurgen s. petrosyan, robert n. tadevosyan and kevork kh. arsalanian institute for informatics and automation problems of nasra e-mail: arthur@sci.am, gurgen@sci.am, robert@sci.am, kevork.arsalanian@sci.am abstract this paper describes the mechanism of authenticating multiple-realm eduroam users via a single multi-eap radius configuration. the solution is based on the fact that some organizations, which are willing to join the eduroam community and use the service, especially in small communities, do not have a huge number of users, thus it will be costeffective to use a single radius server for them instead of having a separate radius server per each realm. the solution is unmatched in terms of practical open implementation. it has been implemented and tested in asnet-am network. keywords: eduroam, wifi, wireless, eap, authentication, radius 1. introduction in the original eduroam model [1], institutions that would like to join eduroam have to install and configure their own institutional radius server (irs), which should be registered at federation level radius server (flrs) within the national roaming operator (nro), meaning that every organization should follow these steps regardless of their number of users, which is not cost-effective for organizations with a few number of users. therefore, the solution of using a single radius server for multiple institutions (organizations, universities, etc.) has been thought up, developed and successfully implemented. 2. architecture generally, for each realm in eduroam, a separate radius server is being configured, which is normal for big organizations with thousands of active users. but for organizations with hundreds or tens of users having a separate radius server, it may not be so practical. in addition, some nros provide hosted radius solutions for connecting institutions, and in case of such relatively 63 mailto:arthur@sci.am mailto:gurgen@sci.am mailto:robert@sci.am development of multi-eap radius configuration for eduroam service 64 small ones it would be much more cost-effective for nro to use a single radius server for multiple supported realms instead of creating separate radius servers for each supported realm. with this configuration, it is now possible to use a central radius server with multiple extensible authentication protocol (eap) configuration for each supported realm [2]. the number of realms supported is unlimited. the authentication itself is performed at the institution site, as before, using the authentication method that is applicable to a particular institution (imap-based email authentication, ldap-based, etc.). when a user tries to authenticate, the request will be directed from the visited institution to the central radius server and from there to the user organization to get authenticated (fig. 1). fig. 1. authentication process. based on our previous boost concept [3], we mainly implemented this solution using the imap/email authentication method, but since the solution is based on freeradius [4], there is no limit for using any required authentication method. the solution described here has an appropriate ansible playbook [5] to automate setting up the process for multi-eap radius configuration. 3. advantages the main advantage of this solution is the creation of an automatically usable freeradius-based multi-eap radius configuration. the solution described in this paper will influence small organizations to use eduroam with minimal administrative overhead and minimal cost. while a. petrosyan, g. petrosyan, r. tadevosyan and k. arsalanian 65 carrying out investigations in this area, we found no such configuration described in public, except for the official general description [2], which lacks many important details about particular eap types. so, this solution is unmatched in terms of practical open implementation. 4. disadvantages although this solution of having multiple organizations on a single radius server is costefficient, it is not an ideal solution for large organizations with thousands of users. 5. conclusion this solution may be interesting in cases, where nros implement hosted radius solutions for relatively small connecting institutions (with hundreds or tens of users) to have a cost-effective single radius server for multiple supported realms instead of creating separate radius servers for each supported realm. references [1] [online]. available: https://www.eduroam.org/ [2] [online]. available: https://wiki.freeradius.org/modules/rlm_eap#i_want_to_enable_multiple_eaptypes_ho w_can_i_configure [3] a. petrosyan, g. petrosyan, r. tadevosyan and k. arsalanian, “identity infrastructure boost concept for eduroam service”, transactions of iiap nas ra, mathematical problems of computer science, vol. 52, pp. 61-65, yerevan 2019. [4] [online]. available: https://freeradius.org/ [5] [online]. available: https://github.com/asnet-am/eduroam-imap-playbook submitted 10.02.2020, accepted 26.05.2020. development of multi-eap radius configuration for eduroam service 66 բազմակի eap radius կարգավորումների մշակում eduroam ծառայության համար արթուր ս. պետրոսյան, գուրգեն ս. պետրոսյան, ռոբերտ ն․ թադևոսյան և գէորգ խ. արսալանյան հհ գաա ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ e-mail: arthur@sci.am, gurgen@sci.am, robert@sci.am, kevork.arsalanian@sci.am ամփոփում հոդվածում նկարագրվում է eduroam-ի օգտագործողների վավերացման մեխանիզմ՝ բազմակի eap radius կարգավորումների միջոցով։ լուծումը հիմնված է այն փաստի վրա, որ որոշ կազմակերպություններ, որոնք ցանկանում են միանալ eduroam համայնքին և օգտվել ծառայությունից, չունեն հսկայական քանակությամբ օգտվողներ, ուստի ծախսարդյունավետ կլինի նմանատիպ կազմակերպություններից յուրաքանչյուրի համար առանձին radius սերվեր ունենալու փոխարեն, օգտագործել մեկ radius սերվեր մի քանի կազմակերպության համար: լուծումը եզակի է՝ գործնական բաց իրականացման առումով: այն իրականացվել և փորձարկվել է asnet-am ցանցում: բանալի բառեր` eduroam, wifi, անլար, eap, նույնականացում, radius. разработка конфигурации multi-eap radius для сервиса eduroam артур с. петросян, гурген с. петросян, роберт н. тадевосян и кеворк х. арсаланян институт проблем информатики и автоматизации нан ра e-mail: arthur@sci.am, gurgen@sci.am, robert@sci.am, kevork.arsalanian@sci.am аннотация в статье представлен механизм аутентификации пользователей eduroam с помощью конфигурации multi-eap radius для сервиса eduroam. решение основано на том факте, что некоторые, не имеющие большого количества пользователей, организации, желающие присоединиться к сообществу eduroam, могут использовать один общий radius сервер. данное решение не имеет аналогов с точки зрения практической открытой реализации. решение реализовано и опробовано в сети asnet-am. ключевые слова: eduroam, wifi, беспроводная связь, eap, аутентификация, radius. mailto:arthur@sci.am mailto:gurgen@sci.am mailto:robert@sci.am mailto:arthur@sci.am mailto:gurgen@sci.am mailto:robert@sci.am начиная с начала 2000 года осуществляется внедрение ghis в здравоохранении, в рамках принятого проекта о реформирование информ mathematical problems of computer science 43, 42--46, 2015. 42 on generalized primitive recursive string functions 1 mikayel h. khachatryan institute for informatics and automation problems of nas ra e-mail: mikayel.khachatur@gmail.com abstract the notion of generalized primitive recursive string function is introduced and relations between such functions and primitive recursive string functions in the usual sense ([1], [2]) are investigated. it is proved that any generalized primitive recursive string function is everywhere defined if and only if it is a primitive recursive string function in the usual sense. keywords:string function, primitive recursive string function, superposition, alphabetic primitive recursion. 1. introduction the notion of primitive recursive string function ([1], [2]) is generalized in the following sense: string functions are considered which are defined similar to the definition of primitive recursive string functions, however, such functions are in general not everywhere defined. namely, the definition of generalized primitive recursive string function is obtained from the definition of primitive recursive string function in the usual sense by adding the everywhere undefined onedimensional string function to the set of basic functions. it is proved that any generalized primitive recursive string function is everywhere defined if and only if it is a primitive recursive string function in the usual sense. similar problems concerning arithmetical functions are considered in [3]. 2. generalized primitive recursive string functions the notion of many-dimensional primitive recursive string function is given in [1], [2]. for the convenience of the reader let us recall the corresponding definitions. let a be an alphabet, i.e. a list of different symbols, { } ( ) by we denote the set of all words in a (including the empty word ). the symbols 1 this work was supported by state committee of science, mesra, in frame of the research project № scs 131b321. m. khachatryan 43 we call letters in a. the length of a word is the number k (the length of the empty word  is 0).  we say that the function f is an n-dimensional string function ( ) in the alphabet a if for any n-tuple ( ) where all are words in a, the value ( ) is either undefined, or is a word in a. by ( ) we denote the statement: the value ( ) is defined. below we consider only the string functions in the fixed alphabet a. basic string functions are defined as functions of the following kinds. 1. one-dimensional function ( )such that ( )  for any word p in a. 2. one-dimensional function ( ) where such that ( ) for any word p in a. 3. n-dimensional functions ( ) where such that ( ) for any n-tuple ( ) of words in a. the operator s of superposition is defined as follows. if g is an n-dimensional string function, are m-dimensional string functions, then the m-dimensional string function ( ) is defined by the following equality: ( ) ( ( ) ( ) ( )) where are any words in a. the operator r of alphabetic primitive recursion is defined as follows. if g is an ndimensional string function, are (n+2)-dimensional string functions, then the (n+1)-dimensional string function ( ) is defined by the following equalities: ( ) ( )   ( ) ( ( )) where and are any words in a. we say that a string function is a primitive recursive string function (prsf), if it can be obtained from basic functions by the operators of superposition and alphabetic primitive recursion. the notion of generalized primitive recursive string function (gprsf) is defined similar to the notion of prsf with the only difference: one-dimensional everywhere undefined u(p) function is added to the set of basic functions. below the statements “f is a primitive recursive string function in the usual sense”, “f is a generalized primitive recursive string function”, will be denoted correspondingly by and as it is known ([1]. [2]) every function is everywhere defined. clearly, any primitive recursive string function in the usual sense is a generalized primitive recursive string function, and, on the other side, the set of generalized primitive recursive string functions is wider than one of primitive recursive string functions in the usual sense. however, the following theorem (which will be proved below) takes place. theorem 1: any everywhere defined string function is a generalized primitive recursive string function iff it is a primitive recursive string function in the usual sense. on generalized primitive recursive string functions 44 the proof of theorem is based on lemma 1 which will be considered below. we will use primitive recursive string functions which are defined by the following equalities (where are any words in a). 1. the function ̇ is defined as follows:  ̇  ̇  ̇  (where ). 2. the function ( ) is defined as follows: ()  ( ) (where ). 3. the function ̅̅ ̅̅ ( ) is defined as follows: ̅̅̅̅ ()   ̅̅̅̅ ( ) (where ). 4. the functions k( )for are defined as follows: 2(   2( ) (where ), 3(   3( ) 2( )(where ), m+1( (where ),  m+1( ) m( ) (where ), it is easily seen that k( )  when one of the words is equal to the empty word  otherwise k( ) a generalized primitive recursive string function ( )(“branching function”) is defined by the following conditions: (1) ( p:(2) ( ) is undefined when  . such a function is obtained by the operator of alphabetic primitive recursion using the everywhere undefined basic function u(p): ( p, ( ) ( ( ( )))(where ). now let us introduce the notion of standard image (or s-image) of string function f in a. namely for any n-dimensional string function f in a its s-image is defined as a function f* such that for any words in a: ( ) { ( ( )) ( ) (let us recall that ( ) for any word qin a). obviously, for any string function f in a the function f* is an everywhere defined string function. lemma 1: any string function f in a is a generalized primitive recursive string function if and only if its s-image f* is a primitive recursive string function in the usual sense. m. khachatryan 45 proof: let f be an n-dimensional generalized primitive recursive string function. we will prove that its s-image f* is a primitive recursive string function in the usual sense. the proof will be implemented using the induction on the process of constructing f from the basic functions by the operators of substitution and alphabetic primitive recursion. if f is a basic function then it has one of the forms ( ) ( ), (where ), ( )(where ), ( ) which is everywhere undefined. it is easily seen that in these cases f* has correspondingly the following forms ( ) ( ) ( ) ( ) ( ) so f* is a primitive recursive string function in the usual sense. now if a function is obtained by the operator s of superposition from functions and the functions are primitive recursive string functions in the usual sense, then the s-image f* of the function f satisfies the following equation: ( ) k+1( ( ( ) ̇ ( ) ̇  ( ) ̇ ) ( ) ̇ ( ) ̇  ( ) ̇ )) where k+1 is the function described above. it is easily seen that finally, if a function is obtained by the operator r of alphabetic primitive recursion from functions and the functions are primitive recursive string functions in the usual sense, then the s-image f* of the function f satisfies the following equalities: ( ) ( )  ( ) ( ( ))  ( ) ( ( )) where for any i such that ( ) 2( ( ̇ ) ) and are s-images correspondingly, of the function is defined above. it is easily seen that so, it is proved that s-image of any generalized primitive recursive string function is a primitive recursive string function in the usual sense. now let us suppose that the s-image f* of some n-dimensional string function f is a primitive recursive string function in the usual sense. clearly, then the function f satisfies the following equality: ( ) ( ( ) ̇ ̅̅̅̅ ( ( ))) were br is the function defined above. this completes the proof of lemma. the proof of theorem 1 is obtained now as follows. if f is an n-dimensional everywhere defined string function such that then and ( ) ( ) ̇ for any words in a. hence, on the other side, if then clearly f is an everywhere defined string function such that this completes the proof of theorem. on generalized primitive recursive string functions 46 references [1] a. i. malcev, algorithms and recursive functions, 2 nd edition, moscow, “nauka”, (in russian), 1986. [2] m. h.khachatryan, “on the representation of arithmetical and string functions in formal languages”, transactions of the iiap of nas of ra, mathematical problems of computer science, vol. 27, pp. 37-53, 2006. [3] i.d. zaslavsky, “on some generalizations of the primitive recursive arithmetic”, theoretical computer science, vol. 322, pp. 221-230, 2004. submitted 10.12.2014, accepted 16. 02. 2015. ընդհանրացված պարզագույն կարգընթաց բառային ֆունկցիաների մասին մ. խաչատրյան ամփոփում սահմանվում է ընդհանրացված պարզագույն կարգընթաց բառային ֆունկցիայի հասկացությունը, ինչպես նաև հետազոտվում են այդպիսի ֆունկցիաների փոխառնչությունները սովորական ձևով սահմանված ([1], [2]) պարզագույն կարգընթաց բառային ֆունկցիաների հետֈ ապացուցվում է, որ ցանկացած ընդհանրացված պարզագույն կարգընթաց բառային ֆունկցիա ամենուրեք որոշված է այն և միայն այն դեպքում, երբ այն սովորական իմաստով պարզագույն կարգընթաց բառային ֆունկցիա էֈ об обобщенных примитивно рекурсивных словарных функциях м. хачатрян аннотация определяется понятие обобщенной примитивно рекурсивной словарной функции и исследуются взаимоотношения таких функций с примитивно рекурсивными словарными функциями ([1], [2]) в обычном смысле этого понятия. доказывается, что обобщенная примитивно рекурсивная словарная функция всюду определена тогда и только тогда, когда она является примитивно рекурсивной словарной функцией в обычном смысле этого понятия. mathematical problems of computer science 53, 57--62, 2020. udc 004 development of management system for eduroam database updated specification arthur s. petrosyan and gurgen s. petrosyan institute for informatics and automation problems of nasra e-mail: arthur@sci.am, gurgen@sci.am abstract this paper presents a system developed to simplify the eduroam database management. the goal of the eduroam database is to provide the necessary information needed for the operation of the eduroam service and related supporting services like eduroam monitoring, service location maps and usage statistics, as well as the eduroam cat tool. eduroam database specifications have been updated to the second version and the update has recently become mandatory, requiring many changes for databases of all national roaming operators (nro). the solution presented here can be useful for nro administrators to simplify the eduroam database management. keywords: eduroam, nro, wi-fi, wireless, monitoring, statistics, database. 1. introduction eduroam (education roaming) [1] has become a well-known secure wireless network roaming access service used by the international research and education community. it enables scientists, researchers, teachers, students from different institutions to securely gain wi-fi internet access at any eduroam-enabled institution worldwide. the eduroam service organization model assumes that in each country there is a national roaming operator (nro), mostly operated by the national research and education network (nren) of that country. the eduroam database has been built as a central database with a mechanism that automatically collects data from nros to enable the operation of the eduroam service and related supporting services like eduroam monitoring, service location maps and usage statistics, as well as the eduroam cat tool. eduroam database specifications have been updated to the second version and the update have recently become mandatory [2], requiring many changes for all national roaming operators (nro). this paper presents a system developed for managing the eduroam database with specifications updated to the second version. 57 mailto:arthur@sci.am mailto:gurgen@sci.am development of management system for eduroam database updated specification 58 2. developed management system according to the new second version (v.2.0) of eduroam database specification [3], each nro should provide general data in the defined xml or json format. the data should be available at the specific, predefined urls: http://www.eduroam./general/ and must be accessible from the eduroam database server site monitor.eduroam.org. data for the eduroam database v.2.0 can be validated by xml [4] or json validators [5]. the developed management system is fully compliant with the eduroam database v.2.0 specification and provides a flexible web interface to manage data for a particular nro. we have chosen to implement only the json version in our system and omit the xml format, since one of them is required, not both, and json seems to be preferred by the eduroam database server-site monitoring. mysql/maria db was chosen as a backend for the implementation of eduroam database specification. appropriate mysql tables were designed and created for datasets (i.e., database tables) and respective fields (attributes) containing general data as described in [3]. the web interface created for database management provides the possibility to add/edit both the institutions and service locations. the main page of the web interface looks like the one presented in fig. 1. fig. 1. main page. the created web interface is english language-based. text fields in the database are bilingual (english and armenian), but only english fields are required. as a result, the system can be used by any nro worldwide. a. petrosyan and g. petrosyan 59 a separate contact table is created for each institution, and contact persons can be added from the web interface and then selected as responsible for multiple institutions (fig. 2). it is allowed to add up to five contact person per institution. fig. 2. contacts page. next, the institution can be added by filling in the required fields in the form presented in fig. 3. fig. 3. institution page. the locations interface then allows specifying the location data for each registered institution (fig. 4). required fields include location gps coordinates. the web interface of our system allows us to easily select a location on the map and put the appropriate coordinates into the form. this makes filling in the data much easier. development of management system for eduroam database updated specification 60 fig. 4. locations page. after having the data of institutions and service locations ready in the database, we can generate a json file, as well as validate it with the validators of central eduroam database server site. after generation, the system places the files in a special folder on the web server, the access to which is open only for the ip address of the central monitoring server eduroam, which downloads them from nros on a daily basis, checks them for compliance with the requirements, and updates them. to prevent data loss, all old previously generated json files are stored in a separate backup folder with the date and time of their generation. all the data can be edited and verified at any time via the web interface. after adding an organization, it is possible to add/edit/delete/sort the eduroam service locations for the organization in accordance with the database structure. in particular, the following fields are available: name, address, city, coordinates, connection status, contact persons, type of service location. in addition, there are specific fields such as: type of wi-fi coverage (single/area/mobile), name of the wi-fi network (ssid) that in most cases is “eduroam”, encryption (wpa, wpa2), number of access points and availability (physical access restrictions or no restrictions). 3. service location map along with the backend management system described above, a frontend service location map was also created. it takes data from the same institutions and service locations database and presents it on the nros website. the current version of it is part of armenian nro website [6] and is based on openstreetmap [7] and leaflet [8]. a. petrosyan and g. petrosyan 61 4. advantages similar eduroam database management systems were developed by greek nren grnet and called djnro [9], as well as by czech nren cesnet [10]. but the main issue of using this djnro is that it has service locations coordinates support based on the google maps api, which has become a paid service since 2018. instead, in our work we used the free openstreetmap/leaflet [7] [8] alternatives. the cesnet solution turned out to be hard to implement on our site because of many separated scripts and insufficiently documented solution. 5. conclusion this solution may be interesting for any nros worldwide. it is currently implemented in asnet-am for managing the armenian part of eduroam database. the solution we presented is all-in-one for nros functions regarding the management of eduroam database, as well as for presenting this data on the service location map. references [1] online]. available: https://www.eduroam.org/ [2] [online]. available: https://monitor.eduroam.org/fact_eduroam_db.php [3] [online]. available: https://monitor.eduroam.org/eduroam-database/v2/docs/eduroamdatabase-ver17102017.pdf [4] [online]. available: https://monitor.eduroam.org/eduroamdatabase/v2/scripts/xml_validation_test.php [5] [online]. available: https://monitor.eduroam.org/eduroamdatabase/v2/scripts/json_validation_test.php [6] [online]. available: https://www.eduroam.am/ [7] [online]. available: https://www.openstreetmap.org [8] [online]. available: https://leafletjs.com/ [9] [online]. available: https://github.com/grnet/djnro [10] [online]. available: https://github.com/cesnet/eduroam-db submitted 10.12.2019, accepted 04.05.2020. https://github.com/grnet/djnro development of management system for eduroam database updated specification 62 նորացված ձևաչափի eduroam տվյալների շտեմարանի կառավարման համակարգի մշակում արթուր ս. պետրոսյան և գուրգեն ս. պետրոսյան հհ գաա ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ e-mail: arthur@sci.am, gurgen@sci.am ամփոփում այս հոդվածում ներկայացված է eduroam տվյալների շտեմարանի կառավարումը պարզեցնելու նպատակով մշակված համակարգը: eduroam տվյալների շտեմարանի նպատակը eduroam ծառայության և դրա հետ կապված աջակցության ծառայությունների համար անհրաժեշտ տեղեկատվություն տրամադրելն է, ինչպիսիք են` eduroam-ի մոնիտորինգը, ծառայության գտնվելու վայրի քարտեզները և օգտագործման վիճակագրությունը, ինչպես նաև` eduroam cat գործիքը: eduroam տվյալների շտեմարանը վերջերս թարմացվել է նոր ձևաչափին համապատասխան, ինչը մեծ փոփոխություններ է պահանջում բոլոր ազգային ռոումինգի օպերատորների համար (nro): այստեղ ներկայացված լուծումը կարող է օգտակար լինել nro-ների ադմինիստրատորների համար: բանալի բառեր` eduroam, nro, wi-fi, անլար, մոնիտորինգ, վիճակագրություն, տվյալների շտեմարան: разработка системы управления обновленной базой данных eduroam артур с. петросян и гурген с. петросян институт проблем информатики и автоматизации нан ра e-mail: arthur@sci.am, gurgen@sci.am аннотация в статье представлена система упрощающая управление базой данных eduroam. цель базы данных eduroam предоставить необходимую информацию для работы службы eduroam и связанных с ней вспомогательных услуг, таких как мониторинг eduroam, карты расположения служб и статистика использования, а также инструмент cat eduroam. спецификации базы данных eduroam были обновлены до второй версии, что требует значительных изменений баз сервиса для всех национальных операторов роуминга (nro). представленное здесь решение может быть полезным для администраторов управления базами данных eduroam nro. ключевые слова: eduroam, nro, wi-fi, беспроводная связь, мониторинг, статистика, база данных. mailto:arthur@sci.am mailto:gurgen@sci.am mailto:arthur@sci.am mailto:gurgen@sci.am начиная с начала 2000 года осуществляется внедрение ghis в здравоохранении, в рамках принятого проекта о реформирование информ mathematical problems of computer science 48, 82-88, 2017. point clouds preprocessing for better registration aram v. gevorgyan russian-armenian university e-mail: aramgv@gmail.com abstract in this article, we review point clouds preprocessing algorithms that enhance the results and performance of point clouds registration. registration is a problem of merging two or more point clouds into one common. if a point cloud is obtained from a real physical object, it definitely has some noise and outliers. this noise can negatively affect the registration process and often prevent from good results. point clouds preprocessing reduces noise and helps to get better registration results. also we present several experiments on real dataset and results. keywords: point clouds, registration, icp, sor filter. 1. introduction 3d technologies are developing very fast in recent years and are used in many spheres. one of the most commonly used formats in which 3d data is stored is a point cloud. point cloud is a set of points in some coordinate system. point cloud can also store some additional information, such as color or surface normals. point clouds have many applications, and they can be converted to other formats. we can also get a surface from point clouds using one of the surface reconstruction algorithms. one of the fundamental problems in computer vision and computer graphics is 3d or point clouds registration problem. registration is the process of merging multiple partially overlapped point clouds from different scenes into one common point cloud. in other words, 3d registration transforms multiple point clouds from different coordinate systems into the same coordinate system so they can be aligned. process of getting a point cloud from a real physical object is known as reverse engineering or 3d scanning. there are active and passive methods of 3d scanning. active methods usually use laser or structured light for getting 3d information. while passive methods don't emit anything, 82 a. gevorgyan 83 they rely on the detection of reflected ambient radiation. examples of passive methods are stereovision, structure from motion, structure from shading. all these methods have their props and corns. but whatever method we use for getting a point cloud, it cannot be ideal. some noise and errors are presented. all these factors negatively affect the process of registration and can prevent for getting good results. also in case of big data, if point clouds have many points performance of the registration algorithms may be inacceptable. so in this article we review some point clouds preprocessing methods that can enhance the results and performance of registration algorithms. the article has the following structure: in section 2 we speak in details about point clouds registration and icp algorithm, in section 3 we review some preprocessing algorithms and in section 4 we present experiments and results. 2. related work suppose we want to align the source point cloud p }),...,,{( 2,1 npppp = with the target point cloud q }),...,,{( 2,1 nqqqq = . the aim of registration problem is to find such a transformation t (rotation matrix and translation vector) (1) applying which to source point cloud p will bring it to the same coordinate system with q.             == 1000 ),( 3333231 2232221 1131211 trrr trrr trrr trt . )1( the registration algorithms can be divided into 2 classes: coarse and fine registration. coarse registration algorithms are usually used for initial alignment and then results are refined with fine registration. the most popular 3d registration algorithm is iterative closest point (icp) [1-2] algorithm. icp is very simple for realization and has good performance. the main idea of icp algorithm is iteratively register point clouds, trying at each iteration to minimize distance between point clouds. icp algorithm consists of the following steps: 1) finding correspondent points between point clouds. the closest point between point clouds are defined as correspondent points. 2) transformation estimation applying which to source point cloud 𝑃𝑃 will minimize the error e. ( )∑ = −+= n i ii qtrpn e 1 21 , where 𝑅𝑅 rotation matrix, 𝑡𝑡 translation vector, 𝑝𝑝𝑖𝑖 and 𝑞𝑞𝑖𝑖 correspondent points, 𝑁𝑁 number of points. this error metric is called as point-to-point metric, there are also point-to-plane metrics defined in [2]. 3) apply the transformation to source point cloud 𝑃𝑃. the steps 1-3 are executed iteratively until the error is smaller than the given threshold. over the years many variants of icp algorithm are developed, more details about them in [3]. icp algorithm has a known local minimum issue: if the initial distance between the point clouds is big icp can give very wrong results. also noise and outliers can negatively affect the results of the registration. so it will be good to reduce noise before the registration process. point clouds preprocessing for better registration 84 3. point clouds preprocessing there are several point clouds preprocessing techniques that can be used for different purposes. let us review some of them. down sampling: down sampling filter decreases the number of points in a point cloud data set. the aim of down sampling is to reduce the number of points in point cloud while still preserving the object and scene it represents. down sampling filter is generally used on big data set to increase the performance of the algorithms working with point clouds. each point is described by a voxel and its centroid. voxel is a box with a specific size in the space, and centroid is a point the coordinates of which are the mean value of coordinates of all points in the voxel. there are two ways of down sampling: "voxel grid" and "uniform sampling". the first way replaces all points in the voxel with the centroid of that voxel, and the second one replaces with the nearest existing point to centroid. in the voxel grid approach a new point is generated, while in the uniform sampling no new point is inserted into the point cloud. the uniform sampling method is a bit slower than the voxel grid, but it represents the underlying surface more accurately. pass-through filter: pass through filter is used for cutting of values that are either inside or outside the given range. it can be used, for example, if we want to remove points that are deeper than some threshold. pass through filter checks for every point if its field (coordinate) is in the given interval or not. radius outlier removal filter: radius outlier removal filter for each point examines a circle with the given radius and with center in that point. if the number of points in that circle is less than the given threshold k, then this point is specified as an outlier and removed from the point cloud. in figure 1 we can see an example of radius outlier removal filter, if k = 1, the yellow point will be removed, if k =2, the green and yellow points will be removed. fig. 1. example of radius outlier removal filter [8]. statistical outlier removal filter (sor): statistical outlier removal filter removes points depending on their local neighborhood. for each point the mean distance from it to its k nearest neighbors is computed. by assuming that the resulted distribution is gaussian with a mean and a standard deviation, all points the mean distances of which are greater than the global distances mean plus standard deviation with some coefficient are defined as outliers and removed from dataset. point is specified as an outlier if its mean distance of its nearest k neighbors is bigger than m, where m is defined as: a. gevorgyan 85 σ*nsigmaavgm += , where 𝑎𝑎𝑎𝑎𝑎𝑎 is the average distance, 𝑛𝑛𝑛𝑛𝑛𝑛𝑎𝑎𝑛𝑛𝑎𝑎 – the number of times the standard deviation (userdefined parameter), 𝜎𝜎 – the standard deviation. an example of statistical outlier removal filter is shown in figure 2. fig. 2. example of statistical outlier removal filter. 4. experiments and results in this section we present some experiments and results with different datasets and preprocessing algorithms. for our realization we use point cloud library (pcl) [6] the biggest library for point clouds processing, viewing and manipulation. a registration with pcl is described in [7]. let us review some experiments of point clouds preprocessing steps. experiment 1: in this experiment we want to show how the downsample filter can affect the performance of registration algorithms, especially if point clouds have many points. we take two point clouds from stanford bunny dataset [4] each point cloud has 40256 points. we downsample these point clouds with the voxel of size 0.01. then we compare the performance of icp registration algorithm of original point clouds and these point clouds after down sample filter is applied. the results were shown in table 1. table 1: point clouds number of points icp (time) original point clouds 40256 32.91 downsampled point clouds 394 0.1 as it is seen downsampling greatly affects the performance, while results in this case are almost the same. experiment 2: in the second experiment we use our dataset of bear object. the point clouds in this dataset were generated from 2 web cameras by stereovision techniques. stereovision is a technique that estimates 3d information of a scene from two or more cameras. 3d information is obtained as a depth map, then the depth map can be converted into a point cloud. more about stereovision -in [5,10]. we scan the bear from different views and get a point cloud for each view. point clouds preprocessing for better registration 86 in this experiment we want to remove background to have a point cloud only of bear object. figure 3 shows the point cloud of whole scene. fig. 3. the whole scene. we segment our bear object from the scene using pass through filter, filtering by x, y and z coordinates. the result is shown in figure 4: fig. 4. segmented point cloud. experiment 3: in this experiment, we want to show how the noise can negatively affect the registration process. we take segmented point clouds from the previous experiment and merge these point clouds without applying any filter and after applying a statistical outlier removal filter. the results are shown in figures 5: a. gevorgyan 87 a) b) fig. 5. the result of merging 10 point clouds with icp algorithm. a) range point clouds, b) after applying statistical outlier removal filter. as we can see from the figures, the noise and outliers in original point clouds negatively affect the registration process bringing to an absolutely wrong result. but after applying the sor filter, we can get a good result. references [1] p. j. besl and h. d. mckay, “a method for registration of 3-dshapes”, ieee trans. pattern anal. mach. intell., vol. 14, no. 2, pp. 239–256, 1992. [2] y. chen and g. medioni, “object modeling by registration of multiple range images”, image and vision computing, vol. 3, no. 10, pp 145–155, april 1992. [3] s. rusinkiewicz and m. levoy, “efficient variants of the icp algorithm”, 3-d digital imaging and modeling, pp. 145–152, 2001. [4] stanford bunny dataset: [online]. available: https://graphics.stanford.edu/data/3dscanrep/ [5] p. j. bagga, “real time depth computation using stereo imaging”, journal electrical and electronic engineering, vol. 1, pp. 51-54, 2013. [6] point cloud library: [online]. available: http://www.pointclouds.org/ [7] d. holz, a.e. ichim, f. tombari, r.b. rusu and s. behnke, “registration with the point cloud library: a modular framework for aligning in 3-d”, ieee robotics & automation magazine, vol. 22, no. 4, pp. 110-124, 2015. [8] [online].available: http://www.pointclouds.org/documentation/tutorials/remove_outliers.php#remove-outliers [9] a. v. gevorgyan, “point clouds registration and generation from stereo images”, ithea journal, "information content and processing", vol. 3, no. 2, pp. 193-200, bulgaria, 2016. submitted 06.08.2017, accepted 04. 12.2017. point clouds preprocessing for better registration 88 կետերի ամպերի մշակում գրանցման արդյունքները բարելավելու նպատակով ա. գևորգյան ամփոփում սույն հոդվածում ներկայացված են կետերի ամպերի մշակման ալգորիթմներ, որոնք բարելավում են կետերի ամպերի գրանցման (registration) արդյունքները և արդյունավետությունը: գրանցման խնդիրը կայանում է երկու կամ ավելի կետերի ամպ միաձուլելու մեջ: եթե կետերի ամպը ստացված է իսկական ֆիզիկական օբյեկտից, այն պարունակում է աղմուկ, որը կարող է բացասական ազդեցություն ունենալ գրանցման գործընթացի վրա և խոչնդոտել ստանալ լավ արդյունքներ: կետերի ամպերի նախամշակումը նվազեցնում է աղմուկը և օգնում է ստանալ ավելի լավ գրանցման արդյունքներ: սույն հոդվածում ներկայացված են նաև մի քանի փորձերի արդյունքներ իրական տվյալների վրա: обработка облаков точек для лучшей регистрации а. геворкян аннотация в данной статье представлены алгоритмы обработки облаков точек, которые улучшают результаты и эффективность регистрации облаков точек. регистрация это задача соединения двух или более облаков точек. если облако точек получено от реального физического объекта, то в нем присутствует шум. данный шум отрицательно влияет на процесс регистрации и часто мешает получить хороший результат. предварительная обработка облаков точек уменьшает шум и помогает получить лучший результат регистрации. в данной статье, также представлены результаты нескольких экспериментов на реальных данных. начиная с начала 2000 года осуществляется внедрение ghis в здравоохранении, в рамках принятого проекта о реформирование информ mathematical problems of computer science 45, 122--126, 2016. symbiosis of email and sms arman h. harutyunyan1, sona h. gharagyozyan2 1yerevan state university 2institute for informatics and automation problems of nas ra e-mail:a_harutyunyan@ipia.sci.am, sona@ipia.sci.am abstract the specific features of the means of written communication through computer and mobile networks, as well as the prehistory of the establishment of hybrid communication system using ip and gsm network technologies have been examined. keywords: symbiosis, sms, email, predictive. 1. introduction the new means of written communicationemail and sms, appearing at the end of the twentieth century, pressed the traditional postal service keeping it mainly as a means to send official documents. in place of the past epistolary genre with its inherent personality came concise information emails. nevertheless, the speed of delivery of messages to the addressee provides undeniable advantages to the electronic means of written communication. at the same time, integrated systems using "one package," technology of email and sms, which are complementary to each other are of particular interest. without going into a detailed assessment of the advantages and disadvantages of these systems, we have pointed out only the specific functional features of email and sms technologies. 2. problems and solutions originally designed for the exchange of written communications between computers, email is considered as a system “on demand” despite of its rapid delivery to the addressee. the fact of reading delivered message depends on the time the addressee opens his mailbox. in contrast to email, sms is not only a mailing system: the volume of transmitted message is limited, the 122 mailto:a_harutyunyan@ipia.sci.am mailto:sona@ipia.sci.am a. harutyunyan, s. gharagyozyan 123 delivery of the message is only possible in the zone of mobile network coverage or according to the current roaming agreement of mobile operator. the message delivery to the “pocket” of the mobile subscriber is an indisputable advantage of sms technology. accordingly, either the message is delivered “on demand” almost anywhere in the world (email), or directly into the hands of the addressee, but for the above mentioned limitations (sms). the integrated solution to the “distance” problem of particular sms service is solved by using ip-communications, as a main environment followed by the locking of current mobile network and web technologies providing the possibility sending sms to a specified, local mobile network from computers from virtually any region of the world. another above discussed problem: problem “on demand” is associated with the integration of sms technology in email system in the form of smsnotification systems on receipt of emails in the subscriber's mailbox. such postal sms-informants analyze the incoming correspondence of the subscriber separating the letters with return addresses listed by the subscriber to the "white list" to which the subscriber receives smsnotification, in case of receiving correspondence [1-3].. in other systems of email-informants, the initiative of sending notification is given to the sender. the problems to create a "hybrid" system of internet/sms is connected to the specifics of displaying web "pictures" on the display of a mobile phone and with the difficulties inputting alphabetic information. if a modern smartphone with an informant and virtual keyboard is being used while working with the system, no special problems will arise. however, the possibility of a user-friendly operation in a system with other common models of mobile phones leads to the need for a special service software. mobile subscribers use a wide variety of models of mobile phones: from budget phone with a small screen and a set of keys, providing only the basic functions of mobile communication: a telephone communication and exchange of sms to multifunctional smartphones with display of 5-6" touchscreen, virtual keyboard, multi-core processors and with the possibility to use internet. there often exists the possibility of connecting to the internet in common models of mobile phones with screens of about 2" and button dialing keyboard. however, the phenomenon of screen with small format and resolution, as well as of touch-tone, makes it extremely inconvenient use these phones working with network resources. however, not having a wide range of additional functions specific smartphones (often redundant), and they are today in demand (the share of push-button telephones in russian mobile networks, for example, is more than 30%. in the first quarter of 2015 there have been sold more than 2.7 million of these mobile phones [4,5]) corresponding to the basic purpose of mobile phones and having the indubitable advantage of the "pocket" device, due to the size and the weight (unlike the majority of smartphones, which are considered as "wearable" devices). these circumstances determine the feasibility of studies and the development of new solutions providing information on mobile devices of a similar class, the development of adaptive interactive "comfort" systems graphical interaction of mobile phone users with communication and information resources of mobile and ip networks (it is evident that this interaction is provided by gsm / ip servers). these dialogue systems should be extremely concise, limitative as far as possible, the participation of the user answers "yes-no" considering the complexity of a set of queries and text on a mobile phone keypad. problems of writing text messages are solved using predictive typing systems anticipating in the already typed letters of the options of the current and the next word (or phrases) while user is typing using the built-in phone dictionary. such systems for mobile phones (designed mainly for typing sms) have been known since 1999 with the development and encapsulation of the t9 system in mobile phone software and similar functions of itap and ezi systems [6,7,8]. being developed by tegic communications, t9 is used in mobile phones by most of the major manufacturers (nokia, symbiosis of email and sms 124 samsung, sony ericsson, etc.). t9 is considered as the most popular system of predictive typing. unlike т9, itap attempts to predict short phrases as well, analyzing not only typed letters of the current word, but also the previous text. basic dictionaries of these predictive typing systems include 35-60 thousands of words and expressions, and support most of the european and some asian languages. unlike the mentioned predictive systems when typing the text of sms there can be offered an algorithm of serial-word letter by letter for the possible continuation of the typing word, using funded words database individual for each user according to the most frequently used words by the user while typing sms: "verbal image" of the lexicon used by the user stored on the sms server. this database is formed by accumulated words containing in the previous sms sent by the user. depending on the frequency of the repetition of words corresponding “weight” is attributed to each word determined by the number of repetitions of the word accumulated in the sms. such predictive system is installed not in the phone but in a centralized server. the system can be used with any mobile telephone having access to the internet, respectively, without requiring additional resources (memory, cpu) for its functioning. the system generates prediction not by semantic analysis of words and sentences comparing them with the information from the database but by the coincidence of images: putting in comparison the literal consistent of the typing string to the "images" of the vocabulary fund used by the user while sending sms accumulated in the individual database. the analysis on the coincidence of characters ("images of words") allows to use prediction system without being tied to a particular language. the database with which the system operates is located on a server in the form of individual lists for each registered user containing a sequence of characters (letters) forming a word. databases are automatically replenished with words from sms sent by the user. the use of automatically generated personal database "images of the words" increases the probability of a correct prediction at the initial stages of typing allowing, at the same time, significantly to reduce the size of the lexicon of the dictionary. while typing, the first two letters of the typing word are taken as a reference (base) letters of the word; further the letters set is compared with the dictionary with the issuance tips with the options of word completion. when typing messages a user can use both latin alphabet and cyrillic alphabet. accordingly, while sending sms there is a need to convert in cyrillic in the similar-sounding words, written in latin letters (operation of transliteration) for reliable message playback at any gadget. in asnet computer network users can access a number of services of infocommunication applications sharing web and sms technologies (www. asnet.am/sms applications),developed in the years from 2007 to 2013 at the institute for informatics and automation problems of national academy of sciences of the republic of armenia(iiap nas ra) [9,10]. the majority of the above mentioned services used as a basis for the development of info-communication mss system of iiap for mobile phones, providing the possibility to comfortably work with smsoip and emails. such system provides: 1. formation and sending of sms via ip network using web technologies 2. formation and sending of email with sms notification (mobile network of the region where the server is running) containing user-selected fragment of the letter. 3. the use of graphical dialog interface, automatically adapting to the class of the gadget served at the moment. 4. when accessing the system by a phone with a small screen and keyboard, automatic switching to the dialogue version, minimizing data volume, user typing in the formation a. harutyunyan, s. gharagyozyan 125 of sms/email at the same time the formation of the address part of email, sms in single request in a natural language 5. the mechanism of "prediction" typed by the user during the formation of the message. 6. the use of the centralized individual savings with no database on the server system (user requisites, tel. book, address book, dictionary of sms: "verbal images”, etc.). references [1] [online]. available: https://help.mail.ru/mail-help/settings/notifications [2] [online]. available: http://iglous.ru/besplatnyj-sposob-poluchat-sms-uvedomleniya-opochte/ [3] d. gevorkyan, k. khachatryan, a. nanassian, a. petrosyan, g. petrosyan, v. sahakyan and e.vardanyan “mail informerselective incoming e-mail instant phone notification system”, proceedings of international conference computer science and information technologies, yerevan, pp. 466-468, 2009. [4] [online]. available: http://secretmag.ru/news/2015/06/24/knopochnie-telefoni/ [5] [online]. available: http://sia.ru/?action=show_news&id=305085§ion=484 [6] [online]. available: http://www.ixbt.com/mobile/review/prtxtsms.shtml [7] [online]. available: http://www.genon.ru/getanswer.aspx?qid=29112f32-777b-4d02b3ab-bbec2afb72ef [8] [online]. available: http://solo-project.com/articles/category/12/message/1241/ [9] d. gevorkyan, а. nanassian and k. khachatryan “new web resources asnet.am”, computer science and information technologies, proceedings of international conference, yerevan, pp. 311-313, 2011. [10] а. nanassian and k. khachatryan “mail2sms.asnet.am – the alert system of incoming”, proceedings of international conference computer science and information technologies, pp. 459-462, 2013. submitted 04.11.2015, accepted 22.02.2016 էլ-փոստի և sms հաղորդագրության համակցում (symbiosis) ա. հարությունյան և ս. ղարագյոզյան ամփոփում դիտարկվել են համակարգչում և բջջային ցանցում հաղորդագրությունների փոխանակման տարածված համակարգերը, ստեղծելով տվյալների փոխանակման նախադրյալներ, որոնք օգտագործում են ip և gsm ցանցերը։ symbiosis of email and sms 126 симбиоз email и sms а. арутюнян и с. карагезян аннотация рассмотрены особенности распространенных систем обмена письменными сообщениями в компьютерных и сотовых сетях, предпосылки создания гибридных систем передачи сообщений, использующих технологии ip и gsm сетей. рассмотрены проблемы доступа к ресурсам подобных систем с мобильных гаджетов, пути их решений. начиная с начала 2000 года осуществляется внедрение ghis в здравоохранении, в рамках принятого проекта о реформирование информ mathematical problems of computer science 46, 55--58, 2016. about some queueing models for computational grid systems vladimir g. sahakyan, yuri h. shoukourian and hrachya v. astsatryan institute for informatics and automation problems of nas ra e-mail: vladimir.sahakyan@sci.am, shouk@sci.am, hrach@sci.am abstract in this paper parametric models of the queues are proposed in grid systems. the models take into account the restrictions on the waiting and interval of execution time of the tasks. keywords: grid computing, queueing systems, resource allocation systems. the optimal usage of cpu times in multi-core computational grid infrastructures depends on several factors, such as the job scheduling, the possibility of dynamic allocation of computational resources, the possibility of job migration to the different phases of implementation in optimal requested environment, performing a stop of the job with the possibility of continuing, etc. the use of grid infrastructures to handle the information stream requires a flexible approach to the allocation of resources as well as for the timely performance of jobs. the job receiving process in the queue for further executing in a grid infrastructure plays an important role in the organization of the whole process. at this stage the incoming job service script is generated based on a maintenance data bursts. this requires synchronization of distributed processes to manage the resources of a grid system. a set of gram (grid resource allocation and management) services allows to manage the resources and jobs, job queues handling, ensuring their execution on the required computational resources. in addition to gram services, the schedulers play special roles. the adoption of the job queue for a service applies to the scheduler responsible for ensuring its timely implementation. nowadays the usage of modern schedulers, such as maui, condor, pbs (portable batch system) has opportunities to perform the planning tasks on specified priorities [1,2,3]. however, in complex cases (for instance, to run the job at a specified time and in specified resources, or to manage multi-stream queues) we need to implement a flexible approach for scheduling. 55 mailto:vladimir.sahakyan@sci.am mailto:shouk@sci.am mailto:hrach@sci.am about some queueing models for computational grid systems 56 the optimal run of the programs in multi-core environments involve selection of service discipline, delivering at least a "loss function", which characterizes the quality of the functioning of the process. as such a function can be considered some functional depending on the average waiting time, utilization of time, the number of denial of service and others. many authors have shown that the discipline of the relative priority is optimal for linear functional without service interruption. if prevent the implementation of programs interrupted, sometimes absolute priority disciplines are better. however, in systems with many devices maintenance procedure can be disrupted, while retaining the properties of known subjects. for example, in case of a fifo discipline, if a job is received after the service does not affect the incoming job before him, it may be served. this can be done using batchfill mechanism (check available periods for low-priority tasks). often it is required to provide manage the job not later or earlier, or in a specified period of time after entering the system. for a description of these conditions we consider the classification of the job queues on systems diagrams defining the service priorities. schemes depending on the order of receipt  mfifo (modified fifo) – received to the job system, it is queued in order of receipt and can serve, if it does not affect the start time of service to all previously received assignments;  mlifo (modified lifo) received to the job system, it is queued in order of receipt and can serve, if it does not affect the start of the service later he received jobs from the queue.  mrs (modified random service) received to the job system, it is queued and can cater for random selection depending on specific task parameters. schemes based on the level of required resources -ju (job up): received to the job system, it is queued in order of required resources for the service ([service time] * [number of required cores]) and can serve, if it does not affect the start of the maintenance of all available jobs in the queue ahead of its assignments. previously, all will go on maintenance task requires the most resources. -jd (job down): received to the job system, it is queued in order of increasing required for maintenance resources ([service time] * [number of required cores]) and can serve, if it does not affect the start of the maintenance of all available jobs in line behind its assignments. previously, all will go on maintenance task requires the least resources. schemes based on the number of processors required -pu (processor up): received to the job system, it is queued in order of processors required for service and can serve if it does not affect the start of the maintenance of all available jobs in the queue ahead of its assignments. previously, all will go on maintenance task requires the most resources. -pd (p down): received to the job system, it is queued in order of increasing required maintenance for the processor and can serve, if it does not affect the start of service available queued jobs behind it. previously, all will go on maintenance task requires the least resources. schemes, with a restriction on the waiting time -wtr (waiting time restriction): received to the job system, it is queued in order acceptable waiting time, i.e., the higher priority admission service has a job with less latency. -itr (interval time restriction): received to the job system, it is queued and must start the handling after a specified time, but no later than the specified timeout. the first goes on a mission handling shall start the service before anyone else. all queuing schemes permitted job handling from the queue, if its handling does not affect the maintenance of higher-priority jobs. v. sahakyan, yu. shoukourian and h. astsatryan 57 schemes are mutually exclusive and only one of the circuits can be selected and when queuing. however, restrictions on the waiting time can be in all schemes. in systems allowing job migrations, these schemes can be described as a service processes without interruption (relative priority) and with interruption (absolute priority). the job interruption may take place in case of entering higher priority jobs. we assume that the job under the new entry to the service will be continued (not started first). setting with interrupted service it is returned to the queue with the adjusted design parameters (service time, waiting time, etc.). for a more detailed formulation let’s consider a computational consisting of m (m ≥ 1) processors. when using systems based on virtual clusters, limiting the number of processors is arbitrary and depends on the performance of the basic configuration. we assume that the number of jobs that can be in the queue is not limited. the grounds of refusal of service can only serve as the impossibility of his service with the user-defined constraints (time, number of processors, etc.). let job stream be supplied. each job can be characterized by parameters (ν, β, ω, γ), where ν the number of processors required for the job, β the time required to run, ω permissible total residence time job in the queue, γ the time from the admission to the system after it is allowed to start the service. fig. 1. the example of task an acceptable execution. if γ = 0, the value of this parameter can be omitted. in systems with no limit on the waiting time the value of the parameter ω is also lowered. for jobs with a restriction on the waiting time for admission to the system is checked on the ability to perform a task and then either taken in turn to perform, or is refused by the implementation. the time required for maintenance is in some sense arbitrary, which means maximum allowable. in reality, it is random and may be less than the predetermined one. therefore, the order may vary both in case of receiving the jobs and finishing the maintenance of jobs. service denial gets jobs, if at the time of admission to the system it finds that it cannot serve the specified parameters. for example, to start services at a specified time. the system is considered at discrete points in time, the job proceeds to the queue or completion of service. we call these moments 0-momentums. in each 0-momentum it carries out queue recalculation and a new order of the queue in the computational system. for various schemes a multithreading queuing model is proposed. between the streams are set priorities, and inside threads can be used as one of the described schemes of service. about some queueing models for computational grid systems 58 for the above mentioned schemes, new algorithms have been developed to schedule jobs with mixed priorities. note that the algorithms can be used both in homogeneous and in lines with mixed schemas with a restriction on waiting time. references [1] i. foster, computational grid, morgan-kufman, 1999. [2] i. foster, c. kesseman and s. tuecke, “the anatomy of the grid”, international journal of hpc applications, vol. 15, no. 3, pp. 25-37, 2001. [3] f. xhafa, “batch mode scheduling in grid systems”, int.j. web and grid services, vol.3, no. 1, pp.19-37, 2007. submitted 04.07.2016, accepted 20.10.2016. հերթերի որոշ մոդելների մասին հաշվողական գրիդ– համակարգերում վ.սահակյան, յու.շուքուրյան և հ. ասցատրյան ամփոփում հոդվածում առաջարկվում է հաշվողական գրիդ–համակարգի համար հերթի պարամետրիկ մոդելը։ մոդելը հաշվի է առնում առաջադրանքի հերթում սպասման և կատարման թույլատրելի ժամանակները։ о некоторых моделях очередей в вычислительных гридсистемах в. саакян, ю. шукурян и г. асцатрян аннотация в статье предложена параметрическая модель очереди для вычислительной гридсистемы. модель учитывает ограничения на допустимые времена ожиданий и промежутков выполнения заданий. начиная с начала 2000 года осуществляется внедрение ghis в здравоохранении, в рамках принятого проекта о реформирование информ mathematical problems of computer science 43, 57--61, 2015. encoding and decoding procedures for double ±1 error correcting linear code over ring 𝑍𝑍5 hamlet k. khachatryan institute for informatics and automation problems of nas ra e-mail: hamletxachatryan.08@gmail.com abstract from practical point of view the codes over 𝑍𝑍2𝑚𝑚 or 𝑍𝑍2𝑚𝑚+1 are interesting, because they can be used in 22𝑚𝑚 –qam (quadrature amplitude modulation) schemes. in this paper a construction of encoding and decoding procedures for double ±1 error correcting optimal(12,8) linear code over ring 𝑍𝑍5 is presented. keywords: error correcting codes, codes over the ring 𝑍𝑍5, encoding and decoding procedures. 1. introduction codes over finite rings, particularly over integer residue rings and their applications in coding theory have been studied for a long time. errors happening in the channel are basically asymmetrical; they also have a limited magnitude and this effect is particularly applicable to flash memories.there are many constructed codes capable to correct up to two errors of value ±1 .the earliest paper discussing the codes over the ring 𝑍𝑍𝐴𝐴 of integers modulo 𝐴𝐴 are due to blake [1], [2]. the optimality criteria for the linear code over fixed ring 𝑍𝑍𝑚𝑚 was considered in 2 ways in [3]. first of all, recall that the code of the length n is optimal-1 if it has a minimum possible number of parity check symbols. secondly, optimality-2 criteria for the code is that for a given number of parity check symbols it has a maximum possible length. here, we propose to construct encoding and decoding algorithms for the optimal codes. the code presented in this paper satisfies the optimality criteria-1([3]). at this point we do not know any codes that satisfy the optimality criteria-2. there have been encoding and decoding procedures for the (4, 2) code over ring 𝑍𝑍9 in [4]. implementation of codes over large alphabets is much more difficult compared with small alphabets. in this paper a construction of encoding and decoding procedures of (12, 8) linear code over ring 𝑍𝑍5 correcting double ±1 errors is presented. 57 encoding and decoding procedures for double ±1 error correcting linear code over ring 𝒁𝒁𝟓𝟓 58 2. presentation of the code let a linear (12, 4) code over ring z5 be given by the following parity check matrix 𝐻𝐻: 𝐻𝐻 = � 1 1 1 1 1 0 1 2 3 4 1 1 0 1 2 3 4 2 2 2 2 2 1 1 3 2 4 4 2 3 2 4 4 2 1 1 1 1 1 1 1 3 2 4 4 2 0 4 �. a linear code over z5 given by the parity check matrix 𝐻𝐻 can correct up to two errors of the type ±1, because 𝐻𝐻 has a property according to which all the syndromes resulting from adding and subtracting operations between any two columns of the matrix 𝐻𝐻 are different (±hi± hj and hi≠hj)(proof of this you can see in [3]). in this case the number of combinations for each code word that can be corrected is (1 + 12 ∗ 2 + (12 𝑐𝑐ℎ𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 2) ∗ 4) = 289. for encoding every vector in 𝑍𝑍5 we should have the generator matrix 𝐺𝐺. for this we should construct a combinatorial equivalent matrix 𝐻𝐻′ from matrix 𝐻𝐻. 𝐻𝐻′ = � 1 0 0 0 3 1 0 3 4 3 4 0 0 1 0 0 2 2 4 4 0 2 4 3 0 0 1 0 0 0 2 4 2 1 3 1 0 0 0 1 1 3 2 0 4 4 3 3 �. in this matrix all 289 possible syndromes will be different, too. from [5] we know, that 𝐺𝐺𝐻𝐻′𝑇𝑇 = 0. (1) if h′ = [−pt|in−k], then g = [ik|p] (the reverse statement is also true), where ik is a 𝑘𝑘 ∗ 𝑘𝑘 identity matrix and p is a 𝑘𝑘 ∗ (𝑛𝑛 − 𝑘𝑘) matrix[5]. thus, we can construct the generator matrix 𝐺𝐺: 𝐺𝐺 = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 2 3 0 4 1 0 0 0 0 0 0 0 4 3 0 2 0 1 0 0 0 0 0 0 0 1 3 3 0 0 1 0 0 0 0 0 2 1 1 0 0 0 0 1 0 0 0 0 1 0 3 1 0 0 0 0 1 0 0 0 2 3 4 1 0 0 0 0 0 1 0 0 1 1 2 2 0 0 0 0 0 0 1 0 0 2 4 2 0 0 0 0 0 0 0 1⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎤ . h. khachatryan 59 3. encoding and decoding procedures 3.1 encoding procedure in our scheme the message was presented by 8-tuples in z5. let 𝐺𝐺 be a generator matrix for (12,8) linear code. 𝑣𝑣 = (𝑎𝑎1, 𝑎𝑎2, 𝑎𝑎3, … , 𝑎𝑎8) is an arbitrary 8-tuple, and consider the vector 𝑢𝑢 that is the linear combination of columns 𝐺𝐺 with 𝑎𝑎𝑖𝑖 is the 𝑖𝑖𝑡𝑡ℎ coefficient. 𝑢𝑢 = 𝑣𝑣𝐺𝐺 = (𝑐𝑐1, 𝑐𝑐2, 𝑐𝑐3, 𝑐𝑐4, 𝑎𝑎1, 𝑎𝑎2, 𝑎𝑎3, … , 𝑎𝑎8), where the first 4 components of the code vector are the check symbols, the next 8 components are information symbols and 𝑐𝑐𝑗𝑗 = �∑ 𝑎𝑎𝑖𝑖𝑝𝑝𝑖𝑖𝑗𝑗 𝑘𝑘 𝑖𝑖=1 �𝑚𝑚𝑜𝑜𝑚𝑚5. (2) example. let (3 4 0 0 2 1 1 4) be the message vector in 𝑍𝑍5. from (2) we can obtain check symbols. for example, the first check symbol is c1: 𝑐𝑐1 = (3 ∗ 2) + (4 ∗ 4) + (0 ∗ 0) + (0 ∗ 2) + (2 ∗ 1) + (1 ∗ 2) + (1 ∗ 1) + (4 ∗ 0) = = 6 + 16 + 0 + 0 + 2 + 2 + 1 + 0 = 27𝑚𝑚𝑜𝑜𝑚𝑚5 = 2 . similarly, we can find other 3 check symbols: 𝑐𝑐2 = 3, 𝑐𝑐3 = 3, 𝑐𝑐4 = 3. after performing other multiple operations with matrix 𝐺𝐺 we obtain this encoded vector: (2 3 3 3 3 4 0 0 2 1 1 4). 3.2 decoding procedure in this section we describe the decoding procedure: 1. receiver multiplies the vector with every column of matrix h′ and gets the syndrome s = vh′. if s = (0,0,0,0) then there were not any errors in the received vector. 2. if the calculated syndrome s is a nonzero vector, then there are some errors. this (12,8) code can correct only up to two errors with magnitude ±1. we know that all possible syndromes of matrix h′ are different (±hi, ±hj and hi ≠ hj) (the number of them is 288 and syndrome (0,0,0,0)). after calculating the syndrome the receiver knows from which two columns of the matrix h′ the syndrome was resulted, consequently, he can find the two corresponding components of the vector, where the error was occurred and the direction of the error (if +hi, then upward direction or if −hi downward direction). on the other hand, if in the table of syndromes we do not have the resulted syndrome, then we cannot correct this kind of errors. 3. after finding the error components the receiver adds or subtracts 1 from them (he adds if downward, else subtracts) and obtains the sent code vector (𝒄𝒄𝟏𝟏, 𝒄𝒄𝟐𝟐, 𝒄𝒄𝟑𝟑, 𝒄𝒄𝟒𝟒, 𝒂𝒂𝟏𝟏, 𝒂𝒂𝟐𝟐, 𝒂𝒂𝟑𝟑, … , 𝒂𝒂𝟖𝟖). so (𝒂𝒂𝟏𝟏, 𝒂𝒂𝟐𝟐, 𝒂𝒂𝟑𝟑, … , 𝒂𝒂𝟖𝟖) is our message vector. encoding and decoding procedures for double ±1 error correcting linear code over ring 𝒁𝒁𝟓𝟓 60 example. (2 3 3 3 3 4 0 0 2 1 1 4) is an encoded vector from the previous example. let there occur 2 errors in the channel, and the receiver get the vector (2 3 3 3 3 4 0 4 2 2 1 4). after performing multiple operations with rows of matrix 𝐻𝐻′ 𝑡𝑡ℎ𝑜𝑜 receiver obtains the syndrome (0 3 2 4). next from the table of syndromes he finds the corresponding columns, now they are -8 and 10. hence, the syndrome (0 3 2 4) was resulted from adding a negated column 8 of matrix 𝐻𝐻 to column −3 +3 −4 +2 −4 +1 0 +4 = 0 −2 −3 4 (𝑚𝑚𝑜𝑜𝑚𝑚5) = (0 3 2 4), (because in 𝑍𝑍5, 0 = 5, −1 = 4, −2 = 3 , −3 = 2, −4 = 1). hence, the error positions of encoded vector are 8 and 10 (in 8𝑡𝑡ℎ downward direction and in 10𝑡𝑡ℎ upward). so, he adds 1 to 8𝑡𝑡ℎ component and subtracts 1 from 10𝑡𝑡ℎ of vector (2 3 3 3 3 4 0 4 2 2 1 4) and obtains the sent encoded vector (2 3 3 3 3 4 0 0 2 1 1 4). consequently, the message vector 𝑖𝑖𝑜𝑜 (3 4 0 0 2 1 1 4). 4. conclusion in this paper a construction of encoding and decoding procedures of optimal-1 (12,8) linear code over ring 𝑍𝑍5 correcting double ±1 errors is presented. we propose that this approach can be extended for constructing similar procedures for the optimal codes over other rings 𝑍𝑍𝑛𝑛 and the research in this direction will follow. references [1] i. blake, “codes over certain rings”, information and control, vol. 20, pp. 396-404, 1972. [2] i. blake, “codes over integer residue rings”, information and control, vol. 29, 1975, 295-300. [3] g. khachatrian and h. morita, “construction of optimal 1 double error correcting linear codes over ring z5 ”, 3th international workshop on advances in communications, boppard, germany, pp. 10-12, may 2014. [4] h. kostadinov, n. manev and h. morita, “double ±1-error correctable codes and their applications to modulation schemes”, proc. elev. intern. workshop acct, pamporovo,june 16-22, pp 155-160,2008. [5] w. w. peterson and e.j. weldon, error-correcting codes, m.i.t. press, cambridge, mass.,1972. submitted 15.10.2014, accepted 12. 02. 2015. h. khachatryan 61 կոդավորման և ապակոդավորման ալգորիթմը z5 օղակում ±1 մեծությամբ կրկնակի սխալ ուղղող կոդերի համար հ. խաչատրյան ամփոփում պրակտիկ տեսանկյունից մեծ հետաքրքրություն են առաջացնում 𝒁𝒁𝟐𝟐𝟐𝟐 կամ 𝒁𝒁𝟐𝟐𝟐𝟐+𝟏𝟏 օղակների վրա դիտարկված կոդերը, քանի որ նրանք ունեն լայն կիրառություն 𝟐𝟐𝟐𝟐𝟐𝟐 –qam մոդուլյացիոն սխեմաներում: այս հոդվածի շրջանակներում ներկայացված է կոդավորման և ապակոդավորման ալգորիթմը z5 օղակում ±1 մեծության մինչև 2 սխալ ուղղող օպտիմալ (12, 8) գծային կոդի համար: алгоритм кодирования и декодирования в кольце z5 для кодов исправляющих двойные ошибки размера ±1 г. хачатрян аннотация с практической точки зрения большой интерес вызывают коды на кольцах 𝑍𝑍2𝑚𝑚 и 𝑍𝑍2𝑚𝑚+1, так как они имеют широкое применение в 22𝑚𝑚 –к а м модуляционных схемах. в данной статье представлен алгоритм кодирования и декодирования в кольце z5 для оптимального (12,8) линейного кода, исправляющего до двух ошибок размера ±1. encoding and decoding procedures for double ±1 error correcting linear code over ring ,𝑍-5. hamlet k. khachatryan from practical point of view the codes over ,𝑍-2𝑚. or ,𝑍-2𝑚+1. are interesting, because they can be used in ,2-2𝑚. –qam (quadrature amplitude modulation) schemes. in this paper a construction of encoding and decoding procedures for double ±1 erro... 1. introduction 2. presentation of the code начиная с начала 2000 года осуществляется внедрение ghis в здравоохранении, в рамках принятого проекта о реформирование информ mathematical problems of computer science 47, 62--67, 2017. design and implementation of "handipum" webrtcbased conferencing service in asnet-am network arthur s. petrosyan, gurgen s. petrosyan and robert n. tadevosyan institute for informatics and automation problems of nas ra e-mail: arthur@sci.am, gurgen@sci.am, robert@sci.am abstract this paper presents the results of research and deployment experience with design and implementation of the asnet-am webrtc-based audio/video conferencing service, called "handipum" (handipum.asnet.am). since the webrtcservices become widely used, this service can provide a modern browser-based conferencing environment for asnet-am users. keywords: real-time communications, rtc, webrtc, selective forwarding unit, sfu, conferencing, multimedia, middleware 1. introduction webrtc is a modern open source technology that enables web browsers with real-time communications (rtc) capabilities via javascript apis. it has been initially developed as a peer-to-peer technology, where clients (web browsers) can directly communicate without any intermediate infrastructure. this model is enough for creating basic applications but features such as group communications, media stream recording, media broadcasting or media transcoding are difficult to implement on top of it. for this reason, many applications require using some kind of intermediate media server. conceptually, the webrtc media server is just a kind of “multimedia middleware” (it is in the middle of the communicating peers) where media traffic passes through when moving from source to destinations. media servers are capable of processing media streams and offering different types including group communications (distributing the media stream that one peer generates among several receivers), mixing (transforming several incoming streams into one single composite stream), transcoding (adapting codecs and formats between incompatible clients), recording (storing in a persistent way the media exchanged among peers), etc. 62 mailto:arthur@sci.am mailto:gurgen@sci.am mailto:robert@sci.am a. petrosyan, g. petrosyan and r. tadevosyan 63 2. architecture models there are in general 3 main architecture models of deploying a multiparty webrtc-based video conferences: mesh, multipoint conferencing unit (mcu) & selective forwarding unit (sfu). in mesh multipoint architecture every participant sends and receives his media to all other participants. this variant is a very common technique used in webrtc to build multipoint conferences. advantages of mesh architecture are that it’s simple to implement in webrtc and requires very little backend infrastructure, keeping the resulting service cheap to operate. but it requires a lot of uplink bandwidth from each participant and thus can’t scale to a large number of participants. an mcu offers the ability to connect multiple participants in a single voice or video session. in mcu participants “speak” to a central entity, which mixes all inputs and sends out a single stream towards each participant. mcus generally implement a mixing architecture and are expensive due to their need for a lot of processing power per session. an sfu is capable of receiving multiple media streams and then decide which of these media streams should be sent to which participants. in sfu the participant sends his media to a central entity, which routes all incoming media as it sees fit to participants each of them receiving usually more than a single stream. so sfu can be treated as a lightweight webrtc implementation, allowing for multiuser video communication by simply relaying the received multimedia flows to all call participants, without mixing into a composite stream. one of the effective open-source sfu solutions is jitsi videobridge. together with other components from jitsi project [1] it proved to be an interesting solution that was used as a basis for creating a webrtc-based audio/video conferencing service in asnet-am network, called "handipum" [2]. 3. "handipum" conferencing service infrastructure there are lots of websites offering online video conferencing solutions on the internet today. many have a user friendly interface and very good video and audio quality. some even are free for use after registration. however, the downside of such solutions is that the data moves through a foreign server. plus no armenian interface is available anywhere in conferencing solutions. thus, it was decided to design and implement an own conferencing solution for asnetam users, based on freely available solutions. after some comparative research, one of such solutions was found to be the jitsi project, which provides an open source, encrypted, and sustainable interface. it works via web front end application called jitsi meet [3], thus making it possible to use any webrtc-compatible web browser as a client. such a modern flexible browser-based solution eliminates the need for a specific client and at the same time provides rich conferencing capabilities. two main components of "handipum" conferencing service are – jitsi videobridge and jitsi meet. they work together to transfer video and audio between the users. videobridge acts as a web real-time communication webrtc-compatible sfu and allows for multiuser communication. jitsi meet is a front end to videobridge and is implemented in javascript. jitsi meet can be configured to be hosted on some http server and in our case the nginx web server [4] was used for that. in addition some implementation of xmpp server is required on the server side. the prosody [5] lightweight, open source jabber/xmpp server is the basic solution used as an xmpp server. design and implementation of "handipum" webrtc-based conferencing service in asnet-am 64 4. "handipum" conferencing service interface "handipum" conferencing service currently offers video and audio conferences in web browsers with real-time text chat, youtube video sharing. other additional services that are under development include: presentation sharing, screen sharing, shared document editing, voip integration. we have done the localization of jitsi meet web interface and "handipum" conferencing service is now available in armenian. we have also provided the armenian translation to the public [6]. so jitsi meet is now translated into 16 languages, among which armenian is proudly presented, thanks to the asnet-am team efforts. users can take part in meetings with webrtc-enabled browsers. the current versions of opera, google chrome, and mozilla firefox already support standard; additional functions such as desktop sharing require browser add-ons. microsoft's internet explorer/edge and apple's safari browsers do not have proper webrtc support yet. all conferencing communication is secure enough thanks to the https encrypted connections. strong ssl certificate with 4096-bit keys sha-256 signature is used in "handipum" conferencing service. additionally each conference room created, can be locked by a password, to ensure limited access. 5. conference room creation users can open a new room in "handipum" conferencing service by opening its start page https://handipum.asnet.am (figure 1) and typing a unique name for conference room. the room name should not contain spaces and should consist of only latin letters and numbers. fig. 1. "handipum" conferencing service start page after clicking the “go” button the system creates a unique room interface as shown on figure 2. https://handipum.asnet.am/ a. petrosyan, g. petrosyan and r. tadevosyan 65 fig. 2. "handipum" conferencing service room interface while entering the conference room, participants should confirm that they allow the "handipum" conferencing service to access their camera and microphone. the initiator of the conference (the user, who initially created a new non-existing room) automatically receives moderator rights, can then protect the room with a password and mute or remove participants. currently it is not possible to provide moderator rights to any other participant. all current room participants are displayed in separate mini-windows at the bottom, and the moderator is marked with an asterisk. 6. sip integration "handipum" service is configured to make instant calls from a conference room to some sip number within asnet-am internal ip telephony service. sip integration is implemented with jigasi (jitsi gateway to sip) [7]. jigasi is a server-side application that allows regular sip clients to join the "handipum" conference. integration is made by setting a specific asnet-am sip server account in the jigasi configuration. a small phone icon appears in conference rooms in the web interface. any participant can call someone at a sip number and add him to current room conversation. clicking on phone icon opens a box in which the inviting participant needs to enter the sip number to call (figure 3). if the individual being called picks up, he/she can take part in the audio conversation within that room. by this, users with sip phones can take part in "handipum" conferences. fig. 3. inviting participant needs to enter the sip number to call design and implementation of "handipum" webrtc-based conferencing service in asnet-am 66 7. conclusion conferencing solution presented above is a modern webrtc-based browser-driven system. it is very efficient and scalable. it is able to run thousands of simultaneous video streams at small bandwidth and cpu usage [8]. before "handipum" many of our users scientists, scientific and technical associates, postgraduates and students used other tools such as microsoft skype or google hangouts for conferencing. since the "handipum" conferencing service is now open to our community and since it works directly from web browser and does not require any specific client installation, we hope it to become a viable alternative that perfectly matches our users’ needs. asnet-am members were informed about the "handipum" conferencing service available, by publishing the appropriate news at asnet-am website. references [1] jitsi project, [online]. available: http://jitsi.org [2] "handipum" asnet-am conferencing service, [online]. available: https://handipum.asnet.am [3] jitsi meet, [online]. available: https://jitsi.org/projects/jitsimeet [4] nginx http server, [online]. available: https://nginx.org/ [5] prosody xmpp communication server, [online]. available: https://prosody.im/ [6] jitsi meet armenian interface, [online]. available: http://translate.jitsi.org/hy/jitsi-meet/ [7] jigasi, [online]. available: https://github.com/jitsi/jigasi [8] jitsi videobridge performance evaluation, [online]. available: https://jitsi.org/projects/jitsivideobridgeperformance submitted 08.10.2016, accepted 22.02.2017. webrtc միջավայրում "handipum" վեբ կոնֆերանս համակարգի նախագծում և իրականացում asnet-am ցանցում ա. պետրոսյան, գ. պետրոսյան և ռ․ թադևոսյան ամփոփում հոդվածում նկարագրված է նոր սերնդի վեբ կոնֆերանս համակարգի նախագծումն ու իրականացումը asnet-am ցանցում, որն իրականացված է webrtc միջավայրում։ webrtc համակարգերը լայն տարածում են ստացել այն պատճառով, որ օգտագործողի համակարգչի վրա չեն պահանջում հատուկ ծրագրերի տեղադրում և http://jitsi.org/ https://handipum.asnet.am/ https://jitsi.org/projects/jitsimeet https://nginx.org/ https://prosody.im/ http://translate.jitsi.org/hy/jitsi-meet/ https://github.com/jitsi/jigasi a. petrosyan, g. petrosyan and r. tadevosyan 67 աշխատում են անմիջապես վեբ բրաուզերներում։ asnet-am ցանցում ներկայումս գործող այդպիսի համակարգը, որի մասին խոսվում է հոդվածում, հիմնված է jitsi բաց կոդով ծրագրային փաթեթի վրա։ նկարագրված են համակարգի հիմնական հնարավորությունները։ վեբ կոնֆերանս համակարգը անվանվել է "handipum" և հասանելի է https://handipum.asnet.am հասցեով։ մինչև "handipum" համակարգի ներդրումը, մեր օգտագործողներից շատերը, որոնց թվում են՝ գիտնականները, գիտական և տեխնիկական աշխատողները, ասպիրանտները, ուսանողները և այլ մասնագետները, օգտվում էին տարբեր այլ արտաքին կոնֆերանս համակարգերից։ այժմ, երբ "handipum" համակարգը հասանելի է ողջ հայկական գիտակրթական հանրության համար և աշխատում է անմիջապես բրաուզերից, հույս ունենք, որ այն արժանի տեղական այլընտրանք կլինի մեր օգտագործողների համար։ разработка и реализация сервиса конференций "handipum" на основе протоколов webrtc в сети asnet-am а. петросян, г. петросян и р․ тадевосян аннотация в статье описана разработка и реализация нового поколения сервиса веб конференций в сети asnet-am на основе протоколов webrtc․ реализация сервисов веб конференций в среде webrtc в настоящее время пользуется большой популярностью по причине отсутствия необходимости установки специального клиентского приложения, в качестве которого выступает обычный веб браузер. действующая в настоящее время в сети asnet-am услуга веб конференций на основе протоколов webrtc базируется на активно развивающемся проекте с открытым кодом jitsi․ описаны основные возможности сервиса․ сервис назван "handipum" и функционирует по адресу https://handipum.asnet.am․ до внедрения сервиса "handipum", многие из наших пользователей ученые, аспиранты и студенты, пользовались прочими внешними возможностями для конференций․ поскольку сервис "handipum" в настоящее время открыт для армянской научно-образовательной среды и работает прямо из браузера, мы надеемся, что он станет достойной альтернативой для наших пользователей․ https://handipum.asnet.am/ начиная с начала 2000 года осуществляется внедрение ghis в здравоохранении, в рамках принятого проекта о реформирование информ mathematical problems of computer science 45, 35--43, 2016. analysis of experiments of a new approach for test quality evaluation mariam e. haroutunian, varazdat k. avetisyan institute for informatics and automation problems of nas ra e-mail: armar@ipia.sci.am, avetvarazdat@gmail.com abstract in the previous paper [1] we suggested a new model of test quality evaluation based on information measures such as shannon entropy and average mutual information. to establish the practical bounds of these measures and the required number of examinees, some experiments were conducted. in this paper the analysis of these experiments are provided. keywords: test quality, shannon entropy, average mutual information, classical test theory, item response theory. 1. introduction test developers are basically concerned about the quality of test items and how examinees respond to it when constructing tests. test theories and related models provide a frame of reference for doing test design work or solving other practical problems. a good test model might specify the precise relationships among test items and ability scores, so that careful design work can be done to produce desired test score distribution and errors of the size that can be allowed. a good test theory or model can also handle errors of measurements by helping understand the role that measurement errors play in estimating examinee’s ability and correlations between variables and true scores or ability scores. there are two currently popular statistical frameworks to address test data analysis and test quality evaluation: classical test theory (ctt) [2] and item response theory (irt) [3]. ctt is a theory about test scores that introduces three concepts test score, true score and error score. in the ctt, the notion of ability is expressed by the true score, which is defined as "the expected value of observed performance on the test of interest." an examinee's ability is defined only in terms of a particular test. when the test is "hard," the examinee will appear to have low ability; when the test is "easy," the examinee will appear to have higher ability. ctt was the dominant statistical approach for 35 mailto:armar@ipia.sci.am mailto:avetvarazdat@gmail.com analysis of the experiments of a new approach for test quality evaluation 36 testing data until lord and novick (1968) placed it in the context with several other statistical theories of mental test scores, notably irt. irt is a model-based measurement statistical theory in which the performance of an examinee on a test item can be predicted (or explained) by a set of factors called traits, latent traits, or abilities; and the relationship between the examinees' item performance and the set of traits underlying item performance can be described by a monotonically increasing function called an item characteristic function or item characteristic curve (icc). each of these approaches has its advantages and disadvantages [4]. for example, in ctt item parameters are dependent on the examinee sample from which they are obtained, but in irt these parameters are examinee group independent. but on the other hand, in case of ctt smaller examinee sample sizes are required for analysis and the methods are simpler compared to irt. besides the existing ctt and irt models, we have developed a new approach [1] based on information measures such as shannon entropy and average mutual information. the main idea of the new approach is the following. suppose that the test consists of n items, each item can be considered as a binary random variable (rv) x1, x2, .., xn with probabilities p for correct answers and 1 − p, for incorrect answers: 𝑋𝑋𝑖𝑖 = � 1 𝑤𝑤𝑤𝑤𝑤𝑤ℎ 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑤𝑤𝑤𝑤𝑝𝑝 𝑝𝑝𝑖𝑖, 0 𝑤𝑤𝑤𝑤𝑤𝑤ℎ 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑤𝑤𝑤𝑤𝑝𝑝 1 − 𝑝𝑝𝑖𝑖, 𝑤𝑤 = 1, 𝑁𝑁.������ we consider shannon entropy of rv 𝑋𝑋𝑖𝑖 𝐻𝐻(𝑋𝑋𝑖𝑖) = −�𝑝𝑝(𝑥𝑥𝑖𝑖 ) log 𝑝𝑝(𝑥𝑥𝑖𝑖 𝑥𝑥𝑖𝑖 ) and the average mutual information of two items: 𝐼𝐼�𝑋𝑋𝑖𝑖 ∧ 𝑋𝑋𝑗𝑗 � = � 𝑝𝑝(𝑥𝑥𝑖𝑖 , 𝑥𝑥𝑗𝑗 ) log 𝑝𝑝(𝑥𝑥𝑖𝑖, 𝑥𝑥𝑗𝑗 ) 𝑝𝑝(𝑥𝑥𝑖𝑖) ∗ 𝑝𝑝(𝑥𝑥𝑗𝑗 )𝑥𝑥𝑖𝑖,𝑥𝑥𝑗𝑗 = 𝐻𝐻(𝑋𝑋𝑖𝑖) − 𝐻𝐻�𝑋𝑋𝑖𝑖 | 𝑋𝑋𝑗𝑗� = 𝐻𝐻�𝑋𝑋𝑗𝑗� − 𝐻𝐻�𝑋𝑋𝑗𝑗 | 𝑋𝑋𝑖𝑖�. our test quality evaluation model consists of the following methods: method 1. if the value of 𝐻𝐻(𝑋𝑋𝑖𝑖) is close to 0, it means that we have a bad test item, which can be very easy or very difficult. if the value of 𝐻𝐻(𝑋𝑋𝑖𝑖) is close to 1 we have a good test item. method 2. if the value of 𝐼𝐼�𝑋𝑋𝑖𝑖 ∧ 𝑋𝑋𝑗𝑗 � is close to 0, it means that there is independency of test items xi and xj . in case of values close to min�𝐻𝐻(𝑋𝑋𝑖𝑖), 𝐻𝐻�𝑋𝑋𝑗𝑗�� xi and xj items repeat each other. method 3. if t h e value of conditional entropy �𝐻𝐻�𝑋𝑋𝑗𝑗 | 𝑋𝑋𝑖𝑖�� is close to 𝐻𝐻(𝑋𝑋𝑖𝑖 ), then xi and xj are independent. however, several questions remain open. 1. how precisely our model evaluates the quality of test items and how comparable is it to ctt and irt estimation methods? 2. which are the permissible limits of 𝐻𝐻(𝑋𝑋𝑖𝑖) and 𝐼𝐼�𝑋𝑋𝑖𝑖 ∧ 𝑋𝑋𝑗𝑗 � ? m. haroutunian, v. avetisyan 37 3. which is the sufficient number of the examinee samples for precise evaluation? the answers to these questions can be found experimentally. 2. description of experiments the results of school final exams of armenian language and literature held in 2008 were selected for testing. the results were provided in encrypted form by the center for assessment and testing. four test-results are chosen to be analyzed. each test consists of 80 items, and the number of schoolchildren who participated in the examination process is 2000. the names of the first 50 𝑋𝑋𝑖𝑖 items are 𝐴𝐴1, 𝐴𝐴2, … 𝐴𝐴50 and the names of the last 30 𝑋𝑋𝑖𝑖 items are 𝐵𝐵1, 𝐵𝐵2, … 𝐵𝐵30. for analysis test quality evaluation system developed by us was used in [5]. for each item of four tests the 𝐻𝐻(𝑋𝑋𝑤𝑤), ctt difficulty index [2] and irt b parameter [3] values have been calculated, the comparability of the mentioned parameters observed and the permissible limits of 𝐻𝐻(𝑋𝑋𝑖𝑖)defined. difficulty is defined in both ctt and irt. in ctt the difficulty index p is the proportion of examinees who answer the item correctly. for multiple-choice, true/false, and other items that are scored as right (1 point) or wrong (0 points), item difficulty is the proportion of examinees who answered the item correctly. it ranges from 0 to 1. item difficulty for a polytomous item (an item scored in more than two ordinal categories) is simply the item mean or average item score. it ranges between the minimum and the maximum possible item scores. in irt the difficulty index b (irt b parameter) is on the same metric as the proficiencies or traits. this metric is arbitrary, but often it is anchored so that the proficiency distribution in a designated group has a mean of 0 and standard deviation of 1. the item difficulty identifies the proficiency at which about 50% of the examinees are expected to answer the item correctly. to observe the dependency of 𝐻𝐻(𝑋𝑋𝑖𝑖) and 𝐼𝐼�𝑋𝑋𝑖𝑖 ∧ 𝑋𝑋𝑗𝑗� values on the examinee sample size and define the enough number of examinee samples five experiments are carried out for each test. the analysis was conducted by choosing the same test at random based on 500, 300, 200, 100, 50 participants’ results. for each test 𝐼𝐼�𝑋𝑋𝑖𝑖 ∧ 𝑋𝑋𝑗𝑗� and ctt correlation coefficient 𝑅𝑅�𝑋𝑋𝑖𝑖 , 𝑋𝑋𝑗𝑗� between 𝑋𝑋𝑖𝑖 and 𝑋𝑋𝑗𝑗 items [2] was calculated, their compatibility was observed and the permissible limits of 𝐼𝐼�𝑋𝑋𝑖𝑖 ∧ 𝑋𝑋𝑗𝑗� were defined. correlation coefficient ranges from -1 +1. coefficient value should be small or equal to 0.3. if coefficient value is close to +1, it means that test items repeat each other and one of that items should be removed from the test. the negative correlation means there is an independency of test items. 3. the analysis of results. based on the first experiment results comparison of 𝐻𝐻(𝑋𝑋𝑖𝑖), ctt difficulty index p and irt b parameter values of test1 are shown in figure 1. according to ctt test items for which difficulty values are between 0.3 and 0.74 interval are good items (not easy and not very difficult 34 items), and based on the analyzed data we can see that 𝐻𝐻(𝑋𝑋𝑖𝑖) values of test 1 for these items are between 0.82 and 1.0. for easy test items, difficulty values are between 0.75 and 0.9 (29 items), 𝐻𝐻(𝑋𝑋𝑖𝑖) values are between 0.48 and 0.81. for very easy test items difficulty values are between 0.9 and 1.0 (14 items), 𝐻𝐻(𝑋𝑋𝑖𝑖) values are between 0.12 and 0.47. approximately the same results were obtained for the tests 2, 3 and 4. as we can see in case of 𝐻𝐻(𝑋𝑋𝑖𝑖)’s large values close to 1 irt b parameter gets large values. analysis of the experiments of a new approach for test quality evaluation 38 fig. 1. 𝐻𝐻(𝑋𝑋𝑖𝑖), ctt difficulty parameters p and irt b parameters of test1. h(xi) irt b difficulty p -5 -4 -3 -2 -1 0 1 2 3 a11a21b19 a3 a48 b6 b9 a50 a4 b12a14a13a47b24a10 a8 a26a24b21a40a25b11b14a46b16b28 m. haroutunian, v. avetisyan 39 to analyze the dependency of 𝐻𝐻(𝑋𝑋𝑖𝑖) values on the number of examinee sample we draw 𝐻𝐻(𝑋𝑋𝑖𝑖) graphics of each test based on the results of five experiments. the graphics are shown in figure 2. fig. 2. 𝐻𝐻(𝑋𝑋𝑖𝑖) graphics for five experiments of test1. the maximum differences of 𝐻𝐻(𝑋𝑋𝑖𝑖) values are presented in table1. table 1. maximum difference of 𝐻𝐻(𝑋𝑋𝑖𝑖) values 500 300 200 100 50 500 0.089 0.07 0.135 0.2 300 0.089 0.13 0.15 0.19 200 0.07 0.13 0.16 100 0.135 0.15 0.16 0.3 50 0.2 0.19 0.23 0.3 while decreasing the examinee sample size until 100, it is obvious that the differences of 𝐻𝐻(𝑋𝑋𝑖𝑖) values are small and the maximum difference is 0.15. but when examinee sample size is decreased more than 100, the difference is close to 0.3, and in case of values equal to 50 the difference is close to 0.3. with the same principle for each test the mutual information 𝐼𝐼�𝑋𝑋𝑖𝑖 ∧ 𝑋𝑋𝑗𝑗� was calculated and the dependency of 𝐼𝐼�𝑋𝑋𝑖𝑖 ∧ 𝑋𝑋𝑗𝑗� values on the number of examinee sample was observed. the graphics are shown in figure 3. analysis of the experiments of a new approach for test quality evaluation 40 fig. 3. 𝐼𝐼�𝑋𝑋𝑖𝑖 ∧ 𝑋𝑋𝑗𝑗� for five experiments of test1 a1 item. the average mutual information and correlation between test items also have been analyzed. the graphics based on some items’ data are presented in figure 4 and figure 5. fig. 4. correlation �𝑅𝑅�𝑋𝑋𝑖𝑖 , 𝑋𝑋𝑗𝑗�� and average mutual information �𝐼𝐼�𝑋𝑋𝑖𝑖 ∧ 𝑋𝑋𝑗𝑗�� between a1 item and other 80 items. a1 (500) a1 (300 a1 (200) a1 (100) a1 (50) 0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 a27b15a12a31 b8 b21a33b25a32 b1 b23a10a16a46 b4 a17a24b13a47b29a14b17 b9 b12 r(x,y) i(x^y)x10 -0.1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 a4 a7 a1 0 a1 3 a1 6 a1 9 a2 2 a2 5 a2 8 a3 1 a3 4 a3 7 a4 0 a4 3 a4 6 a4 9 b2 b5 b8 b1 1 b1 4 b1 7 b2 0 b2 3 b2 6 b2 9 m. haroutunian, v. avetisyan 41 fig. 5. correlation �𝑅𝑅�𝑋𝑋𝑖𝑖 , 𝑋𝑋𝑗𝑗�� and average mutual information �𝐼𝐼�𝑋𝑋𝑖𝑖 ∧ 𝑋𝑋𝑗𝑗�� between a11 item and other 80 items. table 2. a11 a5 a8 a15 a26 a31 b18 b19 b20 b23 r(x,y) -0.0083 -0.0186 -0.0581 -0.0195 -0.0385 -0.0005 -0.0151 0.0219 -0.0177 i(x∧y) 0.0011 0.0013 0.0049 0.0001 0.00001 0.0001 0.000004 0.0004 0.00006 for item a11 the negative correlation with other items and average mutual information values are presented in table 2. when we compare items’ correlations and average mutual information graphics, it is easy to see that the results are comparable. for example, from the correlation matrix and graphics shown in figure 5 we can see that a11 test item has negative correlation with other test items, for these items the values of mutual information are presented in table2. if correlation values are negative, average mutual information values are small enough, but from test we should remove those items, so the smallest permissible limit value of average mutual information should be 0.005. 4. conclusion in this research while analyzing the data, the following has been determined. 1. the methods suggested by us are correctly defining the quality of test items and the results are comparable with ctt and irt estimation methods. 2. simpler mathematical analysis is needed compared to irt. 3. 𝐼𝐼�𝑋𝑋𝑖𝑖 ∧ 𝑋𝑋𝑗𝑗� describes the dependence of test items which does not have an equivalent in irt. 4. for test good items 𝐻𝐻(𝑋𝑋𝑖𝑖) values should be between 0.8 and 1.0, for fairly good items (easy) values are between 0.45 and 0.8, and for bad test items 𝐻𝐻(𝑋𝑋𝑖𝑖) values are between 0 and 0.45. r(x,y) i(x^y)x10 -0.1 -0.05 0 0.05 0.1 0.15 0.2 0.25 a1 a4 a7 a1 0 a1 3 a1 6 a1 9 a2 2 a2 5 a2 8 a3 1 a3 4 a3 7 a4 0 a4 3 a4 6 a4 9 b2 b5 b8 b1 1 b1 4 b1 7 b2 0 b2 3 b2 6 b2 9 analysis of the experiments of a new approach for test quality evaluation 42 5. for 𝐼𝐼�𝑋𝑋𝑖𝑖 ∧ 𝑋𝑋𝑗𝑗 � preferable are the values smaller than 0.05 and greater than 0.005 0.005≤ 𝐼𝐼�𝑋𝑋𝑖𝑖 ∧ 𝑋𝑋𝑗𝑗 � ≤ 0.05 6. smaller sample sizes are required in comparison with ctt and irt. the sample size should be more than 100. in ctt the sample size is between 200 and 500, and in irt it depends on the irt model, but samples over 500 are needed. references [1] m. haroutunian and v. avetisyan, “new approach for test quality evaluation based on shannon information measures”, transactions of ipia of nas ra, mathematical problems of computer science, vol. 44, pp. 7-21, 2015. [2] m. b. chelishkova, theory and practice of pedagogical tests constructing, moscow: logos, 2002. [3] c. demars, item response theory. oxford university press; 1 edition, 2010. [4] k. hambleton and w. jones, “comparison of classical test theory and item response theory and their applications to test development”, educational measurement: issues and practice, vol. 12, no. 3, pp. 38-47, 1993. [5] m. haroutunian and v. avetisyan, “development of the test quality evaluation system”, proceedings of the international conference on computer science and information technologies (csit 2015), yerevan, armenia, september 28-october 2, pp. 372--375, 2015. submitted 10.10.2015, accepted 20.01.2016 թեստի որակի գնահատման նոր մոտեցման փորձարկումների վերլուծություն մ․ հարությունյան,վ․ ավետիսյան ամփոփում նախորդ հոդվածում [1] հեղինակների կողմից առաջարկվել է թեստերի որակի գնահատման նոր մոդել՝ հիմնված շենոնի էնտրոպիայի և միջին փոխադարձ ինֆորմացիայի վրա։ այս մեծությունների սահմանային արժեքները և թեստավորման մասնակիցների բավարար քանակը որոշելու համար կատարվել են փորձարկումներ։ հոդվածում ներկայացված է այդ փորձարկումների վերլուծությունը, որից հետևում է, որ հաշվարկները ավելի պարզ են irt-ի համեմատությամբ, թեստավորման արդյունքների վերլուծության համար պահանջվում է մասնակիցների ավելի քիչ քանակ, քան` ctt-ում և irt-ում։ m. haroutunian, v. avetisyan 43 анализ экспериментов нового подхода для оценки качества теста м. арутюнян, в. аветисян аннотация в предыдущей статье [1] авторами была предложена новая модель оценки качества теста на основе энтропии шэннона и средней взаимной информации. для того, чтобы установить практические пределы этих величин и необходимое количество экзаменуемых, были проведены эксперименты. в данной статье представлен анализ этих экспериментов, из которого следует, что расчеты более просты по сравнению с irt, для анализа результатов тестирований требуется меньшее количество экзаменуемых, чем в стт и irt. analysis of experiments of a new approach for test quality evaluation mariam e. haroutunian, varazdat k. avetisyan 2. description of experiments mathematical problems of computer science 53, 7–13, 2020. udc 510.6 polynomial bounded proof complexities for some classes of dnf-tautologies garik v. petrosyan yerevan state university e-mail: garik.petrosyan.1@gmail.com abstract in this paper, we present the results on frege proof complexities of some dnftautologies. at first we introduce the notion of complete dnfs and prove that complete dnfs are tautologies, we also show that if the proof complexities for the set of complete dnfs are polynomially bounded, then the set of dnf-tautologies d, for which the number of non-negated variables in every conjunct is o(log(d)), also has polynomially bounded proof complexities. later we show that the set of all balanced dnf-tautologies has polynomial proof complexities. keywords: frege systems, proof complexity, dnf, complete dnf, balanced formulas. 1. introduction one of the most fundamental problems of the proof complexity theory is to find an efficient proof system for classical propositional calculus. there is a widespread understanding that polynomial-time computability is the correct mathematical model of feasible computation. according to the opinion, a truly ”effective” system should have a polynomial-size p(n) proof for every tautology of size n. in [1], cook and reckhow named such a system a super system. they showed that np = conp iff there exists a super system. it is well known that many systems are not super. this question about the frege system, the most natural calculi for propositional logic, is still open. in many papers, some specific sets of tautologies are introduced, and it is shown that the question about polynomially bounded sizes for frege-proofs of all tautologies is reduced to an analogous question for a set of specific tautologies. in particular, lutz strasburger introduced in [2] the notion of balanced formulas and showed that if there are polynomially bounded frege proofs for the set of balanced tautologies, then the frege systems are super. an analogous result for some other class of tautologies is proved in [3]. one of the well-known classes of tautologies is the class of tautologies, given in disjunctive normal form (dnf-tautologies), and it is an open question if the frege-proof complexities for the set of dnf-tautologies have polynomial upper bounds. the frege-proof complexities of some dnf-tautology classes are investigated in this paper. at first the notion of complete 7 8 polynomial bounded proof complexities for some classes of dnf-tautologies dnf is introduced, and it is proved that if the proof complexities for the set of complete dnfs are polynomially bounded, then the set of dnf-tautologies d, for which the number of non-negated variables in every conjunct is o(log(d)), also has polynomially bounded proof complexities. then it is proved that the proof complexities of the set of balanced dnf-tautologies has polynomially bounded proof complexities as well. 2. main notions and notations here we give basic definitions, which are necessary to give main results. definition 1: a frege system f uses a denumerable set of propositional variables, a finite complete set of propositional connectives; f has a finite set of inference rules defined by a figure of the form a1a2...an b (the rules of inference with zero hypotheses are axiom schemes); f must be sound and complete, i.e., for each rule of inference a1a2...an b every truth-value assignment, satisfying a1a2...an, also satisfies b, and f must prove every tautology. the particular choice of a language for the presented propositional formulas is immaterial in this consideration. however, because of some technical reasons, we assume that the language contains the propositional variables pi (i ≥ 1) or pij (i ≥ 1; j ≥ 1) logical connectives ¬,∧,∨,⊃ and parentheses (, ). note that some parentheses and ∧ can be omitted in generally accepted cases. note that our convention for serial disjunction a1∨a2∨...∨an (conjunction a1 ∧a2 ∧ ...∧an) associated from left to right. by |ϕ| we denote the size of the formula ϕ defined as the number of all entries of logical signs in it. it is obvious that the full size of the formula, which is understood to be the number of all symbols, is bounded by some linear function in |ϕ|. in the theory of proof complexity, the four main characteristics of the proof are: tcomplexity (length), defined as the number of proof steps, l-complexity (size), defined as the sum of sizes for all formulas in the proof (size), s-complexity (space), informally defined as the maximum of minimal sum of sizes for formulas on blackboard needed to verify all steps in the proof (formal definitions are, for example, in [2]) and w-complexity (width), defined as the maximum of sizes of the proof formulas. definition 2: let φ be a proof system and ϕ be a tautology. we denote by tφϕ (l φ ϕ, s φ ϕ, w φ ϕ) the minimal possible value of t-complexity (l-complexity, s-complexity, w-complexity) for all -proofs of tautology ϕ. by analogy, we can define the mentioned proof complexity characteristics for the proof of any formula a from premises γ and denote them respectively by t φ γ`a (l φ γ`a, s φ γ`a, w φ γ`a). let m be some set of tautologies. definition 3: we call the φ-proofs of tautologies from the set m t-polynomially (lpolynomially, s-polynomially, w-polynomially) bounded if there is a polynomial p() such that tφϕ ≤ p(|ϕ|) (lφϕ ≤ p(|ϕ|) ,sφϕ ≤ p(|ϕ|) ,wφϕ ≤ p(|ϕ|)) for all tautologies ϕ from m. note that if φ-proofs of tautologies from the set m are l-polynomially bounded they are also t-polynomially, s-polynomially, w-polynomially bounded. following the usual terminology, we call the variables and negated variables literals for classical logic. the conjunct k can be represented simply as a set of literals (no conjunct contains a variable and its negation simultaneously). in [4], the notion of balanced formulas is introduced in the following way. g. petrosyan 9 definition 4: a propositional formula is called balanced if every variable has only two occurrences in it, one positive and one with negative. in [4], it is shown that the problem on l-polynomially bounded sizes of proofs for all tautologies is reduced to the problem on l-polynomially bounded sizes of proofs for all balanced tautologies. 3. main results in this part, frege-proof complexities for some classes of dnf-tautologies are investigated. a. here the notion of complete dnf-tautologies is introduced, and it is proved that if the set of complete dnf-tautologies has l-polynomially therefore also t-polynomially, spolynomially, w-polynomially bounded proofs, then the set of dnf-tautologies d, where the number of non-negated variable in each conjunct is o(log(|d|)), also has l-polynomially therefore also t-polynomially, s-polynomially, w-polynomially bounded proofs. let all variables of a dnf n1 ∨n2 ∨ ...∨nn be negated variables. conjunct k is called representative for d if k contains at least one variable (without negation) from each ni (1 ≤ i ≤ n), and every variable of k is from d. definition 5: dnf d1 = c1 ∨ c2 ∨ ... ∨ cm is called a completion of dnf d2 = n1 ∨ n2 ∨ ...∨nn iff for every representative k of d2 there is a ni (1 ≤ i ≤ n), which is a subset of k, and the expression d = (n1 ∨n2 ∨ ...∨nn)∨(c1 ∨c2 ∨ ...∨cm) is called a complete dnf. theorem 1: complete dnfs are tautologies. proof. let’s assume the opposite: there is a complete dnf d = (n1∨n2∨...∨nn)∨(c1∨ c2∨...∨cm) such that it is not a tautology. if d = 0 in any collection, then n1∨n2∨...∨nn should also be 0 in that collection. n1 ∨n2 ∨ ...∨nn = 0, only if each conjunct is equal to 0, therefore, we have that in each conjunct ni (1 ≤ i ≤ n) there is a literal equal to 0. if we consider the conjunct p constructed by the conjunction of the variables of these literals, as we have a complete dnf, there is a cj (1 ≤ j ≤ m) such that cj is a subset of p , hence cj = 1, but we have assumed that d = 0, which is a contradiction. from this proof it is easy to see that all dnf-tautologies, the conjuncts of which do not contain a variable and a negated variable simultaneously, are complete dnfs. to evaluate the proof complexities of dnf-tautologies by reducing the proof to the proof of complete dnftautologies, we must use some transformations of formulas, therefore we give the following auxiliary statements, which are used to perform those transformations. lemma 1: for all formulas a,b and c, the set of the following formulas 1. a∨b ⊃ c ≡ (a ⊃ c) ∧ (b ⊃ c) 2. a ⊃ a∨b 3. a ⊃ (b ∨c) ≡ (a ⊃ b) ∨ (a ⊃ c) 4. b ⊃ (a ⊃ a∧b) 5. (a ⊃ b) ⊃ ((a∨c) ⊃ (b ∨c) has l-polynomially bounded proofs. 10 polynomial bounded proof complexities for some classes of dnf-tautologies proof. the proof is obvious. most dnf-tautologies , the proof complexities of which are being investigated, have small conjuncts sizes compered to their size. using complete dnfs, we can construct polynomial proofs for such dnf-tautologies. the following theorem gives such a construction. theorem 2: if the set of all complete dnfs has l-polynomially bounded proofs then, the set of dnf-tautologies d, where the number of non-negated variables in each conjunct is o(log(|d|)), also has l-polynomially bounded proofs. proof. let’s consider d dnf-tautology, where the number of non-negated variables in each conjunct is o(log(|d|)). for each conjunct, we separate the sub-conjunct of variables with positive entrance and the set of all such conjuncts and its subsets we denote by p . since the number of non-negated variables in each conjunct is o(log(|d|)), there is such a polynomial p() function that |p| ≤ p(|d|). if dnf is a tautology, it should have at least one conjunct, where all the variables are negated, otherwise it does not cover the 0 point we denote the disjunction of all such conjuncts by n. if d is a tautology, then there is a completion of n such that all conjuncts are from p . if such a completion did not exist, we would take a conjunct constructed by taking one variable from each conjunct of n, and this conjunct would not be covered by p , therefore if we set the values of these variables 1 and the values of all other variables 1, the value of d will be 0. let’s denote that completion by c. n ∨ c is a completion dnf; to prove d, we need to prove n ∨c and n ∨c ⊃ d, the first part follows from our condition. let’s prove the second part n ⊃ d. from lemma 1.1 we get two tautologies to prove n ⊃ d and c ⊃ d. from lemma 1.2 we get the polynomial proof of n ⊃ d. now let’s prove c ⊃ d. suppose c = c1 ∨ c2 ∨ ... ∨ cm, where ci(1 ≤ i ≤ m) is a conjunct. using lemma 1.1, we can convert c ⊃ d into (c1 ⊃ d) ∧ (c2 ⊃ d) ∧ ...∧ (cm ⊃ d). as ci (1 ≤ i ≤ m) is a conjunct, we can prove each one alone and later join them with ∧. note that the number of such ci conjuncts is less than p , therefore it has a polynomial upper bound. using lemma 1.4 and 5, we can reduce the proof of each (ci ⊃ d) (1 ≤ i ≤ m) to a new dnf, which also satisfies the condition that the number of non-negated variables in each conjunct is o(log(|d|)). we can use the same technique to prove these new tautologies and note that their p sets are subsets of our initial p set, therefore we will use only the first p . if we continue the proof in this way, we will have several tautologies, the number of which is polynomial from |d|, and each reduction is performed using polynomial steps and polynomial formulas, therefore the proof is l-polynomially bounded. corollary 3: if the set of complete dnfs has l-polynomially bounded proofs, than the set of dnf-tautologies d, where the number of negated variables in each conjunct is o(log(|d|)), also has l-polynomially bounded proofs. proof. the proof can be obtained from the proof of theorem 2 with slight changes. b. here, the proof complexities of some subset of balanced dnf-tautologies are investigated. definition 6: a dnf-tautology is correct if dnf, obtained from it by removing any conjunct, is no longer a tautology. lemma 2: the number of conjuncts in a balanced correct dnf-tautology with n variables is n+1. g. petrosyan 11 proof. we prove the lemma by induction on number n of variables in a balanced dnftautology d. if n = 1, we have d = ¬p∨p. suppose the statement is valid for a balanced dnf-tautology, which has ≤ n variables. if the number of variables is n + 1, then the correctly balanced dnf should have at least one conjunct with at least two literals pα1i1 p α2 i2 . after assigning α1 to the variable pi1 everywhere in the given dnf, both the number of variables and the number of conjuncts decrease by one, hence the number of conjuncts in the primary dnf should be n + 2. corollary 4: every balanced correct dnf-tautology has at least one conjunct, consisting of one literal. theorem 5: all balanced correct dnf-tautologies have l-polynomially bounded proofs. proof. let us have a balanced correct dnf-tautology d = d1 ∨d2 ∨ ...∨dn+1, which depends on the variables p1,p2, ...,pn. we take ¬d and prove the a contradiction. ¬d = n1 ∧n2 ∧ ...∧nn+1, where ni = ¬di (1 ≤ i ≤ n + 1) and ni = pα1i1 ∨p α2 i2 ∨ ...∨pαrir , where αi ∈ {0, 1} (1 ≤ i ≤ n + 1). based on ni, we construct the formula ei by adding instead of every variable pj from p1,p2, ...,pn which has no occurrence in ni, the formula p1 ∧¬p1 on the j-th place with a disjunction. it is obvious that ni = ei, and this equivalence can be derived with polynomially bounded characteristics of proof complexities. by this notation we have that formula ¬d is equivalent to formula d′ = e1 ∧e2...∧en+1. now we introduce new propositional variables pij (1 ≤ i ≤ n + 1; 1 ≤ j ≤ n), where pij is true if the variable pj occurs in ni and is false for the opposite case, and construct on the base of ei new disjunctions d′i by replacing both the primary literals and the formulas p1 ∧¬p1 with the corresponding variables pij. now we consider the well-known formulas of pigeon hole principle phpn = ∧ni=0 ∨ n−1 k=0 pik ⊃∨ n−1 k=0 ∨0≤i 𝑖𝑖, can compute its share for the output wire 𝑤𝑤. 𝑠𝑠𝑤𝑤𝑖𝑖 = (𝑠𝑠𝑢𝑢𝑖𝑖 ∧ 𝑠𝑠𝑣𝑣𝑖𝑖) ⊕ (⊕𝑖𝑖<𝑗𝑗 ��𝑠𝑠𝑢𝑢𝑖𝑖 ∧ 𝑠𝑠𝑣𝑣𝑗𝑗� ⊕ �𝑠𝑠𝑢𝑢𝑗𝑗 ∧ 𝑠𝑠𝑣𝑣𝑖𝑖��. given the methods of share based evaluation of both type gates, each party computes the circuits’ output value shares. the computation of the full value of an output wire can be done after each participant sends the result of its computations to others. note, that computation of an 𝑋𝑋𝑋𝑋𝑋𝑋 gate share values is free in terms of network communication and almost free, in terms of computation (𝑛𝑛 𝑋𝑋𝑋𝑋𝑋𝑋 operation). however, the computation of 𝐴𝐴𝐴𝐴𝐴𝐴 gates takes � 𝑛𝑛 2� ot invocations. 2.3 optimizations white-box oblivious transfer oblivious transfer is an essential cryptographic primitive heavily used in secure computations. it was introduced by rabin in [13] as a protocol where the sender sends a message to the receiver with 1 2 probability and does not reveal if the receiver got the message or not. a modified version of this protocol was introduced later by even et al. in [14], currently known as the basic 1-out-of2 ot protocol. this protocol assumes that the receiver has a selection bit 𝑠𝑠𝑠𝑠{0,1} and the sender has two bits 𝑚𝑚0, 𝑚𝑚1𝑠𝑠{0,1} . after protocol execution the receiver gets 𝑚𝑚𝑠𝑠 and nothing about 𝑚𝑚1−𝑠𝑠 and the sender does not reveal 𝑠𝑠. unfortunately this protocol depends on public-key operations, which require exponentiation operations which are pretty expensive, considering the huge amount of ot operations required for secure computations (in yao’s protocol ots are used for all input bits of one of the participants, in gmw ots are used for all 𝐴𝐴𝐴𝐴𝐴𝐴 gates). in [11] a new approach to ot was introduced using white-box cryptography techniques instead of public-key operations, allowing to reduce cost of an ot in several orders of magnitude, in case of many invocations, as reported. wbot extension 62 secure multiparty computations for collaboration between competing service providers another optimization technique for reducing the ot invocation count is ot extension introduced by beaver in [17] and later enhanced in [16]. we have constructed similar optimization for white-box ot, allowing to reduce the required ot invocation count to a predetermined fixed number. the details of the extension can be found in [8]. 2.4 gmw protocol extension here we introduce an extended version of the gmw protocol, that enables involvement of so called passive parties that don’t participate in the computation process, while having input and expecting output. suppose 𝑛𝑛 + 𝑚𝑚 parties wish to compute a common function based on private inputs, only 𝑚𝑚 of which are passive. in this scenario we suggest the active (participating in computation) parties to behave as they do in the original protocol and share their inputs among 𝑛𝑛 active parties with the method described in section 2.2. each passive participant also generates 𝑛𝑛 shares for each of its input, but doesn’t keep a share for himself and distributes all shares among the active parties. the latter compute the function based on the secret shares as in the original protocol and distribute output shares among all parties. the security requirement for this protocol are also different – here we require at least one non-corrupted active party. 3. platform description the platform processes a file containing a program described in an imperative language for to be computed by the participants. beside the function description the file contains specification on the intended inputs and expected outputs. the program defines computations in a manner they would be carried out by a virtual trusted party possessing all input parameters. our platform consist of three main modules – a compiler, and two modules responsible for two-party and multiparty secure computations respectively. below we briefly describe the main modules. compiler we implemented a compiler generating an equivalent boolean circuit on basis { 𝐴𝐴𝐴𝐴𝐴𝐴, 𝑋𝑋𝑋𝑋𝑋𝑋, 1 } implementing the described function. the compiler generates an initial boolean circuit and passes it through various stages of optimizations trying to minimize the number of gates in generated circuit. another major goal of the compiler is the minimization of 𝐴𝐴𝐴𝐴𝐴𝐴 gates and circuit depth. for this purpose we use low depth circuit constructions developed mainly for vlsi applications. to deal with large circuits efficiently, the compiler generates a file containing the usage count for each gate. when a gate is processed, by a participant, the initial usage count is read from this file, and each time the output of the gate is accessed, the associated counter is decremented. data associated with the gate is removed from memory once the counter hits zero. in this way we minimize the number of gates simultaneously kept in memory during evaluation of the circuit. two-party module although it is possible to perform secure computations with two participants using gmw protocol, in our platform we have a specialized module for this task. for this purpose we have implemented yao’s garbled circuits protocol [12]. the module works on the output of the compiler module. detailed description can be found in [9]. d. danoyan 63 multiparty module the multiparty module is intended for secure computations with more than 2 participants. the module implements the goldreich-micalli-widgerson protocol[18] with several enhancements described in [15] and in the previous section. it also operates on a boolean circuit outputted by the compiler module. 4. applications here we will describe the process of combining multiple delivery services into a unified platform that involves several members. in fact, the application described is suitable for using in different contexts like combining any delivery or transportation services where the members are service providers, who do not want to disclose their current locations or the locations they are available to cover within the fixed time to their competitors, but eager to cooperate with them to have their share in unified ordering system, thus increasing their order counts and service efficiency. concerning the motivation of client to use the unified system, let’s compare the actions needed for getting the fastest service. in case of having an access to the unified application, the client just has to give the application her location and confirm the order. all the computation and decision processes are completed without the clients’ involvement. in absence of such a system one should contact several service providers (possibly with different interfaces), give them its location, compare the offers of different providers, find the best of them and finally put an order. in the latter case the client also has to trust the information it got from service providers. suppose the service providers are taxi service companies with one or more cabs and the client has no priorities for choosing particular service other than fast pick-up. taxi services do not want to make their locations visible to rival companies to avoid them getting advantage by better positioning of their cabs (for example, this can be done by a company with significantly more cabs). all cab locations are also hidden from the client, because a competitor can possibly act as a client to find out the others’ cab locations and get advantage. having the application scenario described we show several methods as candidates for the secure computation itself. this methods are basically computing the minimum value of distances between a client as one point, and provider instances as candidates for the second point. different distance measurement algorithms are presented below. the main purpose of this application is to find the nearest item in the unified database of locations to a submitted location. with the computation securing method already appointed, we still need to have accurate location detecting and network connection hardware for the service providers and individual cabs. in this work we consider the mentioned hardware implemented in a black-box manner – we do not consider their technical and efficiency details. we also assume that the computing parties have identical maps as well and their locations follow common coordinate system, to avoid misinterpretation of function arguments. considering the distance measurement we have several methods as a candidate. euclid distance the most general version of the distance measurement function is computation of the euclid distance between the customer and all the provider instances (e.g. cabs). with the coordinates given in two dimensional format, the customer’s location denoted as (𝑥𝑥𝑐𝑐, 𝑦𝑦𝑐𝑐) and for 𝑖𝑖-th provider instance (𝑥𝑥𝑖𝑖, 𝑦𝑦𝑖𝑖) considering m provider instances, the following function should be computed to determine the “winning” bid: min i